Xiantao Li

We present quantum speedups for sampling from probability distributions of the form $\pi \propto e^{-f}$, where $f:\mathbb{R}^d\mapsto \mathbb{R}$. We consider two oracle models: (i) a stochastic gradient oracle, where $f$ is in finite sum form, i.e., \(f(x)=\frac{1}{n}\sum_{i=1}^n f_i(x)\) and individual component gradients are accessible, (ii) a stochastic zeroth-order oracle, where only noisy evaluations of \(f\) are available. Our main contribution is a general framework for quantumly accelerating classical stochastic sampling algorithms, such as Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC), by replacing stochastic gradient computations with variance-controlled quantum mean and gradient estimation subroutines. In contrast to prior quantum sampling approaches based on quantum walks, our methods do not require reversibility or exact gradient access, and preserve the structure of the underlying (possibly nonreversible) Markov chain. In the stochastic gradient oracle model, we integrate unbiased quantum mean estimation with classical variance-reduction techniques, including stochastic variance-reduced gradients (SVRG) and control variates (CV). By jointly optimizing the target variance of quantum estimators and the frequency of full-gradient recomputation, we obtain provable improvements in gradient query complexity over the best known classical samplers. These results apply both to strongly log-concave and to non-logconcave distributions satisfying a log-Sobolev inequality, with convergence guarantees in Wasserstein distance and Kullback--Leibler divergence. In the stochastic zeroth-order model, we develop new quantum gradient estimation procedures that are robust to noisy and potentially unbounded function evaluations. These estimators lead to improved evaluation complexity for quantum-accelerated LMC and HMC under standard smoothness assumptions. Finally, we show that faster quantum sampling yields quantum speedups for optimization, including nonsmooth and approximately convex objectives. This recovers known quantum advantages for finite-sum optimization and establishes new improvements in the zeroth-order stochastic setting.

The motivating question for this work is how to efficiently estimate the expected value of an observable when the system undergoes a small and time-dependent perturbation. When the underlying system is a Markovian open quantum system, well-established quantum regression theorem (QRT) and linear response theory (LRT) are powerful tools for this task; however, QRT and LRT failed to work beyond the Markovian regime. In this paper, we first develop a novel formulation of linear response functions for open quantum systems that extends the standard QRT beyond the Markov limit. In addition, we present efficient quantum algorithms for estimating such response functions whose cost scales poly-logarithmically in the system dimension and $1/\epsilon^{1+o(1)}$ in the target accuracy $\epsilon$. The framework removes the separability (Born-Markov) assumption and offers a pathway to efficient computation of nonequilibrium properties from open quantum systems.

We present a universal framework for simulating $N$-dimensional linear It\^o stochastic differential equations (SDEs) on quantum computers with additive or multiplicative noises. Building on a unitary dilation technique, we establish a rigorous correspondence between the general linear SDE \[ dX_t = A(t) X_t\,dt + \sum_{j=1}^J B_j(t)X_t\,dW_t^j \] and a Stochastic Schr\"odinger Equation (SSE) on a dilated Hilbert space. Crucially, this embedding is pathwise exact: the classical solution is recovered as a projection of the dilated quantum state for each fixed noise realization. We demonstrate that the resulting SSE is {naturally implementable} on digital quantum processors, where the stochastic Wiener increments correspond directly to measurement outcomes of ancillary qubits. Exploiting this physical mapping, we develop two algorithmic strategies: (1) a trajectory-based approach that uses sequential weak measurements to realize efficient stochastic integrators, including a second-order scheme, and (2) an ensemble-based approach that maps moment evolution to a deterministic Lindblad quantum master equation, enabling simulation without Monte Carlo sampling. We provide error bounds based on a stochastic light-cone analysis and validate the framework with numerical simulations.