- Physical Review Journals
All JournalsPhysics Magazine

Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou1,*,‡, Sheng-Tao Wang1,2,†,‡, Soonwon Choi1,3, Hannes Pichler4,1, and Mikhail D. Lukin1

  • 1Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
  • 2QuEra Computing Inc., Boston, Massachusetts 02135, USA
  • 3Department of Physics, University of California Berkeley, Berkeley, California 94720, USA
  • 4ITAMP, Harvard-Smithsonian Center for Astrophysics, Cambridge, Massachusetts 02138, USA

  • *leozhou@g.harvard.edu
  • †swang@quera-computing.com
  • ‡These authors contributed equally to this work.
PDF

Phys. Rev. X 10, 021067 – Published 24 June, 2020

DOI: https://doi.org/10.1103/PhysRevX.10.021067

Abstract

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems. Despite its promise for near-term quantum applications, not much is currently understood about the QAOA’s performance beyond its lowest-depth variant. An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization. We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations. Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O[poly(p)] time, whereas the standard strategy of random initialization requires 2O(p) optimization runs to achieve similar performance. We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps. The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps. Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA. When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices. We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Quantum computers hold the promise to solve computational problems that are beyond the reach of the most powerful classical computers. Recently, hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) have been proposed as promising applications for the near-term quantum computers. Nevertheless, not much is currently understood about their performance or mechanism beyond the simplest cases, as one critical hurdle is to find the optimal adjustable parameters for the algorithms. Here, we provide the first in-depth study of the performance of the QAOA by developing an efficient parameter-optimization procedure. We show that the QAOA can exploit novel mechanisms to speed up computation and provide tools that will guide the implementation of similar algorithms on near-term quantum computers.

Using the observed pattern in typical problems, our parameter-optimization procedure heuristically selects good initial parameters that can be further optimized. This strategy works remarkably well on all problems tested, efficiently finding high-quality parameters that would be intractable for conventional schemes. With these parameters in hand, we then discover that the QAOA can use operations beyond a conventional quantum paradigm to speed up the computation time by many orders of magnitude. Additionally, we propose a feasible implementation for a near-term experiment with hundreds of atoms that will allow the QAOA to challenge the best classical computers.

This work will greatly stimulate and guide the implementation of the QAOA and similar algorithms on near-term quantum-computing devices. Our theoretical insights will likely induce further understanding of these algorithms and increase confidence in their potential to exhibit quantum computational advantages.

Article Text

References (75)

  1. J. Preskill, Quantum Computing in the NISQ Era and Beyond, Quantum 2, 79 (2018).
  2. E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028.
  3. A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A Variational Eigenvalue Solver on a Photonic Quantum Processor, Nat. Commun. 5, 4213 (2014).
  4. N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gambetta, M. Ganzhorn, A. Kandala, A. Mezzacapo, P. Müller, W. Riess, G. Salis, J. Smolin, I. Tavernelli, and K. Temme, Quantum Optimization Using Variational Algorithms on Near-Term Quantum Devices, Quantum Sci. Technol. 3, 030503 (2018).
  5. A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-Efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets, Nature (London) 549, 242 (2017).
  6. J. S. Otterbach et al., Unsupervised Machine Learning on a Hybrid Quantum Computer, arXiv:1712.05771.
  7. C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A. Muschik, P. Silvi, R. Blatt, C. F. Roos, and P. Zoller, Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model, Nature (London) 569, 355 (2019).
  8. X. Qiang, X. Zhou, J. Wang, C. M. Wilkes, T. Loke, S. O’Gara, L. Kling, G. D. Marshall, R. Santagati, T. C. Ralph, J. B. Wang, J. L. O’Brien, M. G. Thompson, and J. C. F. Matthews, Large-Scale Silicon Quantum Photonics Implementing Arbitrary Two-Qubit Processing, Nat. Photonics 12, 534 (2018).
  9. G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe, Quantum Approximate Optimization with a Trapped-Ion Quantum Simulator, arXiv:1906.02700.
  10. E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062.
  11. E. Farhi and A. W. Harrow, Quantum Supremacy through the Quantum Approximate Optimization Algorithm, arXiv:1602.07674.
  12. M. B. Hastings, Classical and Quantum Bounded Depth Approximation Algorithms, arXiv:1905.07047.
  13. S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obstacles to State Preparation and Variational Optimization from Symmetry Protection, arXiv:1910.08980.
  14. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren Plateaus in Quantum Neural Network Training Landscapes, Nat. Commun. 9, 4812 (2018).
  15. E. Crosson, E. Farhi, C. Y.-Yu. Lin, H.-H. Lin, and P. Shor, Different Strategies for Optimization Using the Quantum Adiabatic Algorithm, arXiv:1401.7320.
  16. S. Muthukrishnan, T. Albash, and D. A. Lidar, Tunneling and Speedup in Quantum Optimization for Permutation-Symmetric Problems, Phys. Rev. X 6, 031010 (2016).
  17. L. Hormozi, E. W. Brown, G. Carleo, and M. Troyer, Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass, Phys. Rev. B 95, 184416 (2017).
  18. T. Albash and D. A. Lidar, Adiabatic Quantum Computation, Rev. Mod. Phys. 90, 015002 (2018).
  19. H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin, Probing Many-Body Dynamics on a 51-Atom Quantum Simulator, Nature (London) 551, 579 (2017).
  20. M. Saffman, T. G. Walker, and K. Mølmer, Quantum Information with Rydberg Atoms, Rev. Mod. Phys. 82, 2313 (2010).
  21. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity (Courier, North Chelmsford, 1998).
  22. B. Korte, J. Vygen, B. Korte, and J. Vygen, Combinatorial Optimization (Springer, New York, 2012), Vol. 2.
  23. J. Håstad, Some Optimal Inapproximability Results, J. ACM 48, 798 (2001).
  24. P. Berman and M. Karpinski, On Some Tighter Inapproximability Results (Extended Abstract) (Springer, Berlin, 1999), pp. 200–209.
  25. M. X. Goemans and D. P. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming, J. ACM 42, 1115 (1995).
  26. E. Halperin, D. Livnat, and U. Zwick, MAX CUT in Cubic Graphs, J. Algorithms 53, 169 (2004).
  27. Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View, Phys. Rev. A 97, 022304 (2018).
  28. D. Wecker, M. B. Hastings, and M. Troyer, Training a Quantum Optimizer, Phys. Rev. A 94, 022309 (2016).
  29. 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).
  30. W. W. Ho and T. H. Hsieh, Efficient Unitary Preparation of Non-trivial Quantum States, SciPost Phys. 6, 029 (2019).
  31. Z. Jiang, E. G. Rieffel, and Z. Wang, Near-Optimal Quantum Circuit for Grover’s Unstructured Search Using a Transverse Field, Phys. Rev. A 95, 062317 (2017).
  32. E. R. Anschuetz, J. P. Olson, A. Aspuru-Guzik, and Y. Cao, Variational Quantum Factoring, arXiv:1808.08927.

  33. The approximation ratio r=(2p+1)/(2p+2) is found for an infinite ring. For a finite ring with N vertices, numerical calculations show that for p<N/2 one has r=(2p+1)/(2p+2) for even N and r={[(2p+1)(N+1)]/[(2p+2)N]} for odd N, and for p≥N/2 one has r=1.

  34. The initial points βi0 are drawn uniformly from [−(π/4),(π/4)), and γi0 are drawn uniformly [−(π/2),(π/2)) for u3R graphs or [−2π,2π) for w3R graphs. Although γi0 can meaningfully take values beyond the restricted range γi0∈[−2π,2π) for a w3R graph, we find that broadening the range does not improve the performance. The ranges of the output parameters are not restricted in our unconstrained optimization routine.

  35. C. G. Broyden, The Convergence of a Class of Double-Rank Minimization Algorithms 1. General Considerations, IMA J. Appl. Math. 6, 76 (1970); R. Fletcher, A New Approach to Variable Metric Algorithms, Comput. J. 13, 317 (1970); D. Goldfarb, A Family of Variable-Metric Methods Derived by Variational Means, Math. Comput. 24, 23 (1970); D. F. Shanno, Conditioning of Quasi-Newton Methods for Function Minimization, 24, 647 (1970).

  36. We denote the best of all local optima optimized from k random initial points (seeds) to be (γ→B[k],β→B[k]). When the same optimum (γ→B[k],β→B[k]) is found from many different seeds and continues to yield the best Fp(γ→B[k],β→B[k]) as we increase the number of seeds k, we then claim that it is a global optimum, i.e., (γ→*,β→*)=limk→∞(γ→B[k],β→B[k]).

  37. J. A. Nelder and R. Mead, A Simplex Method for Function Minimization, Comput. J. 7, 308 (1965).
  38. P. I. Frazier, A Tutorial on Bayesian Optimization, arXiv:1807.02811.
  39. L. D. Landau, Zur Theorie der Energieubertragung II, Z. Sowjetunion 2, 46 (1932); C. Zener, Non-Adiabatic Crossing of Energy Levels, Proc. R. Soc. A 137, 696 (1932).
  40. T. Kadowaki and H. Nishimori, Quantum Annealing in the Transverse Ising Model, Phys. Rev. E 58, 5355 (1998).
  41. 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).
  42. S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, Evidence for Quantum Annealing with More than One Hundred Qubits, Nat. Phys. 10, 218 (2014).
  43. T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, Defining and Detecting Quantum Speedup, Science 345, 420 (2014).

  44. To be consistent with the language of QA, here we use the terminology of ground state and low excited states of −HC instead of referring to them as highest excited states in the MaxCut language.

  45. This result could change with different normalizations of the Hamiltonians HC and HB, but our qualitative results remain the same. The physical limitation in the experiment is typically the interaction strength in HC.

  46. H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays, arXiv:1808.10816.
  47. H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, Computational Complexity of the Rydberg Blockade in Two Dimensions, arXiv:1809.04954.
  48. G. G. Guerreschi and M. Smelyanskiy, Practical Optimization for Hybrid Quantum-Classical Algorithms, arXiv:1701.01450.
  49. F. Rendl, G. Rinaldi, and A. Wiegele, Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations, Math. Program. 121, 307 (2010).
  50. U. Benlic and J.-K. Hao, Breakout Local Search for the Max-Cut Problem, Engineering Applications of Artificial Intelligence 26, 1162 (2013).
  51. E. Cuthill and J. McKee, Reducing the Bandwidth of Sparse Symmetric Matrices, in Proceedings of the 24th National Conference, ACM ’69 (Association for Computing Machinery, New York, 1969), pp. 157–172.
  52. L. Lin and Y. Lin, Square-Root Rule of Two-Dimensional Bandwidth Problem, RAIRO, Theor. Inf. Appl. 45, 399 (2011).
  53. W. Lechner, P. Hauke, and P. Zoller, A Quantum Annealing Architecture with All-to-All Connectivity from Local Interactions, Sci. Adv. 1, e1500838 (2015).
  54. J. Díaz and M. Kamiński, Max-Cut and Max-Bisection Are NP-Hard on Unit Disk Graphs, Theor. Comput. Sci. 377, 271 (2007).
  55. H. Labuhn, D. Barredo, S. Ravets, S. de Léséleuc, T. Macrì, T. Lahaye, and A. Browaeys, Tunable Two-Dimensional Arrays of Single Rydberg Atoms for Realizing Quantum Ising Models, Nature (London) 534, 667 (2016).
  56. A. Keesling, A. Omran, H. Levine, H. Bernien, H. Pichler, S. Choi, R. Samajdar, S. Schwartz, P. Silvi, S. Sachdev, P. Zoller, M. Endres, M. Greiner, V. Vuletic, and M. D. Lukin, Probing Quantum Critical Dynamics on a Programmable Rydberg Simulator, Nature (London) 568, 207 (2019).
  57. A. Kumar, T.-Y. Wu, F. Giraldo, and D. S. Weiss, Sorting Ultracold Atoms in a Three-Dimensional Optical Lattice in a Realization of Maxwell’s Demon, Nature (London) 561, 83 (2018).
  58. H. Häffner, C. F. Roos, and R. Blatt, Quantum Computing with Trapped Ions, Phys. Rep. 469, 155 (2008).
  59. S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Demonstration of a Small Programmable Quantum Computer with Atomic Qubits, Nature (London) 536, 63 (2016).
  60. J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V. Gorshkov, Z. X. Gong, and C. Monroe, Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator, Nature (London) 551, 601 (2017).
  61. R. Barends et al., Digitized Adiabatic Quantum Computing with a Superconducting Circuit, Nature (London) 534, 222 (2016).
  62. C. Neill et al., A Blueprint for Demonstrating Quantum Supremacy with Superconducting Qubits, Science 360, 195 (2018).
  63. H. Levine, A. Keesling, A. Omran, H. Bernien, S. Schwartz, A. S. Zibrov, M. Endres, M. Greiner, V. Vuletić, and M. D. Lukin, High-Fidelity Control and Entanglement of Rydberg-Atom Qubits, Phys. Rev. Lett. 121, 123603 (2018).
  64. L. Isenhower, M. Saffman, and K. Mølmer, Multibit CNOT Quantum Gates via Rydberg Blockade, Quantum Inf. Process. 10, 755 (2011).
  65. T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K.-i. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, A Coherent Ising Machine for 2000-Node Optimization Problems, Science 354, 603 (2016).
  66. P. L. McMahon, A. Marandi, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, R. L. Byer, M. M. Fejer, H. Mabuchi, and Y. Yamamoto, A Fully-Programmable 100-Spin Coherent Ising Machine with All-to-All Connections, Science 354, 614 (2016).
  67. R. Hamerly et al., Experimental Investigation of Performance Differences between Coherent Ising Machines and a Quantum Annealer, Sci. Adv. 5, eaau0823 (2019).
  68. M. Bukov, A. G. R. Day, D. Sels, P. Weinberg, A. Polkovnikov, and P. Mehta, Reinforcement Learning in Different Phases of Quantum Control, Phys. Rev. X 8, 031086 (2018).
  69. A. Vahdatpour, F. Dabiri, M. Moazeni, and M. Sarrafzadeh, Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks, in Distributed Computing (Springer, Berlin, 2008), pp. 481–495.
  70. P. K. Agarwal, M. van Kreveld, and S. Suri, Label Placement by Maximum Independent Set in Rectangles, Comput. Geom. 11, 209 (1998).
  71. G. E. Crooks, Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem, arXiv:1811.08419.
  72. C. Moler and C. Van Loan, Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later, SIAM Rev. 45, 3 (2003).
  73. R. B. Sidje, Expokit: A Software Package for Computing Matrix Exponentials, ACM Trans. Math. Softw. 24, 130 (1998).
  74. A. H. Al-Mohy and N. J. Higham, Computing the Action of the Matrix Exponential, with an Application to Exponential Integrators, SIAM J. Sci. Comput. 33, 488 (2011).
  75. N. Khaneja, T. Reiss, C. Kehlet, T. Schulte-Herbrüggen, and S. J. Glaser, Optimal Control of Coupled Spin Dynamics: Design of NMR Pulse Sequences by Gradient Ascent Algorithms, J. Magn. Reson. 172, 296 (2005).

Outline

Information

Phys. Rev. X 10, 021067– Published 24 June, 2020
  • Received 9 November 2019
  • Accepted 15 May 2020
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation