Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance

Dong An1, Noah Linden2, Jin-Peng Liu3,4,5, Ashley Montanaro2,6, Changpeng Shao2, and Jiasu Wang1

1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2School of Mathematics, Fry Building, University of Bristol, BS8 1UG, UK
3Joint Center for Quantum Information and Computer Science, University of Maryland, MD 20742, USA
4Institute for Advanced Computer Studies, University of Maryland, MD 20742, USA
5Department of Mathematics, University of Maryland, MD 20742, USA
6Phasecraft Ltd, Quantum Technologies Innovation Centre, Bristol BS1 5DD, UK

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


Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly we provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. As applications, we apply it to compute expectation values determined by classical solutions of SDEs, with improved dependence on precision. We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance, such as the Black-Scholes and Local Volatility models, and Greeks. We also provide a quantum algorithm based on sublinear binomial sampling for the binomial option pricing model with the same improvement.

► BibTeX data

► References

[1] A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In 29th Symposium on Theoretical Aspects of Computer Science, volume 14, pages 636–647. LIPIcs, 2012. doi:10.4230/​LIPIcs.STACS.2012.636.

[2] D. An and L. Lin. Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm, 2019. arXiv:1909.05500.

[3] K. E. Atkinson. An introduction to numerical analysis. John Wiley & Sons, 2008.

[4] D. W. Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 47(10):105301, 2014. doi:10.1088/​1751-8113/​47/​10/​105301.

[5] D. W. Berry, A. M. Childs, A. Ostrander, and G. Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356(3):1057–1081, 2017. doi:10.1007/​s00220-017-3002-y.

[6] F. Black and M. Scholes. The pricing of options and corporate liabilities, 1973. doi:10.1086/​260062.

[7] Z. Bodie. Investments. Tata McGraw-Hill Education, 2009.

[8] A. Bouland, W. van Dam, H. Joorati, I. Kerenidis, and A. Prakash. Prospects and challenges of quantum finance, 2020. arXiv:2011.06492.

[9] K. Bringmann, F. Kuhn, K. Panagiotou, U. Peter, and H. Thomas. Internal DLA: Efficient simulation of a physical growth model. In International Colloquium on Automata, Languages, and Programming, pages 247–258. Springer, 2014. doi:10.1007/​978-3-662-43948-7_21.

[10] S. Burgos and M. B. Giles. Computing greeks using multilevel path simulation. In: Plaskota L., Woźniakowski H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2010. Springer Proceedings in Mathematics & Statistics, 23:281–296, 2012. doi:10.1007/​978-3-642-27440-4_13.

[11] K. Burrage, P. M. Burrage, and T. Tian. Numerical methods for strong solutions of stochastic differential equations: An overview. Proc. R. Soc. A Math. Phys. Eng. Sci., 460:373–402, 2004. doi:10.1098/​rspa.2003.1247.

[12] Y. Cao, A. Papageorgiou, I. Petras, J. Traub, and S. Kais. Quantum algorithm and circuit design solving the Poisson equation. New Journal of Physics, 15(1):013021, 2013. doi:10.1088/​1367-2630/​15/​1/​013021.

[13] A. M. Childs, R. Kothari, and R. D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950, 2017. doi:10.1137/​16M1087072.

[14] A. M. Childs and J.-P. Liu. Quantum spectral methods for differential equations. Communications in Mathematical Physics, 375:1427–1457, 2020. doi:10.1007/​s00220-020-03699-z.

[15] A. M. Childs, J.-P. Liu, and A. Ostrander. High-precision quantum algorithms for partial differential equations, 2020. arXiv:2002.07868.

[16] B. D. Clader, B. C. Jacobs, and C. R. Sprouse. Preconditioned quantum linear system algorithm. Physical Review Letters, 110(25):250504, 2013. doi:10.1103/​PhysRevLett.110.250504.

[17] K. A. Cliffe, M. B. Giles, R. Scheichl, and A. L. Teckentrup. Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Computing and Visualization in Science, 14(1):3, 2011. doi:10.1007/​s00791-011-0160-x.

[18] P. C. S. Costa, S. Jordan, and A. Ostrander. Quantum algorithm for simulating the wave equation. Physical Review A, 99(1):012323, 2019. doi:10.1103/​PhysRevA.99.012323.

[19] J. C. Cox, S. A. Ross, and M. Rubinstein. Option pricing: A simplified approach. Journal of financial Economics, 7(3):229–263, 1979. doi:10.1016/​0304-405X(79)90015-1.

[20] E. Derman and I. Kani. Riding on a smile. Risk, 7(2):32–39, 1994.

[21] J. Dick, F. Y. Kuo, and I. H. Sloan. High-dimensional integration: the quasi-Monte Carlo way. Acta Numerica, 22:133, 2013. doi:10.1017/​S0962492913000044.

[22] B. Dupire. Pricing with a smile. Risk, 7(1):18–20, 1994.

[23] A. Engel, G. Smith, and S. E. Parker. Quantum algorithm for the Vlasov equation. Physical Review A, 100(6):062315, 2019. doi:10.1103/​PhysRevA.100.062315.

[24] L. C. Evans. Partial differential equations (2nd ed.). American Mathematical Society, 2010. doi:10.1090/​gsm/​019.

[25] M. Farach-Colton and M.-T. Tsai. Exact sublinear binomial sampling. Algorithmica, 73(4):637–651, 2015. doi:10.1007/​s00453-015-0077-8.

[26] F. Fontanela, A. J. Jacquier, and M. Oumgari. A quantum algorithm for linear PDEs arising in finance, 2019. doi:10.2139/​ssrn.3499134.

[27] E. Fournié, J.-M. Lasry, J. Lebuchoux, P.-L. Lions, and N. Touzi. Applications of malliavin calculus to Monte Carlo methods in finance. Finance and Stochastics, 3:391–412, 1999. doi:10.1007/​s007800050068.

[28] M. B. Giles. Multilevel Monte Carlo path simulation. Operations Research, 56(3):607–617, 2008. doi:10.1287/​opre.1070.0496.

[29] M. B. Giles. Multilevel Monte Carlo methods. Acta Numerica, 24:259–328, 2015. doi:10.1017/​S096249291500001X.

[30] M. B. Giles, D. J. Higham, and X. Mao. Analysing multi-level Monte Carlo for options with non-globally lipschitz payoff. Finance and Stochastics, 13(3):403–413, 2009. doi:10.1007/​s00780-009-0092-1.

[31] M. B. Giles and B. J. Waterhouse. Multilevel quasi-Monte Carlo path simulation. Advanced Financial Modelling, Radon Series on Computational and Applied Mathematics, 8:165–181, 2009. doi:10.1515/​9783110213140.165.

[32] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/​3313276.3316366.

[33] J. Gonzalez-Conde, A. Rodríguez-Rozas, E. Solano, and M. Sanz. Pricing financial derivatives with exponential quantum speedup, 2021. arXiv:2101.04023.

[34] A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009. doi:10.1103/​PhysRevLett.103.150502.

[35] S. Heinrich. Multilevel Monte Carlo methods. In International Conference on Large-Scale Scientific Computing, pages 58–67. Springer, 2001. doi:10.1007/​3-540-45346-6_5.

[36] S. Heston and G. Zhou. On the rate of convergence of discrete-time contingent claims. Mathematical Finance, 10(1):53–75, 2000. doi:10.1111/​1467-9965.00080.

[37] J. C. Hull. Options futures and other derivatives. Pearson Education India, 2003.

[38] R. A. Jarrow and A. T. Rudd. Option pricing. Richard D. Irwin, 1983.

[39] M. H. Kalos and P. A. Whitlock. Monte Carlo methods. John Wiley & Sons, 2009. doi:10.1002/​9783527626212.

[40] K. Kaneko, K. Miyamoto, N. Takeda, and K. Yoshino. Quantum pricing with a smile: Implementation of local volatility model on quantum computer, 2020. arXiv:2007.01467.

[41] K. Kaneko, K. Miyamoto, N. Takeda, and K. Yoshino. Quantum speedup of Monte Carlo integration in the direction of dimension and its application to finance. Quantum Inf Processing, 20:185, 2021. doi:10.1007/​s11128-021-03127-8.

[42] P. E. Kloeden and E. Platen. Numerical solution of stochastic differential equations, volume 23. Springer Science & Business Media, 2013. doi:10.1007/​978-3-662-12616-5.

[43] D. F. Kuznetsov. Strong numerical methods of orders 2.0, 2.5, and 3.0 for ito stochastic differential equations, based on the unified stochastic taylor expansions and multiple fourier-legendre series, 2018. arXiv:1807.02190.

[44] D. P. J. Leisen and M. Reimer. Binomial models for option valuation-examining and improving convergence. Applied Mathematical Finance, 3(4):319–346, 1996. doi:10.1080/​13504869600000015.

[45] L. Lin and Y. Tong. Optimal quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020. doi:10.22331/​q-2020-11-11-361.

[46] N. Linden, A. Montanaro, and C. Shao. Quantum vs. classical algorithms for solving the heat equation, 2020. arXiv:2004.06516.

[47] G. Liu and L. J. Hong. Kernel estimation of the greeks for options with discontinuous payoffs. Operations Research, 59:iii–266, 2010. doi:10.1287/​opre.1100.0844.

[48] J.-P. Liu, H. Ø. Kolden, H. K. Krovi, N. F. Loureiro, K. Trivisa, and A. M. Childs. Efficient quantum algorithm for dissipative nonlinear differential equations, 2020. arXiv:2011.03185.

[49] P. Malliavin and A. Thalmaier. Stochastic Calculus of Variations in Mathematical Finance. Springer-Verlag Berlin Heidelberg, 2006. doi:10.1007/​3-540-30799-0.

[50] X. Mao. Stochastic differential equations and applications. Elsevier, 2007. doi:10.1533/​9780857099402.

[51] A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. doi:10.1098/​rspa.2015.0301.

[52] A. Montanaro and S. Pallister. Quantum algorithms and the finite element method. Physical Review A, 93(3):032324, 2016. doi:10.1103/​PhysRevA.93.032324.

[53] R. Orus, S. Mugel, and E. Lizaso. Quantum computing for finance: overview and prospects. Reviews in Physics, 4:100028, 2019. doi:10.1016/​j.revip.2019.100028.

[54] S. H. Paskov and J. F. Traub. Faster valuation of financial derivatives. The Journal of Portfolio Management, 22(1):113–123, 1995. doi:10.3905/​jpm.1995.409541.

[55] P. Rebentrost, B. Gupt, and T. R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Physical Review A, 98(2):022321, 2018. doi:10.1103/​PhysRevA.98.022321.

[56] R. J. Rendleman. Two-state option pricing. The Journal of Finance, 34(5):1093–1110, 1979. doi:doi.org/​10.2307/​2327237.

[57] N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner. Option pricing using quantum computers. Quantum, 4:291, 2020. doi:10.22331/​q-2020-07-06-291.

[58] Y. Subaşı, R. D. Somma, and D. Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Physical Review Letters, 122(6):060504, 2019. doi:10.1103/​PhysRevLett.122.060504.

[59] Y. Tong, D. An, N. Wiebe, and L. Lin. Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions, 2020. arXiv:2008.13295.

[60] G. Xu, A. J. Daley, P. Givi, and R. D. Somma. Turbulent mixing simulation via a quantum algorithm. AIAA Journal, 56(2):687–699, 2018. doi:10.2514/​1.J055896.

[61] G. Xu, A. J. Daley, P. Givi, and R. D. Somma. Quantum algorithm for the computation of the reactant conversion rate in homogeneous turbulence. Combustion Theory and Modelling, 23(6):1090–1104, 2019. doi:10.1080/​13647830.2019.1626025.

Cited by

[1] Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, and Mikel Sanz, "Efficient Hamiltonian simulation for solving option price dynamics", Physical Review Research 5 4, 043220 (2023).

[2] Koichi Miyamoto, "Bermudan option pricing by quantum amplitude estimation and Chebyshev interpolation", EPJ Quantum Technology 9 1, 3 (2022).

[3] Nabeela Anwar, Iftikhar Ahmad, Adiqa Kausar Kiani, Muhammad Shoaib, and Muhammad Asif Zahoor Raja, "Euler-Maruyama and Kloeden-Platen-Schurz computing paradigm for stochastic vector-borne plant epidemic model", Waves in Random and Complex Media 1 (2023).

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

[5] Dengke Qu, Edric Matwiejew, Kunkun Wang, Jingbo Wang, and Peng Xue, "Experimental implementation of quantum-walk-based portfolio optimization", Quantum Science and Technology 9 2, 025014 (2024).

[6] Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Marc Gerritsma, and Roeland De Breuker, "Review and perspectives in quantum computing for partial differential equations in structural mechanics", Frontiers in Mechanical Engineering 8, 914241 (2022).

[7] Kenji Kubo, Koichi Miyamoto, Kosuke Mitarai, and Keisuke Fujii, "Pricing Multiasset Derivatives by Variational Quantum Algorithms", IEEE Transactions on Quantum Engineering 4, 1 (2023).

[8] Koichi Miyamoto and Kenji Kubo, "Pricing Multi-Asset Derivatives by Finite-Difference Method on a Quantum Computer", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[9] Luis Enrique Andrade-Gorjoux, César Castrejón-Peralta, Jordi Fabián González-Contreras, Jesús Yaljá Montiel-Pérez, and José Luis López-Bonilla, Communications in Computer and Information Science 1938, 246 (2024) ISBN:978-3-031-52516-2.

[10] Hedayat Alghassi, Amol Deshmukh, Noelle Ibrahim, Nicolas Robles, Stefan Woerner, and Christa Zoufal, "A variational quantum algorithm for the Feynman-Kac formula", Quantum 6, 730 (2022).

[11] I. Joseph, Y. Shi, M. D. Porter, A. R. Castelli, V. I. Geyko, F. R. Graziani, S. B. Libby, and J. L. DuBois, "Quantum computing for fusion energy science applications", Physics of Plasmas 30 1, 010501 (2023).

[12] Ahmed I. Osman, Mahmoud Nasr, Mohamed Farghali, Ahmed K. Rashwan, Adel Abdelkader, Ala’a H. Al-Muhtaseb, Ikko Ihara, and David W. Rooney, "Optimizing biodiesel production from waste with computational chemistry, machine learning and policy insights: a review", Environmental Chemistry Letters (2024).

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

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

[15] Jehad K. Mohammed and Ayad R. Khudair, "Solving nonlinear stochastic differential equations via fourth-degree hat functions", Results in Control and Optimization 12, 100291 (2023).

[16] Huibo Wang and Haibin Lv, "Enterprise Financial Asset Risk Measurement Based on Embedded Microprocessor Security Analysis", Wireless Communications and Mobile Computing 2022, 1 (2022).

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

[18] Patrick Rall, "Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation", Quantum 5, 566 (2021).

[19] Ethan Wang, "Efficient Cauchy distribution based quantum state preparation by using the comparison algorithm", AIP Advances 11 10, 105307 (2021).

[20] Ethan T. Wang, "Efficient Quantum State Preparation for the Cauchy Distribution Based on Piecewise Arithmetic", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[21] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).

[22] Steven Herbert, "Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth", Quantum 6, 823 (2022).

[23] Andrés Gómez, Álvaro Leitao, Alberto Manzano, Daniele Musso, María R. Nogueiras, Gustavo Ordóñez, and Carlos Vázquez, "A Survey on Quantum Computational Finance for Derivatives Pricing and VaR", Archives of Computational Methods in Engineering 29 6, 4137 (2022).

[24] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

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

[26] Javier Alcazar, Andrea Cadarso, Amara Katabarwa, Marta Mauri, Borja Peropadre, Guoming Wang, and Yudong Cao, "Quantum algorithm for credit valuation adjustments", New Journal of Physics 24 2, 023036 (2022).

[27] Jeong Yu Han and Patrick Rebentrost, "Quantum advantage for multi-option portfolio pricing and valuation adjustments", arXiv:2203.04924, (2022).

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

[29] Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang, "Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants", arXiv:2210.06539, (2022).

[30] Guillermo González, Rahul Trivedi, and J. Ignacio Cirac, "Quantum algorithms for powering stable Hermitian matrices", Physical Review A 103 6, 062420 (2021).

[31] Aaron Sidford and Chenyi Zhang, "Quantum speedups for stochastic optimization", arXiv:2308.01582, (2023).

[32] Koichi Miyamoto and Kenji Kubo, "Pricing multi-asset derivatives by finite difference method on a quantum computer", arXiv:2109.12896, (2021).

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