Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths

Reuben Tate1, Jai Moondra2, Bryan Gard3, Greg Mohler3, and Swati Gupta4

1CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87544, USA
2Georgia Institute of Technology, Atlanta, GA 30332, USA
3Georgia Tech Research Institute, Atlanta, GA 30332, USA
4Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA 02142, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi et al. (2014) to allow for arbitrary separable initial states with corresponding mixers such that the starting state is the most excited state of the mixing Hamiltonian. We demonstrate this version of QAOA, which we call $QAOA-warmest$, by simulating Max-Cut on weighted graphs. We initialize the starting state as a $warm-start$ using $2$ and $3$-dimensional approximations obtained using randomized projections of solutions to Max-Cut's semi-definite program, and define a warm-start dependent $custom mixer$. We show that these warm-starts initialize the QAOA circuit with constant-factor approximations of $0.658$ for $2$-dimensional and $0.585$ for $3$-dimensional warm-starts for graphs with non-negative edge weights, improving upon previously known trivial (i.e., $0.5$ for standard initialization) worst-case bounds at $p=0$. These factors in fact lower bound the approximation achieved for Max-Cut at higher circuit depths, since we also show that QAOA-warmest with any separable initial state converges to Max-Cut under the adiabatic limit as $p\rightarrow \infty$. However, the choice of warm-starts significantly impacts the rate of convergence to Max-Cut, and we show empirically that our warm-starts achieve a faster convergence compared to existing approaches. Additionally, our numerical simulations show higher quality cuts compared to standard QAOA, the classical Goemans-Williamson algorithm, and a warm-started QAOA without custom mixers for an instance library of $1148$ graphs (upto $11$ nodes) and depth $p=8$. We further show that QAOA-warmest outperforms the standard QAOA of Farhi et al. in experiments on current IBM-Q and Quantinuum hardware.

Quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical technique for combinatorial optimization that promises to be more powerful than any classical optimizer. In this work, we exemplify its potential on a fundamental combinatorial optimization problem, known as Max-Cut, where the best possible classical algorithm is that by Goemans and Williamson (GW). We achieve this by introducing classically obtained warm-starts to the QAOA, with modified mixing operators, and show computationally that this outperforms GW. We modify the quantum algorithm appropriately to maintain the connection to quantum adiabatic computing; we discuss theory and provide numerical and experimental evidence showing the promise of our approach.

► BibTeX data

► References

[1] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[2] Aram W. Harrow and Ashley Montanaro. ``Quantum computational supremacy''. Nature 549, 203–209 (2017).

[3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014).

[4] Iain Dunning, Swati Gupta, and John Silberholz. ``What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO''. INFORMS Journal on Computing 30 (2018).

[5] Michel X Goemans and David P Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming''. Journal of the ACM (JACM) 42, 1115–1145 (1995).

[6] Samuel Burer and Renato DC Monteiro. ``A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization''. Mathematical Programming 95, 329–357 (2003).

[7] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, et al. ``Qiskit: An open-source framework for quantum computing'' (2019).

[8] Madelyn Cain, Edward Farhi, Sam Gutmann, Daniel Ranard, and Eugene Tang. ``The QAOA gets stuck starting from a good classical string'' (2022).

[9] Daniel J. Egger, Jakub Mareček, and Stefan Woerner. ``Warm-starting quantum optimization''. Quantum 5, 479 (2021).

[10] Stefan H Sack, Raimel A Medina, Richard Kueng, and Maksym Serbyn. ``Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement''. Physical Review A 107, 062404 (2023).

[11] Stefan H Sack and Maksym Serbyn. ``Quantum annealing initialization of the quantum approximate optimization algorithm''. quantum 5, 491 (2021).

[12] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. ``Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices''. Physical Review X 10, 021067 (2020).

[13] Ruslan Shaydulin, Phillip C Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S Humble. ``Parameter transfer for quantum approximate optimization of weighted maxcut''. ACM Transactions on Quantum Computing 4, 1–15 (2023).

[14] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. ``Transferability of optimal QAOA parameters between random graphs''. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 171–180. IEEE (2021).

[15] Johannes Weidenfeller, Lucia C Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J Egger. ``Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware''. Quantum 6, 870 (2022).

[16] Phillip C Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S Humble. ``Scaling quantum approximate optimization on near-term hardware''. Scientific Reports 12, 12388 (2022).

[17] Gian Giacomo Guerreschi and Anne Y Matsuura. ``QAOA for max-cut requires hundreds of qubits for quantum speed-up''. Scientific reports 9, 1–7 (2019).

[18] Charles Moussa, Henri Calandra, and Vedran Dunjko. ``To quantum or not to quantum: towards algorithm selection in near-term quantum optimization''. Quantum Science and Technology 5, 044009 (2020).

[19] Colin Campbell and Edward Dahl. ``QAOA of the highest order''. In 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C). Pages 141–146. IEEE (2022).

[20] Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C Lotshaw, Travis S Humble, and George Siopsis. ``Impact of graph structures for QAOA on maxcut''. Quantum Information Processing 20, 1–21 (2021).

[21] Gopal Chandra Santra, Fred Jendrzejewski, Philipp Hauke, and Daniel J Egger. ``Squeezing and quantum approximate optimization'' (2022).

[22] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro. ``Classical symmetries and the quantum approximate optimization algorithm''. Quantum Information Processing 20, 1–28 (2021).

[23] Jonathan Wurtz and Peter Love. ``Maxcut quantum approximate optimization algorithm performance guarantees for p> 1''. Physical Review A 103, 042612 (2021).

[24] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``Quantum algorithms for fixed qubit architectures'' (2017).

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. ``Obstacles to variational quantum optimization from symmetry protection''. Physical Review Letters 125, 260505 (2020).

[26] Edward Farhi, David Gamarnik, and Sam Gutmann. ``The quantum approximate optimization algorithm needs to see the whole graph: A typical case'' (2020).

[27] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. ``Hybrid quantum-classical algorithms for approximate graph coloring''. Quantum 6, 678 (2022).

[28] Matthew B Hastings. ``Classical and quantum bounded depth approximation algorithms'' (2019).

[29] Kunal Marwaha. ``Local classical max-cut algorithm outperforms $ p= 2$ QAOA on high-girth regular graphs''. Quantum 5, 437 (2021).

[30] Boaz Barak and Kunal Marwaha. ``Classical algorithms and quantum limitations for maximum cut on high-girth graphs'' (2021).

[31] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta. ``Bridging classical and quantum with SDP initialized warm-starts for QAOA''. ACM Transactions on Quantum Computing (2022).

[32] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. ``From the quantum approximate optimization algorithm to a quantum alternating operator ansatz''. Algorithms 12 (2019).

[33] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. ``$xy$ mixers: Analytical and numerical results for the quantum alternating operator ansatz''. Phys. Rev. A 101, 012320 (2020).

[34] Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou. ``Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer''. Phys. Rev. Research 4, 033029 (2022).

[35] Andreas Bärtschi and Stephan Eidenbenz. ``Grover mixers for QAOA: Shifting complexity from mixer design to state preparation''. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). Pages 72–82. IEEE (2020).

[36] Zhang Jiang, Eleanor G Rieffel, and Zhihui Wang. ``Near-optimal quantum circuit for grover's unstructured search using a transverse field''. Physical Review A 95, 062317 (2017).

[37] Lov K Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. Pages 212–219. (1996).

[38] Yin Zhang, Samuel Burer, and Renato D. C. Monteiro. ``Rank-2 relaxation heuristics for max-cut and other binary quadratic programs''. SIAM Journal on Optimization 12, 503––521 (2001).

[39] Song Mei, Theodor Misiakiewicz, Andrea Montanari, and Roberto Imbuzeiro Oliveira. ``Solving sdps for synchronization and maxcut problems via the grothendieck inequality''. In Conference on learning theory. Pages 1476–1515. PMLR (2017).

[40] Ojas Parekh and Kevin Thompson. ``An optimal product-state approximation for 2-local quantum hamiltonians with positive terms'' (2022). arXiv:2206.08342.

[41] Reuben Tate and Swati Gupta. ``Ci-qube''. GitHub repository (2021). url: https:/​/​github.com/​swati1729/​CI-QuBe.

[42] Howard Karloff. ``How good is the Goemans–Williamson MAX-CUT algorithm?''. SIAM Journal on Computing 29, 336–350 (1999).

[43] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332–336 (2021).

[44] Sergey Bravyi, Sarah Sheldon, Abhinav Kandala, David C. Mckay, and Jay M. Gambetta. ``Mitigating measurement errors in multiqubit experiments''. Phys. Rev. A 103, 042605 (2021).

[45] George S. Barron and Christopher J. Wood. ``Measurement error mitigation for variational quantum algorithms'' (2020).

[46] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. ``TensorFlow: Large-scale machine learning on heterogeneous systems'' (2015).

[47] Diederik P. Kingma and Jimmy Ba. ``Adam: A method for stochastic optimization'' (2014).

[48] Roger Fletcher. ``Practical methods of optimization (2nd edition)''. John Wiley and Sons. New York, NY, USA (1987).

[49] M.J.D. Powell. ``A direct search optimization method that models the objective and constraint functions by linear interpolation''. Advances in Optimization and Numerical Analysis 275, 51–67 (1994).

[50] Alan J. Laub. ``Matrix analysis for scientists and engineers''. Volume 91. Siam. (2005).

[51] Georg Frobenius. ``Ueber matrizen aus nicht negativen elementen''. Sitzungsberichte der Königlich Preussischen Akademie der WissenschaftenPages 456–477 (1912).

[52] A. Kaveh and H. Rahami. ``A unified method for eigendecomposition of graph products''. Communications in Numerical Methods in Engineering with Biomedical Applications 21, 377–388 (2005).

[53] Simon Špacapan. ``Connectivity of cartesian products of graphs''. Applied Mathematics Letters 21, 682–685 (2008).

[54] Jacek Gondzio and Andreas Grothey. ``Solving nonlinear financial planning problems with 109 decision variables on massively parallel architectures''. WIT Transactions on Modelling and Simulation 43 (2006).

[55] Fan RK Chung. ``Spectral graph theory''. Volume 92. American Mathematical Soc. (1997).

[56] M. A. Nielsen and I. L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press, New York. (2011).

[57] Vincent R. Pascuzzi, Andre He, Christian W. Bauer, Wibe A. de Jong, and Benjamin Nachman. ``Computationally efficient zero-noise extrapolation for quantum-gate-error mitigation''. Physical Review A 105, 042406 (2022).

[58] Ewout Van Den Berg, Zlatko K Minev, Abhinav Kandala, and Kristan Temme. ``Probabilistic error cancellation with sparse pauli–lindblad models on noisy quantum processors''. Nature PhysicsPages 1–6 (2023).

[59] Nathan Krislock, Jérôme Malick, and Frédéric Roupin. ``BiqCrunch: A semidefinite branch-and-bound method for solving binary quadratic problems''. ACM Transactions on Mathematical Software 43 (2017).

[60] Andries E. Brouwer, Sebastian M. Cioabă, Ferdinand Ihringer, and Matt McGinnis. ``The smallest eigenvalues of hamming graphs, johnson graphs and other distance-regular graphs with classical parameters''. Journal of Combinatorial Theory, Series B 133, 88–121 (2018).

[61] Donald Knuth. ``Combinatorial matrices''. Selected Papers on Discrete Mathematics (2000).

Cited by

[1] V Vijendran, Aritra Das, Dax Enshan Koh, Syed M Assad, and Ping Koy Lam, "An expressive ansatz for low-depth quantum approximate optimisation", Quantum Science and Technology 9 2, 025010 (2024).

[2] Runsheng Zhao, Tao Cheng, Rui Wang, Xingkui Fan, and Hongyang Ma, "Artificial intelligence warm-start approach: optimizing the generalization capability of QAOA in complex energy landscapes", New Journal of Physics 26 5, 053016 (2024).

[3] Peter Gleißner, Georg Kruse, and Andreas Roßkopf, "Restricted global optimization for QAOA", APL Quantum 1 2, 026106 (2024).

[4] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun, and Marco Pistoia, "Alignment between initial state and mixer improves QAOA performance for constrained optimization", npj Quantum Information 9 1, 121 (2023).

[5] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J. Egger, "Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware", Quantum 6, 870 (2022).

[6] Phillip C. Lotshaw, Kevin D. Battles, Bryan Gard, Gilles Buchs, Travis S. Humble, and Creston D. Herold, "Modeling noise in global Mølmer-Sørensen interactions applied to quantum approximate optimization", Physical Review A 107 6, 062406 (2023).

[7] Vanessa Dehn and Thomas Wellens, "A hybrid quantum-classical approach to warm-starting optimization", arXiv:2309.13961, (2023).

[8] Andrew Vlasic, Salvatore Certo, and Anh Pham, "Complement Grover's Search Algorithm: An Amplitude Suppression Implementation", arXiv:2209.10484, (2022).

[9] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele, and Procolo Lucignano, "Convergence of digitized-counterdiabatic QAOA: circuit depth versus free parameters", New Journal of Physics 26 1, 013002 (2024).

[10] Vishvesha K. Sridhar, Yanzhu Chen, Bryan Gard, Edwin Barnes, and Sophia E. Economou, "ADAPT-QAOA with a classically inspired initial state", arXiv:2310.09694, (2023).

[11] Guoming Wang, "Classically-Boosted Quantum Optimization Algorithm", arXiv:2203.13936, (2022).

[12] Matteo Vandelli, Alessandra Lignarolo, Carlo Cavazzoni, and Daniele Dragoni, "Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications", arXiv:2311.11621, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-26 07:51:59) and SAO/NASA ADS (last updated successfully 2024-05-26 07:52:00). The list may be incomplete as not all publishers provide suitable and complete citation data.