Quantum-Enhanced Sampling of Schr\"odinger Bridges
En palabras de los autores
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 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 in the state-space size . 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.
Apareció: jueves, 24 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 59 pages, 1 figure