Estimating quantum circuit probabilities and Hamiltonian properties using amplitude estimation

Classical simulation of quantum systems is an old and well-motivated problem. With the advent of quantum technologies this problem takes on new importance, as it becomes essential to have a toolkit for testing and debugging quantum circuits and devices.

We describe a Markov chain monte carlo simulation of quantum circuits based on decomposing the circuit in question as a sum of Clifford gates. The idea is to leverage the classical simulability of Clifford dynamics to cases where the circuit is no longer simulable. The runtime scales quadratically with the 1-norm of the vector of expansion, and the runtime is comparable with state-of-the-art simulators for an important class of circuitslp; the so-called Clifford+T circuits. The simulation method can be extended to two other problems: estimating transition probabilities and estimating the partition function of an n-qubit Hamiltonian. We give theoretical error and runtime estimates, and introduce a few sub-algorithms which can improve the performance in some cases.