arXiv:2609.27103
Quantum-Enhanced Sampling of Schrödinger Bridges
Tom Lollier, Eyal Neuman
Abstract
We consider the dynamic Schrödinger bridge problem on a finite state space and exploit its Markov structure to decompose the problem into an endpoint coupling and a collection of conditional Markov bridges. To sample from the conditional bridges, we develop a quantum Gibbs sampler based on quantum walks on the bridge path space. Under uniformly positive transition probabilities, we derive a spectral-gap bound and provide an explicit procedure for preparing the initial state. Compared with the update bounds of the corresponding classical Gibbs sampler, our quantum walk-query complexity improves the dependence on the time horizon $T$ from quadratic to linear. For the endpoint coupling, we adapt a quantum box-constrained Newton method to compute the Schrödinger potentials, improving the matrix-scaling complexity, at fixed accuracy, from quadratic to $N^{3/2}$ in the state-space size $N$. Finally, we show that exponential reweighting extends both the Schrödinger bridge formulation and the Gibbs spectral-gap estimate to models with additive running costs.
AI Summary
The paper studies quantum algorithms for sampling finite-state dynamic Schrödinger bridges: path distributions minimising relative entropy to a reference Markov law subject to prescribed endpoint marginals. It uses the standard decomposition into an optimal endpoint coupling and reference trajectories conditioned on their endpoints. For conditional trajectories, it analyses random single-coordinate Gibbs updates, whose conditional distributions depend only on neighbouring states. Assuming $P(i,j)\ge\omega_-/N$, a canonical-path argument establishes the spectral-gap bound $\delta\ge\omega_-^4/(T^2N^3)$. Coherent forward simulation prepares an initial state with overlap at least $\sqrt{\omega_-/N}$ with the target. Quantum-walk spectral filtering and amplitude amplification then give a heralded sampler with total-variation error $\varepsilon$, using $O(TN^2\omega_-^{-5/2}\log[N/(\omega_-\varepsilon)])$ walk-primitive calls, plus $O(T\sqrt{N/\omega_-})$ coherent reference-transition calls. For the endpoint coupling, an existing quantum box-constrained Newton matrix-scaling algorithm computes logarithmic potentials in $\widetilde O(B^2N^{3/2}/\varepsilon^2)$ time. An objective-gap identity and Pinsker’s inequality provide coupling-error guarantees; under uniform positivity, $B=O(\log(N/\omega_-))$. Endpoint sampling requires another $O(N)$ operations. The horizon comparison is against a particular classical Gibbs bound, not optimal classical sampling: direct rejection sampling already takes at most $TN/\omega_-$ expected forward transitions. Coherent-update implementation costs and construction of the endpoint-kernel oracle are excluded; endpoint computation assumes exact-entry access and QCRAM. Exponential reweighting incorporates additive running costs and yields $\delta_g\ge\omega_-^4e^{-\Delta_g}/(T^2N^3)$, but an example shows exponentially small initial overlap despite fixed cost range, preventing a general speedup guarantee.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 59 pages, 1 figure