Quantum algorithm for solving McKean-Vlasov stochastic differential equations

• URL: http://arxiv.org/abs/2507.10926v1
• Date: Tue, 15 Jul 2025 02:33:33 GMT
• Title: Quantum algorithm for solving McKean-Vlasov stochastic differential equations
• Authors: Koichi Miyamoto,
• Abstract summary: QMCI is a quantum algorithm for calculating expectations that provides a quadratic speed-up compared to its classical counterpart.<n>We propose the first application of QMCI to solving differential equations (MVSDEs)<n>MVSDEs are a nonlinear class of SDEs whose drift and diffusion coefficients depend on the law $mu_t$ of the solution $X_t$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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}[\varphi_k(X_t)]$, and the goal is to compute the expectation of a function $\mathbb{E}[\phi(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}[\phi(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.

Related papers

• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.46664938579243576]
  We prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation algorithm.<n>Our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost.
  arXiv  Detail & Related papers  (2025-06-25T18:50:44Z)
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
  Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables.<n>In this paper, we propose a method to divide $U_X(t)$ based on orthogonal series density estimation.<n>Our method achieves the circuit depth and total query complexity scaling as $O(sqrtN)$ and $O(N3/2)$, respectively.
  arXiv  Detail & Related papers  (2024-06-04T01:50:21Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• An Improved Classical Singular Value Transformation for Quantum Machine Learning [2.3326951882644553]
  We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. Our key insight is to combine the Clenshaw recurrence, an iterative method for computing matrix stability, with sketching techniques to simulate QSVT classically.
  arXiv  Detail & Related papers  (2023-03-02T18:53:03Z)
• Correspondence between open bosonic systems and stochastic differential equations [77.34726150561087]
  We show that there can also be an exact correspondence at finite $n$ when the bosonic system is generalized to include interactions with the environment. A particular system with the form of a discrete nonlinear Schr"odinger equation is analyzed in more detail.
  arXiv  Detail & Related papers  (2023-02-03T19:17:37Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  This work sharpens the sample complexity of synchronous Q-learning to an order of $frac|mathcalS|| (1-gamma)4varepsilon2$ for any $0varepsilon 1$. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage.
  arXiv  Detail & Related papers  (2021-02-12T14:22:05Z)
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics [0.0]
  We present a digital quantum algorithm to solve Black-Scholes equation on a quantum computer by mapping it to the Schr"odinger equation. The algorithm shows a feasible approach for using efficient Hamiltonian simulation techniques as Quantum Signal Processing.
  arXiv  Detail & Related papers  (2021-01-11T16:54:53Z)
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance [1.128265591164748]
  We study quantum algorithms for differential equations (SDEs) We provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance.
  arXiv  Detail & Related papers  (2020-12-11T12:34:55Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.