Many optimization problems in binary decision variables are hard to solve. In this work, we demonstrate how to leverage decades of research in classical optimization algorithms to warm-start quantum optimization algorithms. This allows the quantum algorithm to inherit the performance guarantees from the classical algorithm used in the warm-start.

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time.

In recent work with colleagues at IBM Research, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

Image credit: Egger, Marecek, Woerner. The figure shows a quantum circuit of warm-start QAOA.

Cite as

@article{Egger2021warmstartingquantum,
 doi = {10.22331/q-2021-06-17-479},
 url = {https://doi.org/10.22331/q-2021-06-17-479},
 title = {Warm-starting quantum optimization},
 author = {Egger, Daniel J. and Mare{\v{c}}ek, Jakub and Woerner, Stefan},
 journal = {{Quantum}},
 issn = {2521-327X},
 publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
 volume = {5},
 pages = {479},
 month = jun,
 year = {2021}
}