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.
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 N3/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.
Szegedy's quantum walk quadratically accelerates reversible classical Markov chains, but extending this mechanism to efficiently implementable quantum Gibbs samplers has remained challenging beyond special classes. We present a walk-free quantum algorithm for preparing purified Gibbs states with a quadratic improvement in spectral-gap dependence for a broad class of quantum Gibbs samplers that satisfy exact Kubo-Martin-Schwinger detailed balance. Our main structural result is an explicit factorization of the corresponding parent Hamiltonian into noncommutative first-order operators. This turns purified Gibbs-state preparation into a singular-value filtering problem and enables a quantum singular value transformation algorithm with quadratically improved gap dependence under standard coherent-access and warm-start assumptions. The framework applies to several efficiently implementable Gibbs samplers beyond the Davies setting. Moreover, we construct noncommuting Hamiltonians with efficiently preparable warm starts whose refinement under quantum Gibbs samplers requires exponential time. For these models, our algorithm achieves an end-to-end quantum speedup over the worst-case mixing scale.
We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in Nβ/Z and polynomial in log(1/ε), where N is the Hilbert space dimension, β is the inverse temperature, Z is the partition function, and ε is the desired precision of the output state. Our quantum algorithm exponentially improves the dependence on 1/ε and quadratically improves the dependence on β of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix P, it runs in time almost linear in 1/(εΔ3/2), where ε is the absolute precision in the estimation and Δ is a parameter determined by P, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the dependence on 1/ε and 1/Δ of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.
We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in p Nβ/Z and polynomial in log(1/epsilon), where N is the Hilbert space dimension, β is the inverse temperature, Z is the partition function, and epsilon is the desired precision of the output state. Our quantum algorithm exponentially improves the complexity dependence on 1/epsilon and polynomially improves the dependence on β of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix P, it runs in time almost linear in 1/(epsilon ∆3/2 ), where epsilon is the absolute precision in the estimation and ∆ is a parameter determined by P, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the complexity dependence on 1/epsilon and 1/∆ of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.
We develop a rigorous and implementable framework for Gibbs sampling of infinite-dimensional quantum systems governed by unbounded Hamiltonians. Extending dissipative Gibbs samplers beyond finite dimensions raises fundamental obstacles, including ill-defined generators, the absence of spectral gaps on natural Banach spaces, and tensions between implementability and convergence guarantees. We overcome these issues by constructing KMS-symmetric quantum Markov semigroups on separable Hilbert spaces that are both well-posed and efficiently implementable on qubit hardware. Our generation theory is based on the abstract framework of Dirichlet forms, adapted here to the case of algebras of bounded operators over separable Hilbert spaces. Leveraging the spectral properties of our self-adjoint generators, we establish quantitative convergence results in trace distance, including regimes of fast thermalization. In contrast, we also identify Hamiltonians for which a naive choice of generators guaranteeing implementability generally comes at the cost of losing uniform exponential convergence guarantees for the associated evolutions, thereby establishing a strong trade-off between implementability and convergence. Our framework applies to a wide class of models - including Schrödinger operators, Gaussian systems, and Bose-Hubbard Hamiltonians - and provides a unified approach linking rigorous infinite-dimensional analysis with algorithmic Gibbs state preparation.
We show how to obtain perfect samples from a quantum Gibbs state on a quantum computer. To do so, we adapt one of the ``Coupling from the Past''-algorithms proposed by Propp and Wilson. The algorithm has a probabilistic run-time and produces perfect samples without any previous knowledge of the mixing time of a quantum Markov chain. To implement it, we assume we are able to perform the phase estimation algorithm for the underlying Hamiltonian and implement a quantum Markov chain such that the transition probabilities between eigenstates only depend on their energy. We provide some examples of quantum Markov chains that satisfy these conditions and analyze the expected run-time of the algorithm, which depends strongly on the degeneracy of the underlying Hamiltonian. For Hamiltonians with highly degenerate spectrum, it is efficient, as it is polylogarithmic in the dimension and linear in the mixing time. For non-degenerate spectra, its runtime is essentially the same as its classical counterpart, which is linear in the mixing time and quadratic in the dimension, up to a logarithmic factor in the dimension. We analyze the circuit depth necessary to implement it, which is proportional to the sum of the depth necessary to implement one step of the quantum Markov chain and one phase estimation. This algorithm is stable under noise in the implementation of different steps. We also briefly discuss how to adapt different ``Coupling from the Past''-algorithms to the quantum setting.
In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment's dynamics (i.e., transition probabilities), we prove that our Quantum Value Iteration (QVI) algorithm QVI-1 achieves a quadratic speedup in the size of the action space (A) compared with the classical value iteration algorithm for computing the optimal policy (π∗) and the optimal V-value function (V0∗). Furthermore, our algorithm QVI-2 provides an additional speedup in the size of the state space (S) when obtaining near-optimal policies and V-value functions. Both QVI-1 and QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on S and A. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms QVI-3 and QVI-4 achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of A, estimation error (ε), and time horizon (H). More importantly, we prove quantum lower bounds to show that QVI-3 and QVI-4 are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.