EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2432. Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic run-time analysis
Invited abstract in session TA-42: Quantum Computing for Continuous Optimization, stream Quantum Computing Optimization.
Tuesday, 8:30-10:00Room: 98 (building: 306)
Authors (first author is the speaker)
| 1. | Fabian Henze
|
| Institute for Theoretical Physics, University Cologne | |
| 2. | Viet Tran
|
| Institute for Integrated Circuits, Johannes Kepler University | |
| 3. | Birte Ostermann
|
| TU Braunschweig | |
| 4. | Richard Kueng
|
| JKU Linz | |
| 5. | Timo de Wolff
|
| TU Braunschweig | |
| 6. | David Gross
|
| University of Cologne |
Abstract
In principle, quantum computers can solve semi-definite programs using resources that scale extremely well in the matrix dimension, though very unfavorably in the precision. In 2019, Brandao, Franca, and Kueng proposed to use quantum SDP solvers in order to speed up the Goeman-Williams-type relaxations of combinatorial optimization problems. One motivation for their ansatz was that the final rounding step that maps SDP solutions to binary variables should be comparatively insensitive to limits in the precision. They did indeed succeed to identify an algorithm that achieves an asymptotic quadratic speedup over state-of-the-art classical methods. Here, we present an analysis of the non-asymptotic resource requirements of this ansatz.
The work consists of two parts. First, we optimize the original algorithm with a view on performance for finite problem instances. In particular, we formulate a version with adaptive step-sizes, an improved detection criterion for infeasible instances, and a more efficient rounding procedure. In a second step, we benchmark both the classical and the quantum version of the algorithm against synthetic and real-world data. Unfortunately, we find that even the optimized quantum algorithm will not beat more standard classical approaches for input sizes that can be realistically solved at all.
Keywords
- Programming, Semidefinite
- Complexity and Approximation
- Convex Optimization
Status: accepted
Back to the list of papers