Document Open Access Logo

Quantum Algorithm for Stochastic Optimal Stopping Problems with Applications in Finance

Authors João F. Doriguello , Alessandro Luongo, Jinge Bao, Patrick Rebentrost, Miklos Santha

PDF
Thumbnail PDF

File

LIPIcs.TQC.2022.2.pdf
  • Filesize: 0.92 MB
  • 24 pages

Document Identifiers

Author Details

João F. Doriguello
  • Centre for Quantum Technologies, National University of Singapore, Singapore
Alessandro Luongo
  • Centre for Quantum Technologies, National University of Singapore, Singapore
Jinge Bao
  • Centre for Quantum Technologies, National University of Singapore, Singapore
Patrick Rebentrost
  • Centre for Quantum Technologies, National University of Singapore, Singapore
Miklos Santha
  • Centre for Quantum Technologies, National University of Singapore, Singapore

Funding

Research at CQT is funded by the National Research Foundation, the Prime Minister’s Office, and the Ministry of Education, Singapore under the Research Centres of Excellence programme’s research grant R-710-000-012-135.

Acknowledgements

We thank Rajagopal Raman for pointing out Ref. [Krah et al., 2018] and the importance of the Longstaff-Schwarz algorithm in the insurance industry. We also thank Koichi Miyamoto for Ref. [Kaneko et al., 2021] and Eric Ghysels for Refs. [Broadie et al., 2000; Broadie et al., 2000].

Cite AsGet BibTex

João F. Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, and Miklos Santha. Quantum Algorithm for Stochastic Optimal Stopping Problems with Applications in Finance. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.TQC.2022.2

Abstract

The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in stochastic optimal stopping theory. In this work, we propose a quantum LSM based on quantum access to a stochastic process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo. For this algorithm, we elucidate the intricate interplay of function approximation and quantum algorithms for Monte Carlo. Our algorithm achieves a nearly quadratic speedup in the runtime compared to the LSM algorithm under some mild assumptions. Specifically, our quantum algorithm can be applied to American option pricing and we analyze a case study for the common situation of Brownian motion and geometric Brownian motion processes.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Stochastic processes
  • Mathematics of computing → Markov-chain Monte Carlo methods
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum computation complexity
  • optimal stopping time
  • stochastic processes
  • American options
  • quantum finance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Directive 2009/138/EC of the European Parliament and of the Council of 25 November 2009 on the taking-up and pursuit of the business of Insurance and Reinsurance (Solvency II), 2009. Google Scholar
  2. Javier Alcazar, Vicente Leyton-Ortega, and Alejandro Perdomo-Ortiz. Classical versus quantum models in machine learning: insights from a finance application. Machine Learning: Science and Technology, 1(3):035003, 2020. Google Scholar
  3. Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang. Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance. Quantum, 5:481, 2021. Google Scholar
  4. Leif B. G. Andersen, Mark Lake, and Dimitri Offengenden. High-performance American option pricing. Journal of Computational Finance, 20(1):39-87, 2016. Google Scholar
  5. Anna Rita Bacinello, Enrico Biffis, and Pietro Millossovich. Pricing life insurance contracts with early exercise features. Journal of computational and applied mathematics, 233(1):27-35, 2009. Google Scholar
  6. Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. Improving variational quantum optimization using CVaR. Quantum, 4:256, 2020. Google Scholar
  7. Giovanni Barone-Adesi and Robert E. Whaley. Efficient analytic approximation of American option values. the Journal of Finance, 42(2):301-320, 1987. Google Scholar
  8. Christian Bender and Jessica Steiner. Least-squares Monte Carlo for backward SDEs. In Numerical methods in finance, pages 257-289. Springer, 2012. Google Scholar
  9. Alain Bensoussan and J.-L. Lions. Applications of variational inequalities in stochastic control. Elsevier, 2011. Google Scholar
  10. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett., 114:090502, 2015. URL: https://doi.org/10.1103/PhysRevLett.114.090502.
  11. Fischer Black and Myron Scholes. The pricing of options and corporate liabilities. Journal of Political Economy, 81:637-654, 1973. Google Scholar
  12. Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash. Prospects and challenges of quantum finance. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.06492.
  13. Phelim P. Boyle. Options: a Monte Carlo approach. Journal of Financial Economics, 4(3):323-338, 1977. Google Scholar
  14. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. Google Scholar
  15. Mark Broadie, Jérôme Detemple, Eric Ghysels, and Olivier Torrès. American options with stochastic dividends and volatility: A nonparametric investigation. Journal of Econometrics, 94(1-2):53-92, 2000. Google Scholar
  16. Mark Broadie, Jérôme Detemple, Eric Ghysels, and Olivier Torrès. Nonparametric estimation of American options’ exercise boundaries and call prices. Journal of Economic Dynamics and Control, 24(11-12):1829-1857, 2000. Google Scholar
  17. Mark Broadie and Paul Glasserman. Monte Carlo methods for pricing high-dimensional American options: an overview. Net Exposure, 3:15-37, 1997. Google Scholar
  18. Shouvanik Chakrabarti, Rajiv Krishnakumar, Guglielmo Mazzola, Nikitas Stamatopoulos, Stefan Woerner, and William J. Zeng. A threshold for quantum advantage in derivative pricing. Quantum, 5:463, 2021. Google Scholar
  19. Don M. Chance. A synthesis of binomial option pricing models for lognormally distributed assets. Journal of Applied Finance (Formerly Financial Practice and Education), 18(1), 2008. Google Scholar
  20. Emmanuelle Clément, Damien Lamberton, and Philip Protter. An analysis of a least squares regression method for American option pricing. Finance and Stochastics, 6(4):449-471, 2002. Google Scholar
  21. Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi. Near-optimal quantum algorithms for multivariate mean estimation. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.09787.
  22. Arjan Cornelissen and Sofiene Jerbi. Quantum algorithms for multivariate Monte Carlo estimation. arXiv preprint, 2021. URL: http://arxiv.org/abs/2107.03410.
  23. John C. Cox, Stephen A. Ross, and Mark Rubinstein. Option pricing: a simplified approach. Journal of Financial Economics, 7(3):229-263, 1979. Google Scholar
  24. Gary Wayne Crosby. Optimal multiple stopping: theory and applications. PhD thesis, The University of North Carolina at Charlotte, 2017. Google Scholar
  25. Samudra Dasgupta and Arnab Banerjee. Quantum annealing algorithm for expected shortfall based dynamic asset allocation. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.12904.
  26. Constantinos Daskalakis and Yasushi Kawase. Optimal stopping rules for sequential hypothesis testing. In 25th Annual European Symposium on Algorithms (ESA), 2017. Google Scholar
  27. Georgios Dimitrakopoulos. Least-squares Monte Carlo simulation and high performance computing for Solvency II regulatory capital estimation. Master’s thesis, The University of Manchester (United Kingdom), 2013. Google Scholar
  28. João F. Doriguello, Alessandro Luongo, Jinge Bao, Patrick Rebentrost, and Miklos Santha. Quantum algorithm for stochastic optimal stopping problems with applications in finance. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.15332.
  29. Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain. Quantum computing for finance: state of the art and future prospects. IEEE Transactions on Quantum Engineering, 2020. Google Scholar
  30. Daniel Egloff. Monte Carlo algorithms for optimal stopping and statistical learning. The Annals of Applied Probability, 15(2):1396-1432, 2005. Google Scholar
  31. Hans Föllmer and Alexander Schied. Stochastic finance. de Gruyter, 2016. Google Scholar
  32. Filipe Fontanela, Antoine Jacquier, and Mugad Oumgari. A quantum algorithm for linear PDEs arising in finance. SIAM Journal on Financial Mathematics, 12(4):SC98-SC114, 2021. Google Scholar
  33. Michael C. Fu, Scott B. Laprise, Dilip B. Madan, Yi Su, and Rongwen Wu. Pricing American options: a comparison of Monte Carlo simulation approaches. Journal of Computational Finance, 4(3):39-88, 2001. Google Scholar
  34. Stefan Gerhold. The Longstaff-Schwartz algorithm for Lévy models: results on fast and slow convergence. The Annals of Applied Probability, 21(2):589-608, 2011. Google Scholar
  35. Emmanuel Gobet, Jean-Philippe Lemor, and Xavier Warin. A regression-based Monte Carlo method to solve backward stochastic differential equations. The Annals of Applied Probability, 15(3):2172-2202, 2005. Google Scholar
  36. Emmanuel Gobet and Plamen Turkedjiev. Approximation of discrete BSDE using least-squares regression, November 2011. Technical report. URL: https://hal.archives-ouvertes.fr/hal-00642685.
  37. Gene H. Golub and Charles F. Van Loan. Matrix computations, 2013. Google Scholar
  38. Andrew Green. XVA: Credit, Funding and Capital Valuation Adjustments. John Wiley & Sons, 2015. Google Scholar
  39. Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv preprint, 2002. URL: http://arxiv.org/abs/quant-ph/0208112.
  40. Eli Gutin. Practical applications of large-scale stochastic control for learning and optimization. PhD thesis, Massachusetts Institute of Technology, 2018. Google Scholar
  41. Yassine Hamoudi. Quantum sub-Gaussian mean estimator. In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  42. Jeong Yu Han and Patrick Rebentrost. Quantum advantage for multi-option portfolio pricing and valuation adjustments. arXiv preprint, 2022. URL: http://arxiv.org/abs/2203.04924.
  43. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009. Google Scholar
  44. Steven Herbert. No quantum speedup with Grover-Rudolph state preparation for quantum Monte Carlo integration. Physical Review E, 103(6):063302, 2021. Google Scholar
  45. Mark Hodson, Brendan Ruck, Hugh Ong, David Garvin, and Stefan Dulman. Portfolio rebalancing experiments using the quantum alternating operator ansatz. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.05296.
  46. Jacqueline Huang and Jong-Shi Pang. Option pricing and linear complementarity. Technical report, Cornell University, 2003. Google Scholar
  47. Dunham Jackson. A general class of problems in approximation. American Journal of Mathematics, 46(4):215-234, 1924. Google Scholar
  48. Patrick Jaillet, Damien Lamberton, and Bernard Lapeyre. Variational inequalities and the pricing of American options. Acta Applicandae Mathematica, 21(3):263-289, 1990. Google Scholar
  49. Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, and Kazuyoshi Yoshino. Quantum pricing with a smile: implementation of local volatility model on quantum computer. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.01467.
  50. Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, and Kazuyoshi Yoshino. Linear regression by quantum amplitude estimation and its extension to convex optimization. Phys. Rev. A, 104:022430, 2021. URL: https://doi.org/10.1103/PhysRevA.104.022430.
  51. In Joon Kim. The analytic valuation of American options. The Review of Financial Studies, 3(4):547-572, 1990. Google Scholar
  52. Michael Kohler. A review on regression-based Monte Carlo methods for pricing American options. In Recent developments in applied probability and statistics, pages 37-58. Springer, 2010. Google Scholar
  53. Anne-Sophie Krah, Zoran Nikolić, and Ralf Korn. A least-squares Monte Carlo framework in proxy modeling of life insurance companies. Risks, 6(2):62, 2018. Google Scholar
  54. Jean-Philippe Lemor, Emmanuel Gobet, and Xavier Warin. Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations. Bernoulli, 12(5):889-916, 2006. Google Scholar
  55. Xiaofei Li, Yi Wu, Quanxin Zhu, Songbo Hu, and Chuan Qin. A regression-based Monte Carlo method to solve two-dimensional forward backward stochastic differential equations. Advances in Difference Equations, 2021(1):1-13, 2021. Google Scholar
  56. Chen Liu, Henry Schellhorn, and Qidi Peng. American option pricing with regression: convergence analysis. International Journal of Theoretical and Applied Finance, 22(08):1950044, 2019. Google Scholar
  57. Francis A. Longstaff and Eduardo S. Schwartz. Valuing American options by simulation: a simple least-squares approach. The review of financial studies, 14(1):113-147, 2001. Google Scholar
  58. Gabriel Marin-Sancheza, Javier Gonzalez-Conde, and Mikel Sanz. Quantum algorithms for approximate function loading. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.07933.
  59. Ana Martin, Bruno Candelas, Ángel Rodríguez-Rozas, José D. Martín-Guerrero, Xi Chen, Lucas Lamata, Román Orús, Enrique Solano, and Mikel Sanz. Toward pricing financial derivatives with an IBM quantum computer. Physical Review Research, 3(1):013167, 2021. Google Scholar
  60. Henry P. McKean Jr. A free boundary problem for the heat equation arising from a problem of mathermatical economics. Industrial Management Review, 6:32-39, 1965. Google Scholar
  61. Robert C. Merton. Theory of rational option pricing. The Bell Journal of Economics and Management Science, 4(1):141-183, 1973. Google Scholar
  62. Koichi Miyamoto. Bermudan option pricing by quantum amplitude estimation and Chebyshev interpolation. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.09014.
  63. Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. Google Scholar
  64. Alexey Muravlev and Mikhail Zhitlukhin. A Bayesian sequential test for the drift of a fractional Brownian motion. Advances in Applied Probability, 52(4):1308-1324, 2020. Google Scholar
  65. Jacques Neveu. Discrete-parameter martingales. Elsevier, 1975. Google Scholar
  66. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
  67. Roman Orus, Samuel Mugel, and Enrique Lizaso. Quantum computing for finance: overview and prospects. Reviews in Physics, 4:100028, 2019. Google Scholar
  68. Art B. Owen. Assessing linearity in high dimensions. The Annals of Statistics, 28(1):1-19, 2000. Google Scholar
  69. Antoon Pelsser and Janina Schweizer. The difference between lsmc and replicating portfolio in insurance liability modeling. European actuarial journal, 6(2):441-494, 2016. Google Scholar
  70. Goran Peskir and Albert Shiryaev. Optimal stopping and free-boundary problems. Springer, 2006. Google Scholar
  71. Warren B. Powell. A unified framework for stochastic optimization. European Journal of Operational Research, 275(3):795-821, 2019. Google Scholar
  72. Santosh Kumar Radha. Quantum option pricing using wick rotated imaginary time evolution. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.04280.
  73. Sergi Ramos-Calderer, Adrián Pérez-Salinas, Diego García-Martín, Carlos Bravo-Prieto, Jorge Cortada, Jordi Planaguma, and José I. Latorre. Quantum unary approach to option pricing. Physical Review A, 103(3):032414, 2021. Google Scholar
  74. Patrick Rebentrost, Brajesh Gupt, and Thomas R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A, 98:022321, 2018. Google Scholar
  75. Patrick Rebentrost and Seth Lloyd. Quantum computational finance: quantum algorithm for portfolio optimization. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.03975.
  76. Patrick Rebentrost, Miklos Santha, and Siyi Yang. Quantum alphatron. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.11670.
  77. Richard J. Rendleman. Two-state option pricing. The Journal of Finance, 34(5):1093-1110, 1979. Google Scholar
  78. Leonard C. G. Rogers. Monte Carlo valuation of American options. Mathematical Finance, 12(3):271-286, 2002. Google Scholar
  79. Joose Mikko Juhani Sauli. On the suitability of the Longstaff-Schwartz term structure model for modelling the cost of government debt. Master’s thesis, Helsingfors Universitet, 2013. Google Scholar
  80. William F. Sharpe, Gordon J. Alexander, and Jeffrey W. Bailey. Investments. Prentice-Hall, 1999. Google Scholar
  81. Albert N. Shiryaev. Optimal stopping rules, volume 8. Springer Science & Business Media, 2007. Google Scholar
  82. Albert N. Shiryaev. Quickest detection problems: fifty years later. Sequential Analysis, 29(4):345-385, 2010. Google Scholar
  83. Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen, and Stefan Woerner. Option pricing using quantum computers. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.02666.
  84. Nikitas Stamatopoulos, Guglielmo Mazzola, Stefan Woerner, and William J. Zeng. Towards quantum advantage in financial market risk using quantum gradient algorithms. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.12509.
  85. Peter Tankov, Ekaterina Voltchkova, and Rama Cont. Option pricing models with jumps: integro-differential equations and inverse problems. In European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2004), 2004. Google Scholar
  86. Elliot Tonkes and Dharma Lesmono. A Longstaff and Schwartz approach to the early election problem. Advances in Decision Sciences, 2012, 2012. Google Scholar
  87. John N. Tsitsiklis and Benjamin Van Roy. Regression methods for pricing complex American-style options. IEEE Transactions on Neural Networks, 12(4):694-703, 2001. Google Scholar
  88. Pierre Van Moerbeke. On optimal stopping and free boundary problems. Archive for Rational Mechanics and Analysis, 60(2):101-148, 1976. Google Scholar
  89. Almudena Carrera Vazquez and Stefan Woerner. Efficient state preparation for quantum amplitude estimation. Physical Review Applied, 15(3):034027, 2021. Google Scholar
  90. Abraham Wald. Sequential Analysis. John Wiley and Sons, 1st edition edition, 1947. Google Scholar
  91. Pawel Wocjan, Chen-Fu Chiang, Daniel Nagaj, and Anura Abeyesinghe. Quantum algorithm for approximating partition functions. Phys. Rev. A, 80:022340, 2009. Google Scholar
  92. Stefan Woerner and Daniel J. Egger. Quantum risk analysis. arXiv preprint, 2018. URL: http://arxiv.org/abs/1806.06893.
  93. Daniel Z. Zanger. Convergence of a least-squares Monte Carlo algorithm for bounded approximating sets. Applied Mathematical Finance, 16(2):123-150, 2009. Google Scholar
  94. Daniel Z. Zanger. Quantitative error estimates for a least-squares Monte Carlo algorithm for American option pricing. Finance and Stochastics, 17(3):503-534, 2013. Google Scholar
  95. Daniel Z. Zanger. Convergence of a least-squares Monte Carlo algorithm for American option pricing with dependent sample data. Mathematical Finance, 28(1):447-479, 2018. Google Scholar
  96. Daniel Z. Zanger. General error estimates for the Longstaff-Schwartz least-squares Monte Carlo algorithm. Mathematics of Operations Research, 45(3):923-946, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact