Quantum annealing initialization of the quantum approximate optimization algorithm

Stefan H. Sack and Maksym Serbyn

IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria

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


The quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm due to its modest circuit depth and promising benchmarks. However, an external parameter optimization required in QAOA could become a performance bottleneck. This motivates studies of the optimization landscape and search for heuristic ways of parameter initialization. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs, demonstrating that random initialization of the QAOA is prone to converging to local minima with sub-optimal performance. We introduce the initialization of QAOA parameters based on the Trotterized quantum annealing (TQA) protocol, parameterized by the Trotter time step. We find that the TQA initialization allows to circumvent the issue of false minima for a broad range of time steps, yielding the same performance as the best result out of an exponentially scaling number of random initializations. Moreover, we demonstrate that the optimal value of the time step coincides with the point of proliferation of Trotter errors in quantum annealing. Our results suggest practical ways of initializing QAOA protocols on near-term quantum devices and reveals new connections between QAOA and quantum annealing.

The Quantum Approximate Optimization Algorithm (QAOA) is among the most promising near-term algorithms due to its modest hardware requirements and promising benchmarks. In this algorithm, a quantum computer is used to implement a variational ansatz, which is optimized in a feedback loop with a classical computer to find an approximate solution for a discrete classical optimization problem. The optimization landscape is however characterized by an exponentially scaling number of local optima, which could lead to a potential performance bottleneck. To address this issue we propose a novel, efficient initialization technique of the QAOA based on Trotterized Quantum Annealing. Our initialization achieves, within a single optimization run, a performance comparable to the best out of an exponentially scaling number of random initializations. Our results open the door for more time-efficient practical implementations of the QAOA on NISQ devices and inspire future research that could lead to a better understanding of the inner workings of the QAOA.

► BibTeX data

► References

[1] F. Arute et al., Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor, arXiv e-prints , arXiv:2004.04197 (2020a), arXiv:2004.04197 [quant-ph].

[2] F. Arute et al., Hartree-Fock on a superconducting qubit quantum computer, Science 369, 1084 (2020b), arXiv:2004.04174 [quant-ph].

[3] F. Arute et al., Observation of separated dynamics of charge and spin in the Fermi-Hubbard model, arXiv e-prints , arXiv:2010.07965 (2020c), arXiv:2010.07965 [quant-ph].

[4] K. Wright et al., Benchmarking an 11-qubit quantum computer, Nature Communications 10, 5464 (2019), arXiv:1903.08181 [quant-ph].

[5] J. Preskill, Quantum Computing in the NISQ era and beyond, arXiv e-prints , arXiv:1801.00862 (2018), arXiv:1801.00862 [quant-ph].

[6] E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv e-prints , arXiv:1411.4028 (2014), arXiv:1411.4028 [quant-ph].

[7] 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, Phys. Rev. X 10, 021067 (2020).

[8] G. E. Crooks, Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem, arXiv e-prints , arXiv:1811.08419 (2018), arXiv:1811.08419 [quant-ph].

[9] M. Willsch, D. Willsch, F. Jin, H. De Raedt, and K. Michielsen, Benchmarking the quantum approximate optimization algorithm, Quantum Information Processing 19, 197 (2020), arXiv:1907.02359 [quant-ph].

[10] S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to State Preparation and Variational Optimization from Symmetry Protection, arXiv e-prints , arXiv:1910.08980 (2019), arXiv:1910.08980 [quant-ph].

[11] G. G. Guerreschi and A. Y. Matsuura, QAOA for Max-Cut requires hundreds of qubits for quantum speed-up, Scientific Reports 9, 6903 (2019).

[12] R. Shaydulin, I. Safro, and J. Larson, Multistart methods for quantum approximate optimization, in 2019 IEEE High Performance Extreme Computing Conference (HPEC) (2019) pp. 1–8.

[13] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications 9, 4812 (2018), arXiv:1803.11173 [quant-ph].

[14] Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, Connecting ansatz expressibility to gradient magnitudes and barren plateaus, arXiv e-prints , arXiv:2101.02138 (2021), arXiv:2101.02138 [quant-ph].

[15] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nature Communications 12, 1791 (2021), arXiv:2001.00550 [quant-ph].

[16] F. G. S. L. 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 e-prints , arXiv:1812.04170 (2018), arXiv:1812.04170 [quant-ph].

[17] D. J. Egger, J. Marecek, and S. Woerner, Warm-starting quantum optimization, arXiv e-prints , arXiv:2009.10095 (2020), arXiv:2009.10095 [quant-ph].

[18] M. Alam, A. Ash-Saki, and S. Ghosh, Accelerating Quantum Approximate Optimization Algorithm using Machine Learning, arXiv e-prints , arXiv:2002.01089 (2020), arXiv:2002.01089 [cs.ET].

[19] S. Khairy, R. Shaydulin, L. Cincio, Y. Alexeev, and P. Balaprakash, Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems, arXiv e-prints , arXiv:1911.11071 (2019), arXiv:1911.11071 [cs.LG].

[20] T. Albash and D. A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018).

[21] D. Liang, L. Li, and S. Leichenauer, Investigating quantum approximate optimization algorithms under bang-bang protocols, Phys. Rev. Research 2, 033402 (2020).

[22] M. Heyl, P. Hauke, and P. Zoller, Quantum localization bounds Trotter errors in digital quantum simulation, Science Advances 5, 10.1126/​sciadv.aau8342 (2019).

[23] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115 (1995).

[24] J. Wurtz and P. J. Love, Bounds on MAXCUT QAOA performance for $p>1$, arXiv e-prints , arXiv:2010.11209 (2020), arXiv:2010.11209 [quant-ph].

[25] C. G. BROYDEN, The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations, IMA Journal of Applied Mathematics 6, 76 (1970).

[26] R. Fletcher, A new approach to variable metric algorithms, The Computer Journal 13, 317 (1970).

[27] D. Goldfarb, A family of variable-metric methods derived by variational means, Mathematics of Computation 24, 23 (1970).

[28] D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Mathematics of Computation 24, 647 (1970).

[29] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors, SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python, Nature Methods 17, 261 (2020).

[30] M. Rosenblatt, Remarks on some nonparametric estimates of a density function, Ann. Math. Statist. 27, 832 (1956).

[31] E. Parzen, On estimation of a probability density function and mode, Ann. Math. Statist. 33, 1065 (1962).

[32] T. Kadowaki and H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E 58, 5355 (1998).

[33] J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aeppli, Quantum Annealing of a Disordered Magnet, Science 284, 779 (1999).

[34] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem, Science 292, 472 (2001), arXiv:quant-ph/​0104129 [quant-ph].

[35] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum Computation by Adiabatic Evolution, arXiv e-prints , quant-ph/​0001106 (2000), arXiv:quant-ph/​0001106 [quant-ph].

[36] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation, SIAM Review 50, 755 (2008).

[37] A. Smith, M. S. Kim, F. Pollmann, and J. Knolle, Simulating quantum many-body dynamics on a current digital quantum computer, npj Quantum Information 5, 106 (2019), arXiv:1906.06343 [quant-ph].

[38] U. Schollwöck, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326, 96 (2011), arXiv:1008.3477 [cond-mat.str-el].

[39] G. Carleo and M. Troyer, Solving the quantum many-body problem with artificial neural networks, Science 355, 602 (2017), arXiv:1606.02318 [cond-mat.dis-nn].

[40] M. Medvidovic and G. Carleo, Classical variational simulation of the Quantum Approximate Optimization Algorithm, arXiv e-prints , arXiv:2009.01760 (2020), arXiv:2009.01760 [quant-ph].

[41] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner, The power of quantum neural networks, arXiv e-prints , arXiv:2011.00027 (2020), arXiv:2011.00027 [quant-ph].

[42] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, Shortcuts to adiabaticity: Concepts, methods, and applications, Rev. Mod. Phys. 91, 045001 (2019).

[43] D. Sels and A. Polkovnikov, Minimizing irreversible losses in quantum systems by local counterdiabatic driving, Proceedings of the National Academy of Sciences 114, E3909 (2017).

[44] P. W. Claeys, M. Pandey, D. Sels, and A. Polkovnikov, Floquet-engineering counterdiabatic protocols in quantum many-body systems, Phys. Rev. Lett. 123, 090602 (2019).

[45] Z.-C. Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon, Optimizing variational quantum algorithms using Pontryagin's minimum principle, Phys. Rev. X 7, 021027 (2017).

[46] S. H. Sack, Trotterized quantum annealing initialization of the QAOA, https:/​/​github.com/​shsack/​TQA-init.-for-QAOA (2021).

[47] A. Hagberg, P. Swart, and D. S Chult, Exploring network structure, dynamics, and function using NetworkX, Tech. Rep. (Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008).

[48] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Efficient Quantum Algorithms for Simulating Sparse Hamiltonians, Communications in Mathematical Physics 270, 359 (2007), arXiv:quant-ph/​0508139 [quant-ph].

Cited by

[1] Ioannis Kolotouros and Petros Wallden, "Evolving objective function for improved variational quantum optimization", Physical Review Research 4 2, 023225 (2022).

[2] Antonio A. Mele, Glen B. Mbeng, Giuseppe E. Santoro, Mario Collura, and Pietro Torta, "Avoiding barren plateaus via transferability of smooth solutions in a Hamiltonian variational ansatz", Physical Review A 106 6, L060401 (2022).

[3] Vrinda Mehta, Fengping Jin, Hans De Raedt, and Kristel Michielsen, "Quantum annealing with trigger Hamiltonians: Application to 2-satisfiability and nonstoquastic problems", Physical Review A 104 3, 032421 (2021).

[4] Qing Xie, Kazuhiro Seki, and Seiji Yunoki, "Variational counterdiabatic driving of the Hubbard model for ground-state preparation", Physical Review B 106 15, 155153 (2022).

[5] Jonathan Wurtz and Peter J. Love, "Counterdiabaticity and the quantum approximate optimization algorithm", Quantum 6, 635 (2022).

[6] 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 4 2, 1 (2023).

[7] Alicia B. Magann, Kenneth M. Rudinger, Matthew D. Grace, and Mohan Sarovar, "Lyapunov-control-inspired strategies for quantum combinatorial optimization", Physical Review A 106 6, 062414 (2022).

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

[9] Zheng-Hang Sun, Yong-Yi Wang, Jian Cui, and Heng Fan, "Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry", New Journal of Physics 25 1, 013015 (2023).

[10] Xinwei Lee, Yoshiyuki Saito, Dongsheng Cai, and Nobuyoshi Asai, 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) 10 (2021) ISBN:978-1-6654-1691-7.

[11] Stefan H. Sack, Raimel A. Medina, Alexios A. Michailidis, Richard Kueng, and Maksym Serbyn, "Avoiding Barren Plateaus Using Classical Shadows", PRX Quantum 3 2, 020365 (2022).

[12] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", Quantum 6, 861 (2022).

[13] James Sud, Jeffrey Marshall, Zhihui Wang, Eleanor Rieffel, and Filip A. Wudarski, "Dual-map framework for noise characterization of quantum computers", Physical Review A 106 1, 012606 (2022).

[14] Massimiliano Incudini, Fabio Tarocco, Riccardo Mengoni, Alessandra Di Pierro, and Antonio Mandarino, "Computing graph edit distance on quantum devices", Quantum Machine Intelligence 4 2, 24 (2022).

[15] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[16] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, "Parameter concentrations in quantum approximate optimization", Physical Review A 104 1, L010401 (2021).

[17] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta, "Bridging Classical and Quantum with SDP initialized warm-starts for QAOA", arXiv:2010.14021, (2020).

[18] Stefan H. Sack, Raimel A. Medina, Richard Kueng, and Maksym Serbyn, "Transition states and greedy exploration of the QAOA optimization landscape", arXiv:2209.01159, (2022).

[19] Noah L. Wach, Manuel S. Rudolph, Fred Jendrzejewski, and Sebastian Schmitt, "Data re-uploading with a single qudit", arXiv:2302.13932, (2023).

[20] Dennis Willsch, Madita Willsch, Fengping Jin, Kristel Michielsen, and Hans De Raedt, "GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm", Computer Physics Communications 278, 108411 (2022).

[21] Xinwei Lee, Ningyi Xie, Yoshiyuki Saito, Dongsheng Cai, and Nobuyoshi Asai, "A Depth-Progressive Initialization Strategy for Quantum Approximate Optimization Algorithm", arXiv:2209.11348, (2022).

[22] Ohad Amosy, Tamuz Danzig, Ely Porat, Gal Chechik, and Adi Makmal, "Iterative-Free Quantum Approximate Optimization Algorithm Using Neural Networks", arXiv:2208.09888, (2022).

[23] Elijah Pelofske, Georg Hahn, and Hristo Djidjev, "Initial state encoding via reverse quantum annealing and h-gain features", arXiv:2303.13748, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-04-14 08:30:37) and SAO/NASA ADS (last updated successfully 2023-06-05 13:32:42). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-06-05 13:32:39: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2021-07-01-491.