Warm-Started QAOA With Custom Mixers Provably Converges And Computationally Beats Goemans-Williamson’s Max-Cut At Low Circuit Depths

Republished By Plato

Followers: 0

Reuben Tate¹, Jai Moondra², Bryan Gard³, Greg Mohler³, and Swati Gupta⁴

¹CCS-3 Information Sciences, Los Alamos National Laboratory, Los Alamos, NM 87544, USA
²Georgia Institute of Technology, Atlanta, GA 30332, USA
³Georgia Tech Research Institute, Atlanta, GA 30332, USA
⁴Sloan 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.

Abstract

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 $prightarrow 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.

Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson’s Max-Cut at Low Circuit Depths PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: Performance of QAOA-warmest (with warm-starts) and standard QAOA as a function of QAOA depth for an ideal (dashed) and noisy simulation (dotted). For the chosen 20-node graph, GW achieves an approximation ratio of 0.912, while in the ideal case, QAOA-warmest outperforms GW for $p geq 2$ while standard QAOA requires $p > 4$. The noise simulation is based on calibration data from IBM-Q’s Guadalupe device.

Popular summary

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

@article{Tate2023warmstartedqaoa, doi = {10.22331/q-2023-09-26-1121}, url = {https://doi.org/10.22331/q-2023-09-26-1121}, title = {Warm-{S}tarted {QAOA} with {C}ustom {M}ixers {P}rovably {C}onverges and {C}omputationally {B}eats {G}oemans-{W}illiamson’s {M}ax-{C}ut at {L}ow {C}ircuit {D}epths}, author = {Tate, Reuben and Moondra, Jai and Gard, Bryan and Mohler, Greg and Gupta, Swati}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1121}, month = sep, year = {2023}<br /> }

► References

[1] John Preskill. “Quantum computing in the NISQ era and beyond”. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[2] Aram W. Harrow and Ashley Montanaro. “Quantum computational supremacy”. Nature 549, 203–209 (2017).
https://doi.org/10.1038/nature23458

[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).
https://doi.org/10.1287/ijoc.2017.0798

[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).
https://doi.org/10.1145/227683.227684

[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).
https://doi.org/10.1007/s10107-002-0352-8

[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).
https://doi.org/10.22331/q-2021-06-17-479

[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).
https://doi.org/10.1103/PhysRevA.107.062404

[11] Stefan H Sack and Maksym Serbyn. “Quantum annealing initialization of the quantum approximate optimization algorithm”. quantum 5, 491 (2021).
https://doi.org/10.22331/q-2021-07-01-491

[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).
https://doi.org/10.1103/PhysRevX.10.021067

[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).
https://doi.org/10.1145/3584706

[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).
https://doi.org/10.1109/QCE52317.2021.00034

[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).
https://doi.org/10.22331/q-2022-12-07-870

[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).
https://doi.org/10.1038/s41598-022-14767-w

[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).
https://doi.org/10.1038/s41598-019-43176-9

[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).
https://doi.org/10.1088/2058-9565/abb8e5

[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).
https://doi.org/10.1109/ICSA-C54293.2022.00035

[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).
https://doi.org/10.1007/s11128-021-03232-8

[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).
https://doi.org/10.1007/s11128-021-03298-4

[23] Jonathan Wurtz and Peter Love. “Maxcut quantum approximate optimization algorithm performance guarantees for p> 1”. Physical Review A 103, 042612 (2021).
https://doi.org/10.1103/PhysRevA.103.042612

[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).
https://doi.org/10.1103/PhysRevLett.125.260505

[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).
https://doi.org/10.22331/q-2022-03-30-678

[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).
https://doi.org/10.22331/q-2021-04-20-437

[30] Boaz Barak and Kunal Marwaha. “Classical algorithms and quantum limitations for maximum cut on high-girth graphs” (2021).
https://doi.org/10.4230/LIPIcs.ITCS.2022.14

[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).
https://doi.org/10.1145/3549554

[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).
https://doi.org/10.3390/a12020034

[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).
https://doi.org/10.1103/PhysRevA.101.012320

[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).
https://doi.org/10.1103/PhysRevResearch.4.033029

[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).
https://doi.org/10.1109/QCE49297.2020.00020

[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).
https://doi.org/10.1103/PhysRevA.95.062317

[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).
https://doi.org/10.1145/237814.237866

[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).
https://doi.org/10.1137/S1052623400382467

[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).
https://doi.org/10.48550/arXiv.1703.08729

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

[41] Reuben Tate and Swati Gupta. “Ci-qube”. GitHub repository (2021). url: https://github.com/swati1729/CI-QuBe.
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).
https://doi.org/10.1137/S0097539797321481

[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).
https://doi.org/10.1038/s41567-020-01105-y

[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).
https://doi.org/10.1103/PhysRevA.103.042605

[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).
https://doi.org/10.1002/9781118723203

[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).
https://doi.org/10.1007/978-94-015-8330-5_4

[50] Alan J. Laub. “Matrix analysis for scientists and engineers”. Volume 91. Siam. (2005).
https://doi.org/10.1137/1.9780898717907

[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).
https://doi.org/10.1002/cnm.753

[53] Simon Špacapan. “Connectivity of cartesian products of graphs”. Applied Mathematics Letters 21, 682–685 (2008).
https://doi.org/10.1016/j.aml.2007.06.010

[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).
https://doi.org/10.2495/CF060101

[55] Fan RK Chung. “Spectral graph theory”. Volume 92. American Mathematical Soc. (1997).
https://doi.org/10.1090/cbms/092

[56] M. A. Nielsen and I. L. Chuang. “Quantum computation and quantum information: 10th anniversary edition”. Cambridge University Press, New York. (2011).
https://doi.org/10.1017/CBO9780511976667

[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).
https://doi.org/10.1103/PhysRevA.105.042406

[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).
https://doi.org/10.1038/s41567-023-02042-2

[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).
https://doi.org/10.1145/3005345

[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).
https://doi.org/10.1016/j.jctb.2018.04.005

[61] Donald Knuth. “Combinatorial matrices”. Selected Papers on Discrete Mathematics (2000).
https://doi.org/10.1016/S0898-1221(04)90150-2

Cited by

[1] 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).

[2] 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 Portfolio Optimization”, arXiv:2305.03857, (2023).

[3] V. Vijendran, Aritra Das, Dax Enshan Koh, Syed M. Assad, and Ping Koy Lam, “An Expressive Ansatz for Low-Depth Quantum Optimisation”, arXiv:2302.04479, (2023).

[4] Andrew Vlasic, Salvatore Certo, and Anh Pham, “Complement Grover’s Search Algorithm: An Amplitude Suppression Implementation”, arXiv:2209.10484, (2022).

[5] Mara Vizzuso, Gianluca Passarelli, Giovanni Cantele, and Procolo Lucignano, “Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters”, arXiv:2307.14079, (2023).

[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] Guoming Wang, “Classically-Boosted Quantum Optimization Algorithm”, arXiv:2203.13936, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2023-09-27 01:31:19). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-09-27 01:31:17).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2023-09-26-1121/

Time Stamp: September 26, 2023

Time Stamp: May 22, 2023

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

Republished By Plato

Abstract

Popular summary

► BibTeX data

► References

Cited by

More from Quantum Journal

Correlations in typicality and an affirmative solution to the exact catalytic entropy conjecture

Driven-dissipative topological phases in parametric resonator arrays

Semi-device-dependent blind quantum tomography

Transitions in Entanglement Complexity in Random Circuits

Classical shadows based on locally-entangled measurements

Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth

Mitiq: A software package for error mitigation on noisy quantum computers

The minimal communication cost for simulating entangled qubits

Entanglement Trajectory and its Boundary

Bell-type inequalities for systems of relativistic vector bosons

A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit

About Us

Vertical Search & Ai

Platform

Stay Connected

Account