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:2109.10210 · Physical Review A

Improved graph formalism for quantum circuit simulation

Alexander Tianlin Hu, Andrey Boris Khesin

Published Feb 22, 2022• 7 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.105.022432

Related papers

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,515 citations

Efficient Inner-product Algorithm for Stabilizer States

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

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.

arXiv:1210.6646•Oct 24, 2012•15 citations

Fast simulation of stabilizer circuits using a graph-state representation

Simon Anders, Hans J. Briegel

According to the Gottesman-Knill theorem, a class of quantum circuits---namely, the so-called stabilizer circuits---can be simulated efficiently on a classical computer. We introduce an algorithm for this task, which is based on the graph-state formalism. It shows significant improvement in comparison to an existing algorithm, given by Gottesman and Aaronson, in terms of speed and of the number of qubits the simulator can handle. We also present an implementation.

arXiv:quant-ph/0504117•Physical Review A•Feb 21, 2006•163 citations

Improvements of the classical simulation of quantum circuits: Using graph states with local Cliffords

Matthijs S. C. Rijlaarsdam

With this thesis project, we improve the classical simulation of quantum computers using stabilizers in the GSLC formalism. We do this in two ways: we present new algorithms that speed up their simulation and extend their applicability by defining new operations and subroutines for existing general circuit simulation using GSLC. To be precise: we present multiple new algorithms that speed up the simulation of the CZ gates, the most computationally expensive quantum operation in GSLC formalism. We define two new operations on GSLC that are useful when simulating stabilizer circuits: calculating fidelity (a measure of 'closeness' between two quantum states), and tracing out qubits (throwing away the information about the state contained in these qubits) from a GSLC. Finally, we present a new GSLC-based subroutine for a state of the art general quantum circuit simulation algorithm by Bravyi et al. that allows for the usage of the faster CZ algorithms. We show that the GSLC formalism can give a speedup in practical simulation tasks by evaluating the complexity of simulating an algorithm with possible applications on near-term quantum hardware: the quantum approximate optimization algorithm.

•Jan 1, 2020•0 citations

Extending the graph formalism to higher-order gates

Andrey Boris Khesin, K. Ren

We present an algorithm for efficiently simulating a quantum circuit in the graph formalism. In the graph formalism, we present states as a linear combination of graphs with Clifford operations on their vertices. We show how a $\calC_3$ gate such as the Toffoli gate or $\frac\pi8$ gate acting on a stabilizer state splits it into two stabilizer states. We also describe conditions for merging two stabilizer states into one. We discuss applications of our algorithm to circuit identities and finding low stabilizer rank presentations of magic states.

arXiv:2108.02686•Quantum Information and Computation•Nov 1, 2023•0 citations

On the Geometry of Stabilizer States

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

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 gates) and can be represented compactly on conventional computers using $O(n^2)$ bits, where $n$ is the number of qubits. As an additional application, the work by Aaronson and Gottesman 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.

arXiv:1711.07848•Nov 20, 2017•5 citations
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.
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.
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.
With this thesis project, we improve the classical simulation of quantum computers using stabilizers in the GSLC formalism. We do this in two ways: we present new algorithms that speed up their simulation and extend their applicability by defining new operations and subroutines for existing general circuit simulation using GSLC. To be precise: we present multiple new algorithms that speed up the simulation of the CZ gates, the most computationally expensive quantum operation in GSLC formalism. We define two new operations on GSLC that are useful when simulating stabilizer circuits: calculating fidelity (a measure of 'closeness' between two quantum states), and tracing out qubits (throwing away the information about the state contained in these qubits) from a GSLC. Finally, we present a new GSLC-based subroutine for a state of the art general quantum circuit simulation algorithm by Bravyi et al. that allows for the usage of the faster CZ algorithms. We show that the GSLC formalism can give a speedup in practical simulation tasks by evaluating the complexity of simulating an algorithm with possible applications on near-term quantum hardware: the quantum approximate optimization algorithm.
We present an algorithm for efficiently simulating a quantum circuit in the graph formalism. In the graph formalism, we present states as a linear combination of graphs with Clifford operations on their vertices. We show how a $\calC_3$ gate such as the Toffoli gate or π8\frac\pi88π​ gate acting on a stabilizer state splits it into two stabilizer states. We also describe conditions for merging two stabilizer states into one. We discuss applications of our algorithm to circuit identities and finding low stabilizer rank presentations of magic states.
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 gates) and can be represented compactly on conventional computers using O(n2)O(n^2)O(n2) bits, where nnn is the number of qubits. As an additional application, the work by Aaronson and Gottesman 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.