Improved simulation of stabilizer circuits

Scott Aaronson and Daniel Gottesman
Phys. Rev. A 70, 052328 – Published 30 November 2004

Abstract

The Gottesman-Knill theorem says that a stabilizer circuit—that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates—can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely available program called CHP (CNOT-Hadamard-phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class L, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any n-qubit stabilizer circuit into a “canonical form” that requires at most O(n2logn) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.

  • Figure
  • Figure
  • Received 25 June 2004

DOI:https://doi.org/10.1103/PhysRevA.70.052328

©2004 American Physical Society

Authors & Affiliations

Scott Aaronson*

  • Computer Science Department, University of California, Berkeley, California 94720, USA

Daniel Gottesman

  • Perimeter Institute, Waterloo, Canada N2L 2Y5

  • *Present address: Institute for Advanced Study, Princeton, NY 08540, USA. Electronic address: aaronson@ias.edu
  • Electronic address: dgottesman@perimeterinstitute.ca

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 70, Iss. 5 — November 2004

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×