Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth

Steven Herbert

Quantinuum (Cambridge Quantum), Terrington House, 13-15 Hills Rd, Cambridge, CB2 1NL, UK
Department of Computer Science and Technology, University of Cambridge, UK

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

Abstract

This paper proposes a method of quantum Monte Carlo integration that retains the full quadratic quantum advantage, without requiring any arithmetic or quantum phase estimation to be performed on the quantum computer. No previous proposal for quantum Monte Carlo integration has achieved all of these at once. The heart of the proposed method is a Fourier series decomposition of the sum that approximates the expectation in Monte Carlo integration, with each component then estimated individually using quantum amplitude estimation. The main result is presented as theoretical statement of asymptotic advantage, and numerical results are also included to illustrate the practical benefits of the proposed method. The method presented in this paper is the subject of a patent application [Quantum Computing System and Method: Patent application GB2102902.0 and SE2130060-3].

► BibTeX data

► References

[1] 4 C. Blank, D. K. Park, and F. Petruccione, ``Quantum-enhanced analysis of discrete stochastic processes,'' NPJ Quantum Information, vol. 7, no. 126, 2021. [Online]. Available: https:/​/​doi.org/​10.1038/​s41534-021-00459-2 0pt.
https:/​/​doi.org/​10.1038/​s41534-021-00459-2

[2] 4 A. Montanaro, ``Quantum speedup of Monte Carlo methods,'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 471, no. 2181, p. 20150301, 2015. [Online]. Available: https:/​/​doi.org/​10.1098/​rspa.2015.0301 0pt.
https:/​/​doi.org/​10.1098/​rspa.2015.0301

[3] 4 G. Brassard, P. Høyer, M. Mosca, and A. Tapp, ``Quantum amplitude amplification and estimation,'' pp. 53–74, 2002. [Online]. Available: https:/​/​doi.org/​10.1090/​conm/​305/​05215 0pt.
https:/​/​doi.org/​10.1090/​conm/​305/​05215

[4] 4 D. An, N. Linden, J.-P. Liu, A. Montanaro, C. Shao, and J. Wang, ``Quantum-accelerated multilevel monte carlo methods for stochastic differential equations in mathematical finance,'' Quantum, vol. 5, p. 481, jun 2021. [Online]. Available: https:/​/​doi.org/​10.22331/​q-2021-06-24-481 0pt.
https:/​/​doi.org/​10.22331/​q-2021-06-24-481

[5] 4 R. Orús, S. Mugel, and E. Lizaso, ``Quantum computing for finance: Overview and prospects,'' Reviews in Physics, vol. 4, p. 100028, 2019. [Online]. Available: https:/​/​doi.org/​10.1016/​j.revip.2019.100028 0pt.
https:/​/​doi.org/​10.1016/​j.revip.2019.100028

[6] 4 D. J. Egger, R. García Gutiérrez, J. C. Mestre, and S. Woerner, ``Credit risk analysis using quantum computers,'' IEEE Transactions on Computers, vol. 70, no. 12, pp. 2136–2145, 2021. [Online]. Available: https:/​/​doi.org/​10.1109/​TC.2020.3038063 0pt.
https:/​/​doi.org/​10.1109/​TC.2020.3038063

[7] 4 S. Chakrabarti, R. Krishnakumar, G. Mazzola, N. Stamatopoulos, S. Woerner, and W. J. Zeng, ``A threshold for quantum advantage in derivative pricing,'' Quantum, vol. 5, p. 463, jun 2021. [Online]. Available: https:/​/​doi.org/​10.22331/​q-2021-06-01-463 0pt.
https:/​/​doi.org/​10.22331/​q-2021-06-01-463

[8] 4 P. Rebentrost and S. Lloyd, ``Quantum computational finance: quantum algorithm for portfolio optimization,'' 2018. [Online]. Available: https:/​/​doi.org/​10.48550/​arxiv.1811.03975 0pt.
https:/​/​doi.org/​10.48550/​arxiv.1811.03975

[9] 4 K. Kaneko, K. Miyamoto, N. Takeda, and K. Yoshino, ``Quantum pricing with a smile: Implementation of local volatility model on quantum computer,'' 2022. [Online]. Available: https:/​/​doi.org/​10.1140/​epjqt/​s40507-022-00125-2 0pt.
https:/​/​doi.org/​10.1140/​epjqt/​s40507-022-00125-2

[10] 4 S. Woerner and D. J. Egger, ``Quantum risk analysis,'' npj Quantum Information, vol. 5, no. 1, Feb 2019. [Online]. Available: http:/​/​doi.org/​10.1038/​s41534-019-0130-6 0pt.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[11] 4 P. Rebentrost, B. Gupt, and T. R. Bromley, ``Quantum computational finance: Monte Carlo pricing of financial derivatives,'' Physical Review A, vol. 98, no. 2, Aug 2018. [Online]. Available: https:/​/​doi.org/​10.1103/​physreva.98.022321 0pt.
https:/​/​doi.org/​10.1103/​physreva.98.022321

[12] 4 D. J. Egger, C. Gambella, J. Marecek, S. McFaddin, M. Mevissen, R. Raymond, A. Simonetto, S. Woerner, and E. Yndurain, ``Quantum computing for finance: State-of-the-art and future prospects,'' IEEE Transactions on Quantum Engineering, vol. 1, pp. 1–24, 2020. [Online]. Available: https:/​/​doi.org/​10.1109/​TQE.2020.3030314 0pt.
https:/​/​doi.org/​10.1109/​TQE.2020.3030314

[13] 4 K. Miyamoto and K. Shiohara, ``Reduction of qubits in a quantum algorithm for monte carlo simulation by a pseudo-random-number generator,'' Physical Review A, vol. 102, no. 2, Aug 2020. [Online]. Available: https:/​/​doi.org/​10.1103/​PhysRevA.102.022424 0pt.
https:/​/​doi.org/​10.1103/​PhysRevA.102.022424

[14] 4 K. Kubo, Y. O. Nakagawa, S. Endo, and S. Nagayama, ``Variational quantum simulations of stochastic differential equations,'' Phys. Rev. A, vol. 103, p. 052425, May 2021. [Online]. Available: https:/​/​doi.org/​10.1103/​PhysRevA.103.052425 0pt.
https:/​/​doi.org/​10.1103/​PhysRevA.103.052425

[15] 4 L. Grover and T. Rudolph, ``Creating superpositions that correspond to efficiently integrable probability distributions,'' 2002. [Online]. Available: https:/​/​doi.org/​10.48550/​arxiv.quant-ph/​0208112 0pt.
https:/​/​doi.org/​10.48550/​arxiv.quant-ph/​0208112
arXiv:quant-ph/0208112

[16] 4 S. Herbert, ``No quantum speedup with Grover-Rudolph state preparation for quantum Monte Carlo integration,'' Physical Review E, vol. 103, no. 6, jun 2021. [Online]. Available: https:/​/​doi.org/​10.1103/​physreve.103.063302 0pt.
https:/​/​doi.org/​10.1103/​physreve.103.063302

[17] 4 Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, ``Amplitude estimation without phase estimation,'' Quantum Information Processing, vol. 19, no. 2, Jan 2020. [Online]. Available: http:/​/​doi.org/​10.1007/​s11128-019-2565-2 0pt.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

[18] 4 D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, ``Iterative quantum amplitude estimation,'' npj Quantum Information, vol. 7, no. 1, mar 2021. [Online]. Available: https:/​/​doi.org/​10.1038/​s41534-021-00379-1 0pt.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[19] 4 S. Aaronson and P. Rall, ``Quantum approximate counting, simplified,'' Symposium on Simplicity in Algorithms, p. 24–32, Jan 2020. [Online]. Available: http:/​/​doi.org/​10.1137/​1.9781611976014.5 0pt.
https:/​/​doi.org/​10.1137/​1.9781611976014.5

[20] 4 K. Nakaji, ``Faster amplitude estimation,'' Quantum Information and Computation, vol. 20, no. 13&14, pp. 1109–1123, nov 2020. [Online]. Available: https:/​/​doi.org/​10.26421/​qic20.13-14-2 0pt.
https:/​/​doi.org/​10.26421/​qic20.13-14-2

[21] I. Kerenidis and A. Prakash, ``A method for amplitude estimation with noisy intermediate-scale quantum computers. U.S. Patent Application No. 16/​892,229,'' 2020.

[22] 4 T. Giurgica-Tiron, I. Kerenidis, F. Labib, A. Prakash, and W. Zeng, ``Low depth algorithms for quantum amplitude estimation,'' Quantum, vol. 6, p. 745, jun 2022. [Online]. Available: https:/​/​doi.org/​10.22331/​q-2022-06-27-745 0pt.
https:/​/​doi.org/​10.22331/​q-2022-06-27-745

[23] 4 N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner, ``Option pricing using quantum computers,'' Quantum, vol. 4, p. 291, Jul 2020. [Online]. Available: http:/​/​doi.org/​10.22331/​q-2020-07-06-291 0pt.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

[24] S. Herbert, ``Quantum Computing System and Method: Patent application GB2102902.0 and SE2130060-3,'' 2021.

[25] 4 A. Bouland, W. van Dam, H. Joorati, I. Kerenidis, and A. Prakash, ``Prospects and challenges of quantum finance,'' 2020. [Online]. Available: https:/​/​doi.org/​10.48550/​arxiv.2011.06492 0pt.
https:/​/​doi.org/​10.48550/​arxiv.2011.06492

[26] 4 T. Häner, M. Roetteler, and K. M. Svore, ``Optimizing quantum circuits for arithmetic,'' 2018. [Online]. Available: https:/​/​doi.org/​10.48550/​arxiv.1805.12445 0pt.
https:/​/​doi.org/​10.48550/​arxiv.1805.12445

[27] 4 J. Preskill, ``Quantum computing in the NISQ era and beyond,'' Quantum, vol. 2, p. 79, Aug 2018. [Online]. Available: http:/​/​doi.org/​10.22331/​q-2018-08-06-79 0pt.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[28] 4 ``IBM quantum roadmap.'' [Online]. Available: https:/​/​www.ibm.com/​blogs/​research/​2021/​02/​quantum-development-roadmap 0pt.
https:/​/​www.ibm.com/​blogs/​research/​2021/​02/​quantum-development-roadmap

[29] 4 N. d. Beaudrap and S. Herbert, ``Quantum linear network coding for entanglement distribution in restricted architectures,'' Quantum, vol. 4, p. 356, Nov 2020. [Online]. Available: http:/​/​doi.org/​10.22331/​q-2020-11-01-356 0pt.
https:/​/​doi.org/​10.22331/​q-2020-11-01-356

[30] S. Herbert and N. de Beaudrap, ``Method of Operating a Quantum Information Processing System. U.S. Patent Application No. 17/​064,980,'' 2020.

Cited by

[1] Zoltán Udvarnoki, Gábor Fáth, and Norbert Fogarasi, "Quantum advantage of Monte Carlo option pricing", Journal of Physics Communications 7 5, 055001 (2023).

[2] Koichi Miyamoto, "Quantum algorithms for numerical differentiation of expected values with respect to parameters", Quantum Information Processing 21 3, 109 (2022).

[3] Zhe-Hao Zhang, Yi-Cong Yu, Yang-Yang Chen, Song Cheng, and Xi-Wen Guan, "Monte Carlo Bethe-ansatz approach for the study of the Lieb-Liniger model", Physical Review A 109 3, 033320 (2024).

[4] Pierre-Yves Lagrave and Frédéric Barbaresco, MaxEnt 2022 17 (2022).

[5] Vladimir Skavysh, Sofia Priazhkina, Diego Guala, and Thomas R. Bromley, "Quantum monte carlo for economics: Stress testing and macroeconomic deep learning", Journal of Economic Dynamics and Control 153, 104680 (2023).

[6] Sascha Wilkens and Joe Moorhouse, "Quantum computing for financial risk measurement", Quantum Information Processing 22 1, 51 (2023).

[7] Salvatore Certo, Anh Pham, Nicolas Robles, and Andrew Vlasic, "Conditional generative models for learning stochastic processes", Quantum Machine Intelligence 5 2, 42 (2023).

[8] Koichi Miyamoto, "Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration", Physical Review Research 5 3, 033059 (2023).

[9] Guoqiang Shu, Zheng Shan, Jinchen Xu, Jie Zhao, and Shuya Wang, "A general quantum algorithm for numerical integration", Scientific Reports 14 1, 10432 (2024).

[10] Nikitas Stamatopoulos and William J. Zeng, "Derivative Pricing using Quantum Signal Processing", Quantum 8, 1322 (2024).

[11] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).

[12] Koichi Miyamoto, "Quantum algorithm for calculating risk contributions in a credit portfolio", EPJ Quantum Technology 9 1, 32 (2022).

[13] Jorge J. Martínez de Lejarza, Michele Grossi, Leandro Cieri, and Germán Rodrigo, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 571 (2023) ISBN:979-8-3503-4323-6.

[14] Sauro Succi, Wael Itani, Claudio Sanavio, Katepalli R. Sreenivasan, and René Steijl, "Ensemble fluid simulations on quantum computers", Computers & Fluids 270, 106148 (2024).

[15] 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, (2022).

[16] Ismail Yunus Akhalwaya, Adam Connolly, Roland Guichard, Steven Herbert, Cahit Kargi, Alexandre Krajenbrink, Michael Lubasch, Conor Mc Keever, Julien Sorci, Michael Spranger, and Ifan Williams, "A Modular Engine for Quantum Monte Carlo Integration", arXiv:2308.06081, (2023).

[17] Bernhard Jobst, Kevin Shen, Carlos A. Riofrío, Elvira Shishenina, and Frank Pollmann, "Efficient MPS representations and quantum circuits from the Fourier modes of classical image data", arXiv:2311.07666, (2023).

[18] Kirill Plekhanov, Matthias Rosenkranz, Mattia Fiorentini, and Michael Lubasch, "Variational quantum amplitude estimation", Quantum 6, 670 (2022).

[19] Selomit Ramírez-Uribe, Andrés E. Rentería-Olivo, and Germán Rodrigo, "Quantum querying based on multicontrolled Toffoli gates for causal Feynman loop configurations and directed acyclic graphs", arXiv:2404.03544, (2024).

[20] Philip Intallura, Georgios Korpas, Sudeepto Chakraborty, Vyacheslav Kungurtsev, and Jakub Marecek, "A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo Integration and Beyond", arXiv:2303.04945, (2023).

[21] Garrett T. Floyd, David P. Landau, and Michael R. Geller, "Quantum algorithm for Wang-Landau sampling", arXiv:2208.09543, (2022).

[22] M. C. Braun, T. Decker, N. Hegemann, S. F. Kerstan, C. Maier, and J. Ulmanis, "Quantum amplitude estimation with error mitigation for time-evolving probabilistic networks", arXiv:2303.16588, (2023).

[23] Koichi Miyamoto, "Quantum algorithm for calculating risk contributions in a credit portfolio", arXiv:2201.11394, (2022).

[24] Koichi Miyamoto, "Bermudan option pricing by quantum amplitude estimation and Chebyshev interpolation", arXiv:2108.09014, (2021).

[25] M. C. Braun, T. Decker, N. Hegemann, and S. F. Kerstan, "Error Resilient Quantum Amplitude Estimation from Parallel Quantum Phase Estimation", arXiv:2204.01337, (2022).

[26] Germán Rodrigo, "Quantum algorithms in particle physics", arXiv:2401.16208, (2024).

[27] Eric Ghysels, Jack Morgan, and Hamed Mohammadbagherpoor, "Quantum Computational Algorithms for Derivative Pricing and Credit Risk in a Regime Switching Economy", arXiv:2311.00825, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 09:04:06) and SAO/NASA ADS (last updated successfully 2024-07-15 09:04:07). The list may be incomplete as not all publishers provide suitable and complete citation data.