IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
Featured image: The figure schematically displays the quantum circuit that implements the QAOA ansatz (left), the variational parameters before and after optimization (middle) and a cartoon of the optimization landscape (right).
Popular summary
► 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].
https://doi.org/10.1038/s41567-020-01105-y
arXiv:2004.04197
[2] F. Arute et al., Hartree-Fock on a superconducting qubit quantum computer, Science 369, 1084 (2020b), arXiv:2004.04174 [quant-ph].
https://doi.org/10.1126/science.abb9811
arXiv:2004.04174
[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].
arXiv:2010.07965
[4] K. Wright et al., Benchmarking an 11-qubit quantum computer, Nature Communications 10, 5464 (2019), arXiv:1903.08181 [quant-ph].
https://doi.org/10.1038/s41467-019-13534-2
arXiv:1903.08181
[5] J. Preskill, Quantum Computing in the NISQ era and beyond, arXiv e-prints , arXiv:1801.00862 (2018), arXiv:1801.00862 [quant-ph].
https://doi.org/10.22331/q-2018-08-06-79
arXiv:1801.00862
[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].
arXiv:1411.4028
[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).
https://doi.org/10.1103/PhysRevX.10.021067
[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].
arXiv:1811.08419
[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].
https://doi.org/10.1007/s11128-020-02692-8
arXiv:1907.02359
[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].
https://doi.org/10.1103/PhysRevLett.125.260505
arXiv:1910.08980
[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).
https://doi.org/10.1038/s41598-019-43176-9
[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.
https://doi.org/10.1109/HPEC.2019.8916288
[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].
https://doi.org/10.1038/s41467-018-07090-4
arXiv:1803.11173
[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].
arXiv:2101.02138
[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].
https://doi.org/10.1038/s41467-021-21728-w
arXiv:2001.00550
[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].
arXiv:1812.04170
[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].
https://doi.org/10.22331/q-2021-06-17-479
arXiv:2009.10095
[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].
arXiv:2002.01089
[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].
https://doi.org/10.1609/aaai.v34i03.5616
arXiv:1911.11071
[20] T. Albash and D. A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002
[21] D. Liang, L. Li, and S. Leichenauer, Investigating quantum approximate optimization algorithms under bang-bang protocols, Phys. Rev. Research 2, 033402 (2020).
https://doi.org/10.1103/PhysRevResearch.2.033402
[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).
https://doi.org/10.1126/sciadv.aau8342
[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).
https://doi.org/10.1145/227683.227684
[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].
https://doi.org/10.1103/PhysRevA.103.042612
arXiv:2010.11209
[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).
https://doi.org/10.1093/imamat/6.1.76
[26] R. Fletcher, A new approach to variable metric algorithms, The Computer Journal 13, 317 (1970).
https://doi.org/10.1093/comjnl/13.3.317
[27] D. Goldfarb, A family of variable-metric methods derived by variational means, Mathematics of Computation 24, 23 (1970).
https://doi.org/10.2307/2004873%20
http://www.jstor.org/stable/2004873
[28] D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Mathematics of Computation 24, 647 (1970).
https://doi.org/10.2307/2004840
http://www.jstor.org/stable/2004840
[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).
https://doi.org/10.1038/s41592-019-0686-2
[30] M. Rosenblatt, Remarks on some nonparametric estimates of a density function, Ann. Math. Statist. 27, 832 (1956).
https://doi.org/10.1214/aoms/1177728190
[31] E. Parzen, On estimation of a probability density function and mode, Ann. Math. Statist. 33, 1065 (1962).
https://doi.org/10.1214/aoms/1177704472
[32] T. Kadowaki and H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E 58, 5355 (1998).
https://doi.org/10.1103/PhysRevE.58.5355
[33] J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aeppli, Quantum Annealing of a Disordered Magnet, Science 284, 779 (1999).
https://doi.org/10.1126/science.284.5415.779
[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].
https://doi.org/10.1126/science.1057726
arXiv:quant-ph/0104129
[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].
arXiv:quant-ph/0001106
[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).
https://doi.org/10.1137/080734479
[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].
https://doi.org/10.1038/s41534-019-0217-0
arXiv:1906.06343
[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].
https://doi.org/10.1016/j.aop.2010.09.012
arXiv:1008.3477
[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].
https://doi.org/10.1126/science.aag2302
arXiv:1606.02318
[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].
https://doi.org/10.1038/s41534-021-00440-z
arXiv:2009.01760
[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].
https://doi.org/10.1038/s43588-021-00084-1
arXiv:2011.00027
[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).
https://doi.org/10.1103/RevModPhys.91.045001
[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).
https://doi.org/10.1073/pnas.1619826114
[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).
https://doi.org/10.1103/PhysRevLett.123.090602
[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).
https://doi.org/10.1103/PhysRevX.7.021027
[46] S. H. Sack, Trotterized quantum annealing initialization of the QAOA, https://github.com/shsack/TQA-init.-for-QAOA (2021).
https://github.com/shsack/TQA-init.-for-QAOA
[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).
https://networkx.org/
[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].
https://doi.org/10.1007/s00220-006-0150-x
arXiv:quant-ph/0508139
Cited by
[1] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, “Parameter Concentration in Quantum Approximate Optimization”, arXiv:2103.11976.
[2] Vrinda Mehta, Fengping Jin, Hans De Raedt, and Kristel Michielsen, “Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems”, arXiv:2106.04864.
The above citations are from SAO/NASA ADS (last updated successfully 2021-07-01 14:27:10). 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 2021-07-01 14:27:08: Could not fetch cited-by data for 10.22331/q-2021-07-01-491 from Crossref. This is normal if the DOI was registered recently.
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.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Source: https://quantum-journal.org/papers/q-2021-07-01-491/
