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], Physical Review A 70:052328, 2004. quant-ph/0406196.

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.

• 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²/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.

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