A variational quantum algorithm for the Feynman-Kac formula

Hedayat Alghassi; Amol Deshmukh; Noelle Ibrahim; Nicolas Robles; Stefan Woerner; Christa Zoufal

doi:10.22331/q-2022-06-07-730

A variational quantum algorithm for the Feynman-Kac formula

Hedayat Alghassi¹, Amol Deshmukh¹, Noelle Ibrahim¹, Nicolas Robles¹, Stefan Woerner², and Christa Zoufal^2,3

¹IBM Quantum, Yorktown Heights, NY, US
²IBM Quantum, IBM Research Europe – Zurich, Switzerland
³Institute for Theoretical Physics, ETH Zurich, Switzerland

Published:	2022-06-07, volume 6, page 730
Eprint:	arXiv:2108.10846v2
Doi:	https://doi.org/10.22331/q-2022-06-07-730
Citation:	Quantum 6, 730 (2022).

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

Abstract

We propose an algorithm based on variational quantum imaginary time evolution for solving the Feynman-Kac partial differential equation resulting from a multidimensional system of stochastic differential equations. We utilize the correspondence between the Feynman-Kac partial differential equation (PDE) and the Wick-rotated Schrödinger equation for this purpose. The results for a $(2+1)$ dimensional Feynman-Kac system obtained through the variational quantum algorithm are then compared against classical ODE solvers and Monte Carlo simulation. We see a remarkable agreement between the classical methods and the quantum variational method for an illustrative example on six and eight qubits. In the non-trivial case of PDEs which are preserving probability distributions – rather than preserving the $\ell_2$-norm – we introduce a proxy norm which is efficient in keeping the solution approximately normalized throughout the evolution. The algorithmic complexity and costs associated to this methodology, in particular for the extraction of properties of the solution, are investigated. Future research topics in the areas of quantitative finance and other types of PDEs are also discussed.

Popular summary

We consider a variational quantum algorithm based on imaginary time evolution to solve the Feynman-Kac partial differential equation induced from a system of stochastic differential equations. The correspondence between the Feynman-Kac partial differential equation and the Wick-rotated Schrödinger equation is utilized for this purpose. The VarQITE results for our Feynman-Kac system are then compared against classical ODE solvers and Monte Carlo simulation. A remarkable agreement between the classical methods and VarQITE is observed for an illustrative example on six and eight qubits with an efficient ansatz. In the non-trivial case of PDEs that preserve $\ell_1$ norms — rather than $\ell_2$ norms — we introduce a proxy norm that is efficient in keeping the solution approximately normalized throughout the evolution. The algorithmic complexity and costs associated with this methodology, in particular for the extraction of properties of the solution, are investigated. Future research topics in other types of PDEs are also discussed.

► BibTeX data

@article{Alghassi2022variationalquantum,
  doi = {10.22331/q-2022-06-07-730},
  url = {https://doi.org/10.22331/q-2022-06-07-730},
  title = {A variational quantum algorithm for the {F}eynman-{K}ac formula},
  author = {Alghassi, Hedayat and Deshmukh, Amol and Ibrahim, Noelle and Robles, Nicolas and Woerner, Stefan and Zoufal, Christa},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {730},
  month = jun,
  year = {2022}
}

► References

[1] R. P. Feynman. The principle of least action in quantum mechanics. In Feynman's Thesis—A New Approach To Quantum Theory, pages 1–69. World Scientific, 2005. Available online: https://doi.org/10.1142/9789812567635_0001.
https://doi.org/10.1142/9789812567635_0001

[2] M. Kac. On Distributions of Certain Wiener Functionals. Transactions of the American Mathematical Society, 65(1):1–13, 1949. DOI: 10.1090/S0002-9947-1949-0027960-X.
https://doi.org/10.1090/S0002-9947-1949-0027960-X

[3] F. Black and M. Scholes. The pricing of options and corporate liabilities. Journal of Political Economy, 81(3):637–654, 1973. Available online: https://doi.org/10.1086/260062.
https://doi.org/10.1086/260062

[4] J. Glimm and A. Jaffe. Quantum Physics: A Functional Integral Point of View. Springer-Verlag New York, 2012. DOI: 10.1007/978-1-4612-4728-9.
https://doi.org/10.1007/978-1-4612-4728-9

[5] J. Lörinczi, F. Hiroshima, and V. Betz. Feynman-Kac-Type Theorems and Gibbs Measures on Path Space: With Applications to Rigorous Quantum Field Theory. De Gruyter, 2011. DOI: 10.1515/9783110203738.
https://doi.org/10.1515/9783110203738

[6] A. Korzeniowski, J. Fry, D. Orr, and N. Fazleev. Feynman-Kac path-integral calculation of the ground-state energies of atoms. Phys Rev Lett, 10(69):893–896, 1992. DOI: 10.1103/PhysRevLett.69.893.
https://doi.org/10.1103/PhysRevLett.69.893

[7] M. Caffarel and P. Claverie. Development of a pure diffusion quantum Monte Carlo method using a full generalized Feynman–Kac formula. I. Formalism. The Journal of Chemical Physics, 88(2):1088–1099, 1988. DOI: 10.1063/1.454227.
https://doi.org/10.1063/1.454227

[8] P. A. Faria da Veiga, M. O'Carroll, and R. Schor. Existence of baryons, baryon spectrum and mass splitting in strong coupling lattice QCD. Commun. Math. Phys., 245:383–405, 2004. DOI: 10.1007/s00220-003-1022-2.
https://doi.org/10.1007/s00220-003-1022-2

[9] J. Gonzalez-Conde, Á. Rodríguez-Rozas, E. Solano, and M. Sanz. Pricing Financial Derivatives with Exponential Quantum Speedup. arxiv:2101.04023, 2021. DOI: 10.48550/arXiv.2101.04023.
https://doi.org/10.48550/arXiv.2101.04023
arXiv:2101.04023

[10] S. K. Radha. Quantum option pricing using Wick rotated imaginary time evolution. arXiv:2101.04280, 2021. DOI: 10.48550/arXiv.2101.04280.
https://doi.org/10.48550/arXiv.2101.04280
arXiv:2101.04280

[11] F. Fontanela, A. Jacquier, and M. Oumgari. A Quantum algorithm for linear PDEs arising in Finance. SSRN Electronic Journal, 2019. DOI: 10.2139/ssrn.3499134.
https://doi.org/10.2139/ssrn.3499134

[12] K. Kubo, Y. O. Nakagawa, S. Endo, and S. Nagayama. Variational quantum simulations of stochastic differential equations. Phys. Rev. A, 103:052425, 2021. DOI: 10.1103/PhysRevA.103.052425.
https://doi.org/10.1103/PhysRevA.103.052425

[13] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum Amplitude Amplification and Estimation. Quantum Computation and Quantum Information, Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics, 305:53–74, 2002. DOI: 10.1090/conm/305.
https://doi.org/10.1090/conm/305

[14] A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A, 471(2181), 2015. DOI: 10.1098/rspa.2015.0301.
https://doi.org/10.1098/rspa.2015.0301

[15] Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto. Amplitude Estimation without Phase Estimation. Quantum Inf Process, 19(75), 2020. DOI: 10.1007/s11128-019-2565-2.
https://doi.org/10.1007/s11128-019-2565-2

[16] D. Grinko, J. Gacon, C. Zoufal, and S. Woerner. Iterative quantum amplitude estimation. npj Quantum Information, 7:52, 2021. DOI: 10.1038/s41534-021-00379-1.
https://doi.org/10.1038/s41534-021-00379-1

[17] A. Carrera Vazquez and S. Woerner. Efficient state preparation for quantum amplitude estimation. Phys. Rev. Applied, 15:034027, 2021. DOI: 10.1103/PhysRevApplied.15.034027.
https://doi.org/10.1103/PhysRevApplied.15.034027

[18] N. Stamatopolous, 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

[19] S. Woerner and D. J. Egger. Quantum Risk Analysis. npj Quantum Information, 5(15), 2019. DOI: 10.1038/s41534-019-0130-6.
https://doi.org/10.1038/s41534-019-0130-6

[20] D. J. Egger, R. Garcia Gutierrez, J. Cahue Mestre, and S. Woerner. Credit risk analysis using quantum computers. IEEE Transactions on Computers, pages 1–1, 2020. DOI: 10.1109/TC.2020.3038063.
https://doi.org/10.1109/TC.2020.3038063

[21] S. Chakrabarti, R. Krishnakumar, G. Mazzola, N. Stamatopoulos, S. Woerner, and W. J. Zeng. A Threshold for Quantum Advantage in Derivative Pricing. Quantum, 5:463, 2021. DOI: 10.22331/q-2021-06-01-463.
https://doi.org/10.22331/q-2021-06-01-463

[22] 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, 5:481, 2021. DOI: 10.22331/q-2021-06-24-481.
https://doi.org/10.22331/q-2021-06-24-481

[23] P. Rebentrost, B. Gupt, and T. R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A, 98:022321, 2018. DOI: 10.1103/PhysRevA.98.022321.
https://doi.org/10.1103/PhysRevA.98.022321

[24] B. Oksendal. Stochastic Differential Equations. Springer, 2013. DOI: 10.1007/978-3-642-14394-6.
https://doi.org/10.1007/978-3-642-14394-6

[25] ocw.mit.edu. Lecture 21: Stochastic Differential Equations. Available online: https://ocw.mit.edu/courses/mathematics/18-s096-topics-in-mathematics-with-applications-in-finance-fall-2013/lecture-notes/MIT18_S096F13_lecnote21.pdf.
https://ocw.mit.edu/courses/mathematics/18-s096-topics-in-mathematics-with-applications-in-finance-fall-2013/lecture-notes/MIT18_S096F13_lecnote21.pdf

[26] S. Endo, J. Sun, Y. Li, S. C. Benjamin, and X. Yuan. Variational quantum simulation of general processes. Phys. Rev. Lett., 125:010501, 2020. DOI: 10.1103/PhysRevLett.125.010501.
https://doi.org/10.1103/PhysRevLett.125.010501

[27] X. Yuan, S. Endo, Q. Zhao, Y. Li, and S. C. Benjamin. Theory of variational quantum simulation. Quantum, 3(191), 2019. DOI: 10.22331/q-2019-10-07-191.
https://doi.org/10.22331/q-2019-10-07-191

[28] C. Zoufal, D. Sutter, and S. Woerner. Error Bounds for Variational Quantum Time Evolution. arXiv:2108.00022, 2021. DOI: 10.48550/arXiv.2108.00022.
https://doi.org/10.48550/arXiv.2108.00022
arXiv:2108.00022

[29] N. H. Bingham and R. Kiesel. Risk-Neutral Valuation: Pricing and Hedging Financial Derivatives. Springer-Verlag Berlin Heidelberg, 2004. DOI: 10.1007/978-1-4471-3856-3.
https://doi.org/10.1007/978-1-4471-3856-3

[30] S. Ramos-Calderer, A. Pérez-Salinas, D. García-Martín, C. Bravo-Prieto, J. Cortada, J. Planagumà, and J. I. Latorre. Quantum unary approach to option pricing. Phys. Rev. A, 103:032414, 2021. DOI: 10.1103/PhysRevA.103.032414.
https://doi.org/10.1103/PhysRevA.103.032414

[31] I. Karatzas and S. Shreve. Brownian Motion and Stochastic Calculus. Graduate Texts in Mathematics, Springer, 1984. DOI: 10.1007/978-1-4612-0949-2.
https://doi.org/10.1007/978-1-4612-0949-2

[32] M. Musiela and M. Rutkowski. Martingale Methods in Financial Modelling. Springer-Verlag Berlin Heidelberg, 2005. DOI: 10.1007/b137866.
https://doi.org/10.1007/b137866

[33] M. Baxter and A. Rennie. Financial Calculus: An introduction to derivative pricing. Cambridge University Press, 1996. DOI: 10.1017/CBO9780511806636.
https://doi.org/10.1017/CBO9780511806636

[34] E. Chin, D. Nel, and S. Olafsson. Problems and Solutions in Mathematical Finance: Stochastic Calculus. Wiley Finance Series, 2014. DOI: 10.1002/9781118845141.
https://doi.org/10.1002/9781118845141

[35] A. Papanicolaou. Introduction to Stochastic Differential Equations (SDEs) for Finance. arXiv:1504.05309, 2015. DOI: 10.48550/arXiv.1504.05309.
https://doi.org/10.48550/arXiv.1504.05309
arXiv:1504.05309

[36] P. Wilmott. Paul Wilmott On Quantitative Finance. Wiley, 2006.

[37] T. Constantinescu. Schur parameters, Dilation and Factorization Problems. Birkhauser Verlag 82, 1996. DOI: 10.1007/978-3-0348-9108-0.
https://doi.org/10.1007/978-3-0348-9108-0

[38] F. Bagarello. Susy for non-Hermitian Hamiltonians, with a view to coherent states. Math. Phys. Anal. Geom., 23(3):28, 2020. DOI: 10.1007/s11040-020-09353-3.
https://doi.org/10.1007/s11040-020-09353-3

[39] S. Dogra, A. A. Melnikov, and G. S. Paraoanu. Quantum simulation of parity–time symmetry breaking with a superconducting quantum processor. Communications Physics, 4(26), 2021. DOI: 10.1038/s42005-021-00534-2.
https://doi.org/10.1038/s42005-021-00534-2

[40] J. N. D. of Mathematics at Stanford University) math.stanford.edu/$\sim$ryzhik/STANFORD/STANF227-10/notes227-09.pdf. Partial differential equations and diffusion processes. Available online: http://math.stanford.edu/ ryzhik/STANFORD/STANF227-10/notes227-09.pdf.
http://math.stanford.edu/~ryzhik/STANFORD/STANF227-10/notes227-09.pdf

[41] S. L. D. of Statistics at University of Chicago) stat.uchicago.edu/$\sim$lalley/Courses/391/Lecture12.pdf. Stochastic Differential Equations, Diffusion Processes and the Feynman-Kac formula. Available online: http://www.stat.uchicago.edu/ lalley/Courses/391/Lecture12.pdf.
http://www.stat.uchicago.edu/~lalley/Courses/391/Lecture12.pdf

[42] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes 3rd Edition: The Art of Scientific Computing. Cambridge University Press, 2007. DOI: 10.1145/1874391.187410.
https://doi.org/10.1145/1874391.187410

[43] Y. Li and S. C. Benjamin. Efficient variational quantum simulator incorporating active error minimization. Phys. Rev. X, 7:021050, 2017. DOI: 10.1103/PhysRevX.7.021050.
https://doi.org/10.1103/PhysRevX.7.021050

[44] S. McArdle, T. Jones, S. Endo, Y. Li, S. Benjamin, and X. Yuan. Variational ansatz-based quantum simulation of imaginary time evolution. npj Quantum Information, 5(75), 2019. DOI: 10.1038/s41534-019-0187-2.
https://doi.org/10.1038/s41534-019-0187-2

[45] A. D. McLachlan. A variational solution of the time-dependent Schrödinger equation. Molecular Physics, 8(1), 1964. DOI: 10.1080/00268976400100041.
https://doi.org/10.1080/00268976400100041

[46] G. M. D'Ariano, M. G. Paris, and M. F. Sacchi. Quantum tomography. Advances in Imaging and Electron Physics, 128:206–309, 2003. DOI: 10.1016/S1076-5670(03)80065-4.
https://doi.org/10.1016/S1076-5670(03)80065-4

[47] L. C. Evans. Partial Differential Equations. American Mathematical Society, 1998. DOI: 10.1112/blms/20.4.375.
https://doi.org/10.1112/blms/20.4.375

[48] J. Solomon, L. Guibas, and A. Butscher. Dirichlet energy for analysis and synthesis of soft maps. In Computer Graphics Forum, volume 32, pages 197–206. Wiley Online Library, 2013. DOI: 10.1111/cgf.12186.
https://doi.org/10.1111/cgf.12186

[49] K. Zhou, X. Huang, D. Zha, R. Chen, L. Li, S.-H. Choi, and X. Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34, 2021. DOI: 10.48550/arXiv.2107.02392.
https://doi.org/10.48550/arXiv.2107.02392

[50] O. Stein, M. Wardetzky, A. Jacobson, and E. Grinspun. A simple discretization of the vector dirichlet energy. In Computer Graphics Forum, volume 39, pages 81–92. Wiley Online Library, 2020. DOI: 10.1111/cgf.14070.
https://doi.org/10.1111/cgf.14070

[51] O. Stein, A. Jacobson, M. Wardetzky, and E. Grinspun. A smoothness energy without boundary distortion for curved surfaces. ACM Transactions on Graphics (TOG), 39(3):1–17, 2020. DOI: 10.1145/3377406.
https://doi.org/10.1145/3377406

[52] G. Sussmann. Uncertainty Relation: From Inequality to Equality. Zeitschrift fur Naturforschung A, 1997. DOI: 10.1515/zna-1997-1-214.
https://doi.org/10.1515/zna-1997-1-214

[53] X. Li, G. Yang, C. M. Torres, D. Zheng, and K. L. Wang. A Class of Efficient Quantum Incrementer Gates for Quantum Circuit Synthesis. International Journal of Modern Physics B, 28(1), 2014. DOI: 10.1142/S0217979213501919.
https://doi.org/10.1142/S0217979213501919

[54] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2012. DOI: 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[55] L. Grover and T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:0208112, 2002. DOI: 10.48550/arXiv.quant-ph/0208112.
https://doi.org/10.48550/arXiv.quant-ph/0208112
arXiv:0208112

[56] A. Carrera Vazquez, R. Hiptmair, and S. Woerner. Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation. arXiv:2009.04484, 2020. DOI: 10.1063/1.454227.
https://doi.org/10.1063/1.454227
arXiv:2009.04484

[57] N. Berline, E. Getzler, and M. Vergne. Heat Kernels and Dirac Operators. Springer-Verlag Berlin Heidelberg, 2004.

[58] P. DuChateau and D. W. Zachmann. Schaum's outlines: partial differential equations. McGraw-Hill, 1986. DOI: 10.1007/978-1-4612-0949-2.
https://doi.org/10.1007/978-1-4612-0949-2

[59] qiskit.org/documentation/stubs/qiskit.circuit.library.RealAmplitudes.html. qiskit.circuit.library.realamplitudes, 2021. Available online: qiskit.org.
http://qiskit.org

[60] A. Hayashi, T. Hashimoto, and M. Horibe. Reexamination of optimal quantum state estimation of pure states. Physical Review A, 72(3), 2005. DOI: 10.1103/PhysRevA.72.032325.
https://doi.org/10.1103/PhysRevA.72.032325

[61] A. Ambainis and J. Emerson. Quantum t-designs: t-wise Independence in the Quantum World. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007. DOI: 10.1109/CCC.2007.26.
https://doi.org/10.1109/CCC.2007.26

[62] J. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9, 2018. DOI: 10.1038/s41467-018-07090-4.
https://doi.org/10.1038/s41467-018-07090-4

[63] J. Vecer. A New PDE Approach for Pricing Arithmetic Average Asian Options. Journal of Computational Finance, 4(4), 2001. DOI: 10.21314/JCF.2001.064.
https://doi.org/10.21314/JCF.2001.064

[64] R. C. Dalang, C. Mueller, and R. Tribe. A Feynman-Kac Type Formula for the deterministic and stochastic wave equations and other PDEs. Transactions of the American Mathematical Society, 360(9):4681–4703, 2008. DOI: 10.1090/S0002-9947-08-04351-1.
https://doi.org/10.1090/S0002-9947-08-04351-1

[65] R. Brummelhuis. Mathematical Methods - MSc Financial Engineering - Birbeck College, 2004. Available online: http://www.cato.tzo.com/brad_bbk/teaching/Methods/old_methods_notes_RB.pdf.
http://www.cato.tzo.com/brad_bbk/teaching/Methods/old_methods_notes_RB.pdf

[66] V. V. Shende, S. S. Bullock, and I. L. Markov. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6), 2006. DOI: 10.1109/TCAD.2005.855930.
https://doi.org/10.1109/TCAD.2005.855930

[67] C. Zoufal, A. Lucchi, and S. Woerner. Quantum Generative Adversarial Networks for learning and loading random distributions. npj Quantum Information, 5(103), 2019. DOI: 10.1038/s41534-019-0223-2.
https://doi.org/10.1038/s41534-019-0223-2

[68] F. Oberhettinger. Tables of Mellin Transforms. Springer-Verlag Berlin Heidelberg, 1974. DOI: 10.1007/978-3-642-65975-1.
https://doi.org/10.1007/978-3-642-65975-1

[69] E. Knill, G. Ortiz, and R. D. Somma. Optimal quantum measurements of expectation values of observables. Phys. Rev. A, 75:012328, 2007. DOI: 10.1103/PhysRevA.75.012328.
https://doi.org/10.1103/PhysRevA.75.012328

[70] D. Wang, O. Higgott, and S. Brierley. Accelerated variational quantum eigensolver. Phys. Rev. Lett., 122:140504, 2019. DOI: 10.1103/PhysRevLett.122.140504.
https://doi.org/10.1103/PhysRevLett.122.140504

Cited by

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

[2] Tianchen Zhao, Chuhao Sun, Asaf Cohen, James Stokes, and Shravan Veerapaneni, "Quantum-inspired variational algorithms for partial differential equations: Application to financial derivative pricing", arXiv:2207.10838, (2022).

[3] Mitsuharu Takeori, Takahiro Yamamoto, Ryutaro Ohira, and Shungo Miyabe, "A Gauss-Newton based Quantum Algorithm for Combinatorial Optimization", arXiv:2203.13939, (2022).

[4] Christa Zoufal, "Generative Quantum Machine Learning", arXiv:2111.12738, (2021).

[5] Oleksandr Kyriienko, Annie E. Paine, and Vincent E. Elfving, "Protocols for Trainable and Differentiable Quantum Generative Modelling", arXiv:2202.08253, (2022).

[6] 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 SAO/NASA ADS (last updated successfully 2023-03-31 08:18:33). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-03-31 08:18:31).

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.