Nothing Special   »   [go: up one dir, main page]
Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Review Article
  • Published:

Variational quantum algorithms

Nature Reviews Physics volume 3, pages 625–644 (2021)Cite this article

Subjects

Abstract

Applications such as simulating complicated quantum systems or solving large-scale linear algebra problems are very challenging for classical computers, owing to the extremely high computational cost. Quantum computers promise a solution, although fault-tolerant quantum computers will probably not be available in the near future. Current quantum devices have serious constraints, including limited numbers of qubits and noise processes that limit circuit depth. Variational quantum algorithms (VQAs), which use a classical optimizer to train a parameterized quantum circuit, have emerged as a leading strategy to address these constraints. VQAs have now been proposed for essentially all applications that researchers have envisaged for quantum computers, and they appear to be the best hope for obtaining quantum advantage. Nevertheless, challenges remain, including the trainability, accuracy and efficiency of VQAs. Here we overview the field of VQAs, discuss strategies to overcome their challenges and highlight the exciting prospects for using them to obtain quantum advantage.

Key points

  • Variational quantum algorithms (VQAs) are the leading proposal for achieving quantum advantage using near-term quantum computers.

  • VQAs have been developed for a wide range of applications, including finding ground states of molecules, simulating dynamics of quantum systems and solving linear systems of equations.

  • VQAs share a common structure, where a task is encoded into a parameterized cost function that is evaluated using a quantum computer, and a classical optimizer trains the parameters in the VQA.

  • The adaptive nature of VQAs is well suited to handle the constraints of near-term quantum computers.

  • Trainability, accuracy and efficiency are three challenges that arise when applying VQAs to large-scale applications, and strategies are currently being developed to address these challenges.

Access through your institution
Buy or subscribe

This is a preview of subscription content, access via your institution

Access options

Access through your institution

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Fig. 1: Applications of variational quantum algorithms.
Fig. 2: Schematic diagram of a variational quantum algorithm.
Fig. 3: Schematic diagram of an ansatz.
Fig. 4: Variational quantum eigensolver implementation.
Fig. 5: Quantum approximate optimization algorithm.
Fig. 6: Barren plateau phenomenon.

Similar content being viewed by others

References

  1. Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th Annual Symposium on Foundations of Computer Science, 124–134 (IEEE, 1994).

  2. Lloyd, S. Universal quantum simulators. Science 273, 1073–1078 (1996).

    Article  ADS  MathSciNet  MATH  Google Scholar 

  3. Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009).

    Article  ADS  MathSciNet  Google Scholar 

  4. IBM Makes Quantum Computing Available on IBM Cloud to Accelerate Innovation. Press release at https://www-03.ibm.com/press/us/en/pressrelease/49661.wss (2016).

  5. Adedoyin, A. et al. Quantum algorithm implementations for beginners. Preprint at https://arxiv.org/abs/1804.03719 (2018).

  6. Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018).

    Article  Google Scholar 

  7. Arute, F. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).

    Article  ADS  Google Scholar 

  8. Zhong, H.-S. et al. Quantum computational advantage using photons. Science 370, 1460–1463 (2020).

    Article  ADS  Google Scholar 

  9. Bittel, L. & Kliesch, M. Training variational quantum algorithms is np-hard — even for logarithmically many qubits and free fermionic systems. Preprint at https://arxiv.org/abs/2101.07267 (2021).

  10. Kingma, D. P. & Ba, J. Adam: a method for stochastic optimization. In Proc. 3rd International Conference on Learning Representations (ICLR) (ICLR, 2015).

  11. Kübler, J. M., Arrasmith, A., Cincio, L. & Coles, P. J. An adaptive optimizer for measurement-frugal variational algorithms. Quantum 4, 263 (2020).

    Article  Google Scholar 

  12. Sweke, R. et al. Stochastic gradient descent for hybrid quantum–classical optimization. Quantum 4, 314 (2020).

    Article  Google Scholar 

  13. McArdle, S. et al. Variational ansatz-based quantum simulation of imaginary time evolution. NPJ Quantum Inf. 5, 75 (2019).

    Article  ADS  Google Scholar 

  14. Stokes, J., Izaac, J., Killoran, N. & Carleo, G. Quantum natural gradient. Quantum 4, 269 (2020).

    Article  Google Scholar 

  15. Koczor, B. & Benjamin, S. C. Quantum natural gradient generalised to non-unitary circuits. Preprint at https://arxiv.org/abs/1912.08660 (2019).

  16. Wilson, M. et al. Optimizing quantum heuristics with meta-learning. Preprint at https://arxiv.org/abs/1908.03185 (2019).

  17. Spall, J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Automat. Control 37, 332–341 (1992).

    Article  MathSciNet  MATH  Google Scholar 

  18. Nakanishi, K. M., Fujii, K. & Todo, S. Sequential minimal optimization for quantum–classical hybrid algorithms. Phys. Rev. Res. 2, 043158 (2020).

    Article  Google Scholar 

  19. Parrish, R. M., Iosue, J. T., Ozaeta, A. & McMahon, P. L. A Jacobi diagonalization and Anderson acceleration algorithm for variational quantum algorithm parameter optimization. Preprint at https://arxiv.org/abs/1904.03206 (2019).

  20. Huembeli, P. & Dauphin, A. Characterizing the loss landscape of variational quantum circuits. Quantum Sci. Technol. 6, 025011 (2021).

    Article  ADS  Google Scholar 

  21. Harrow, A. & Napp, J. Low-depth gradient measurements can improve convergence in variational hybrid quantum–classical algorithms. Phys. Rev. Lett. 126, 140502 (2021).

    Article  ADS  Google Scholar 

  22. Kandala, A. et al. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature 549, 242–246 (2017).

    Article  ADS  Google Scholar 

  23. Gard, B. T. et al. Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm. NPJ Quantum Inf. 6, 10 (2020).

    Article  ADS  Google Scholar 

  24. Otten, M., Cortes, C. L. & Gray, S. K. Noise-resilient quantum dynamics using symmetry-preserving ansatzes. Preprint at https://arxiv.org/abs/1910.06284 (2019).

  25. Tkachenko, N. V. et al. Correlation-informed permutation of qubits for reducing ansatz depth in VQE. PRX Quantum 2, 020337 (2021).

    Article  ADS  Google Scholar 

  26. Kokail, C. et al. Self-verifying variational quantum simulation of lattice models. Nature 569, 355–360 (2019).

    Article  ADS  Google Scholar 

  27. Bravo-Prieto, C., Lumbreras-Zarapico, J., Tagliacozzo, L. & Latorre, J. I. Scaling of variational quantum circuit depth for condensed matter systems. Quantum 4, 272 (2020).

    Article  Google Scholar 

  28. Taube, A. G. & Bartlett, R. J. New perspectives on unitary coupled-cluster theory. Int. J. Quantum Chem. 106, 3393–3401 (2006).

    Article  ADS  Google Scholar 

  29. Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014).

    Article  ADS  Google Scholar 

  30. Bravyi, S. B. & Kitaev, A. Y. Fermionic quantum computation. Ann. Phys. 298, 210–226 (2002).

    Article  ADS  MathSciNet  MATH  Google Scholar 

  31. Lee, J., Huggins, W. J., Head-Gordon, M. & Whaley, K. B. Generalized unitary coupled cluster wave functions for quantum computation. J. Chem. Theory Comput. 15, 311–324 (2019).

    Article  Google Scholar 

  32. Motta, M. et al. Low rank representations for quantum simulation of electronic structure. Preprint at https://arxiv.org/abs/1808.02625 (2018).

  33. Matsuzawa, Y. & Kurashige, Y. Jastrow-type decomposition in quantum chemistry for low-depth quantum circuits. J. Chem. Theory Comput. 16, 944–952 (2020).

    Article  Google Scholar 

  34. Kivlichan, I. D. et al. Quantum simulation of electronic structure with linear depth and connectivity. Phys. Rev. Lett. 120, 110501 (2018).

    Article  ADS  MathSciNet  Google Scholar 

  35. Setia, K., Bravyi, S., Mezzacapo, A. & Whitfield, J. D. Superfast encodings for fermionic quantum simulation. Phys. Rev. Res. 1, 033033 (2019).

    Article  Google Scholar 

  36. Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm. Preprint at https://arxiv.org/abs/1411.4028 (2014).

  37. Hadfield, S. et al. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms 12, 34 (2019).

    Article  MathSciNet  MATH  Google Scholar 

  38. Lloyd, S. Quantum approximate optimization is computationally universal. Preprint at https://arxiv.org/abs/1812.11075 (2018).

  39. Morales, M. E., Biamonte, J. & Zimborás, Z. On the universality of the quantum approximate optimization algorithm. Quantum Inf. Process. 19, 291 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  40. Wang, Z., Rubin, N. C., Dominy, J. M. & Rieffel, E. G. XY mixers: analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A 101, 012320 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  41. Wecker, D., Hastings, M. B. & Troyer, M. Progress towards practical quantum variational algorithms. Phys. Rev. A 92, 042303 (2015).

    Article  ADS  Google Scholar 

  42. Wiersema, R. et al. Exploring entanglement and optimization within the Hamiltonian variational ansatz. Phys. Rev. X Quantum 1, 020319 (2020).

    Google Scholar 

  43. Ho, W. W. & Hsieh, T. H. Efficient variational simulation of non-trivial quantum states. SciPost Phys. 6, 029 (2019).

    Article  ADS  MathSciNet  Google Scholar 

  44. Grimsley, H. R., Economou, S. E., Barnes, E. & Mayhall, N. J. An adaptive variational algorithm for exact molecular simulations on a quantum computer. Nat. Commun. 10, 3007 (2019).

    Article  ADS  Google Scholar 

  45. Tang, H. L. et al. qubit-ADAPT-VQE: an adaptive algorithm for constructing hardware-efficient ansatze on a quantum processor. PRX Quantum 2, 020310 (2021).

    Article  ADS  Google Scholar 

  46. Yordanov, Y. S., Armaos, V., Barnes, C. H. & Arvidsson-Shukur, D. R. Iterative qubit-excitation based variational quantum eigensolver. Preprint at https://arxiv.org/abs/2011.10540 (2020).

  47. Zhu, L. et al. An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. Preprint at https://arxiv.org/abs/2005.10258 (2020).

  48. Rattew, A. G., Hu, S., Pistoia, M., Chen, R. & Wood, S. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver. Preprint at https://arxiv.org/abs/1910.09694 (2019).

  49. Chivilikhin, D. et al. MoG-VQE: multiobjective genetic variational quantum eigensolver. Preprint at https://arxiv.org/abs/2007.04424 (2020).

  50. Cincio, L., Rudinger, K., Sarovar, M. & Coles, P. J. Machine learning of noise-resilient quantum circuits. Phys. Rev. X Quantum 2, 010324 (2021).

    Google Scholar 

  51. Cincio, L., Subaşı, Y., Sornborger, A. T. & Coles, P. J. Learning the quantum algorithm for state overlap. New J. Phys. 20, 113022 (2018).

    Article  ADS  Google Scholar 

  52. Du, Y., Huang, T., You, S., Hsieh, M.-H. & Tao, D. Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers. Preprint at https://arxiv.org/abs/2010.10217 (2020).

  53. Zhang, S.-X., Hsieh, C.-Y., Zhang, S. & Yao, H. Differentiable quantum architecture search. Preprint at https://arxiv.org/abs/2010.08561 (2020).

  54. Bilkis, M., Cerezo, M., Verdon, G., Coles, P. J. & Cincio, L. A semi-agnostic ansatz with variable structure for quantum machine learning. Preprint at https://arxiv.org/abs/2103.06712 (2021).

  55. Rattew, A. G., Hu, S., Pistoia, M., Chen, R. & Wood, S. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver. Preprint at https://arxiv.org/abs/1910.09694 (2019).

  56. Yang, Z.-C., Rahmani, A., Shabani, A., Neven, H. & Chamon, C. Optimizing variational quantum algorithms using Pontryagin’s minimum principle. Phys. Rev. X 7, 021027 (2017).

    Google Scholar 

  57. Magann, A. B. et al. From pulses to circuits and back again: a quantum optimal control perspective on variational quantum algorithms. Phys. Rev. X Quantum 2, 010101 (2021).

    Google Scholar 

  58. Choquette, A. et al. Quantum-optimal-control-inspired ansatz for variational quantum algorithms. Phys. Rev. Res. 3, 023092 (2021).

    Article  Google Scholar 

  59. Li, J., Yang, X., Peng, X. & Sun, C.-P. Hybrid quantum–classical approach to quantum optimal control. Phys. Rev. Lett. 118, 150503 (2017).

    Article  ADS  Google Scholar 

  60. Lu, D. et al. Enhancing quantum control by bootstrapping a quantum processor of 12 qubits. NPJ Quantum Inf. 3, 45 (2017).

    Article  ADS  Google Scholar 

  61. O’Malley, P. J. et al. Scalable quantum simulation of molecular energies. Phys. Rev. X 6, 031007 (2016).

    Google Scholar 

  62. Takeshita, T. et al. Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources. Phys. Rev. X 10, 011004 (2020).

    Google Scholar 

  63. Valiant, L. G. Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput. 31, 1229–1254 (2002).

    Article  MathSciNet  MATH  Google Scholar 

  64. Terhal, B. M. & DiVincenzo, D. P. Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A 65, 032325 (2002).

    Article  ADS  Google Scholar 

  65. Jozsa, R. & Miyake, A. Matchgates and classical simulation of quantum circuits. Proc. Math. Phys. Eng. Sci. 464, 3089–3106 (2008).

    MathSciNet  MATH  Google Scholar 

  66. Mizukami, W. et al. Orbital optimized unitary coupled cluster theory for quantum computer. Phys. Rev. Res. 2, 033421 (2020).

    Article  Google Scholar 

  67. Sokolov, I. O. et al. Quantum orbital-optimized unitary coupled cluster methods in the strongly correlated regime: can quantum algorithms outperform their classical equivalents? J. Chem. Phys. 152, 124107 (2020).

    Article  ADS  Google Scholar 

  68. McClean, J. R., Kimchi-Schwartz, M. E., Carter, J. & de Jong, W. A. Hybrid quantum–classical hierarchy for mitigation of decoherence and determination of excited states. Phys. Rev. A 95, 042308 (2017).

    Article  ADS  Google Scholar 

  69. Parrish, R. M., Hohenstein, E. G., McMahon, P. L. & Martínez, T. J. Quantum computation of electronic transitions using a variational quantum eigensolver. Phys. Rev. Lett. 122, 230401 (2019).

    Article  ADS  Google Scholar 

  70. Parrish, R. M. & McMahon, P. L. Quantum filter diagonalization: quantum eigendecomposition without full quantum phase estimation. Preprint at https://arxiv.org/abs/1909.08925 (2019).

  71. Huggins, W. J., Lee, J., Baek, U., O’Gorman, B. & Whaley, K. B. A non-orthogonal variational quantum eigensolver. New J. Phys. 22, 073009 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  72. Stair, N. H., Huang, R. & Evangelista, F. A. A multireference quantum Krylov algorithm for strongly correlated electrons. J. Chem. Theory Comput. 16, 2236–2245 (2020).

    Article  Google Scholar 

  73. Bharti, K. & Haug, T. Iterative quantum assisted eigensolver. Preprint at https://arxiv.org/abs/2010.05638 (2020).

  74. Bharti, K. & Haug, T. Quantum assisted simulator. Preprint at https://arxiv.org/abs/2011.06911 (2020).

  75. Markov, I. L. & Shi, Y. Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38, 963–981 (2008).

    Article  MathSciNet  MATH  Google Scholar 

  76. Kim, I. H. & Swingle, B. Robust entanglement renormalization on a noisy quantum computer. Preprint at https://arxiv.org/abs/1711.07500 (2017).

  77. Kim, I. H. Holographic quantum simulation. Preprint at https://arxiv.org/abs/1702.02093 (2017).

  78. Liu, J.-G., Zhang, Y.-H., Wan, Y. & Wang, L. Variational quantum eigensolver with fewer qubits. Phys. Rev. Res. 1, 023025 (2019).

    Article  Google Scholar 

  79. Barratt, F. et al. Parallel quantum simulation of large systems on small quantum computers. npj Quantum Inf. 7, 79 (2021).

    Article  ADS  Google Scholar 

  80. Yuan, X., Sun, J., Liu, J., Zhao, Q. & Zhou, Y. Quantum simulation with hybrid tensor networks. Preprint at https://arxiv.org/abs/2007.00958 (2020).

  81. Fujii, K., Mitarai, K., Mizukami, W. & Nakagawa, Y. O. Deep variational quantum eigensolver: a divide-and-conquer method for solving a larger problem with smaller size quantum computers. Preprint at https://arxiv.org/abs/2007.10917 (2020).

  82. Mazzola, G., Ollitrault, P. J., Barkoutsos, P. K. & Tavernelli, I. Nonunitary operations for ground-state calculations in near-term quantum computers. Phys. Rev. Lett. 123, 130501 (2019).

    Article  ADS  Google Scholar 

  83. Martyn, J. & Swingle, B. Product spectrum ansatz and the simplicity of thermal states. Phys. Rev. A 100, 032107 (2019).

    Article  ADS  MathSciNet  Google Scholar 

  84. Yoshioka, N., Nakagawa, Y. O., Mitarai, K. & Fujii, K. Variational quantum algorithm for nonequilibrium steady states. Phys. Rev. Res. 2, 043289 (2020).

    Article  Google Scholar 

  85. Verdon, G., Marks, J., Nanda, S., Leichenauer, S. & Hidary, J. Quantum Hamiltonian-based models and the variational quantum thermalizer algorithm. Preprint at https://arxiv.org/abs/1910.02071 (2019).

  86. Liu, J., Mao, L., Zhang, P. & Wang, L. Solving quantum statistical mechanics with variational autoregressive networks and quantum circuits. Mach. Learn. Sci. Technol. 2, 025011 (2021).

    Article  Google Scholar 

  87. Sim, S., Johnson, P. D. & Aspuru-Guzik, A. Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum–classical algorithms. Adv. Quantum Technol. 2, 1900070 (2019).

    Article  Google Scholar 

  88. Nakaji, K. & Yamamoto, N. Expressibility of the alternating layered ansatz for quantum computation. Quantum5, 434 (2021).

    Article  Google Scholar 

  89. Schuld, M., Sweke, R. & Meyer, J. J. The effect of data encoding on the expressive power of variational quantum machine learning models. Phys. Rev. A 103, 032430 (2021).

    Article  ADS  MathSciNet  Google Scholar 

  90. Abbas, A. et al. The power of quantum neural networks. Nat. Comput. Sci. 1, 403–409 (2021).

    Article  Google Scholar 

  91. Holmes, Z., Sharma, K., Cerezo, M. & Coles, P. J. Connecting ansatz expressibility to gradient magnitudes and barren plateaus. Preprint at https://arxiv.org/abs/2101.02138 (2021).

  92. Guerreschi, G. G. & Smelyanskiy, M. Practical optimization for hybrid quantum–classical algorithms. Preprint at https://arxiv.org/abs/1701.01450 (2017).

  93. Mitarai, K., Negoro, M., Kitagawa, M. & Fujii, K. Quantum circuit learning. Phys. Rev. A 98, 032309 (2018).

    Article  ADS  Google Scholar 

  94. Schuld, M., Bergholm, V., Gogolin, C., Izaac, J. & Killoran, N. Evaluating analytic gradients on quantum hardware. Phys. Rev. A 99, 032331 (2019).

    Article  ADS  Google Scholar 

  95. Bergholm, V. et al. Pennylane: Automatic differentiation of hybrid quantum–classical computations. Preprint at https://arxiv.org/abs/1811.04968 (2018).

  96. Mari, A., Bromley, T. R. & Killoran, N. Estimating the gradient and higher-order derivatives on quantum hardware. Phys. Rev. A 103, 012405 (2021).

    Article  ADS  MathSciNet  Google Scholar 

  97. Cerezo, M. & Coles, P. J. Impact of barren plateaus on the Hessian and higher order derivatives. Quantum Sci. Technol. 6, 035006 (2021).

    Article  ADS  Google Scholar 

  98. Koczor, B. & Benjamin, S. C. Quantum analytic descent. Preprint at https://arxiv.org/abs/2008.13774 (2020).

  99. Li, Y. & Benjamin, S. C. Efficient variational quantum simulator incorporating active error minimization. Phys. Rev. X 7, 021050 (2017).

    Google Scholar 

  100. Yuan, X., Endo, S., Zhao, Q., Li, Y. & Benjamin, S. C. Theory of variational quantum simulation. Quantum 3, 191 (2019).

    Article  Google Scholar 

  101. Endo, S., Sun, J., Li, Y., Benjamin, S. C. & Yuan, X. Variational quantum simulation of general processes. Phys. Rev. Lett. 125, 010501 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  102. Mitarai, K. & Fujii, K. Methodology for replacing indirect measurements with direct measurements. Phys. Rev. Res. 1, 013006 (2019).

    Article  Google Scholar 

  103. Biamonte, J. Universal variational quantum computation. Phys. Rev. A 103, L030401 (2021).

    Article  MathSciNet  Google Scholar 

  104. Abrams, D. S. & Lloyd, S. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Phys. Rev. Lett. 83, 5162–5165 (1999).

    Article  ADS  Google Scholar 

  105. Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. & Head-Gordon, M. Simulated quantum computation of molecular energies. Science 309, 1704–1707 (2005).

    Article  ADS  Google Scholar 

  106. Higgott, O., Wang, D. & Brierley, S. Variational quantum computation of excited states. Quantum 3, 156 (2019).

    Article  Google Scholar 

  107. Buhrman, H., Cleve, R., Watrous, J. & De Wolf, R. Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001).

    Article  ADS  Google Scholar 

  108. Jones, T., Endo, S., McArdle, S., Yuan, X. & Benjamin, S. C. Variational quantum algorithms for discovering Hamiltonian spectra. Phys. Rev. A 99, 062304 (2019).

    Article  ADS  Google Scholar 

  109. Nakanishi, K. M., Mitarai, K. & Fujii, K. Subspace-search variational quantum eigensolver for excited states. Phys. Rev. Res. 1, 033062 (2019).

    Article  Google Scholar 

  110. McClean, J. R. et al. Low depth mechanisms for quantum optimization. Preprint at https://arxiv.org/abs/2008.08615 (2020).

  111. Garcia-Saez, A. & Latorre, J. Addressing hard classical problems with adiabatically assisted variational quantum eigensolvers. Preprint at https://arxiv.org/abs/1806.02287 (2018).

  112. Cerezo, M., Sharma, K., Arrasmith, A. & Coles, P. J. Variational quantum state eigensolver. Preprint at https://arxiv.org/abs/2004.01372 (2020).

  113. Wang, D., Higgott, O. & Brierley, S. Accelerated variational quantum eigensolver. Phys. Rev. Lett. 122, 140504 (2019).

    Article  ADS  Google Scholar 

  114. Wang, G., Koh, D. E., Johnson, P. D. & Cao, Y. Minimizing estimation runtime on noisy quantum computers. Phys. Rev. X Quantum 2, 010346 (2021).

    Google Scholar 

  115. Guoming, W., Koh, D. E., Johnson, P. D. & Cao, Yudong. Bayesian inference with engineered likelihood functions for robust amplitude estimation. PRX Quantum 2, 010346 (2021).

    Google Scholar 

  116. Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information, 10th Anniversary Edition (Cambridge Univ. Press, 2011).

  117. McLachlan, A. A variational solution of the time-dependent Schrodinger equation. Mol. Phys. 8, 39–44 (1964).

    Article  ADS  MathSciNet  Google Scholar 

  118. Yao, Y.-X. et al. Adaptive variational quantum dynamics simulations. Preprint at https://arxiv.org/abs/2011.00622 (2020).

  119. Zhang, Z.-J., Sun, J., Yuan, X. & Yung, M.-H. Low-depth hamiltonian simulation by adaptive product formula. Preprint at https://arxiv.org/abs/2011.05283 (2020).

  120. Heya, K., Nakanishi, K. M., Mitarai, K. & Fujii, K. Subspace variational quantum simulator. Preprint at https://arxiv.org/abs/1904.08566 (2019).

  121. Cirstoiu, C. et al. Variational fast forwarding for quantum simulation beyond the coherence time. NPJ Quantum Inf. 6, 82 (2020).

    Article  ADS  Google Scholar 

  122. Gibbs, J. et al. Long-time simulations with high fidelity on quantum hardware. Preprint at https://arxiv.org/abs/2102.04313 (2021).

  123. Khatri, S. et al. Quantum-assisted quantum compiling. Quantum 3, 140 (2019).

    Article  Google Scholar 

  124. Commeau, B. et al. Variational Hamiltonian diagonalization for dynamical quantum simulation. Preprint at https://arxiv.org/abs/2009.02559 (2020).

  125. Moll, N. et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Sci. Technol. 3, 030503 (2018).

    Article  ADS  Google Scholar 

  126. Lin, C. Y.-Y. & Zhu, Y. Performance of qaoa on typical instances of constraint satisfaction problems with bounded degree. Preprint at https://arxiv.org/abs/1601.01744 (2016).

  127. Wang, Z., Hadfield, S., Jiang, Z. & Rieffel, E. G. Quantum approximate optimization algorithm for MaxCut: a fermionic view. Phys. Rev. A 97, 022304 (2018).

    Article  ADS  Google Scholar 

  128. Shaydulin, R., Safro, I. & Larson, J. Multistart methods for quantum approximate optimization. In 2019 IEEE High Performance Extreme Computing Conference (HPEC) (IEEE, 2019); https://ieeexplore.ieee.org/document/8916288/

  129. Romero, J. et al. Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Sci. Technol. 4, 014008 (2018).

    Article  ADS  Google Scholar 

  130. Crooks, G. E. Performance of the quantum approximate optimization algorithm on the maximum cut problem. Preprint at https://arxiv.org/abs/1811.08419 (2018).

  131. Wecker, D., Hastings, M. B. & Troyer, M. Training a quantum optimizer. Phys. Rev. A 94, 022309 (2016).

    Article  ADS  Google Scholar 

  132. Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y. & Balaprakash, P. Learning to optimize variational quantum circuits to solve combinatorial problems. Proc. AAAI Conf. Artif. Intell. 34, 2367–2375 (2020).

    Google Scholar 

  133. Ambainis, A. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. In 29th Int. Symp. Theoretical Aspects of Computer Science (STACS 2012), 636–647 (Dagstuhl, 2012).

  134. Subaşı, Y., Somma, R. D. & Orsucci, D. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett. 122, 060504 (2019).

    Article  ADS  Google Scholar 

  135. Childs, A., Kothari, R. & Somma, R. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput. 46, 1920–1950 (2017).

    Article  MathSciNet  MATH  Google Scholar 

  136. Chakraborty, S., Gilyén, A. & Jeffery, S. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In Leibniz International Proceedings in Informatics (LIPIcs) Vol. 132, 33:1–33:14 (Dagstuhl, 2019).

  137. Scherer, A. et al. Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target. Quantum Inf. Process. 16, 60 (2017).

    Article  ADS  MathSciNet  MATH  Google Scholar 

  138. Bravo-Prieto, C. et al. Variational quantum linear solver: a hybrid algorithm for linear systems. Preprint at https://arxiv.org/abs/1909.05820 (2019).

  139. Xu, X. et al. Variational algorithms for linear algebra. Preprint at https://arxiv.org/abs/1911.05759 (2019).

  140. Huang, H.-Y., Bharti, K. & Rebentrost, P. Near-term quantum algorithms for linear systems of equations. Preprint at https://arxiv.org/abs/1909.07344 (2019).

  141. Lubasch, M., Joo, J., Moinier, P., Kiffner, M. & Jaksch, D. Variational quantum algorithms for nonlinear problems. Phys. Rev. A 101, 010301 (2020).

    Article  ADS  Google Scholar 

  142. Kyriienko, O., Paine, A. E. & Elfving, V. E. Solving nonlinear differential equations with differentiable quantum circuits. Phys. Rev. A 103, 052416 (2021).

    Article  ADS  MathSciNet  Google Scholar 

  143. Anschuetz, E., Olson, J., Aspuru-Guzik, A. & Cao, Y. Variational quantum factoring. In International Workshop on Quantum Technology and Optimization Problems, 74–85 (Springer, 2019).

  144. Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum principal component analysis. Nat. Phys. 10, 631–633 (2014).

    Article  Google Scholar 

  145. LaRose, R., Tikku, A., O’Neel-Judy, É., Cincio, L. & Coles, P. J. Variational quantum state diagonalization. NPJ Quantum Inf. 5, 57 (2019).

    Article  Google Scholar 

  146. Heya, K., Suzuki, Y., Nakamura, Y. & Fujii, K. Variational quantum gate optimization. Preprint at https://arxiv.org/abs/1810.12745 (2018).

  147. Jones, T. & Benjamin, S. C. Quantum compilation and circuit optimisation via energy dissipation. Preprint at https://arxiv.org/abs/1811.03147 (2018).

  148. Sharma, K., Khatri, S., Cerezo, M. & Coles, P. J. Noise resilience of variational quantum compiling. New J. Phys. 22, 043006 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  149. Carolan, J. et al. Variational quantum unsampling on a quantum photonic processor. Nat. Phys. 16, 322–327 (2020).

    Article  Google Scholar 

  150. Johnson, P. D., Romero, J., Olson, J., Cao, Y. & Aspuru-Guzik, A. Qvector: an algorithm for device-tailored quantum error correction. Preprint at https://arxiv.org/abs/1711.02249 (2017).

  151. Xu, X., Benjamin, S. C. & Yuan, X. Variational circuit compiler for quantum error correction. Phys. Rev. Appl. 15, 034068 (2021).

    Article  ADS  Google Scholar 

  152. Biamonte, J. et al. Quantum machine learning. Nature 549, 195–202 (2017).

    Article  ADS  Google Scholar 

  153. Farhi, E. & Neven, H. Classification with quantum neural networks on near term processors. Preprint at https://arxiv.org/abs/1802.06002 (2018).

  154. Schuld, M., Bocharov, A., Svore, K. M. & Wiebe, N. Circuit-centric quantum classifiers. Phys. Rev. A 101, 032308 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  155. Schuld, M. & Killoran, N. Quantum machine learning in feature Hilbert spaces. Phys. Rev. Lett. 122, 040504 (2019).

    Article  ADS  Google Scholar 

  156. Havlíček, V. et al. Supervised learning with quantum-enhanced feature spaces. Nature 567, 209–212 (2019).

    Article  ADS  Google Scholar 

  157. Stoudenmire, E. & Schwab, D. J. Supervised learning with tensor networks. Adv. Neural Inf. Proc. Syst. 29, 4799–4807 (2016).

  158. Lloyd, S., Schuld, M., Ijaz, A., Izaac, J. & Killoran, N. Quantum embeddings for machine learning. Preprint at https://arxiv.org/abs/2001.03622 (2020).

  159. Pérez-Salinas, A., Cervera-Lierta, A., Gil-Fuster, E. & Latorre, J. I. Data re-uploading for a universal quantum classifier. Quantum 4, 226 (2020).

    Article  Google Scholar 

  160. Kusumoto, T., Mitarai, K., Fujii, K., Kitagawa, M. & Negoro, M. Experimental quantum kernel machine learning with nuclear spins in a solid. Physica A 541, 123290 (2020).

    MathSciNet  Google Scholar 

  161. Romero, J., Olson, J. P. & Aspuru-Guzik, A. Quantum autoencoders for efficient compression of quantum data. Quantum Sci. Technol. 2, 045001 (2017).

    Article  ADS  Google Scholar 

  162. Wan, K. H., Dahlsten, O., Kristjánsson, H., Gardner, R. & Kim, M. Quantum generalisation of feedforward neural networks. NPJ Quantum Inf. 3, 36 (2017).

    Article  ADS  Google Scholar 

  163. Verdon, G., Pye, J. & Broughton, M. A universal training algorithm for quantum deep learning. Preprint at https://arxiv.org/abs/1806.09729 (2018).

  164. Cerezo, M., Sone, A., Volkoff, T., Cincio, L. & Coles, P. J. Cost function dependent barren plateaus in shallow parameterized quantum circuits. Nat. Commun. 12, 1791 (2021).

    Article  ADS  Google Scholar 

  165. Cao, C. & Wang, X. Noise-assisted quantum autoencoder. Phys. Rev. Appl. 15, 054012 (2021).

    Article  ADS  Google Scholar 

  166. Pepper, A., Tischler, N. & Pryde, G. J. Experimental realization of a quantum autoencoder: the compression of qutrits via machine learning. Phys. Rev. Lett. 122, 060501 (2019).

    Article  ADS  Google Scholar 

  167. Verdon, G., Broughton, M. & Biamonte, J. A quantum algorithm to train neural networks using low-depth circuits. Preprint at https://arxiv.org/abs/1712.05304 (2017).

  168. Benedetti, M. et al. A generative modeling approach for benchmarking and training shallow quantum circuits. NPJ Quantum Inf. 5, 45 (2019).

    Article  ADS  Google Scholar 

  169. Du, Y., Hsieh, M.-H., Liu, T. & Tao, D. Expressive power of parameterized quantum circuits. Phys. Rev. Res. 2, 033125 (2020).

    Article  Google Scholar 

  170. Liu, J.-G. & Wang, L. Differentiable learning of quantum circuit Born machines. Phys. Rev. A 98, 062324 (2018).

    Article  ADS  Google Scholar 

  171. Coyle, B., Mills, D., Danos, V. & Kashefi, E. The Born supremacy: quantum advantage and training of an Ising Born machine. NPJ Quantum Inf. 6, 60 (2020).

    Article  ADS  Google Scholar 

  172. Romero, J. & Aspuru-Guzik, A. Variational quantum generators: generative adversarial quantum machine learning for continuous distributions. Preprint at https://arxiv.org/abs/1901.00848 (2019).

  173. Altaisky, M. Quantum neural network. Preprint at https://arxiv.org/abs/quant-ph/0107012 (2001).

  174. Beer, K. et al. Training deep quantum neural networks. Nat. Commun. 11, 808 (2020).

    Article  ADS  Google Scholar 

  175. Cong, I., Choi, S. & Lukin, M. D. Quantum convolutional neural networks. Nat. Phys. 15, 1273–1278 (2019).

    Article  Google Scholar 

  176. Franken, L. & Georgiev, B. Explorations in quantum neural networks with intermediate measurements. In Proc. ESANN (2020); https://www.esann.org/sites/default/files/proceedings/2020/ES2020-197.pdf

  177. Pesah, A. et al. Absence of barren plateaus in quantum convolutional neural networks. Preprint at https://arxiv.org/abs/2011.02966 (2020).

  178. Zhang, K., Hsieh, M.-H., Liu, L. & Tao, D. Toward trainability of quantum neural networks. Preprint at https://arxiv.org/abs/2011.06258 (2020).

  179. Zurek, W. H. Quantum Darwinism. Nat. Phys. 5, 181–188 (2009).

    Article  Google Scholar 

  180. Arrasmith, A., Cincio, L., Sornborger, A. T., Zurek, W. H. & Coles, P. J. Variational consistent histories as a hybrid algorithm for quantum foundations. Nat. Commun. 10, 3438 (2019).

    Article  ADS  Google Scholar 

  181. Griffiths, R. B. Consistent Quantum Theory (Cambridge Univ. Press, 2003).

  182. Holmes, Z. et al. Barren plateaus preclude learning scramblers. Phys. Rev. Lett. 126, 190501 (2021).

    Article  ADS  MathSciNet  Google Scholar 

  183. Hayden, P. & Preskill, J. Black holes as mirrors: quantum information in random subsystems. J. High Energy Phys. 2007, 120 (2007).

    Article  MathSciNet  Google Scholar 

  184. Wilde, M. M. Quantum Information Theory (Cambridge Univ. Press, 2013).

  185. Rosgen, B. & Watrous, J. On the hardness of distinguishing mixed-state quantum computations. In 20th Annual IEEE Conference on Computational Complexity (CCC’05) 344–354 (IEEE, 2005).

  186. Cerezo, M., Poremba, A., Cincio, L. & Coles, P. J. Variational quantum fidelity estimation. Quantum 4, 248 (2020).

    Article  Google Scholar 

  187. Bravo-Prieto, C., García-Martín, D. & Latorre, J. I. Quantum singular value decomposer. Phys. Rev. A 101, 062310 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  188. Koczor, B., Endo, S., Jones, T., Matsuzaki, Y. & Benjamin, S. C. Variational-state quantum metrology. New J. Phys. 22, 083038 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  189. Kaubruegger, R. et al. Variational spin-squeezing algorithms on programmable quantum sensors. Phys. Rev. Lett. 123, 260505 (2019).

    Article  ADS  Google Scholar 

  190. Ma, Z. et al. Adaptive circuit learning for quantum metrology. Preprint at https://arxiv.org/abs/2010.08702 (2020).

  191. Beckey, J. L., Cerezo, M., Sone, A. & Coles, P. J. Variational quantum algorithm for estimating the quantum Fisher information. Preprint at https://arxiv.org/abs/2010.10488 (2020).

  192. McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R. & Neven, H. Barren plateaus in quantum neural network training landscapes. Nat. Commun. 9, 4812 (2018).

    Article  ADS  Google Scholar 

  193. Arrasmith, A., Cerezo, M., Czarnik, P., Cincio, L. & Coles, P. J. Effect of barren plateaus on gradient-free optimization. Preprint at https://arxiv.org/abs/2011.12245 (2020).

  194. Harrow, A. W. & Low, R. A. Random quantum circuits are approximate 2-designs. Commun. Math. Phys. 291, 257–302 (2009).

    Article  ADS  MathSciNet  MATH  Google Scholar 

  195. Brandao, F. G., Harrow, A. W. & Horodecki, M. Local random quantum circuits are approximate polynomial-designs. Commun. Math. Phys. 346, 397–434 (2016).

    Article  ADS  MathSciNet  MATH  Google Scholar 

  196. Uvarov, A., Biamonte, J. D. & Yudin, D. Variational quantum eigensolver for frustrated quantum systems. Phys. Rev. B 102, 075104 (2020).

    Article  ADS  Google Scholar 

  197. Uvarov, A. & Biamonte, J. On barren plateaus and cost function locality in variational quantum algorithms. J. Phys. A 54, 245301 (2021).

    Article  ADS  MathSciNet  Google Scholar 

  198. Sharma, K., Cerezo, M., Cincio, L. & Coles, P. J. Trainability of dissipative perceptron-based quantum neural networks. Preprint at https://arxiv.org/abs/2005.12458 (2020).

  199. Marrero, C. O., Kieferová, M. & Wiebe, N. Entanglement induced barren plateaus. Preprint at https://arxiv.org/abs/2010.15968 (2020).

  200. Wang, S. et al. Noise-induced barren plateaus in variational quantum algorithms. Preprint at https://arxiv.org/abs/2007.14384 (2020).

  201. Franca, D. S. & Garcia-Patron, R. Limitations of optimization algorithms on noisy quantum devices. Preprint at https://arxiv.org/abs/2009.05532 (2020).

  202. Zhou, L., Wang, S.-T., Choi, S., Pichler, H. & Lukin, M. D. Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. Phys. Rev. X 10, 021067 (2020).

    Google Scholar 

  203. Grant, E., Wossnig, L., Ostaszewski, M. & Benedetti, M. An initialization strategy for addressing barren plateaus in parameterized quantum circuits. Quantum 3, 214 (2019).

    Article  Google Scholar 

  204. Volkoff, T. & Coles, P. J. Large gradients via correlation in random parameterized quantum circuits. Quantum Sci. Technol. 6, 025008 (2021).

    Article  ADS  Google Scholar 

  205. Skolik, A., McClean, J. R., Mohseni, M., van der Smagt, P. & Leib, M. Layerwise learning for quantum neural networks. Preprint at https://arxiv.org/abs/2006.14904 (2020).

  206. Campos, E., Nasrallah, A. & Biamonte, J. Abrupt transitions in variational quantum circuit training. Phys. Rev. A 103, 032607 (2021).

    Article  ADS  MathSciNet  Google Scholar 

  207. Verdon, G. et al. Learning to learn with quantum neural networks via classical neural networks. Preprint at https://arxiv.org/abs/1907.05415 (2019).

  208. Anand, A., Degroote, M. & Aspuru-Guzik, A. Natural evolutionary strategies for variational quantum computation. Preprint at https://arxiv.org/abs/2012.00101 (2020).

  209. Cai, Z. Resource estimation for quantum variational simulations of the hubbard model. Phys. Rev. Appl. 14, 014059 (2020).

    Article  ADS  Google Scholar 

  210. Cade, C., Mineh, L., Montanaro, A. & Stanisic, S. Strategies for solving the Fermi–Hubbard model on near-term quantum computers. Phys. Rev. B 102, 235122 (2020).

    Article  ADS  Google Scholar 

  211. Jena, A., Genin, S. & Mosca, M. Pauli partitioning with respect to gate sets. Preprint at https://arxiv.org/abs/1907.07859 (2019).

  212. Crawford, O. et al. Efficient quantum measurement of Pauli operators in the presence of finite sampling error. Quantum 5, 385 (2021).

    Article  Google Scholar 

  213. Verteletskyi, V., Yen, T.-C. & Izmaylov, A. F. Measurement optimization in the variational quantum eigensolver using a minimum clique cover. J. Chem. Phys. 152, 124114 (2020).

    Article  ADS  Google Scholar 

  214. Izmaylov, A. F., Yen, T.-C., Lang, R. A. & Verteletskyi, V. Unitary partitioning approach to the measurement problem in the variational quantum eigensolver method. J. Chem. Theory Comput. 16, 190–195 (2019).

    Article  Google Scholar 

  215. Zhao, A. et al. Measurement reduction in variational quantum algorithms. Phys. Rev. A 101, 062322 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  216. Yen, T.-C., Verteletskyi, V. & Izmaylov, A. F. Measuring all compatible operators in one series of single-qubit measurements using unitary transformations. J. Chem. Theory Comput. 16, 2400–2409 (2020).

    Article  Google Scholar 

  217. Gokhale, P. & Chong, F. T. o(n3) measurement cost for variational quantum eigensolver on molecular Hamiltonians. Preprint at https://arxiv.org/abs/1908.11857 (2019).

  218. McClean, J. R., Romero, J., Babbush, R. & Aspuru-Guzik, A. The theory of variational hybrid quantum–classical algorithms. New J. Phys. 18, 023023 (2016).

    Article  ADS  MATH  Google Scholar 

  219. Huggins, W. J. et al. Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers. NPJ Quantum Inf. 7, 1–9 (2021).

    Article  Google Scholar 

  220. Rubin, N. C., Babbush, R. & McClean, J. Application of fermionic marginal constraints to hybrid quantum algorithms. New J. Phys. 20, 053020 (2018).

    Article  ADS  MathSciNet  Google Scholar 

  221. Arrasmith, A., Cincio, L., Somma, R. D. & Coles, P. J. Operator sampling for shot-frugal optimization in variational algorithms. Preprint at https://arxiv.org/abs/2004.06252 (2020).

  222. van Straaten, B. & Koczor, B. Measurement cost of metric-aware variational quantum algorithms. Preprint at https://arxiv.org/abs/2005.05172 (2020).

  223. Huang, H.-Y., Kueng, R. & Preskill, J. Predicting many properties of a quantum system from very few measurements. Nat. Phys. 16, 1050–1057 (2020).

    Article  Google Scholar 

  224. Hadfield, C., Bravyi, S., Raymond, R. & Mezzacapo, A. Measurements of quantum Hamiltonians with locally-biased classical shadows. Preprint at https://arxiv.org/abs/2006.15788 (2020).

  225. Torlai, G., Mazzola, G., Carleo, G. & Mezzacapo, A. Precise measurement of quantum observables with neural-network estimators. Phys. Rev. Res. 2, 022060 (2020).

    Article  Google Scholar 

  226. Endo, S., Cai, Z., Benjamin, S. C. & Yuan, X. Hybrid quantum–classical algorithms and quantum error mitigation. J. Phys. Soc. Japan 90, 032001 (2021).

    Article  ADS  Google Scholar 

  227. Temme, K., Bravyi, S. & Gambetta, J. M. Error mitigation for short-depth quantum circuits. Phys. Rev. Lett. 119, 180509 (2017).

    Article  ADS  MathSciNet  Google Scholar 

  228. Kandala, A. et al. Error mitigation extends the computational reach of a noisy quantum processor. Nature 567, 491–495 (2019).

    Article  ADS  Google Scholar 

  229. Endo, S., Benjamin, S. C. & Li, Y. Practical quantum error mitigation for near-future applications. Phys. Rev. X 8, 031027 (2018).

    Google Scholar 

  230. Cai, Z. Multi-exponential error extrapolation and combining error mitigation techniques for nisq applications. Preprint at https://arxiv.org/abs/2007.01265 (2020).

  231. Otten, M. & Gray, S. K. Recovering noise-free quantum observables. Phys. Rev. A 99, 012338 (2019).

    Article  ADS  Google Scholar 

  232. Endo, S., Zhao, Q., Li, Y., Benjamin, S. & Yuan, X. Mitigating algorithmic errors in a Hamiltonian simulation. Phys. Rev. A 99, 012334 (2019).

    Article  ADS  Google Scholar 

  233. Sun, J. et al. Mitigating realistic noise in practical noisy intermediate-scale quantum devices. Phys. Rev. Appl. 15, 034026 (2021).

    Article  ADS  Google Scholar 

  234. Strikis, A., Qin, D., Chen, Y., Benjamin, S. C. & Li, Y. Learning-based quantum error mitigation. Preprint at https://arxiv.org/abs/2005.07601 (2020).

  235. Czarnik, P., Arrasmith, A., Coles, P. J. & Cincio, L. Error mitigation with Clifford quantum-circuit data. Preprint at https://arxiv.org/abs/2005.10189 (2020).

  236. Lowe, A. et al. Unified approach to data-driven quantum error mitigation. Preprint at https://arxiv.org/abs/2011.01157 (2020).

  237. McArdle, S., Yuan, X. & Benjamin, S. Error-mitigated digital quantum simulation. Phys. Rev. Lett. 122, 180501 (2019).

    Article  ADS  Google Scholar 

  238. Bonet-Monroig, X., Sagastizabal, R., Singh, M. & O’Brien, T. Low-cost error mitigation by symmetry verification. Phys. Rev. A 98, 062339 (2018).

    Article  ADS  Google Scholar 

  239. McClean, J. R., Jiang, Z., Rubin, N. C., Babbush, R. & Neven, H. Decoding quantum errors with subspace expansions. Nat. Commun. 11, 636 (2020).

    Article  ADS  Google Scholar 

  240. Koczor, B. Exponential error suppression for near-term quantum devices. Preprint at https://arxiv.org/abs/2011.05942 (2020).

  241. Huggins, W. J. et al. Virtual distillation for quantum error mitigation. Preprint at https://arxiv.org/abs/2011.07064 (2020).

  242. Bravyi, S., Sheldon, S., Kandala, A., Mckay, D. C. & Gambetta, J. M. Mitigating measurement errors in multi-qubit experiments. Phys. Rev. A 103, 042605 (2021).

    Article  ADS  Google Scholar 

  243. Su, D. et al. Error mitigation on a near-term quantum photonic device. Quantum 5, 452 (2021).

    Article  Google Scholar 

  244. Gentini, L., Cuccoli, A., Pirandola, S., Verrucchi, P. & Banchi, L. Noise-resilient variational hybrid quantum–classical optimization. Phys. Rev. A 102, 052414 (2020).

    Article  ADS  MathSciNet  Google Scholar 

  245. Fontana, E., Cerezo, M., Arrasmith, A., Rungger, I. & Coles, P. J. Optimizing parameterized quantum circuits via noise-induced breaking of symmetries. Preprint at https://arxiv.org/abs/2011.08763 (2020).

  246. Xue, C., Chen, Z.-Y., Wu, Y.-C. & Guo, G.-P. Effects of quantum noise on quantum approximate optimization algorithm. Preprint at https://arxiv.org/abs/1909.02196 (2019).

  247. Marshall, J., Wudarski, F., Hadfield, S. & Hogg, T. Characterizing local noise in QAOA circuits. IOP SciNotes 1, 025208 (2020).

    Article  ADS  Google Scholar 

  248. Kim, I. H. Noise-resilient preparation of quantum many-body ground states. Preprint at https://arxiv.org/abs/1703.00032 (2017).

  249. Broughton, M. et al. Tensorflow quantum: a software framework for quantum machine learning. Preprint at https://arxiv.org/abs/2003.02989 (2020).

  250. Luo, X.-Z., Liu, J.-G., Zhang, P. & Wang, L. Yao. jl: Extensible, efficient framework for quantum algorithm design. Quantum 4, 341 (2020).

    Article  Google Scholar 

  251. Sanders, Y. R. et al. Compilation of fault-tolerant quantum heuristics for combinatorial optimization. Phys. Rev. X Quantum 1, 020312 (2020).

    Google Scholar 

Download references

Acknowledgements

M.C. thanks K. Sharma for discussions. M.C. was initially supported by the Laboratory Directed Research and Development (LDRD) programme of Los Alamos National Laboratory (LANL) under project no. 20180628ECR, and later supported by the Center for Nonlinear Studies at LANL. A.A. was initially supported by the LDRD programme of LANL under project no. 20200056DR, and later supported by the US Department of Energy (DOE), Office of Science, Office of High Energy Physics QuantISED programme under contract nos. DE-AC52-06NA25396 and KA2401032. S.C.B. acknowledges financial support from EPSRC Hub grants under the agreement nos. EP/M013243/1 and EP/T001062/1, and from EU H2020-FETFLAG-03-2018 under the grant agreement no. 820495 (AQTION). S.E. was supported by MEXT Quantum Leap Flagship Program (MEXT QLEAP) grant nos. JPMXS0120319794, JPMXS0118068682 and JST ERATO grant no. JPMJER1601. K.F. was supported by Japan Society for the Promotion of Science (JSPS) KAKENHI grant no. 16H02211, JST ERATO JPMJER1601 and JST CREST JPMJCR1673. K.M. was supported by JST PRESTO grant no. JPMJPR2019 and JSPS KAKENHI grant no. 20K22330. K.M. and K.F. were also supported by MEXT QLEAP grant no. JPMXS0118067394 and JPMXS0120319794. X.Y. acknowledges support from the Simons Foundation. L.C. was initially supported by the LDRD programme of LANL under project no. 20190065DR, and later supported by the US DOE, Office of Science, Office of Advanced Scientific Computing Research under the Quantum Computing Application Teams (QCAT) programme. P.J.C. was initially supported by the LANL ASC Beyond Moore’s Law project, and later supported by the US DOE, Office of Science, Office of Advanced Scientific Computing Research, under the Accelerated Research in Quantum Computing (ARQC) programme. Most recently, M.C., L.C. and P.J.C. were supported by the Quantum Science Center (QSC), a National Quantum Information Science Research Center of the US DOE.

Author information

Authors and Affiliations

  1. Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM, USA

    M. Cerezo, Andrew Arrasmith, Lukasz Cincio & Patrick J. Coles

  2. Center for Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, NM, USA

    M. Cerezo

  3. Quantum Science Center, Oak Ridge, TN, USA

    M. Cerezo, Andrew Arrasmith, Lukasz Cincio & Patrick J. Coles

  4. Google Quantum AI Team, Venice, CA, USA

    Ryan Babbush & Jarrod R. McClean

  5. Department of Materials, University of Oxford, Oxford, UK

    Simon C. Benjamin

  6. NTT Secure Platform Laboratories, NTT Corporation, Tokyo, Japan

    Suguru Endo

  7. Graduate School of Engineering Science, Osaka University, Osaka, Japan

    Keisuke Fujii & Kosuke Mitarai

  8. Center for Quantum Information and Quantum Biology, Institute for Open and Transdisciplinary Research Initiatives, Osaka University, Osaka, Japan

    Keisuke Fujii & Kosuke Mitarai

  9. Center for Emergent Matter Science, RIKEN, Saitama, Japan

    Keisuke Fujii

  10. JST, PRESTO, Saitama, Japan

    Kosuke Mitarai

  11. Center on Frontiers of Computing Studies, Department of Computer Science, Peking University, Beijing, China

    Xiao Yuan

  12. Stanford Institute for Theoretical Physics, Stanford University, Stanford, CA, USA

    Xiao Yuan

Authors
  1. M. Cerezo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Arrasmith
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ryan Babbush
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Simon C. Benjamin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Suguru Endo
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Keisuke Fujii
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Jarrod R. McClean
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Kosuke Mitarai
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Xiao Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  10. Lukasz Cincio
    View author publications

    You can also search for this author in PubMed Google Scholar

  11. Patrick J. Coles
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors have read, discussed and contributed to the writing of the manuscript.

Corresponding authors

Correspondence to M. Cerezo or Patrick J. Coles.

Ethics declarations

Competing interests

The authors declare no competing interests.

Additional information

Peer review information

Nature Reviews Physics thanks Lei Wang and the other, anonymous, reviewer(s) for their contribution to the peer review of this work.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary information

Glossary

Circuit depth

An integer number that counts the maximum length in the circuit between the input and the output. This length is usually defined in terms of layers of gates acting in parallel.

Ancilla qubits

Auxiliary qubits used during a quantum computation.

Trotterized adiabatic transformation

A quantum adiabatic transformation involves changing a system’s Hamiltonian slowly enough that the system remains in the ground state. Trotterization approximates this evolution with a series of discrete steps.

Pauli strings

A Pauli string acting on n qubits is defined as a Hermitian operator from the set {1,X,Y,Z}⊗n, where X,Y,Z are Pauli operators, and 1 is the identity on a single qubit.

Trotter

A mathematical method used to approximate the matrix etH, which describes the evolution for a time t under a Hamiltonian H as \({e}^{tH}\sim {({e}^{\frac{tH}{n}})}^{n}\). The Trotter error is the error induced from the Trotter method approximation.

Quantum optimal control

Quantum optimal control is a theoretical framework that provides tools for the systematic manipulation of quantum dynamical systems.

Rayleigh–Ritz variational principle

Principle stating that the lowest eigenvalue of a Hermitian operator H is upper-bounded by the minimum expectation value 〈ψ∣H∣ψ〉 found by varying the state \(| \psi \rangle \).

Hadamard test

Method used to estimate the real and complex part of the expectation value of a unitary operator over a quantum state.

Max-Cut

The Max-Cut problem aims to find the maximum cut of a graph, that is, the partitioning of a graph’s vertices that cuts through the most edges.

Schur concavity

A Schur concave function f is a funtion \(f:{{\mathbb{R}}}^{d}\to {\mathbb{R}}\) that for all x and y in \({{\mathbb{R}}}^{d}\) is such that if x is majorized by y, then f(x) ≥ f(y).

Unitary 2-design

Ensemble of unitaries, such that sampling over their distribution yields the same properties as sampling random unitaries from the Haar distribution measure up to the first two moments.

Born machines

Generative models that represent the probability distribution of classical dataset as quantum pure states.

Restricted Boltzmann machine

Generative computational model that can learn a probability distribution over its set of inputs.

Quantum Fisher information

The quantum Fisher information quantifies the sensitivity of a quantum state to a parameter or a set of parameters.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cerezo, M., Arrasmith, A., Babbush, R. et al. Variational quantum algorithms. Nat Rev Phys 3, 625–644 (2021). https://doi.org/10.1038/s42254-021-00348-9

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/s42254-021-00348-9

This article is cited by

Search

Advanced search

Quick links

Nature Briefing AI and Robotics

Sign up for the Nature Briefing: AI and Robotics newsletter — what matters in AI and robotics research, free to your inbox weekly.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing: AI and Robotics