Quantum algorithm for solving McKean-Vlasov stochastic differential equations

Abstract

Quantum Monte Carlo integration, a quantum algorithm for calculating expectations that provides a quadratic speed-up compared to its classical counterpart, is now attracting increasing interest in the context of its industrial and scientific applications. In this paper, we propose the first application of QMCI to solving McKean-Vlasov stochastic differential equations (MVSDEs), a nonlinear class of SDEs whose drift and diffusion coefficients depend on the law ${\mu }_t$ of the solution $X_t$ -- appearing in fields such as finance and fluid mechanics. We focus on the problem setting where the coefficients depend on ${\mu }_t$ through expectations of some functions $\mathbb{E}[{\phi }_k(X_t)]$, and the goal is to compute the expectation of a function $\mathbb{E}[\varphi (X_T)]$ at a terminal time $T$. We devise a quantum algorithm that leverages QMCI to compute these expectations, combined with a high-order time discretization method for SDEs and extrapolation of the expectations in time. The proposed algorithm estimates $\mathbb{E}[\varphi (X_T)]$ with accuracy $\epsilon$, making $O(1/{\epsilon }^{1+2/p})$ queries to the quantum circuit for time evolution over one step, where $p\in (1,2]$ is the weak order of the SDE discretization method. This demonstrates the speed-up over the well-known classical algorithm called the particle method with complexity of $O(1/{\epsilon }^3)$. We conduct a numerical demonstration of our quantum algorithm applied to an example of MVSDEs, with some parts emulated classically, and observe that the accuracy and complexity behave as expected.

36 pages, 8 figures

References in corpus (14)

• Quantum Amplitude Amplification and Estimation
• Quantum speedup of Monte Carlo methods
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Creating superpositions that correspond to efficiently integrable probability distributions
• Amplitude estimation without phase estimation
• Option Pricing using Quantum Computers
• Black-box quantum state preparation without arithmetic
• A Threshold for Quantum Advantage in Derivative Pricing
• Rooted Tree Analysis for Order Conditions of Stochastic Runge-Kutta Methods for the Weak Approximation of Stochastic Differential Equations
• Quantum algorithms for approximate function loading
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Preparing Arbitrary Continuous Functions in Quantum Registers With Logarithmic Complexity
• Everything You Always Wanted to Know About Quantum Circuits
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation