Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1210.6646 · Quantum Information and Computation

On the geometry of stabilizer states

Héctor J. García, Igor L. Markov, Andrew W. Cross

Published May 1, 2014• 102 citations
arXivHTMLPDF

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 {\em stabilizer circuits} (consisting of CNOT, Hadamard and Phase gates) and can be represented compactly on conventional computers using $\Theta (n^2)$ bits, where $n$ is the number of qubits \cite{Gottes98}. As an additional application, the work in~\cite{Aaron, AaronGottes} suggests the use of superpositions of stabilizer states to represent arbitrary quantum states. To aid in such applications and improve our understanding of stabilizer states, we characterize and count nearest-neighbor stabilizer states, quantify the distribution of angles between pairs of stabilizer states, study succinct stabilizer superpositions and stabilizer bivectors, explore the approximation of non-stabilizer states by single stabilizer states and short linear combinations of stabilizer states, develop an improved inner-product computation for stabilizer states via synthesis of compact canonical stabilizer circuits, propose an orthogonalization procedure for stabilizer states, and evaluate several of these algorithms empirically.

DOI
10.26421/qic14.7-8-9

Related papers

Hybrid Techniques for Simulating Quantum Circuits using the Heisenberg Representation.

Hector J. Garcia-Ramirez

Simulation of quantum information processing remains a major challenge with important applications in quantum computer science and engineering. Generic quantum-circuit simulation appears intractable for conventional computers and may be unnecessary because useful quantum circuits exhibit significant structure that can be exploited during simulation. For example, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently using the Heisenberg representation for quantum computers. Stabilizer circuits are exclusively composed of stabilizer gates -- Hadamard, Phase and CNOT -- followed by one-qubit measurements in the computational basis. Such circuits are applied to a computational-basis state and produce so-called stabilizer states. Aaronson and Gottesman generalized stabilizer-circuit simulation to additionally handle a small number of non-stabilizer gates. We design new, more efficient data structures and algorithms for such beyond-stabilizer simulation using superpositions of stabilizer states. One such data structure, a stabilizer frame, offers more compact storage than previous approaches but require additional algorithms to maintain the global phases of each state in the superposition. To explore the advantages and limitations of our technique, we analyze the geometric structure of stabilizer states and their embedding in Hilbert space. Our analysis includes results on the computational geometry of stabilizer states such as efficient algorithms for computing distances, angles and volumes between them. The main advantages of using stabilizer-state superpositions to simulate quantum circuits are: (i) stabilizer subcircuits are simulated with high efficiency, (ii) superpositions can be restructured and compressed on the fly during simulation to reduce resource requirements, and (iii) operations performed on such superpositions lend themselves to distributed or asynchronous processing. Our software implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., reversible ripple-carry adders) and quantum Fourier transform circuits in polynomial time and space for specific input states. On such instances, known linear-algebraic simulation techniques, such as the (state-of-the-art) BDD-based simulator QuIDDPro, take exponential time. We simulate quantum fault-tolerant circuits using Quipu, and the results indicate that our stabilizer-based technique empirically outperforms QuIDDPro in all cases. While previous structure-aware simulations of quantum circuits were difficult to parallellize, we demonstrate a parallel version of Quipu that achieves a nontrivial speedup.

•Jan 1, 2014•3 citations

Improved simulation of stabilizer circuits

Scott Aaronson, Daniel Gottesman

The Gottesman-Knill theorem says that a stabilizer circuit---that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates---can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 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. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class $\ensuremath{\bigoplus}\mathsf{L}$, which means that stabilizer circuits are probably not even universal for classical computation. Third, 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}∕\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)$ gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.

arXiv:quant-ph/0406196•Physical Review A•Nov 30, 2004•1,846 citations

Phase-sensitive representation of Majorana stabilizer states

Tomislav Begušić, Garnet Kin-Lic Chan

Stabilizer states hold a special place in quantum information science due to their connection with quantum error correction and quantum circuit simulation. In the context of classical simulations of many-body physics, they are an example of states that can be both highly entangled and efficiently represented and transformed under Clifford operators. Recently, Clifford operators have been discussed in the context of fermionic quantum computation through their extension, the Majorana Clifford group. Here, we document the phase-sensitive form of the corresponding Majorana stabilizer states, as well as the algorithms for computing their amplitudes, their inner products, and update rules for transforming Majorana stabilizer states under Majorana Clifford gates.

quant-pharXiv:2602.17604•Feb 20, 2026•0 citations

Improved graph formalism for quantum circuit simulation

Alexander Tianlin Hu, Andrey Boris Khesin

Improving the simulation of quantum circuits on classical computers is important for understanding quantum advantage and increasing development speed. In this paper, we explore a way to express stabilizer states and further improve the speed of simulating stabilizer circuits with a current existing approach. First, we discover a unique and elegant canonical form for stabilizer states based on graph states to better represent stabilizer states and show how to efficiently simplify stabilizer states to canonical form. Second, we develop an improved algorithm for graph state stabilizer simulation and establish limitations on reducing the quadratic runtime of applying controlled Pauli $Z$ gates. We do so by creating a simpler formula for combining two Pauli-related stabilizer states into one. Third, to better understand the linear dependence of stabilizer states, we characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our controlled Pauli $Z$ algorithm, we improve runtime for inner product computation from $O({n}^{3})$ to $O(n{d}^{2})$, where $d$ is the maximum degree of the graph encountered during the calculation.

arXiv:2109.10210•Physical Review A•Feb 22, 2022•11 citations

Optimization of Quantum Circuits for Stabilizer Codes

Arijit Mondal, Keshab K. Parhi

Quantum computing is an emerging technology that has the potential to achieve exponential speedups over their classical counterparts. To achieve quantum advantage, quantum principles are being applied to fields such as communications, information processing, and artificial intelligence. However, quantum computers face a fundamental issue since quantum bits are extremely noisy and prone to decoherence. Keeping qubits error free is one of the most important steps towards reliable quantum computing. Different stabilizer codes for quantum error correction have been proposed in past decades and several methods have been proposed to import classical error correcting codes to the quantum domain. Design of encoding and decoding circuits for the stabilizer codes have also been proposed. Optimization of these circuits in terms of the number of gates is critical for reliability of these circuits. In this paper, we propose a procedure for optimization of encoder circuits for stabilizer codes. Using the proposed method, we optimize the encoder circuit in terms of the number of 2-qubit gates used. The proposed optimized eight-qubit encoder uses 18 CNOT gates and 4 Hadamard gates, as compared to 14 single qubit gates, 33 2-qubit gates, and 6 CCNOT gates in a prior work. The encoder and decoder circuits are verified using IBM Qiskit. We also present encoder circuits for the Steane code and a 13-qubit code, that are optimized with respect to the number of gates used, leading to a reduction in number of CNOT gates by 1 and 8, respectively.

arXiv:2309.12373•IEEE Transactions on Circuits and Systems I Regular Papers•Apr 17, 2024•16 citations

Introduction to quantum error correction

Andrew M. Steane

An introduction to quantum error correction (QEC) is given, and some recent developments are described. QEC consists of two parts: the physics of error processes and their reversal, and the construction of quantum error–correcting codes. Errors are caused both by imperfect quantum operations, and by coupling between the quantum system and its environment. Any such process can be analysed into a sum of ‘error operators’, which are tensor products of Pauli spin operators. These are the analogues of classical error vectors. A quantum error correcting code is a set of orthogonal states, ‘quantum codewords’, which behave in a certain useful way under the action of the most likely error operators. A computer or channel which only uses such states can be corrected by measurements which determine the error while yielding no information about which codeword or superposition of codewords is involved. Powerful codes can be found using a construction based on classical error–correcting codes. An analysis which allows even the corrective operations themselves to be imperfect leads to powerful and counter–intuitive results: the quantum coherence of a long quantum computation can be preserved even though every qubit in the computer relaxes spontaneously many times before the computation is complete.

Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 15, 1998•39 citations
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 {\em stabilizer circuits} (consisting of CNOT, Hadamard and Phase gates) and can be represented compactly on conventional computers using Θ(n2)\Theta (n^2)Θ(n2) bits, where nnn is the number of qubits \cite{Gottes98}. As an additional application, the work in~\cite{Aaron, AaronGottes} suggests the use of superpositions of stabilizer states to represent arbitrary quantum states. To aid in such applications and improve our understanding of stabilizer states, we characterize and count nearest-neighbor stabilizer states, quantify the distribution of angles between pairs of stabilizer states, study succinct stabilizer superpositions and stabilizer bivectors, explore the approximation of non-stabilizer states by single stabilizer states and short linear combinations of stabilizer states, develop an improved inner-product computation for stabilizer states via synthesis of compact canonical stabilizer circuits, propose an orthogonalization procedure for stabilizer states, and evaluate several of these algorithms empirically.
Simulation of quantum information processing remains a major challenge with important applications in quantum computer science and engineering. Generic quantum-circuit simulation appears intractable for conventional computers and may be unnecessary because useful quantum circuits exhibit significant structure that can be exploited during simulation. For example, Gottesman and Knill identified an important subclass, called stabilizer circuits, which can be simulated efficiently using the Heisenberg representation for quantum computers. Stabilizer circuits are exclusively composed of stabilizer gates -- Hadamard, Phase and CNOT -- followed by one-qubit measurements in the computational basis. Such circuits are applied to a computational-basis state and produce so-called stabilizer states. Aaronson and Gottesman generalized stabilizer-circuit simulation to additionally handle a small number of non-stabilizer gates. We design new, more efficient data structures and algorithms for such beyond-stabilizer simulation using superpositions of stabilizer states. One such data structure, a stabilizer frame, offers more compact storage than previous approaches but require additional algorithms to maintain the global phases of each state in the superposition. To explore the advantages and limitations of our technique, we analyze the geometric structure of stabilizer states and their embedding in Hilbert space. Our analysis includes results on the computational geometry of stabilizer states such as efficient algorithms for computing distances, angles and volumes between them. The main advantages of using stabilizer-state superpositions to simulate quantum circuits are: (i) stabilizer subcircuits are simulated with high efficiency, (ii) superpositions can be restructured and compressed on the fly during simulation to reduce resource requirements, and (iii) operations performed on such superpositions lend themselves to distributed or asynchronous processing. Our software implementation, called Quipu, simulates certain quantum arithmetic circuits (e.g., reversible ripple-carry adders) and quantum Fourier transform circuits in polynomial time and space for specific input states. On such instances, known linear-algebraic simulation techniques, such as the (state-of-the-art) BDD-based simulator QuIDDPro, take exponential time. We simulate quantum fault-tolerant circuits using Quipu, and the results indicate that our stabilizer-based technique empirically outperforms QuIDDPro in all cases. While previous structure-aware simulations of quantum circuits were difficult to parallellize, we demonstrate a parallel version of Quipu that achieves a nontrivial speedup.
The Gottesman-Knill theorem says that a stabilizer circuit---that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates---can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 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. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class $\ensuremath{\bigoplus}\mathsf{L}$, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any nnn-qubit stabilizer circuit into a ``canonical form'' that requires at most O(n2∕logn)O({n}^{2}∕\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)O(n2∕logn) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.
Stabilizer states hold a special place in quantum information science due to their connection with quantum error correction and quantum circuit simulation. In the context of classical simulations of many-body physics, they are an example of states that can be both highly entangled and efficiently represented and transformed under Clifford operators. Recently, Clifford operators have been discussed in the context of fermionic quantum computation through their extension, the Majorana Clifford group. Here, we document the phase-sensitive form of the corresponding Majorana stabilizer states, as well as the algorithms for computing their amplitudes, their inner products, and update rules for transforming Majorana stabilizer states under Majorana Clifford gates.
Improving the simulation of quantum circuits on classical computers is important for understanding quantum advantage and increasing development speed. In this paper, we explore a way to express stabilizer states and further improve the speed of simulating stabilizer circuits with a current existing approach. First, we discover a unique and elegant canonical form for stabilizer states based on graph states to better represent stabilizer states and show how to efficiently simplify stabilizer states to canonical form. Second, we develop an improved algorithm for graph state stabilizer simulation and establish limitations on reducing the quadratic runtime of applying controlled Pauli ZZZ gates. We do so by creating a simpler formula for combining two Pauli-related stabilizer states into one. Third, to better understand the linear dependence of stabilizer states, we characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our controlled Pauli ZZZ algorithm, we improve runtime for inner product computation from O(n3)O({n}^{3})O(n3) to O(nd2)O(n{d}^{2})O(nd2), where ddd is the maximum degree of the graph encountered during the calculation.
Quantum computing is an emerging technology that has the potential to achieve exponential speedups over their classical counterparts. To achieve quantum advantage, quantum principles are being applied to fields such as communications, information processing, and artificial intelligence. However, quantum computers face a fundamental issue since quantum bits are extremely noisy and prone to decoherence. Keeping qubits error free is one of the most important steps towards reliable quantum computing. Different stabilizer codes for quantum error correction have been proposed in past decades and several methods have been proposed to import classical error correcting codes to the quantum domain. Design of encoding and decoding circuits for the stabilizer codes have also been proposed. Optimization of these circuits in terms of the number of gates is critical for reliability of these circuits. In this paper, we propose a procedure for optimization of encoder circuits for stabilizer codes. Using the proposed method, we optimize the encoder circuit in terms of the number of 2-qubit gates used. The proposed optimized eight-qubit encoder uses 18 CNOT gates and 4 Hadamard gates, as compared to 14 single qubit gates, 33 2-qubit gates, and 6 CCNOT gates in a prior work. The encoder and decoder circuits are verified using IBM Qiskit. We also present encoder circuits for the Steane code and a 13-qubit code, that are optimized with respect to the number of gates used, leading to a reduction in number of CNOT gates by 1 and 8, respectively.
An introduction to quantum error correction (QEC) is given, and some recent developments are described. QEC consists of two parts: the physics of error processes and their reversal, and the construction of quantum error–correcting codes. Errors are caused both by imperfect quantum operations, and by coupling between the quantum system and its environment. Any such process can be analysed into a sum of ‘error operators’, which are tensor products of Pauli spin operators. These are the analogues of classical error vectors. A quantum error correcting code is a set of orthogonal states, ‘quantum codewords’, which behave in a certain useful way under the action of the most likely error operators. A computer or channel which only uses such states can be corrected by measurements which determine the error while yielding no information about which codeword or superposition of codewords is involved. Powerful codes can be found using a construction based on classical error–correcting codes. An analysis which allows even the corrective operations themselves to be imperfect leads to powerful and counter–intuitive results: the quantum coherence of a long quantum computation can be preserved even though every qubit in the computer relaxes spontaneously many times before the computation is complete.