Efficient Inner-product Algorithm for Stabilizer States

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.

14 pages, 5 figures, 3 tables

References in corpus (5)

• Multi-party entanglement in graph states
• Randomized Benchmarking of Quantum Gates
• Bell Inequalities for Graph States
• Entanglement in the stabilizer formalism
• Quantitative verification of entanglement and fidelities from incomplete measurement data

Cited by in corpus (12)

• Fast estimation of outcome probabilities for quantum circuits
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Randomized Benchmarking of Clifford Operators
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Improved Graph Formalism for Quantum Circuit Simulation
• Predicting Features of Quantum Systems from Very Few Measurements
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• GraphiQ: Quantum circuit design for photonic graph states
• Transforming graph states via Bell state measurements
• Quantum State Isomorphism
• Efficient classical simulation of cluster state quantum circuits with alternative inputs