CoChat
Sign Up
PreprintCited by 45Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchQuantum many-body systems

The DOI matches its DataCite record.

Low depth mechanisms for quantum optimization

Open access
McClean, Jarrod R., Harrigan, Matthew P., Mohseni, Masoud, Rubin, Nicholas C., Jiang, Zhang, Boixo, Sergio, Smelyanskiy, Vadim N., Babbush, Ryan, Neven, Hartmut·2020·arXiv
DOI 10.48550/arxiv.2008.08615arXiv 2008.08615
Open this paper in CoChat — free accountOpen PDF

Abstract

One of the major application areas of interest for both near-term and fault-tolerant quantum computers is the optimization of classical objective functions. In this work, we develop intuitive constructions for a large class of these algorithms based on connections to simple dynamics of quantum systems, quantum walks, and classical continuous relaxations. We focus on developing a language and tools connected with kinetic energy on a graph for understanding the physical mechanisms of success and failure to guide algorithmic improvement. This physical language, in combination with uniqueness results related to unitarity, allow us to identify some potential pitfalls from kinetic energy fundamentally opposing the goal of optimization. This is connected to effects from wavefunction confinement, phase randomization, and shadow defects lurking in the objective far away from the ideal solution. As an example, we explore the surprising deficiency of many quantum methods in solving uncoupled spin problems and how this is both predictive of performance on some more complex systems while immediately suggesting simple resolutions. Further examination of canonical problems like the Hamming ramp or bush of implications show that entanglement can be strictly detrimental to performance results from the underlying mechanism of solution in approaches like QAOA. Kinetic energy and graph Laplacian perspectives provide new insights to common initialization and optimal solutions in QAOA as well as new methods for more effective layerwise training. Connections to classical methods of continuous extensions, homotopy methods, and iterated rounding suggest new directions for research in quantum optimization. Throughout, we unveil many pitfalls and mechanisms in quantum optimization using a physical perspective, which aim to spur the development of novel quantum optimization algorithms and refinements.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2008.08615

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Weighted subspace VQE provides an alternative way to simulate dynamics in the subspace of low energy eigenstates.

    “The weighted subspace VQE [110] provides an alternative way to simulate dynamics in the subspace of the low energy eigenstates [121].”

    From Variational quantum algorithms (2021) · cites this paper as [110]

    Section III describes VQE as a method for finding ground states, and Section VII discusses adiabatic evolution, but neither addresses simulating dynamics within a subspace of low-energy eigenstates. Searches for “weighted subspace VQE” and “simulate dynamics low energy eigenstates subspace” found no passage supporting the claim. In the citing sentence, the weighted-subspace VQE citation is [110]; this source is cited for the dynamics portion. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 95

  1. L. K. Grover, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (ACM, STOC, Philadelphia, PA, 1996), p. 212.
  2. C. Durr and P. Hoyer, A quantum algorithm for finding the minimum, ArXiv:quant-ph/9607014 (1996). · arXiv
  3. M. Szegedy, in 45th Annual IEEE Symposium on Founda- tions of Computer Science (IEEE, 2004), p. 32.
  4. R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, Focus beyond quadratic speedups for error-corrected quantum advantage, PRX Quantum 2, 010103 (2021). · DOI · Paper page
  5. N. J. Cerf, L. K. Grover, and C. P. Williams, Nested quan- tum search and structured problems, Phys. Rev. A 61, 032303 (2000). · DOI
  6. C. Dürr, M. Heiligman, P. Hoyer, and M. Mhalla, Quantum query complexity of some graph problems, SIAM J. Comput. 35, 1310 (2006). · DOI
  7. S. Mandra, G. G. Guerreschi, and A. Aspuru-Guzik, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, New J. Phys. 18, 073003 (2016). · DOI
  8. A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prūsis, and J. Vihrovs, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2019), p. 1783.
  9. A. Montanaro, Quantum speedup of branch-and-bound algorithms, Phys. Rev. Res. 2, 013056 (2020). · DOI
  10. Y. R. Sanders, D. W. Berry, P. Costa, N. Wiebe, C. Gid- ney, H. Neven, and R. Babbush, Compilation of fault- tolerant quantum heuristics for combinatorial optimization, ArXiv:2007.07391 (2020). · arXiv
  11. E. Campbell, A. Khurana, and A. Montanaro, Applying quantum algorithms to constraint satisfaction problems, Quantum 3, 167 (2019). · DOI
  12. B. Heim, T. F. Rønnow, S. V. Isakov, and M. Troyer, Quan- tum versus classical annealing of Ising spin glasses, Science 348, 215 (2015). · DOI
  13. A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70, 022314 (2004). · DOI · Paper page
  14. T. Kadowaki and H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E 58, 5355 (1998). · DOI · Paper page
  15. 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). · DOI · Paper page
  16. M. W. Johnson, M. H. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, et al., Quantum annealing with manufactured spins, Nature 473, 194 (2011). · DOI · Paper page
  17. 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). · DOI · Paper page
  18. V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Bab- bush, V. Smelyanskiy, J. Martinis, and H. Neven, What is the Computational Value of Finite-Range Tunneling? Phys. Rev. X 6, 031015 (2016). · DOI · Paper page
  19. M. Mohseni, J. Strumpfer, and M. M. Rams, Engineer- ing non-equilibrium quantum phase transitions via causally gapped Hamiltonians, New J. Phys. 20, 105002 (2018). · DOI
  20. Y. Susa, Y. Yamashiro, M. Yamamoto, and H. Nishimori, Exponential speedup of quantum annealing by inhomoge- neous driving of the transverse field, J. Phys. Soc. Jpn. 87, 023002 (2018). · DOI
  21. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220, 671 (1983). · DOI · Paper page
  22. D. J. Earl and M. W. Deem, Parallel tempering: Theory, applications, and new perspectives, Phys. Chem. Chem. Phys. 7, 3910 (2005). · DOI
  23. R. H. Swendsen and J.-S. Wang, Nonuniversal Critical Dynamics in Monte Carlo Simulations, Phys. Rev. Lett. 58, 86 (1987). · DOI
  24. U. Wolff, Collective Monte Carlo Updating for Spin Sys- tems, Phys. Rev. Lett. 62, 361 (1989). · DOI
  25. J. Houdayer, A cluster Monte Carlo algorithm for 2- dimensional spin glasses, Eur. Phys. J. B 22, 479 (2001). · DOI
  26. F. Hamze and N. de Freitas, in Proceedings of the 20th Con- ference on Uncertainty in Artificial Intelligence, UAI '04 (AUAI Press, 2004), p. 243.
  27. A. Selby, Efficient subgraph-based sampling of Ising-type models with frustration, ArXiv:1409.3934 (2014). · arXiv
  28. I. Hen, Solving spin glasses with optimized trees of clus- tered spins, Phys. Rev. E 96, 022105 (2017). · DOI
  29. M. M. Rams, M. Mohseni, and B. Gardas, Heuris- tic optimization and sampling with tensor networks, ArXiv:1811.06518 (2018). · arXiv
  30. G. S. Hartnett and M. Mohseni, Self-supervised learn- ing of generative spin-glasses with normalizing flows, ArXiv:2001.00585 (2020). · arXiv
  31. V. N. Smelyanskiy, K. Kechedzhi, S. Boixo, S. V. Isakov, H. Neven, and B. Altshuler, Nonergodic Delocalized States for Efficient Population Transfer within a Narrow Band of the Energy Landscape, Phys. Rev. X 10, 011017 (2020). · DOI
  32. B. Gidas, in 1985 24th IEEE Conference on Decision and Control (IEEE, 1985), p. 774.
  33. K. Kechedzhi, V. Smelyanskiy, J. R. McClean, V. S. Denchev, M. Mohseni, S. Isakov, S. Boixo, B. Altshuler, and H. Neven, Efficient population transfer via non-ergodic extended states in quantum spin glass, ArXiv:1807.04792 (2018). · arXiv
  34. E. Crosson and A. W. Harrow, in 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2016), p. 714.
  35. Z. Jiang, V. N. Smelyanskiy, S. V. Isakov, S. Boixo, G. Mazzola, M. Troyer, and H. Neven, Scaling analysis and instantons for thermally assisted tunneling and quantum monte carlo simulations, Phys. Rev. A 95, 012322 (2017). · DOI
  36. Z. Jiang, V. N. Smelyanskiy, S. Boixo, and H. Neven, Path-integral quantum monte carlo simulation with open- boundary conditions, Phys. Rev. A 96, 042330 (2017). · DOI
  37. P. W. Shor, Polynomial-time algorithms for prime factor- ization and discrete logarithms on a quantum computer, SIAM Rev. 41, 303 (1999). · DOI · Paper page
  38. S. Aaronson and A. Ambainis, The need for structure in quantum speedups, ArXiv:0911.0996 (2009). · arXiv
  39. 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). · DOI · Paper page
  40. J. R. McClean, J. Romero, R. Babbush, and A. Aspuru- Guzik, The theory of variational hybrid quantum-classical algorithms, New J. Phys. 18, 023023 (2016). · DOI · Paper page
  41. P. J. J. O'Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, et al., Scalable Quantum Simulation of Molecular Energies, Phys. Rev. X 6, 031007 (2016). · DOI · Paper page
  42. E. Farhi, J. Goldstone, and S. Gutmann, A quantum approx- imate optimization algorithm, ArXiv:quant-ph/1411.4028 (2014).
  43. G. Nannicini, Performance of hybrid quantum-classical variational heuristics for combinatorial optimization, Phys. Rev. E 99, 013304 (2019). · DOI · Paper page
  44. E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quan- tum computation by adiabatic evolution, ArXiv:quant-ph/ 0001106 (2000).
  45. L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum Approximate Optimization Algorithm: Perfor- mance, Mechanism, and Implementation on Near-Term Devices, Phys. Rev. X 10, 021067 (2020). · DOI · Paper page
  46. M. B. Hastings, Classical and quantum bounded depth approximation algorithms, ArXiv:1905.07047 (2019). · arXiv
  47. S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Obsta- cles to state preparation and variational optimization from symmetry protection, ArXiv:1910.08980 (2019). · arXiv
  48. F. G. 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:1812.04170 (2018). · arXiv
  49. G. Verdon, M. Broughton, J. R. McClean, K. J. Sung, R. Babbush, Z. Jiang, H. Neven, and M. Mohseni, Learning to learn with quantum neural networks via classical neural networks, ArXiv:1907.05415 (2019). · arXiv
  50. L. Li, M. Fan, M. Coram, P. Riley, and S. Leichenauer, Quantum optimization with a novel Gibbs objective func- tion and ansatz architecture search, Phys. Rev. Res. 2, 023074 (2020). · DOI · Paper page
  51. T. Albash and D. A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018). · DOI · Paper page
  52. E. Farhi and S. Gutmann, Analog analogue of a digital quantum computation, Phys. Rev. A 57, 2403 (1998). · DOI
  53. L. Novo, S. Chakraborty, M. Mohseni, H. Neven, and Y. Omar, Systematic dimensionality reduction for quantum walks: Optimal spatial search and transport on non-regular graphs, Sci. Rep. 5, 13304 (2015). · DOI
  54. S. Apers and A. Sarlette, Quantum fast-forwarding: Markov chains and graph property testing, ArXiv:1804.02321 (2018). · arXiv
  55. Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quantum approximate optimization algorithm for max- cut: A fermionic view, Phys. Rev. A 97, 022304 (2018). ArXiv:1706.02998 · DOI · Paper page
  56. Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, XY mixers: Analytical and numerical results for the quan- tum alternating operator ansatz, Phys. Rev. A 101, 012320 (2020). · DOI · Paper page
  57. A. Chapman and S. T. Flammia, Characterization of solv- able spin models via graph invariants, ArXiv:2003.05465 (2020). · arXiv
  58. R. Nandkishore and D. A. Huse, Many-body localization and thermalization in quantum statistical mechanics, Annu. Rev. Condens. Matter Phys. 6, 15 (2015). · DOI
  59. S. Hadfield, Z. Wang, B. O'Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum approx- imate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019). · DOI · Paper page
  60. J. Nocedal and S. Wright, Numerical Optimization (Springer Science & Business Media, New York, 2006).
  61. I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning (MIT Press, Cambridge, 2016).
  62. M. Streif and M. Leib, Comparison of QAOA with quantum and simulated annealing, ArXiv:1901.01903 (2019). · arXiv
  63. A. Bapat and S. Jordan, Bang-bang control as a design prin- ciple for classical and quantum optimization algorithms, ArXiv:1812.02746 (2018). · arXiv
  64. M. M. Wauters, G. B. Mbeng, and G. E. Santoro, Polyno- mial scaling of QAOA for ground-state preparation: Tam- ing first-order phase transitions, ArXiv:2003.07419 (2020). · arXiv
  65. M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Nest, and H.-J. Briegel, Entanglement in graph states and its applications, ArXiv:quant-ph/0602096 (2006). · arXiv
  66. E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size, ArXiv: 1910.08187 (2019). · arXiv
  67. D. S. Fisher, Critical behavior of random transverse-field Ising spin chains, Phys. Rev. B 51, 6411 (1995). · DOI
  68. B. W. Reichardt, in Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC, 2004), p. 502.
  69. S. Dughmi, Submodular functions: Extensions, distribu- tions, and algorithms. A survey, ArXiv:0912.0322 (2009). · arXiv
  70. V. V. Vazirani, Approximation Algorithms (Springer Sci- ence & Business Media, New York, 2013).
  71. P. Raghavan and C. D. Tompson, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica 7, 365 (1987). · DOI
  72. D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms (Cambridge University Press, Cambridge, 2011).
  73. M. Mezard and A. Montanari, Information, Physics, and Computation (Oxford University Press, Oxford, 2009).
  74. M. M. Rams, M. Mohseni, and B. Gardas, Spin-glass droplets learning and approximate optimization with tensor networks, ArXiv:1811.06518v4 (2018). · arXiv
  75. L. C. Lau, R. Ravi, and M. Singh, Iterative Methods in Combinatorial Optimization (Cambridge University Press, Cambridge, 2011), Vol. 46.
  76. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nat. Commun. 9, 1 (2018). · DOI · Paper page
  77. M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost-function-dependent barren plateaus in shallow quantum neural networks, ArXiv:2001.00550 (2020). · arXiv
  78. K. A. Smith, Neural networks for combinatorial opti- mization: A review of more than a decade of research, INFORMS J. Comput. 11, 15 (1999). · DOI
  79. I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Ben- gio, Neural combinatorial optimization with reinforcement learning, ArXiv:1611.09940 (2016). · arXiv
  80. P.-W. Wang, P. L. Donti, B. Wilder, and Z. Kolter, Satnet: Bridging deep learning and logical reasoning using a differ- entiable satisfiability solver, ArXiv:1905.12149 (2019). · arXiv
  81. L. T. Watson and R. T. Haftka, Modern homotopy methods in optimization, Comput. Methods Appl. Mech. Eng. 74, 289 (1989). · DOI
  82. B. Addis and S. Leyffer, A trust-region algorithm for global optimization, Comput. Optim. Appl. 35, 287 (2006). · DOI
  83. C. A. Floudas and P. M. Pardalos, Recent Advances in Global Optimization (Princeton University Press, Prince- ton, NJ, 2014), Vol. 176.
  84. E. L. Allgower and K. Georg, Numerical Continuation Methods: An Introduction (Springer Science & Business Media, Berlin, Heidelberg, 2012), Vol. 13.
  85. A. Garcia-Saez and J. Latorre, Addressing hard classical problems with adiabatically assisted variational quantum eigensolvers, ArXiv:1806.02287 (2018). · arXiv
  86. E. Farhi, J. Goldstone, and S. Gutmann, Quantum adiabatic evolution algorithms with different paths, ArXiv:quant-ph/0208135 (2002). · arXiv
  87. E. Farhi, J. Goldston, D. Gosset, S. Gutmann, H. B. Meyer, and P. Shor, Quantum adiabatic algorithms, small gaps, and different paths, Quantum Inf. Comput. 11, 181 (2011). · DOI
  88. V. Akshay, H. Philathong, M. E. Morales, and J. D. Bia- monte, Reachability Deficits in Quantum Approximate Optimization, Phys. Rev. Lett. 124, 090504 (2020). · DOI · Paper page
  89. P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, Improving variational quantum optimization using CVaR, Quantum 4, 256 (2020). · DOI · Paper page
  90. E. Crosson, T. Albash, I. Hen, and A. Young, De- signing Hamiltonians for quantum adiabatic optimization, ArXiv:2004.07681 (2020). · arXiv
  91. A. M. Childs, E. Farhi, J. Goldstone, and S. Gut- mann, Finding cliques by quantum adiabatic evolution, ArXiv:quant-ph/0012104 (2000). · arXiv
  92. W. J. Huggins, J. McClean, N. Rubin, Z. Jiang, N. Wiebe, K. B. Whaley, and R. Babbush, Efficient and noise resilient measurements for quantum chemistry on near-term quan- tum computers, ArXiv:1907.13117 (2019). · arXiv
  93. A. F. Izmaylov, T.-C. Yen, R. A. Lang, and V. Verteletskyi, Unitary partitioning approach to the measurement problem in the variational quantum eigensolver method, J. Chem. Theory Comput. 16, 190 (2019). · DOI · Paper page
  94. P. Gokhale and F. T. Chong, O(n 3 ) measurement cost for variational quantum eigensolver on molecular hamiltoni- ans, ArXiv:1908.11857 (2019). · arXiv
  95. F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, ArXiv:2004.04197 (2020). · arXiv

Cited by

Sorted by citations

Metadata

Authors
McClean, J. R., Harrigan, M. P., Mohseni, M., Rubin, N. C., Jiang, Z., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H.
Affiliations
Google (United States) (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
2
Issue
3
ISSN
2691-3399 (ISSN-L)
DOI
10.48550/arxiv.2008.08615
arXiv
2008.08615
OpenAlex
W3057420237
Cited by
45
References
0
Citations by year
2026: 1 · 2025: 5 · 2024: 14 · 2023: 4 · 2022: 13 · 2021: 7 · 2020: 1
FWCI
3.36
Type
journal article
Language
en
Open access
Licence
Locations
  • PRX Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum optimization algorithms, low-depth quantum circuits, variational quantum algorithms, algorithm optimization, quantum annealing, combinatorial optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review