Abstract
We present two classical algorithms for the simulation of universal quantum circuits on qubits constructed from instances of Clifford gates and arbitrary-angle -rotation gates such as gates. Our algorithms complement each other by performing best in different parameter regimes. The 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 (which scales like for gates). Our algorithm is state-of-the-art for this task: as an example, in approximately hours (on a standard desktop computer), we estimated the Born rule probability to within an additive error of , for a -qubit, non-Clifford gate quantum circuit with more than Clifford gates. Our second algorithm, , calculates the probability of a chosen measurement outcome to machine precision with run-time where is an efficiently computable, circuit-specific quantity. With high probability, is very close to $\min \{t, n-w\}w$ is the number of measured qubits. can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+ circuits with , , and gates, and then compute the Born rule probability with a run-time consistently less than minutes 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 (QAOA).