# Quantum-Enhanced Sampling of Schr"odinger Bridges

arXiv: https://arxiv.org/abs/2609.27103 · HTML: https://mlsanity.com/paper/2609.27103/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2026.

## Built on by (most cited first, 1 of 1)

- [Cost-augmented Schr"odinger bridges on graphs are exactly solvable: a Feynman-Kac tilt replaces learned control](https://mlsanity.com/paper/2610.02195/) (2026)

## Abstract (arXiv)

We consider the dynamic Schr"odinger 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"odinger potentials, improving the matrix-scaling complexity, at fixed accuracy, from quadratic to N3/2 in the state-space size N. Finally, we show that exponential reweighting extends both the Schr"odinger bridge formulation and the Gibbs spectral-gap estimate to models with additive running costs.