The DOI matches its Crossref record; 122 of the 122 references it cites were found in a registry or an index.
Warm-starting quantum optimization
Open accessAbstract
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. Here, 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Concerning the former, a preconditioning of the quantum algorithm for VQAs is provided by warm-starting with classical solvers for relaxed CO problems [42], e.g., an SDP solver [137].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [42]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
Markowitz, H. M. (1952) · The Journal of Finance · doi:10.2307/2975974 · Cited by 4,606
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
A second course in stochastic processes
Karlin, S., & Taylor, H. E. (1981) · Cited by 2,770
Supervised learning with quantum-enhanced feature spaces
Havlíček, V., Córcoles, A. D., Temme, K., Harrow, A. W., Kandala, A., Chow, J. M., & Gambetta, J. M. (2019) · Nature · doi:10.1038/s41586-019-0980-2 · Cited by 2,572
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Global Optimization with Polynomials and the Problem of Moments
Lasserre, J. B. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623400366802 · Cited by 2,412
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,374
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Research works printed but not linked: 4
- Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014a. URL https://arxiv.org/abs/1411.4028. · arXiv
- Michael Juenger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi, and Tobias Stollenwerk. Performance of a quantum annealer for Ising ground state computations on chimera graphs, 2019. URL https://arxiv.org/abs/1904.11965. · arXiv
- Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Hybrid quantum-classical algorithms for approximate graph coloring, 2020b. URL https://arxiv.org/abs/2011.13420. · arXiv
- Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 563
Quantum Computing for High-Energy Physics: State of the Art and Challenges
Meglio, A. D., Jansen, K., Tavernelli, I., Alexandrou, C., Arunachalam, S., Bauer, C., Borras, K., Carrazza, S., Crippa, A., Croft, V. A., et al. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.037001 · Cited by 359
Self-citationChallenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
Self-citationNoisy intermediate-scale quantum (NISQ) algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2021) · arXiv · doi:10.48550/arxiv.2101.08448 · Cited by 166
Metadata
- Authors
- Egger, D. J., Mareček, J., & Woerner, S.
- Affiliations
- IBM Research - Zurich (CH)
- Czech Technical University in Prague (CZ)
- Venue
- Quantum
- Published
- 2021-06-17
- Volume
- 5
- Pages
- 479
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W3088409280
- Cited by
- 269
- References
- 122
- Citations by year
- 2026: 44 · 2025: 61 · 2024: 57 · 2023: 56 · 2022: 34 · 2021: 16
- FWCI
- 14.35
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- arXiv (Cornell University) (cc-by)
- Bulletin of the American Physical Society
- Funders
- OP RDE project Research Center for Informatic (CZ.02.1.01/0.0/0.0/16_019/0000765)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- warm start, quantum optimization, quantum approximate optimization algorithm, MaxCut, portfolio optimization, semidefinite relaxation, Unique Games Conjecture, randomized rounding, integer programming, combinatorial optimization, performance guarantees
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
