Efficient Inner-product Algorithm for Stabilizer States
Preprint
Abstract
Large-scale quantum computation is likely to require massive quantum error correction (QEC). QEC codes and circuits are described via the stabilizer formalism, which represents stabilizer states by keeping track of the operators that preserve them. Such states are obtained by stabilizer circuits (consisting of CNOT, Hadamard and Phase only) and can be represented compactly on conventional computers using Omega(n^2) bits, where n is the number of qubits. Although techniques for the efficient simulation of stabilizer circuits have been studied extensively, techniques for efficient manipulation of stabilizer states are not currently available. To this end, we design new algorithms for: (i) obtaining canonical generators for stabilizer states, (ii) obtaining canonical stabilizer circuits, and (iii) computing the inner product between stabilizer states. Our inner-product algorithm takes O(n^3) time in general, but observes quadratic behavior for many practical instances relevant to QECC (e.g., GHZ states). We prove that each n-qubit stabilizer state has exactly 4(2^n - 1) nearest-neighbor stabilizer states, and verify this claim experimentally using our algorithms. We design techniques for representing arbitrary quantum states using stabilizer frames and generalize our algorithms to compute the inner product between two such frames.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyondQuantum Information & Computation, 2010
- Randomized benchmarking of quantum gatesPhysical Review A, 2008
- Bell Inequalities for Graph StatesPhysical Review Letters, 2005
- Local unitary versus local Clifford equivalence of stabilizer statesPhysical Review A, 2005
- Improved simulation of stabilizer circuitsPhysical Review A, 2004
- Multiparty entanglement in graph statesPhysical Review A, 2004
- Clifford group, stabilizer states, and linear and quadratic operations over GF(2)Physical Review A, 2003
- Multiparticle Entanglement Purification for Graph StatesPhysical Review Letters, 2003
- Quantum error correction via codes over GF(4)IEEE Transactions on Information Theory, 1998
- Efficient computations of encodings for quantum error correctionPhysical Review A, 1997