Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 24, 2016 | Published + Supplemental Material + Submitted
Journal Article Open

Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates

Abstract

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.

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.

Attached Files

Published - PhysRevLett.116.250501.pdf

Submitted - 1601.07601v1.pdf

Supplemental Material - supp_material_prl.pdf

Files

1601.07601v1.pdf
Files (1.2 MB)
Name Size Download all
md5:5cf610ab068ff58669dc593c6d428666
614.9 kB Preview Download
md5:507db20f3190c3126a1f6333934ce746
429.6 kB Preview Download
md5:d5940dd09203c3dde481a11ac20b02d4
163.6 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 19, 2023