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.
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
► 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] Patrick Rall, “Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation”, arXiv:2103.09717.
[2] Guillermo González, Rahul Trivedi, and J. Ignacio Cirac, “Quantum algorithms for powering stable Hermitian matrices”, arXiv:2103.08329.
[3] Javier Alcazar, Andrea Cadarso, Amara Katabarwa, Marta Mauri, Borja Peropadre, Guoming Wang, and Yudong Cao, “Quantum algorithm for credit valuation adjustments”, arXiv:2105.12087.
The above citations are from SAO/NASA ADS (last updated successfully 2021-06-24 14:30:06). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-06-24 14:30:04: Could not fetch cited-by data for 10.22331/q-2021-06-24-481 from Crossref. This is normal if the DOI was registered recently.
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.
PlatoAi. Web3 Reimagined. Data Inteligence Amplifed.
Click here for Free Trial.
Source: https://quantum-journal.org/papers/q-2021-06-24-481/
