Perfect Sampling for Quantum Gibbs States

Daniel Stilck França

Published 2017-03-16Version 1

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.