A variational quantum algorithm for the Feynman-Kac formula

Hedayat Alghassi1, Amol Deshmukh1, Noelle Ibrahim1, Nicolas Robles1, Stefan Woerner2, and Christa Zoufal2,3

1IBM Quantum, Yorktown Heights, NY, US
2IBM Quantum, IBM Research Europe – Zurich, Switzerland
3Institute for Theoretical Physics, ETH Zurich, Switzerland

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


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.

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

► 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.

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

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

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

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

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

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

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

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

[10] S. K. Radha. Quantum option pricing using Wick rotated imaginary time evolution. arXiv:2101.04280, 2021. DOI: 10.48550/​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.

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

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

[14] A. Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A, 471(2181), 2015. DOI: 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.

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

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

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

[19] S. Woerner and D. J. Egger. Quantum Risk Analysis. npj Quantum Information, 5(15), 2019. DOI: 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.

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

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

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

[24] B. Oksendal. Stochastic Differential Equations. Springer, 2013. DOI: 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.

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

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

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

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

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

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

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

[33] M. Baxter and A. Rennie. Financial Calculus: An introduction to derivative pricing. Cambridge University Press, 1996. DOI: 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.

[35] A. Papanicolaou. Introduction to Stochastic Differential Equations (SDEs) for Finance. arXiv:1504.05309, 2015. DOI: 10.48550/​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.

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

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

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

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

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

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

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

[45] A. D. McLachlan. A variational solution of the time-dependent Schrödinger equation. Molecular Physics, 8(1), 1964. DOI: 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.

[47] L. C. Evans. Partial Differential Equations. American Mathematical Society, 1998. DOI: 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.

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

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

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

[52] G. Sussmann. Uncertainty Relation: From Inequality to Equality. Zeitschrift fur Naturforschung A, 1997. DOI: 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.

[54] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2012. DOI: 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.

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

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

[59] qiskit.org/​documentation/​stubs/​qiskit.circuit.library.RealAmplitudes.html. qiskit.circuit.library.realamplitudes, 2021. Available online: 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.

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

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

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

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

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

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

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

[68] F. Oberhettinger. Tables of Mellin Transforms. Springer-Verlag Berlin Heidelberg, 1974. DOI: 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.

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

Cited by

[1] N. M. Guseynov, A. A. Zhukov, W. V. Pogosov, and A. V. Lebedev, "Depth analysis of variational quantum algorithms for the heat equation", Physical Review A 107 5, 052422 (2023).

[2] Koichi Miyamoto and Hiroshi Ueda, "Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion", Quantum Information Processing 22 6, 239 (2023).

[3] Fong Yew Leong, Dax Enshan Koh, Wei-Bin Ewe, and Jian Feng Kong, "Variational quantum simulation of partial differential equations: applications in colloidal transport", International Journal of Numerical Methods for Heat & Fluid Flow 33 11, 3669 (2023).

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

[5] Fong Yew Leong, Dax Enshan Koh, Jian Feng Kong, Siong Thye Goh, Jun Yong Khoo, Wei-Bin Ewe, Hongying Li, Jayne Thompson, and Dario Poletti, "Solving fractional differential equations on a quantum computer: A variational approach", AVS Quantum Science 6 3, 033802 (2024).

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

[7] Xi Wang, Jun Jiang, Ling Hong, and Jian-Qiao Sun, "A novel method for response probability density of nonlinear stochastic dynamic systems", Nonlinear Dynamics (2024).

[8] Salvatore Certo, Anh Pham, Nicolas Robles, and Andrew Vlasic, "Conditional generative models for learning stochastic processes", Quantum Machine Intelligence 5 2, 42 (2023).

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

[10] Sachin Kasture, Oleksandr Kyriienko, and Vincent E. Elfving, "Protocols for classically training quantum generative models on probability distributions", Physical Review A 108 4, 042406 (2023).

[11] Tianchen Zhao, Chuhao Sun, Asaf Cohen, James Stokes, and Shravan Veerapaneni, "Quantum-inspired variational algorithms for partial differential equations: application to financial derivative pricing", Quantitative Finance 24 1, 1 (2024).

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

[13] Muhammad Zafarullah Baber, Nauman Ahmed, Changjin Xu, Muhammad Sajid Iqbal, and Tukur Abdulkadir Sulaiman, "A computational scheme and its comparison with optical soliton solutions for the stochastic Chen–Lee–Liu equation with sensitivity analysis", Modern Physics Letters B 2450376 (2024).

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

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

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

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

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

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

[20] Nam Nguyen and Richard Thompson, "Solving Maxwells Equations using Variational Quantum Imaginary Time Evolution", arXiv:2402.14156, (2024).

[21] Swagat Kumar and Colin Michael Wilmott, "Simulating the non-Hermitian dynamics of financial option pricing with quantum computers", arXiv:2407.01147, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 15:20:16) and SAO/NASA ADS (last updated successfully 2024-07-15 15:20:22). The list may be incomplete as not all publishers provide suitable and complete citation data.