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.
A PowerPoint presentation is also available.
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(n2/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?
- 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