Quantum-Enhanced Sampling of Schr"odinger Bridges

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.