Perfect Sampling for Quantum Gibbs States
arXiv:1703.05800 · doi:10.26421/QIC18.5-6
Abstract
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.
arXiv comment28 pages, 4 figures, close to published version
References in corpus (18)
- Quantum Algorithms Revisited
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Quantum measurements and the Abelian Stabilizer Problem
- Quantum Metropolis Sampling
- Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
- The problem of equilibration and the computation of correlation functions on a quantum computer
- Thermalization in Nature and on a Quantum Computer
- A dissipative quantum Church-Turing theorem
- A Quantum-Quantum Metropolis Algorithm
- Ergodic and Mixing Quantum Channels in Finite Dimensions
- Rapid adiabatic preparation of injective PEPS and Gibbs states
- Preparing thermal states of quantum systems by dimension reduction
- Davies maps for qubits and qutrits
- Spectral convergence bounds for classical and quantum Markov processes
- Perturbation Bounds for Quantum Markov Processes and their Fixed Points
- Lower bounds to the spectral gap of Davies generators
- On sensitivity of mixing times and cutoff
- Quantum algorithm for exact Monte Carlo sampling