Fast Estimation of Outcome Probabilities for Quantum Circuits

Abstract

We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates. Our algorithms complement each other by performing best in different parameter regimes. The Estimate algorithm produces an additive precision estimate of the Born-rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (with scaling approximately equal to 1.17^{t} for T gates). Our algorithm is state of the art for this task: as an example, in approximately 13 h (on a standard desktop computer), we estimate the Born-rule probability to within an additive error of 0.03, for a 50-qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates. Our second algorithm, Compute, calculates the probability of a chosen measurement outcome to machine precision with run time O(2^{t−r}t), where r is an efficiently computable, circuit-specific quantity. With high probability, r is very close to min{t,n−w} for random circuits with many Clifford gates, where w is the number of measured qubits. Compute can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n=55, w=5, c=10^{5}, and t=80T gates, and then compute the Born-rule probability with a run time consistently less than 10 min using a single core of a standard desktop computer. We provide a C+Python implementation of our algorithms and benchmark them using random circuits, the hidden-shift algorithm, and the quantum approximate optimization algorithm.