Perfect Sampling for Quantum Gibbs States


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 that satisfies certain conditions, implied e.g. by detailed balance, and is primitive. We analyse the expected run-time of the algorithm, which is linear in the mixing time and quadratic in the dimension. We also analyse 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.
Submitted 16 Mar 2017 to Quantum Physics [quant-ph]
Published 20 Mar 2017
Author comments: 18 pages, 4 figures