RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Improved classical simulation of quantum circuits dominated by Clifford gates

July 27, 2016 - 11:00am
David Gosset

We present a new algorithm for classical simulation of quantum circuits over the 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. This is joint work with Sergey Bravyi (PRL 116, 250501, 2016).

CSS 3100A

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to