Technical Summary: Quantum-Enhanced Sampling of Schrödinger Bridges

Problem Statement

The paper addresses the dynamic Schrödinger bridge problem on a finite state space $\chi$ of size $N$. Given a reference Markov process $P$ with transition kernel $P$ and prescribed initial and terminal distributions $\mu_0$ and $\mu_T$, the goal is to find a path measure $Q^*$ that minimizes the relative entropy (Kullback–Leibler divergence) $KL(Q \| P)$ subject to the marginal constraints $Q_0 = \mu_0$ and $Q_T = \mu_T$.

The problem is decomposed into two distinct computational tasks:

1. Endpoint Coupling: Computing the optimal joint distribution $Q^*_{0,T}$ of the endpoints $(X_0, X_T)$. This reduces to a static Schrödinger bridge problem, solvable via matrix scaling (finding Schrödinger potentials $\phi^\circ, \phi^*$).
2. Conditional Path Sampling: Sampling a trajectory $x_{0:T}$ from the reference Markov bridge $P(\cdot | X_0=a, X_T=b)$ conditioned on a specific endpoint pair $(a, b)$ drawn from $Q^*_{0,T}$.

The paper also extends this framework to include additive running costs, where the objective function includes an expected accumulated cost term $\mathbb{E}_Q[\sum g(X_t)]$.

Methodology

The authors propose a hybrid quantum-classical approach, leveraging specific quantum algorithms for each component of the decomposition.

1. Quantum Matrix Scaling for Endpoint Coupling

To compute the Schrödinger potentials, the authors adapt a quantum box-constrained Newton method (based on Gribling and Nieuwboer [14]).

• Formulation: The problem is cast as minimizing a convex potential function $f(x, y)$ involving logarithmic scaling variables.
• Quantum Acceleration: The algorithm utilizes quantum amplitude estimation to approximate gradients and quantum graph sparsification to construct sparse Hessian approximations.
• Access Model: The method assumes coherent entry-query access to the reference endpoint matrix $P_{0,T}$ and the marginals.

2. Quantum Gibbs Sampler for Conditional Path Sampling

To sample trajectories from the conditional Markov bridge $P_{a,b}$, the authors develop a quantum Gibbs sampler based on quantum walks.

• Classical Baseline: A classical Gibbs sampler updates one interior coordinate at a time, resampling it from the conditional distribution given its neighbors. The convergence rate depends on the spectral gap $\delta$ of the Gibbs kernel.
• Quantum Construction:
  • The authors construct a projected unitary encoding (PUE) of the Gibbs kernel $K$.
  • They define a quantum walk $W$ on the path space. Due to the spectral properties of quantum walks, a spectral gap $\delta$ in the classical kernel translates to a phase gap of order $\sqrt{\delta}$ in the quantum walk.
  • Amplitude Amplification: An initial state is prepared by simulating the reference chain for $T-1$ steps and fixing the final endpoint. This state has a known overlap with the target stationary state. Amplitude amplification is used to boost the probability of projecting onto the stationary state.
  • Projector Approximation: A polynomial approximation of the projector onto the stationary state is implemented using quantum singular value transformation (or quantum signal processing) techniques.

3. Extension to Additive Costs

For problems with running costs $g$, the authors show that the problem can be transformed into a standard Schrödinger bridge with a reweighted reference law $\tilde{V}$.

• The reweighting involves exponential factors $e^{-g(x_t)}$.
• The spectral gap analysis for the weighted Gibbs kernel is adjusted to account for the cost range $\Delta_g = \max g - \min g$, introducing a factor of $e^{-\Delta_g}$ in the gap lower bound.

Key Contributions and Results

1. Spectral Gap Bounds for Markov Bridges

The paper establishes a lower bound on the spectral gap $\delta$ of the classical Gibbs sampler on the path space of a Markov bridge:
$$\delta \geq \frac{\omega_-^4}{T^2 N^3}$$
where $\omega_-$ is a uniform positivity parameter for the transition kernel. This bound is derived using the canonical paths method. Crucially, this result holds despite the path space size being exponential ($N^{T-1}$), providing the necessary quantitative input for the quantum speedup analysis.

2. Quantum Speedup in Sampling Complexity

The quantum Gibbs sampler achieves a linear dependence on the time horizon $T$, compared to the quadratic dependence of the classical Gibbs sampler.

• Classical Complexity: $O\left( \frac{T^2 N^3}{\omega_-^4} \log \frac{N}{\omega_- \epsilon} \right)$ updates.
• Quantum Complexity: $O\left( \frac{T N^2}{\omega_-^{5/2}} \log \frac{N}{\omega_- \epsilon} \right)$ calls to walk primitives.
• Mechanism: The improvement stems from the square-root dependence on the spectral gap ($\delta^{-1/2}$ vs $\delta^{-1}$) inherent in quantum walk-based sampling.

3. Quantum Speedup in Matrix Scaling

For computing the endpoint coupling, the quantum box-constrained Newton method improves the dependence on the state-space size $N$:

• Classical Complexity: $\tilde{O}(B N^2)$ (where $B$ bounds the potentials).
• Quantum Complexity: $\tilde{O}(B^2 N^{3/2} / \epsilon^2)$.
• Mechanism: This improvement arises from the use of quantum amplitude estimation and sparsification, reducing the matrix-scaling complexity from quadratic to $N^{3/2}$ at fixed accuracy.

4. Handling Running Costs

The paper provides a rigorous analysis of how additive costs affect the sampling process. While the spectral gap bound degrades by a factor of $e^{-\Delta_g}$, the authors highlight a critical initialization challenge: if the initial state does not account for the running cost, the overlap with the target state may decay exponentially with $T$. The paper notes that while the quantum method retains its square-root improvement in the spectral gap, the overall speedup is contingent on the initial overlap $c_g$ and the cost range $\Delta_g$.

Significance and Claims

The paper claims to provide a complete quantum-enhanced sampling framework for dynamic Schrödinger bridges. Its significance lies in:

1. Decomposition Strategy: It successfully separates the problem into endpoint coupling and conditional path sampling, applying the most suitable quantum algorithm to each.
2. Explicit Complexity Bounds: It provides explicit, non-asymptotic bounds on the query complexity for both components, distinguishing between the number of oracle calls and total computational time.
3. Modest Speedup Claims: The authors are careful to note that the linear dependence on $T$ for the quantum sampler is a specific improvement over the local Gibbs classical sampler. They do not claim an unconditional quadratic speedup over all classical bridge samplers (e.g., direct rejection sampling might have different scaling). Similarly, the matrix scaling speedup is conditional on specific input access models (coherent entry queries) and the assumption that the endpoint kernel $P_{0,T}$ can be efficiently constructed.
4. Initialization Sensitivity: The paper explicitly warns that for problems with running costs, the "quantum speedup" is not guaranteed if the initial state preparation is standard, as the overlap with the target state can vanish exponentially. This highlights a practical constraint on the applicability of the quantum method in cost-sensitive scenarios.

In summary, the paper demonstrates that by exploiting the Markov structure of Schrödinger bridges, one can achieve polynomial improvements in state-space size ($N$) and time-horizon ($T$) dependencies using quantum walks and quantum matrix scaling, provided specific access assumptions and initialization conditions are met.