Variational quantum amplitude estimation

Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini, and Michael Lubasch

Cambridge Quantum Computing Limited, SW1P 1BX London, United Kingdom

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We propose to perform amplitude estimation with the help of constant-depth quantum circuits that variationally approximate states during amplitude amplification. In the context of Monte Carlo (MC) integration, we numerically show that shallow circuits can accurately approximate many amplitude amplification steps. We combine the variational approach with maximum likelihood amplitude estimation [Y. Suzuki et al., Quantum Inf. Process. 19, 75 (2020)] in variational quantum amplitude estimation (VQAE). VQAE typically has larger computational requirements than classical MC sampling. To reduce the variational cost, we propose adaptive VQAE and numerically show in 6 to 12 qubit simulations that it can outperform classical MC sampling.

Amplitude estimation is an important quantum algorithm that has a wide range of applications. However, running it on current quantum computers is challenging. In our work, we explore the possibility of realizing amplitude estimation with constant-depth quantum circuits by making use of variational quantum algorithms. To benchmark our algorithms, we consider mean calculations of shifted and univariate Gaussian, Cauchy-Lorentz and log-normal probability distributions. We find that an adaptive implementation of the algorithms significantly reduces the variational cost and can be more efficient than classical Monte Carlo sampling. These results pave the way for the efficient realization of amplitude estimation on current gate-based quantum devices.

► BibTeX data

► References

[1] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemp. Math., 305: 53–74, 2002. 10.1090/​conm/​305.
https:/​/​doi.org/​10.1090/​conm/​305

[2] Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proc. Math. Phys. Eng. Sci., 471 (2181), 2015. 10.1098/​rspa.2015.0301.
https:/​/​doi.org/​10.1098/​rspa.2015.0301

[3] Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma. Optimal quantum measurements of expectation values of observables. Phys. Rev. A, 75: 012328, Jan 2007. 10.1103/​PhysRevA.75.012328.
https:/​/​doi.org/​10.1103/​PhysRevA.75.012328

[4] Ivan Kassal, Stephen P Jordan, Peter J Love, Masoud Mohseni, and Alán Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proc. Natl. Acad. Sci. USA, 105 (48): 18681–18686, 2008. 10.1073/​pnas.0808245105.
https:/​/​doi.org/​10.1073/​pnas.0808245105

[5] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning. Quantum Info. Comput., 15 (3-4): 316–356, mar 2015. ISSN 1533-7146. URL https:/​/​dl.acm.org/​doi/​10.5555/​2871393.2871400.
https:/​/​dl.acm.org/​doi/​10.5555/​2871393.2871400

[6] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum Deep Learning. Quantum Info. Comput., 16 (7-8): 541–587, may 2016. ISSN 1533-7146. URL https:/​/​dl.acm.org/​doi/​10.5555/​3179466.3179467.
https:/​/​dl.acm.org/​doi/​10.5555/​3179466.3179467

[7] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. Adv. Neural Inf. Process. Syst., 32, 2019. URL https:/​/​proceedings.neurips.cc/​paper/​2019/​file/​16026d60ff9b54410b3435b403afd226-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2019/​file/​16026d60ff9b54410b3435b403afd226-Paper.pdf

[8] Román Orús, Samuel Mugel, and Enrique Lizaso. Quantum computing for finance: Overview and prospects. Rev. Phys., 4: 100028, 2019. ISSN 2405-4283. 10.1016/​j.revip.2019.100028.
https:/​/​doi.org/​10.1016/​j.revip.2019.100028

[9] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain. Quantum Computing for Finance: State-of-the-Art and Future Prospects. IEEE Trans. Quantum Eng., 1: 1–24, 2020. 10.1109/​TQE.2020.3030314.
https:/​/​doi.org/​10.1109/​TQE.2020.3030314

[10] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash. Prospects and challenges of quantum finance. arXiv:2011.06492, 2020. 10.48550/​arXiv.2011.06492.
https:/​/​doi.org/​10.48550/​arXiv.2011.06492
arXiv:2011.06492

[11] Stefan Woerner and Daniel J. Egger. Quantum risk analysis. npj Quantum Inf., 5: 15, February 2019. 10.1038/​s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[12] M. C. Braun, T. Decker, N. Hegemann, S. F. Kerstan, and C. Schäfer. A Quantum Algorithm for the Sensitivity Analysis of Business Risks. arXiv:2103.05475, March 2021. 10.48550/​arXiv.2103.05475.
https:/​/​doi.org/​10.48550/​arXiv.2103.05475
arXiv:2103.05475

[13] Patrick Rebentrost, Brajesh Gupt, and Thomas R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A, 98: 022321, Aug 2018. 10.1103/​PhysRevA.98.022321.
https:/​/​doi.org/​10.1103/​PhysRevA.98.022321

[14] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen, and Stefan Woerner. Option Pricing using Quantum Computers. Quantum, 4: 291, July 2020. ISSN 2521-327X. 10.22331/​q-2020-07-06-291.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

[15] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, and Naoki Yamamoto. Amplitude estimation without phase estimation. Quantum Inf. Process., 19 (2): 75, January 2020. 10.1007/​s11128-019-2565-2.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

[16] Tomoki Tanaka, Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tamiya Onodera, and Naoki Yamamoto. Amplitude estimation via maximum likelihood on noisy quantum computer. Quantum Inf. Process., 20 (9): 293, Sep 2021. ISSN 1573-1332. 10.1007/​s11128-021-03215-9.
https:/​/​doi.org/​10.1007/​s11128-021-03215-9

[17] Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Symposium on Simplicity in Algorithms, pages 24–32. SIAM, 2020. 10.1137/​1.9781611976014.5.
https:/​/​doi.org/​10.1137/​1.9781611976014.5

[18] Dmitry Grinko, Julien Gacon, Christa Zoufal, and Stefan Woerner. Iterative quantum amplitude estimation. npj Quantum Inf., 7 (1): 1–6, 2021. 10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[19] Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng. Low depth algorithms for quantum amplitude estimation. arXiv:2012.03348, December 2020. URL https:/​/​arxiv.org/​abs/​2012.03348.
arXiv:2012.03348

[20] Steven Herbert. Quantum Monte-Carlo Integration: The Full Advantage in Minimal Circuit Depth. arXiv:2105.09100, May 2021. 10.48550/​arXiv.2105.09100.
https:/​/​doi.org/​10.48550/​arXiv.2105.09100
arXiv:2105.09100

[21] Guoming Wang, Dax Enshan Koh, Peter D. Johnson, and Yudong Cao. Minimizing Estimation Runtime on Noisy Quantum Computers. PRX Quantum, 2: 010346, Mar 2021. 10.1103/​PRXQuantum.2.010346.
https:/​/​doi.org/​10.1103/​PRXQuantum.2.010346

[22] Amara Katabarwa, Alex Kunitsa, Borja Peropadre, and Peter Johnson. Reducing runtime and error in VQE using deeper and noisier quantum circuits. arXiv:2110.10664, 2021. 10.48550/​arXiv.2110.10664.
https:/​/​doi.org/​10.48550/​arXiv.2110.10664
arXiv:2110.10664

[23] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Sci. Technol., 4 (4): 043001, nov 2019. 10.1088/​2058-9565/​ab4eb5.
https:/​/​doi.org/​10.1088/​2058-9565/​ab4eb5

[24] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nat. Rev. Phys., 3 (9): 625–644, Sep 2021a. ISSN 2522-5820. 10.1038/​s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[25] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. Noisy intermediate-scale quantum algorithms. Rev. Mod. Phys., 94 (1), Feb 2022. ISSN 1539-0756. 10.1103/​RevModPhys.94.015004.
https:/​/​doi.org/​10.1103/​RevModPhys.94.015004

[26] Gilles Brassard and Peter Hoyer. An exact quantum polynomial-time algorithm for Simon's problem. In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 12–23. IEEE, 1997. 10.1109/​ISTCS.1997.595153.
https:/​/​doi.org/​10.1109/​ISTCS.1997.595153

[27] Lov K Grover. Quantum computers can search rapidly by using almost any transformation. Phys. Rev. Lett., 80 (19): 4329, 1998. 10.1103/​PhysRevLett.80.4329.
https:/​/​doi.org/​10.1103/​PhysRevLett.80.4329

[28] William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C. Cambridge University Press, Cambridge, USA, second edition, 1992. URL https:/​/​dl.acm.org/​doi/​10.5555/​148286.
https:/​/​dl.acm.org/​doi/​10.5555/​148286

[29] J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of ICNN'95 - International Conference on Neural Networks, volume 4, pages 1942–1948, 1995. 10.1109/​ICNN.1995.488968.
https:/​/​doi.org/​10.1109/​ICNN.1995.488968

[30] Mohammad Reza Bonyadi and Zbigniew Michalewicz. Particle Swarm Optimization for Single Objective Continuous Space Problems: A Review. Evol. Comput., 25 (1): 1–54, 03 2017. ISSN 1063-6560. 10.1162/​EVCO_r_00180.
https:/​/​doi.org/​10.1162/​EVCO_r_00180

[31] Javier Gil Vidal and Dirk Oliver Theis. Calculus on parameterized quantum circuits. arXiv:1812.06323, dec 2018. URL https:/​/​arxiv.org/​abs/​1812.06323.
arXiv:1812.06323

[32] Robert M. Parrish, Joseph T. Iosue, Asier Ozaeta, and Peter L. McMahon. A Jacobi Diagonalization and Anderson Acceleration Algorithm For Variational Quantum Algorithm Parameter Optimization. arXiv:1904.03206, 2019. 10.48550/​arXiv.1904.03206.
https:/​/​doi.org/​10.48550/​arXiv.1904.03206
arXiv:1904.03206

[33] Ken M. Nakanishi, Keisuke Fujii, and Synge Todo. Sequential minimal optimization for quantum-classical hybrid algorithms. Phys. Rev. Research, 2: 043158, Oct 2020. 10.1103/​PhysRevResearch.2.043158.
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.043158

[34] Mateusz Ostaszewski, Edward Grant, and Marcello Benedetti. Structure optimization for parameterized quantum circuits. Quantum, 5: 391, 2021. 10.22331/​q-2021-01-28-391.
https:/​/​doi.org/​10.22331/​q-2021-01-28-391

[35] Marcello Benedetti, Mattia Fiorentini, and Michael Lubasch. Hardware-efficient variational quantum algorithms for time evolution. Phys. Rev. Research, 3 (3): 033083, 2021a. 10.1103/​PhysRevResearch.3.033083.
https:/​/​doi.org/​10.1103/​PhysRevResearch.3.033083

[36] Elad Hazan, Kfir Y Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. arXiv:1507.02030, 2015. URL https:/​/​arxiv.org/​abs/​1507.02030.
arXiv:1507.02030

[37] Yudai Suzuki, Hiroshi Yano, Rudy Raymond, and Naoki Yamamoto. Normalized Gradient Descent for Variational Quantum Algorithms. arXiv:2106.10981, 2021. 10.48550/​arXiv.2106.10981.
https:/​/​doi.org/​10.48550/​arXiv.2106.10981
arXiv:2106.10981

[38] Jun Li, Xiaodong Yang, Xinhua Peng, and Chang-Pu Sun. Hybrid Quantum-Classical Approach to Quantum Optimal Control. Phys. Rev. Lett., 118 (15): 150503, April 2017. 10.1103/​PhysRevLett.118.150503.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.150503

[39] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Phys. Rev. A, 98 (3): 032309, September 2018. 10.1103/​PhysRevA.98.032309.
https:/​/​doi.org/​10.1103/​PhysRevA.98.032309

[40] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Phys. Rev. A, 99 (3): 032331, mar 2019. 10.1103/​PhysRevA.99.032331.
https:/​/​doi.org/​10.1103/​PhysRevA.99.032331

[41] Leonardo Banchi and Gavin E Crooks. Measuring analytic gradients of general quantum evolution with the stochastic parameter shift rule. Quantum, 5: 386, 2021. 10.22331/​q-2021-01-25-386.
https:/​/​doi.org/​10.22331/​q-2021-01-25-386

[42] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. arXiv:1412.6980, December 2014. URL https:/​/​arxiv.org/​abs/​1412.6980.
arXiv:1412.6980

[43] Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55 (3): 395–421, 2009. 10.1007/​s00453-008-9168-0.
https:/​/​doi.org/​10.1007/​s00453-008-9168-0

[44] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles. Cost function dependent barren plateaus in shallow parameterized quantum circuits. Nat. Commun., 12: 1791, 2021b. 10.1038/​s41467-021-21728-w.
https:/​/​doi.org/​10.1038/​s41467-021-21728-w

[45] David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch. Filtering variational quantum algorithms for combinatorial optimization. Quantum Sci. Technol., 7 (1): 015021, Jan 2022. ISSN 2058-9565. 10.1088/​2058-9565/​ac3e54.
https:/​/​doi.org/​10.1088/​2058-9565/​ac3e54

[46] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Quantum inference on Bayesian networks. Phys. Rev. A, 89: 062315, Jun 2014. 10.1103/​PhysRevA.89.062315.
https:/​/​doi.org/​10.1103/​PhysRevA.89.062315

[47] Marcello Benedetti, Brian Coyle, Mattia Fiorentini, Michael Lubasch, and Matthias Rosenkranz. Variational inference with a quantum computer. Phys. Rev. Applied, 16: 044057, Oct 2021b. 10.1103/​PhysRevApplied.16.044057.
https:/​/​doi.org/​10.1103/​PhysRevApplied.16.044057

[48] Robert M. Parrish and Peter L. McMahon. Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation. arXiv:1909.08925, 2019. 10.48550/​arXiv.1909.08925.
https:/​/​doi.org/​10.48550/​arXiv.1909.08925
arXiv:1909.08925

[49] Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista. A Multireference Quantum Krylov Algorithm for Strongly Correlated Electrons. J. Chem. Theory Comput., 16: 2236, 2020. 10.1021/​acs.jctc.9b01125.
https:/​/​doi.org/​10.1021/​acs.jctc.9b01125

[50] Katherine Klymko, Carlos Mejuto-Zaera, Stephen J. Cotton, Filip Wudarski, Miroslav Urbanek, Diptarka Hait, Martin Head-Gordon, K. Birgitta Whaley, Jonathan Moussa, Nathan Wiebe, Wibe A. de Jong, and Norm M. Tubman. Real time evolution for ultracompact Hamiltonian eigenstates on quantum hardware. arXiv:2103.08563, 2021. 10.48550/​arXiv.2103.08563.
https:/​/​doi.org/​10.48550/​arXiv.2103.08563
arXiv:2103.08563

[51] John C. Snyder, Matthias Rupp, Katja Hansen, Klaus-Robert Müller, and Kieron Burke. Finding Density Functionals with Machine Learning. Phys. Rev. Lett., 108: 253002, Jun 2012. 10.1103/​PhysRevLett.108.253002.
https:/​/​doi.org/​10.1103/​PhysRevLett.108.253002

[52] Michael Lubasch, Johanna I. Fuks, Heiko Appel, Angel Rubio, J. Ignacio Cirac, and Mari-Carmen Bañuls. Systematic construction of density functionals based on matrix product state computations. New J. Phys., 18 (8): 083039, aug 2016. 10.1088/​1367-2630/​18/​8/​083039.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​8/​083039

[53] Sebastian Dick and Marivi Fernandez-Serra. Machine learning accurate exchange and correlation functionals of the electronic density. Nat. Commun., 11: 3509, 2020. 10.1038/​s41467-020-17265-7.
https:/​/​doi.org/​10.1038/​s41467-020-17265-7

Cited by

[1] Xiaozhen Ge, Re-Bing Wu, and Herschel Rabitz, "The optimization landscape of hybrid quantum–classical algorithms: From quantum control to NISQ applications", Annual Reviews in Control (2022).

[2] Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia, and Yuri Alexeev, "A Survey of Quantum Computing for Finance", arXiv:2201.02773.

[3] Tomoki Tanaka, Shumpei Uno, Tamiya Onodera, Naoki Yamamoto, and Yohichi Suzuki, "Noisy quantum amplitude estimation without noise estimation", Physical Review A 105 1, 012411 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2022-10-04 21:53:01) and SAO/NASA ADS (last updated successfully 2022-10-04 21:53:02). The list may be incomplete as not all publishers provide suitable and complete citation data.