EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4371. Solving Combinatorial Optimization Problems with Quantum Annealers
Invited abstract in session MB-42: Decomposition methods for Quantum Optimization, stream Quantum Computing Optimization.
Monday, 10:30-12:00Room: 98 (building: 306)
Authors (first author is the speaker)
| 1. | Janez Povh
|
| Rudolfovo |
Abstract
In this talk, we present a comprehensive analysis of solving two famous NP-hard problems: the Max-Cut and the Stable Set Problem. While the former is equivalent to Quadratic Unconstrained Binary Optimization (QUBO) problem, the latter needs to be reframed as a QUBO problem. We solve both using exact solvers like GUROBI or BiqBin, and approximately by quantum annealing solvers such as the D-Wave quantum processing unit and D-Wave hybrid solver.
In cases where the capabilities of quantum annealing solvers are exceeded, we introduce for the Stable Set Problem a specialized decomposition technique, which effectively breaks down the input graph into smaller graphs, rendering them more manageable for quantum annealers.
Finally, we conduct a thorough assessment of both quantum solvers alongside a classical simulated annealing solver. Our extensive numerical evaluation on various families of benchmark graphs demonstrates that the simulated annealing approach remains highly competitive. This competitiveness is primarily attributed to its simplicity and computational efficiency compared to quantum solvers.
Keywords
- Algorithms
- Combinatorial Optimization
Status: accepted
Back to the list of papers