CoChat
Sign Up
PreprintCited by 61Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsQuantum many-body systems

Bridging Classical and Quantum with SDP initialized warm-starts for QAOA

Open access
Tate, Reuben, Farhadi, Majid, Herold, Creston, Mohler, Greg, Gupta, Swati·2020·arXiv
DOI 10.48550/arxiv.2010.14021arXiv 2010.14021
Open this paper in CoChat — free account

Abstract

We study the Quantum Approximate Optimization Algorithm (QAOA) in the context of the Max-Cut problem. Near-term (noisy) quantum devices are only able to (accurately) execute QAOA at low circuit depths while QAOA requires a relatively high circuit-depth in order to "see" the whole graph. We introduce a classical pre-processing step that initializes QAOA with a biased superposition of all possible cuts in the graph, referred to as a warm-start. In particular, our initialization informs QAOA by a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA, called QAOA-Warm, is able to outperform standard QAOA on lower circuit depths with less training time (in the optimization stage for QAOA's variational parameters). We provide experimental evidence as well as theoretical intuition on performance of the proposed framework.

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2010.14021

Cites

Statistics

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.

A few free checks a day · papers already verified open instantly · results are public

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?

  • Preconditioning of quantum algorithms for VQAs is provided by warm-starting with classical solvers for relaxed CO problems.

    “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 [137]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 38

  1. [1]E. Farhi, D. Gamarnik, and S. Gutmann, The quantum approximate optimization algorithm needs to see the whole graph: A typical case, arXiv preprint arXiv:2004.09002 (2020). · arXiv
  2. [3]E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 (2014). · arXiv
  3. [4]S. Khot, On the power of unique 2-prover 1-round games, in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (2002) pp. 767-775.
  4. [5]E. Mossel, R. O'Donnell, and K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) (IEEE, 2005) pp. 21-30.
  5. [6]S. Khot, G. Kindler, E. Mossel, and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM Journal on Computing 37 , 319 (2007).
  6. [7]M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM) 42 , 1115 (1995).
  7. [8]L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson, Gadgets, approximation, and linear programming, SIAM Journal on Computing 29 , 2074 (2000).
  8. [9]J. H˚ astad, Some optimal inapproximability results, Journal of the ACM (JACM) 48 , 798 (2001).
  9. [10]M. Charikar and A. Wirth, Maximizing quadratic programs: extending grothendieck's inequality, in 45th Annual IEEE Symposium on Foundations of Computer Science (2004) pp. 54-60.
  10. [11]D. Bertsimas, A. King, and R. Mazumder, Best subset selection via a modern optimization lens, The Annals of Statistics 44 , 813 (2016).
  11. [12]T. Marcucci and R. Tedrake, Warm start of mixed-integer programs for model predictive control of hybrid systems, IEEE Transactions on Automatic Control 10.1109/TAC.2020.3007688 (2020). · DOI
  12. [13]T. Ralphs and M. G¨ uzelsoy, Duality and warm starting in integer programming, in Proceedings of 2006 NSF Design, Service, and Manufacturing Grantees and Research Conference (2006).
  13. [16]G. B. Mbeng, R. Fazio, and G. E. Santoro, Quantum annealing: a journey through digitalization, control, and hybrid quantum variational schemes, arXiv preprint arXiv:1906.08948 (2019). · arXiv
  14. [17]L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices, arXiv preprint arXiv:1812.01041 (2018). · arXiv
  15. [18]L. Zhu, H. L. Tang, G. S. Barron, F. Calderon-Vargas, N. J. Mayhall, E. Barnes, and S. E. Economou, An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer, arXiv preprint arXiv:2005.10258 [quant-ph] (2020). · arXiv
  16. [19]S. H. Sack and M. Serbyn, Quantum annealing initialization of the quantum approximate optimization algorithm, arXiv preprint arXiv:2101.05742 [quant-ph] (2021). · arXiv
  17. [20]A. B¨ artschi and S. Eidenbenz, Grover mixers for QAOA: Shifting complexity from mixer design to state preparation, arXiv preprint arXiv:2006.00354 (2020). · arXiv
  18. [21]V. Akshay, H. Philathong, M. E. Morales, and J. D. Biamonte, Reachability deficits in quantum approximate optimization, arXiv preprint arXiv:1906.11259v2 (2019). · arXiv
  19. [22]D. J. Egger, J. Marecek, and S. Woerner, Warm-starting quantum optimization, arXiv preprint arXiv:2009.10095 (2020). · arXiv
  20. [23]I. Dunning, S. Gupta, and J. Silberholz, What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO, INFORMS Journal on Computing 30 , 608 (2018).
  21. [24]D. Kingma and J. L. Ba, Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980 (2017). · arXiv
  22. [27]R. Fletcher, Practical Methods of Optimization (2nd edition) (John Wiley and Sons, New York, NY, USA, 1987).
  23. [28]W. Lavrijsen, A. Tudor, J. M¨ uller, C. Iancu, and W. de Jong, Classical optimizers for noisy intermediate-scale quantum devices, arXiv preprint arXiv:2004.030043 (2021).
  24. [30]F. G. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances, arXiv preprint arXiv:1812.04170 (2018). · arXiv
  25. [32]S. Poljak and F. Rendl, Nonpolyhedral relaxations of graph-bisection problems, SIAM Journal on Optimization 5 , 467(1995).
  26. [36]N. Boumal, V. Voroninski, and A. S. Bandeira, The non-convex burer-monteiro approach works on smooth semidefinite programs, arXiv preprint arXiv:1606.04970 (2018). · arXiv
  27. [38]S. Burer, R. D. C. Monteiro, and Y. Zhang, Rank-2 relaxation heuristics for Max-Cut and other binary quadratic programs, SIAM Journal on Optimization 12 , 503 (2001).
  28. [39]S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira, Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality, arXiv preprint arXiv:1703.08729 (2017). · arXiv
  29. [41]Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum approximate optimization algorithm for MaxCut: A fermionic view, Physical Review A 97 , 022304 (2018).
  30. [42]S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to state preparation and variational optimization from symmetry protection, arXiv preprint arXiv:1910.08980 (2019). · arXiv
  31. [43]R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations (Springer US, Boston, MA, 1972) pp. 85-103.
  32. [44]F. Glover, G. Kochenberger, and Y. Du, Quantum bridge analytics I: A tutorial on formulating and using QUBO models, arXiv preprint arxiv:1811.11538 (2019). · arXiv
  33. [45]B. Lodewijks, Mapping NP-hard and NP-complete optimization problems to quadratic unconstrained binary optimization problems, arXiv preprint arxiv:1911.08043 (2020). · arXiv
  34. [47]W. Feller, An Introduction to Probability Theory and Its Applications , 3rd ed., Vol. 2 (Wiley, Hoboken, New Jersey, 1971).
  35. [49]R. Lyons and Y. Peres, Probability on trees and networks , Vol. 42 (Cambridge University Press, 2017).
  36. [50]W. Karush, Minima of functions of several variables with inequalities as side conditions , Master's thesis, University of Chicago (1939).
  37. [51]H. W. Kuhn and A. W. Tucker, Nonlinear programming, in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability (University of California Press, Berkeley, Calif., 1951) pp. 481-492.
  38. [52]Y. T. Lee and S. Padmanabhan, An ˜ O ( m/ϵ 3 . 5)-cost algorithm for semidefinite programs with diagonal constraints, arXiv preprint arXiv:1903.01859 (2019). · arXiv

Cited by

Sorted by citations

Authors
Tate, R., Farhadi, M., Herold, C., Mohler, G., & Gupta, S.
Affiliations
  • Georgia Institute of Technology (US)
  • Georgia Tech Research Institute (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
4
Issue
2
Pages
1-39
ISSN
2643-6809 (ISSN-L)
DOI
10.48550/arxiv.2010.14021
arXiv
2010.14021
OpenAlex
W3097920226
Cited by
61
References
0
Citations by year
2026: 6 · 2025: 18 · 2024: 15 · 2023: 12 · 2022: 5 · 2021: 5
FWCI
4.12
Type
journal article
Language
en
Open access
Licence
Locations
  • ACM Transactions on Quantum Computing (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Defense Advanced Research Projects Agency (HR001120C0046)
  • Advanced Research Projects Agency
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 › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum approximate optimization algorithm, max-cut problem, warm-start initialization, semidefinite relaxation, low-depth quantum circuits, noisy quantum devices, combinatorial optimization

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