Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates

We present a new algorithm for classical simulation of quantum circuits over the $\text{Clifford}+T$ gate set. The runtime of the algorithm is polynomial in the number of qubits and the number of Clifford gates in the circuit but exponential in the number of $T$ gates. The exponential scaling is sufficiently mild that the algorithm can be used in practice to simulate medium-sized quantum circuits dominated by Clifford gates. The first demonstrations of fault-tolerant quantum circuits based on 2D topological codes are likely to be dominated by Clifford gates due to a high implementation cost associated with logical $T$ gates. Thus our algorithm may serve as a verification tool for near-term quantum computers which cannot in practice be simulated by other means. To demonstrate the power of the new method, we performed a classical simulation of a hidden shift quantum algorithm with 40 qubits, a few hundred Clifford gates, and nearly 50 $T$ gates.

Figure 1

Output single-qubit probability distributions obtained by a classical simulation of the hidden shift quantum algorithm on $n=40$ qubits. Only one half of all qubits are shown (qubits $21,22,\dots ,40$). The final state of the algorithm is $|s⟩=U|0^{\otimes n}⟩$, where $s$ is the hidden shift string to be found and $U$ is a $\text{Clifford}+T$ circuit with the $T$ count $t=40$ (left) and $t=48$ (right). In both cases the circuit $U$ contains a few hundred Clifford gates. For each qubit the probability of measuring “1” in the final state is indicated in blue. The $x$-axis labels indicate the correct hidden shift bits. The entire simulation took several hours on a laptop computer.

Figure 2

The $T$-gate gadget. The Clifford gate $S$ is classically controlled by the measurement outcome.