Scott Aaronson and Daniel Gottesman

What is CHP?

CHP is a high-performance simulator of *stabilizer circuits* -- quantum circuits that consist of controlled-NOT, Hadamard, and π/2 phase gates as well as 1-qubit measurement gates.

What can it help me do?

- Design and debug quantum error-correction architectures
- Study large, highly-entangled quantum systems numerically
- Create pedagogical demonstrations of famous quantum effects, such as teleportation, dense coding, and the GHZ paradox

Where can I learn more?

The following paper contains the algorithmic ideas on which CHP is based.

- S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits [PS] [PDF],
- By removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor-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.
- We show that the problem of simulating stabilizer circuits is complete
for the classical complexity class ParityL, which means that
stabilizer circuits are probably not even universal for
*classical*computation. - 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(n
^{2}/log n) gates, and other useful tasks. - We extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of non-stabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.

*Abstract:* The Gottesman-Knill theorem says that a stabilizer circuit -- that is, a
quantum circuit consisting solely of CNOT, Hadamard, and phase gates -- can be
simulated efficiently on a classical computer. This paper improves that
theorem in several directions.

Where can I download CHP?

- Source: chp.c
- DOS executable: chp.exe
- Sample quantum circuits:
- epr.chp: prepares an EPR (Einstein-Podolsky-Rosen) pair and then collapses it
- ghz.chp: performs the GHZ (Greenberger-Horne-Zeilinger) experiment
- teleport.chp: teleports a qubit that you specify from one register to another
- simon.chp: runs Simon's algorithm for detecting a hidden shift
- densecoding.chp: uses the Bennett-Wiesner dense quantum coding protocol to transmit 2 classical bits that you specify using 1 qubit and 1 EPR pair
- qecc9.chp: encodes a qubit that you specify using the Shor 9-qubit quantum error-correcting code, then applies an encoded Pauli operation that you specify, and finally decodes
- rand100.chp, rand200.chp, rand300.chp: randomly-generated 10000-gate circuits on 100, 200, and 300 qubits respectively

- Program to generate random stabilizer quantum circuits: randqc.c (source), randqc.exe (DOS executable)

Is CHP freeware?

Yes, but:

- It's copyrighted. Don't incorporate it into any commercial product without permission.
- Cite the paper by Aaronson and Gottesman in any publications based on CHP.
- If you're using or extending CHP in an interesting way, consider dropping the author a note.

Why was CHP written?

Scott Aaronson wrote it in order to pass the Graduate Computer Architecture course at Berkeley, taught by John Kubiatowicz.

*Last modified: February 6, 2005*