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
• 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

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation [3.3636842548621275]
  A central test case for quantum linear system algorithms (QLSA) is elliptic PDEs after a finite element discretization.<n>We present a multilevel framework for this readout problem, motivated by the variance-reduction mechanism of multilevel Monte Carlo.<n>Our algorithm is based on Schur-complement factorization of the corrected Green's operator through a Ritz-complement map.
  arXiv  Detail & Related papers  (2026-05-31T14:47:58Z)
• Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems [0.007807026251125201]
  We present an efficient, nearly optimal quantum algorithm for solving linear matrix differential equations.<n>For unitary or dissipative dynamics, the algorithm computes an entry of the solution matrix with query $widetildemathcalO(mathcalL t/)$.<n>We demonstrate the utility of the algorithm through an end-to-end application, namely the simulation of dissipative dynamics for non-interacting fermions.
  arXiv  Detail & Related papers  (2026-05-15T17:11:07Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Quantum Algorithms for Finite-horizon Markov Decision Processes [40.812944518646006]
  We design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs)<n>In the exact dynamics setting, we prove that our $textbfQVI-1$ algorithm achieves a quadratic speedup in the size of the action space $(A)$.<n>In the generative model setting, we prove that our algorithms $textbfQVI-3$ and $textbfQVI-4$ achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm.
  arXiv  Detail & Related papers  (2025-08-07T09:00:23Z)
• Quantum simulation of a noisy classical nonlinear dynamics [2.0065923589074735]
  We present an end-to-end quantum algorithm for simulating nonlinear dynamics described by a system of dissipative differential equations with a quadratic nonlinearity.<n>Our algorithm can approximate the expected value of any correlation function that depends on $O(1)$ variables with rigorous approximation error.<n>To the best of our knowledge, this is the first rigorous quantum algorithm capable of simulating strongly nonlinear systems with $Jgg lambda$ at the cost poly-logarithmic in $N$ and in $t$.
  arXiv  Detail & Related papers  (2025-07-08T17:25:40Z)
• 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.