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

Steven Herbert

doi:10.22331/q-2022-09-29-823

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

Published:	2022-09-29, volume 6, page 823
Eprint:	arXiv:2105.09100v4
Doi:	https://doi.org/10.22331/q-2022-09-29-823
Citation:	Quantum 6, 823 (2022).

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

@article{Herbert2022quantummontecarlo,
  doi = {10.22331/q-2022-09-29-823},
  url = {https://doi.org/10.22331/q-2022-09-29-823},
  title = {Quantum {M}onte {C}arlo {I}ntegration: {T}he {F}ull {A}dvantage in {M}inimal {C}ircuit {D}epth},
  author = {Herbert, Steven},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {823},
  month = sep,
  year = {2022}
}

► 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] Steven Herbert, "Quantum computing for data-centric engineering and science", Data-Centric Engineering 3, e36 (2022).

[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] Koichi Miyamoto, "Quantum algorithm for calculating risk contributions in a credit portfolio", EPJ Quantum Technology 9 1, 32 (2022).

[7] Sascha Wilkens and Joe Moorhouse, "Quantum computing for financial risk measurement", Quantum Information Processing 22 1, 51 (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] 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).

[10] 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).

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

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

[13] 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).

[14] 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).

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

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

[17] 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).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-27 21:26:42) and SAO/NASA ADS (last updated successfully 2023-09-27 21:26:43). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.