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

Dong An; Noah Linden; Jin-Peng Liu; Ashley Montanaro; Changpeng Shao; Jiasu Wang

doi:10.22331/q-2021-06-24-481

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

Dong An¹, Noah Linden², Jin-Peng Liu^3,4,5, Ashley Montanaro^2,6, Changpeng Shao², and Jiasu Wang¹

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

Published:	2021-06-24, volume 5, page 481
Eprint:	arXiv:2012.06283v2
Doi:	https://doi.org/10.22331/q-2021-06-24-481
Citation:	Quantum 5, 481 (2021).

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

Abstract

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

@article{An2021quantumaccelerated,
  doi = {10.22331/q-2021-06-24-481},
  url = {https://doi.org/10.22331/q-2021-06-24-481},
  title = {Quantum-accelerated multilevel {M}onte {C}arlo methods for stochastic differential equations in mathematical finance},
  author = {An, Dong and Linden, Noah and Liu, Jin-Peng and Montanaro, Ashley and Shao, Changpeng and Wang, Jiasu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {481},
  month = jun,
  year = {2021}
}

► 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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/10.1007/s00220-017-3002-y

[6] F. Black and M. Scholes. The pricing of options and corporate liabilities, 1973. doi:10.1086/260062.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1103/PhysRevA.100.062315

[24] L. C. Evans. Partial differential equations (2nd ed.). American Mathematical Society, 2010. doi:10.1090/gsm/019.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1287/opre.1070.0496

[29] M. B. Giles. Multilevel Monte Carlo methods. Acta Numerica, 24:259–328, 2015. doi:10.1017/S096249291500001X.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
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.
https://doi.org/10.1007/3-540-30799-0

[50] X. Mao. Stochastic differential equations and applications. Elsevier, 2007. doi:10.1533/9780857099402.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://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.
https://doi.org/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.
https://doi.org/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.
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.
https://doi.org/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.
https://doi.org/10.1080/13647830.2019.1626025

Cited by

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-05 20:02:20) and SAO/NASA ADS (last updated successfully 2023-06-05 20:02:21). 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.