- Physical Review Journals
All JournalsPhysics Magazine

PRX Quantum

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

Minimizing Estimation Runtime on Noisy Quantum Computers

Guoming Wang*, Dax Enshan Koh†, Peter D. Johnson‡, and Yudong Cao§

  • Zapata Computing Inc., 100 Federal Street, Boston, Massachusetts 02110, USA

  • *Current address: 325 Front Street West, Suite 300, Toronto, ON M5V 2Y1, Canada. guoming.wang@zapatacomputing.com
  • †Current address: Institute of High Performance Computing, Agency for Science, Technology and Research (A*STAR), 1 Fusionopolis Way, #16-16 Connexis, Singapore 138632, Singapore. dax_koh@ihpc.a-star.edu.sg
  • ‡peter@zapatacomputing.com
  • §yudong@zapatacomputing.com
PDF

PRX Quantum 2, 010346 – Published 19 March, 2021

DOI: https://doi.org/10.1103/PRXQuantum.2.010346

Abstract

The number of measurements demanded by hybrid quantum-classical algorithms such as the variational quantum eigensolver (VQE) is prohibitively high for many problems of practical value. For such problems, realizing quantum advantage will require methods that dramatically reduce this cost. Previous quantum algorithms that reduce the measurement cost (e.g., quantum amplitude and phase estimation) require error rates that are too low for near-term implementation. Here we propose methods that take advantage of the available quantum coherence to maximally enhance the power of sampling on noisy quantum devices, reducing the measurement number and runtime compared to the standard sampling method of the VQE. Our scheme derives inspiration from quantum metrology, phase estimation, and the more recent “alpha-VQE” proposal, arriving at a general formulation that is robust to error and does not require ancilla qubits. The central object of this method is what we call the “engineered likelihood function” (ELF), used for carrying out Bayesian inference. We show how the ELF formalism enhances the rate of information gain in sampling as the physical hardware transitions from the regime of noisy intermediate-scale quantum computers to that of quantum error–corrected ones. This technique speeds up a central component of many quantum algorithms, with applications including chemistry, materials, finance, and beyond. Similar to the VQE, we expect small-scale implementations to be realizable on today’s quantum devices.

View figure in article

Physics Subject Headings (PhySH)

Popular Summary

Quantum algorithms hold the promise of tackling certain computational problems dramatically faster than their classical counterparts. Many algorithms, including those that run on today’s hardware, rely on accurate statistical estimation of certain quantities. Recent studies indicate that current statistical estimation methods require an exorbitant number of samples, rendering them impractical for solving valuable problems. What methods are needed to dramatically reduce these costs in the near term? We develop a more efficient estimation scheme that is suited for imperfect quantum computers. Compared to state-of-the-art methods, this gives near-term quantum algorithms more potential to realize a quantum advantage.

In quantum estimation, measurement samples from a quantum device are used to infer the value of an unknown parameter of interest. In practice, this device is noisy, reducing the performance of previous approaches to estimation. To overcome this issue, we develop the framework of “engineered likelihood functions” in which signal processing techniques are used to boost the information gain from each measurement sample. Consequently, fewer samples are required to obtain the same performance. Moreover, we analyze how the runtimes of our methods depend on the degree of noise in the device and establish a model that can be used to determine the fidelity needed to achieve some desired quantum speedup.

Our methods accelerate a core component of near-term quantum algorithms for chemistry and combinatorial optimization, driving them towards quantum advantage. Furthermore, these methods reduce the resource costs of far-term quantum algorithms for finance and machine learning, bringing their implementation closer into the range of near-term quantum computers.

Article Text

References (71)

  1. Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nat. Commun. 5, 4213 (2014).
  2. Dave Wecker, Matthew B. Hastings, and Matthias Troyer, Progress towards practical quantum variational algorithms, Phys. Rev. A 92, 042303 (2015).
  3. Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik, The theory of variational hybrid quantum-classical algorithms, New J. Phys. 18, 023023 (2016).
  4. Jonathan Romero, Ryan Babbush, Jarrod R. McClean, Cornelius Hempel, Peter J. Love, and Alán Aspuru-Guzik, Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz, Quantum Sci. Technol. 4, 014008 (2018).
  5. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028 (2014).
  6. Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor Rieffel, Davide Venturelli, and Rupak Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12, 34 (2019).
  7. Carlos Bravo-Prieto, Ryan LaRose, Marco Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles, Variational quantum linear solver, arXiv:1909.05820 (2019).
  8. Dong An and Lin Lin, Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm, arXiv:1909.05500 (2019).
  9. Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan, Variational algorithms for linear algebra, arXiv:1909.03898 (2019).
  10. Ying Li and Simon C. Benjamin, Efficient Variational Quantum Simulator Incorporating Active Error Minimization, Phys. Rev. X 7, 021050 (2017).
  11. Jonathan Romero, Jonathan P. Olson, and Alan Aspuru-Guzik, Quantum autoencoders for efficient compression of quantum data, Quantum Sci. Technol. 2, 045001 (2017).
  12. Maria Schuld and Nathan Killoran, Quantum Machine Learning in Feature Hilbert Spaces, Phys. Rev. Lett. 122, 040504 (2019).
  13. D. Zhu, N. M. Linke, M. Benedetti, K. A. Landsman, N. H. Nguyen, C. H. Alderete, A. Perdomo-Ortiz, N. Korda, A. Garfoot, C. Brecque, L. Egan, O. Perdomo, and C. Monroe, Training of quantum circuits on a hybrid quantum computer, Sci. Adv. 5, eaaw9918 (2019).
  14. William J. Huggins, Jarrod McClean, Nicholas Rubin, Zhang Jiang, Nathan Wiebe, K. Birgitta Whaley, and Ryan Babbush, Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers, arXiv:1907.13117 (2019).
  15. Jerome F. Gonthier, Maxwell D. Radin, Corneliu Buda, Eric J. Doskocil, Clena M. Abuan, and Jhonathan Romero, Identifying challenges towards practical quantum advantage through resource estimation: The measurement roadblock in the variational quantum eigensolver, arXiv:2012.04001 (2020).
  16. Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven, Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity, Phys. Rev. X 8, 041015 (2018).
  17. Ashley Montanaro, Quantum speedup of monte carlo methods, Proc. R. Soc. A: Math., Phys. Eng. Sci. 471, 20150301 (2015).
  18. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, Quantum Algorithm for Linear Systems of Equations, Phys. Rev. Lett. 103, 150502 (2009).
  19. B. D. Clader, B. C. Jacobs, and C. R. Sprouse, Preconditioned Quantum Linear System Algorithm, Phys. Rev. Lett. 110, 250504 (2013).
  20. Daochen Wang, Oscar Higgott, and Stephen Brierley, Accelerated Variational Quantum Eigensolver, Phys. Rev. Lett. 122, 140504 (2019).
  21. Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma, Optimal quantum measurements of expectation values of observables, Phys. Rev. A 75, 012328 (2007).
  22. Alexandr Sergeevich, Anushya Chandran, Joshua Combes, Stephen D. Bartlett, and Howard M. Wiseman, Characterization of a qubit Hamiltonian using adaptive measurements in a fixed basis, Phys. Rev. A 84, 052315 (2011).
  23. Christopher Ferrie, Christopher E. Granade, and D. G. Cory, How to best sample a periodic probability distribution, or on the accuracy of Hamiltonian finding strategies, Quantum Inf. Process. 12, 611 (2012).
  24. Krysta M. Svore, Matthew B. Hastings, and Michael Freedman, Faster phase estimation, Quantum Inf. Comput. 14, 306 (2013).
  25. Nathan Wiebe and Chris Granade, Efficient Bayesian Phase Estimation, Phys. Rev. Lett. 117, 010503 (2016).
  26. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemp. Math. 305, 53 (2002).
  27. V. Giovannetti, Quantum-enhanced measurements: Beating the standard quantum limit, Science 306, 1330 (2004).
  28. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, Advances in quantum metrology, Nat. Photonics 5, 222 (2011).
  29. Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang, Fixed-Point Quantum Search with an Optimal Number of Queries, Phys. Rev. Lett. 113, 210501 (2014).
  30. Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang, Methodology of Resonant Equiangular Composite Quantum Gates, Phys. Rev. X 6, 041067 (2016).
  31. Guang Hao Low and Isaac L. Chuang, Hamiltonian simulation by qubitization, Quantum 3, 163 (2019).
  32. Guang Hao Low and Isaac L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing, Phys. Rev. Lett. 118, 010501 (2017).
  33. Thomas E. O’Brien, Brian Tarasinski, and Barbara M. Terhal, Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments, New J. Phys. 21, 023022 (2019).
  34. A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem, quant-ph/9511026 (1995).
  35. Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel, Quantum approximate optimization algorithm for maxCut: A fermionic view, Phys. Rev. A 97, 022304 (2018).
  36. Z. Ji, G. Wang, R. Duan, Y. Feng, and M. Ying, Parameter estimation of quantum channels, IEEE Trans. Inf. Theory 54, 5172 (2008).
  37. Ilia Zintchenko and Nathan Wiebe, Randomized gap and amplitude estimation, Phys. Rev. A 93, 062306 (2016).
  38. Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Yamamoto, Amplitude estimation without phase estimation, Quantum Inf. Process. 19, 75 (2020).
  39. Joel J. Wallman and Joseph Emerson, Noise tailoring for scalable quantum computation via randomized compiling, Phys. Rev. A 94, 052325 (2016).
  40. Gilles Brassard, Peter Høyer, and Alain Tapp, in International Colloquium on Automata, Languages, and Programming (Springer, 1998), p. 820.
  41. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, Quantum Metrology, Phys. Rev. Lett. 96, 010401 (2006).
  42. Jonas M. Kübler, Andrew Arrasmith, Lukasz Cincio, and Patrick J. Coles, An adaptive optimizer for measurement-frugal variational algorithms, Quantum 4, 263 (2020).
  43. Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K. Faehrmann, Barthélémy Meynard-Piganeau, and Jens Eisert, Stochastic gradient descent for hybrid quantum-classical optimization, Quantum 4, 314 (2020).
  44. Andrew Arrasmith, Lukasz Cincio, Rolando D. Somma, and Patrick J. Coles, Operator sampling for shot-frugal optimization in variational algorithms, arXiv:2004.06252 (2020).
  45. Kevin J. Sung, Jiahao Yao, Matthew P. Harrigan, Nicholas C. Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, and Jarrod R. McClean, Using models to improve optimizers for variational quantum algorithms, Quantum Sci. Technol. 5, 044008 (2020).
  46. Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).
  47. We call this scheme “ancilla-free” since it does not involve any ancilla qubits. In Appendix pp4, we consider a different scheme named the “ancilla-based” scheme that involves one ancilla qubit.
  48. To ensure that S is two dimensional, we assume that Π≠±1, i.e., θ≠0 or π.
  49. In practice, the establishment of the noise model requires a procedure for calibrating the likelihood function for the specific device being used. With respect to Bayesian inference, the parameters of this model are known as nuisance parameters [70, 71]; the target parameter does not depend directly on them, but they determine how the data relate to the target parameter and, hence, should be incorporated into the inference process. We explore likelihood function calibration in future work. For the remainder of this article, we assume that the noise model has been calibrated to sufficient precision so as to render the effect of model error negligible. In Sec. 7 we touch upon the relationship between model error and estimation error.
  50. Eric G. Brown, Oktay Goktas, and W. K. Tham, Quantum amplitude estimation in the presence of noise, arXiv:2006.14145 (2020).
  51. Shumpei Uno, Yohichi Suzuki, Keigo Hisanaga, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Yamamoto, Modified Grover operator for amplitude estimation, arXiv:2010.11656 (2020).
  52. Tomoki Tanaka, Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tamiya Onodera, and Naoki Yamamoto, Amplitude estimation via maximum likelihood on noisy quantum computer, arXiv:2006.16223 (2020).
  53. Google Quantum AI, Accurately computing electronic properties of materials using eigenenergies, arXiv:2012.00921 (2020).
  54. Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  55. Dax Enshan Koh, Guoming Wang, Peter D. Johnson, and Yudong Cao, A framework for engineering quantum likelihood functions for expectation estimation, arXiv:2006.09349 (2020).
  56. Christopher E. Granade, Christopher Ferrie, Nathan Wiebe, and David G. Cory, Robust online Hamiltonian learning, New J. Phys. 14, 103013 (2012).
  57. Although we can compute the mean and variance of the posterior distribution p(θ|d;f,x→) directly by definition, this approach is time consuming, as it involves numerical integration. Instead, we accelerate this process by taking advantage of certain properties of engineered likelihood functions. See Sec. 4b for more details.
  58. In the simplest case, δ(t)=δ is constant. But in order to achieve better performance, we might want δ(t)→0 as t→∞.
  59. Since Algorithms 1 and 2 only output a local maximum point of I(θ;f,x→) for given θ and f, we need to run them multiple times with random initial points to find a global maximum point of the same function. We find that this does not require many trials. For example, for L≤6, a global-optimal solution can be found in ten trials with high probability. Similar statements hold for the other algorithms for parameter tuning in this paper.
  60. Though not shown in Fig. 13, the R^0 factors of the AB ELF and AF ELF actually diverge to +∞ as Π→±1, and this is true for any L∈Z+.
  61. More precisely, the slopes of the AB ELF and AF ELF scale linearly in the number L of circuit layers.
  62. For the Chebyshev likelihood functions, we can express the variance reduction factor as V[μ,σ;f,(π/2)⊕2L]=mL2/[1+(f−2emL2σ2−1)csc2(mLμ)] whenever sin(mLμ)≠0. Then, csc2(mLμ)≥1 implies that V[μ,σ;f,(π/2)⊕2L]≤f2mL2e−mL2σ2. Here (π/2)⊕2L=(π/2,π/2,…,π/2)∈R2L.
  63. We search over a uniform grid of 50 000 values of θ, L values from L∗/3 to 3L∗, where L∗ is to the optimized value used to arrive at Eq. (59), and σ and λ ranging over 10−1,10−2,…,10−5. For each (σ,λ) pair, we find the θ for which the maximum inverse variance rate (over L) is a minimum. For all (σ,λ) pairs checked, this worst-case rate is always between 0.4 and 0.5, with the smallest value found being R=0.41700368≥(e−1)2/e2.
  64. Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F. Izmaylov, Measurement optimization in the variational quantum eigensolver using a minimum clique cover, J. Chem. Phys. 152, 124114 (2020).
  65. Artur F. Izmaylov, Tzu-Ching Yen, Robert A. Lang, and Vladyslav Verteletskyi, Unitary partitioning approach to the measurement problem in the variational quantum eigensolver method, J. Chem. Theory Comput. 16, 190 (2020).
  66. Ophelia Crawford, Barnaby van Straaten, Daochen Wang, Thomas Parks, Earl Campbell, and Stephen Brierley, Efficient quantum measurement of Pauli operators in the presence of finite sampling error, Quantum 5, 385 (2021).
  67. Andrew Zhao, Andrew Tranter, William M. Kirby, Shu Fay Ung, Akimasa Miyake, and Peter J. Love, Measurement reduction in variational quantum algorithms, Phys. Rev. A 101, 062322 (2020).
  68. Ian Hincks, Joel J. Wallman, Chris Ferrie, Chris Granade, and David G. Cory, Bayesian inference for randomized benchmarking protocols, arXiv:1802.00401 (2018).
  69. J. M. Gambetta, A. D. Córcoles, S. T. Merkel, B. R. Johnson, J. A. Smolin, J. M. Chow, C. A. Ryan, C. Rigetti, S. Poletto, T. A. Ohki, M. B. Ketchen, and M. Steffen, Characterization of Addressability by Simultaneous Randomized Benchmarking, Phys. Rev. Lett. 109, 240504 (2012).
  70. Edwin T. Jaynes, Probability Theory: The Logic of Science (Cambridge University Press, Cambridge, 2003).
  71. Richard Royall, On the probability of observing misleading statistical evidence, J. Am. Stat. Assoc. 95, 760 (2000).

Outline

Information

PRX Quantum 2, 010346– Published 19 March, 2021
  • Received 6 July 2020
  • Revised 14 December 2020
  • Accepted 18 February 2021
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