A Caltech Library Service

Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates

Bravyi, Sergey and Gosset, David (2016) Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates. Physical Review Letters, 116 (25). Art. No. 250501. ISSN 0031-9007. doi:10.1103/PhysRevLett.116.250501.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.

[img] PDF - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Material Paper
Additional Information:© 2016 American Physical Society. Received 9 March 2016; published 20 June 2016. D. G. acknowledges funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NFS Grant No. PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). S. B. thanks Alexei Kitaev for helpful discussions and comments.
Group:Institute for Quantum Information and Matter, Walter Burke Institute for Theoretical Physics
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Issue or Number:25
Record Number:CaltechAUTHORS:20160620-110726584
Persistent URL:
Official Citation:Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates Sergey Bravyi and David Gosset Phys. Rev. Lett. 116, 250501
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68527
Deposited By: Tony Diaz
Deposited On:20 Jun 2016 18:55
Last Modified:11 Nov 2021 04:01

Repository Staff Only: item control page