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.08629 · Quantum

Fast Stabiliser Simulation with Quadratic Form Expansions

Niel de Beaudrap, Steven Herbert

Published Sep 15, 2022• 28 citations
arXivHTMLPDF

Abstract

This paper builds on the idea of simulating stabiliser circuits through transformations of {quadratic form expansions}. This is a representation of a quantum state which specifies a formula for the expansion in the standard basis, describing real and imaginary relative phases using a degree-2 polynomial over the integers. We show how, with deft management of the quadratic form expansion representation, we may simulate individual stabiliser operations in O(n2) time matching the overall complexity of other simulation techniques \cite{Aaronson2004,Anders2006,Bravyi2016}. Our techniques provide economies of scale in the time to simulate simultaneous measurements of all (or nearly all) qubits in the standard basis. Our techniques also allow single-qubit measurements with deterministic outcomes to be simulated in constant time. We also describe throughout how these bounds may be tightened when the expansion of the state in the standard basis has relatively few terms (has low `rank'), or can be specified by sparse matrices. Specifically, this allows us to simulate a `local' stabiliser syndrome measurement in time O(n) , for a stabiliser code subject to Pauli noise --- matching what is possible using techniques developed by Gidney \cite{gidney2021stim} without the need to store which operations have thus far been simulated.

DOI
10.22331/q-2022-09-15-803

Related papers

Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions

Aleks Kissinger, John van de Wetering, Renaud Vilmart

Recent developments in classical simulation of quantum circuits make use of clever decompositions of chunks of magic states into sums of efficiently simulable stabiliser states. We show here how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up these simulations. This is made possible by using the ZX-calculus, which allows us to easily find instances of these entangled states in the simplified diagram representing the quantum circuit to be simulated. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With this technique we require only $2^{αt}$ stabiliser terms, where $α\approx 0.396$, to simulate a circuit with T-count $t$. This matches the $α$ found by Qassim et al., but whereas they only get this scaling in the asymptotic limit, ours applies for a circuit of any size. Our method builds upon a recently proposed scheme for simulation combining stabiliser decompositions and optimisation strategies implemented in the software QuiZX. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.

arXiv:2202.09202•Leibniz international proceedings in informatics•Jan 1, 2022•54 citations

Bases for optimising stabiliser decompositions of quantum states

Nadish de Silva, Ming Yin, Sergii Strelchuk

Abstract Stabiliser states play a central role in the theory of quantum computation. For example, they are used to encode computational basis states in the most common quantum error correction schemes. Arbitrary quantum states admit many stabiliser decompositions: ways of being expressed as a superposition of stabiliser states. Understanding the structure of stabiliser decompositions has significant applications in verifying and simulating near-term quantum computers. We introduce and study the vector space of linear dependencies of n-qubit stabiliser states. These spaces have canonical bases containing vectors whose size grows exponentially in n. We construct elegant bases of linear dependencies of constant size three. Critically, our sparse bases can be computed without first compiling a dictionary of all n-qubit stabiliser states. We utilise them to explicitly compute the stabiliser extent of states of more qubits than is feasible with existing techniques. Finally, we delineate future applications to improving theoretical bounds on the stabiliser rank of magic states.

arXiv:2311.17384•Quantum Science and Technology•Jun 4, 2024•2 citations

A linearized stabilizer formalism for systems of finite dimension

Niel de Beaudrap

The stabilizer formalism is a scheme, generalizing well-known techniques developed by Gottesman~\cite{GottPhD} in the case of qubits, to efficiently simulate a class of transformations (\emph{stabilizer circuits}, which include the quantum Fourier transform and highly entangling operations) on standard basis states of $d$-dimensional qudits. To determine the state of a simulated system, existing treatments involve the computation of cumulative phase factors which involve quadratic dependencies. We present a simple formalism in which Pauli operators are represented using displacement operators in discrete phase space, expressing the evolution of the state via linear transformations modulo $D \le 2d$. We thus obtain a simple proof that simulating stabilizer circuits on $n$ qudits, involving any constant number of measurement rounds, is complete for the complexity class \coMod[d]\Log\ and may be simulated by $O(\log(n)^2)$-depth circuits for any constant $d \ge 2$.

arXiv:1102.3354•Quantum Information and Computation•Jan 1, 2013•50 citations

SyQMA: A memory-efficient, symbolic and exact universal simulator for quantum error correction

George Umbrarescu, David Amaro

The classical simulation of universal quantum circuits is crucial both fundamentally and practically for quantum computation. We propose SyQMA, a simulator with several convenient features, particularly suited for quantum error correction (QEC). SyQMA simulates universal quantum circuits with incoherent Pauli noise and computes exact expectation values and measurement probabilities as symbolic functions of circuit parameters: rotation angles, measurement outcomes, and noise rates. This simulator can sample measurement outcomes, enabling the simulation of dynamic quantum programs where circuit composition depends on prior measurement outputs. For QEC, it performs circuit-level maximum-likelihood decoding, provides exact symbolic expressions for logical error rates, and verifies the fault distance of fault-tolerant (FT) stabiliser and magic state preparation protocols. These features are enabled by an intuitive extension of stabiliser simulators, where each non-Clifford Pauli rotation and incoherent Pauli channel is compactly represented via auxiliary qubits and a modified trace. Representing the state requires only polynomial memory and time, while computing expectation values and measurement probabilities takes exponential time in the number of non-Clifford rotations and deterministic measurements, but only polynomial memory. The FT preparation of stabiliser and magic states, including the first stage of magic state cultivation, is analysed without approximations. We also exactly convert the disjoint error probabilities of a general multi-qubit Pauli channel to independent ones, a key step for creating and sampling from detector error models. The code is publicly available and open-source.

quant-pharXiv:2604.15043•Apr 17, 2026•6 citations

Efficient simulation of logical magic state preparation protocols

Samyak Surti, Lucas Daguerre, Isaac H. Kim

Developing space- and time-efficient logical magic state preparation protocols will likely be an essential step towards building a large-scale fault-tolerant quantum computer. Motivated by this need, we introduce a scalable method for simulating logical magic state preparation protocols under the standard circuit-level noise model. When applied to protocols based on code switching, magic state cultivation, and magic state distillation, our method yields a complexity polynomial in (i) the number of qubits and (ii) the non-stabilizerness, e.g., stabilizer rank or Pauli rank, of the target encoded magic state. The efficiency of our simulation method is rooted in a curious fact: every circuit-level Pauli error in these protocols propagates to a Clifford error at the end. This property is satisfied by a large family of protocols, including those that repeatedly measure a transversal Clifford that squares to a Pauli. We provide a proof-of-principle numerical simulation that prepares a magic state using such logical Clifford measurements. Our work enables practical simulation of logical magic state preparation protocols without resorting to approximations or resource-intensive state-vector simulations.

quant-pharXiv:2512.23799•PRX Quantum•Dec 31, 2025•13 citations

On stabiliser techniques and their application to simulation and certification of quantum devices

Markus Heinrich

The stabiliser formalism is a widely used and successful subtheory of quantum mechanics consisting of stabiliser states, Clifford unitaries and Pauli measurements. The power of the formalism comes from the description of its elements via simple group theory. Although the origins of the formalism lie in quantum error correction and fault-tolerant quantum computing, the utility of the formalism goes beyond that. The Gottesman-Knill theorem states that the dynamics of stabiliser states under Clifford unitaries and Pauli measurements can be efficiently simulated on a classical computer. This algorithm can be extended to arbitrary states and unitaries in multiple ways at the cost of an increased runtime. This runtime can be seen as a quantification of the non-stabiliser resources needed to implement a quantum circuit. Moreover, as non-stabiliser elements are necessary for universal quantum computing, the runtime provides a way to measure the “non-classicality” of a computation. This is particularly pronounced in the magic state model of quantum computing where the only non-stabiliser elements are given by magic states. Hence, in the resource theory of magic, resources are measured through magic monotones which are operationally linked to runtimes of classical simulation algorithms. In this thesis, I discuss different aspects of the resource theory of magic. The mentioned classical simulation algorithms require the computation of magic monotones which is in general a computationally intractable problem. However, I show that the computational complexity can be exponentially reduced for certain classes of symmetric states, such as copies of magic states. To this end, the symmetries of the convex hull of stabiliser states are characterised and linked to their properties as so-called designs. In addition, I study the recently introduced class of completely stabiliser-preserving channels (CSP), which is the class of quantum channels unable to generate magic resources. It is shown that this class is strictly larger than the class of stabiliser operations, composed of Clifford unitaries and Pauli measurements. This finding could have several interesting consequences. First, it implies that there is a class of efficiently simulable quantum channels beyond the Gottesman-Knill theorem. Second, it is possible that optimal magic state distillation rates cannot be achieved via stabiliser operations and this gap is in fact significant. Further applications of the stabiliser formalism come through design theory. A unitary t-design is an ensemble of unitaries which reproduce the first t moments of the Haar measure on the unitary group. Randomness in the form of Haar-random unitaries is an essential building block in many quantum information protocols. Implementing such Haar-random unitaries is however often impractical. Here, designs can exhibit considerably lower resource requirements while still being random enough for most applications. Some of the most prominent examples of such protocols concern the certification and characterisation of quantum systems, such as randomised benchmarking. Interestingly, the group of Clifford unitaries forms a unitary 3-design and is often the prime choice thanks to efficient group operations. In this thesis, I summarise my recent results obtained with collaborators in constructing approximate unitary t-designs from the Clifford group supplemented by only few non-Clifford gates. Intriguingly, this construction uses only O(t^4) single qubit non-Clifford gates and is independent of the number of qubits n. Overall, this yields a gate count which is a significant improvement over for the Brandao-Harrow- Horodecki construction based on local random circuits. To provide context for this result, I review the representation theory of the Clifford group and define the Clifford semigroup. In an attempt to generalise approximations results for the unitary group to the Clifford group, the Clifford semigroup is investigated for suitable approximations of the Clifford twirl.

•Jan 1, 2021•4 citations
This paper builds on the idea of simulating stabiliser circuits through transformations of {quadratic form expansions}. This is a representation of a quantum state which specifies a formula for the expansion in the standard basis, describing real and imaginary relative phases using a degree-2 polynomial over the integers. We show how, with deft management of the quadratic form expansion representation, we may simulate individual stabiliser operations in O(n2) time matching the overall complexity of other simulation techniques \cite{Aaronson2004,Anders2006,Bravyi2016}. Our techniques provide economies of scale in the time to simulate simultaneous measurements of all (or nearly all) qubits in the standard basis. Our techniques also allow single-qubit measurements with deterministic outcomes to be simulated in constant time. We also describe throughout how these bounds may be tightened when the expansion of the state in the standard basis has relatively few terms (has low rank'), or can be specified by sparse matrices. Specifically, this allows us to simulate a local' stabiliser syndrome measurement in time O(n) , for a stabiliser code subject to Pauli noise --- matching what is possible using techniques developed by Gidney \cite{gidney2021stim} without the need to store which operations have thus far been simulated.
Recent developments in classical simulation of quantum circuits make use of clever decompositions of chunks of magic states into sums of efficiently simulable stabiliser states. We show here how, by considering certain non-stabiliser entangled states which have more favourable decompositions, we can speed up these simulations. This is made possible by using the ZX-calculus, which allows us to easily find instances of these entangled states in the simplified diagram representing the quantum circuit to be simulated. We additionally find a new technique of partial stabiliser decompositions that allow us to trade magic states for stabiliser terms. With this technique we require only 2αt2^{αt}2αt stabiliser terms, where α≈0.396α\approx 0.396α≈0.396, to simulate a circuit with T-count ttt. This matches the ααα found by Qassim et al., but whereas they only get this scaling in the asymptotic limit, ours applies for a circuit of any size. Our method builds upon a recently proposed scheme for simulation combining stabiliser decompositions and optimisation strategies implemented in the software QuiZX. With our techniques we manage to reliably simulate 50-qubit 1400 T-count hidden shift circuits in a couple of minutes on a consumer laptop.
Abstract Stabiliser states play a central role in the theory of quantum computation. For example, they are used to encode computational basis states in the most common quantum error correction schemes. Arbitrary quantum states admit many stabiliser decompositions: ways of being expressed as a superposition of stabiliser states. Understanding the structure of stabiliser decompositions has significant applications in verifying and simulating near-term quantum computers. We introduce and study the vector space of linear dependencies of n-qubit stabiliser states. These spaces have canonical bases containing vectors whose size grows exponentially in n. We construct elegant bases of linear dependencies of constant size three. Critically, our sparse bases can be computed without first compiling a dictionary of all n-qubit stabiliser states. We utilise them to explicitly compute the stabiliser extent of states of more qubits than is feasible with existing techniques. Finally, we delineate future applications to improving theoretical bounds on the stabiliser rank of magic states.
The stabilizer formalism is a scheme, generalizing well-known techniques developed by Gottesman~\cite{GottPhD} in the case of qubits, to efficiently simulate a class of transformations (\emph{stabilizer circuits}, which include the quantum Fourier transform and highly entangling operations) on standard basis states of ddd-dimensional qudits. To determine the state of a simulated system, existing treatments involve the computation of cumulative phase factors which involve quadratic dependencies. We present a simple formalism in which Pauli operators are represented using displacement operators in discrete phase space, expressing the evolution of the state via linear transformations modulo D≤2dD \le 2dD≤2d. We thus obtain a simple proof that simulating stabilizer circuits on nnn qudits, involving any constant number of measurement rounds, is complete for the complexity class \coMod[d]\Log\ and may be simulated by O(log⁡(n)2)O(\log(n)^2)O(log(n)2)-depth circuits for any constant d≥2d \ge 2d≥2.
The classical simulation of universal quantum circuits is crucial both fundamentally and practically for quantum computation. We propose SyQMA, a simulator with several convenient features, particularly suited for quantum error correction (QEC). SyQMA simulates universal quantum circuits with incoherent Pauli noise and computes exact expectation values and measurement probabilities as symbolic functions of circuit parameters: rotation angles, measurement outcomes, and noise rates. This simulator can sample measurement outcomes, enabling the simulation of dynamic quantum programs where circuit composition depends on prior measurement outputs. For QEC, it performs circuit-level maximum-likelihood decoding, provides exact symbolic expressions for logical error rates, and verifies the fault distance of fault-tolerant (FT) stabiliser and magic state preparation protocols. These features are enabled by an intuitive extension of stabiliser simulators, where each non-Clifford Pauli rotation and incoherent Pauli channel is compactly represented via auxiliary qubits and a modified trace. Representing the state requires only polynomial memory and time, while computing expectation values and measurement probabilities takes exponential time in the number of non-Clifford rotations and deterministic measurements, but only polynomial memory. The FT preparation of stabiliser and magic states, including the first stage of magic state cultivation, is analysed without approximations. We also exactly convert the disjoint error probabilities of a general multi-qubit Pauli channel to independent ones, a key step for creating and sampling from detector error models. The code is publicly available and open-source.
Developing space- and time-efficient logical magic state preparation protocols will likely be an essential step towards building a large-scale fault-tolerant quantum computer. Motivated by this need, we introduce a scalable method for simulating logical magic state preparation protocols under the standard circuit-level noise model. When applied to protocols based on code switching, magic state cultivation, and magic state distillation, our method yields a complexity polynomial in (i) the number of qubits and (ii) the non-stabilizerness, e.g., stabilizer rank or Pauli rank, of the target encoded magic state. The efficiency of our simulation method is rooted in a curious fact: every circuit-level Pauli error in these protocols propagates to a Clifford error at the end. This property is satisfied by a large family of protocols, including those that repeatedly measure a transversal Clifford that squares to a Pauli. We provide a proof-of-principle numerical simulation that prepares a magic state using such logical Clifford measurements. Our work enables practical simulation of logical magic state preparation protocols without resorting to approximations or resource-intensive state-vector simulations.
The stabiliser formalism is a widely used and successful subtheory of quantum mechanics consisting of stabiliser states, Clifford unitaries and Pauli measurements. The power of the formalism comes from the description of its elements via simple group theory. Although the origins of the formalism lie in quantum error correction and fault-tolerant quantum computing, the utility of the formalism goes beyond that. The Gottesman-Knill theorem states that the dynamics of stabiliser states under Clifford unitaries and Pauli measurements can be efficiently simulated on a classical computer. This algorithm can be extended to arbitrary states and unitaries in multiple ways at the cost of an increased runtime. This runtime can be seen as a quantification of the non-stabiliser resources needed to implement a quantum circuit. Moreover, as non-stabiliser elements are necessary for universal quantum computing, the runtime provides a way to measure the “non-classicality” of a computation. This is particularly pronounced in the magic state model of quantum computing where the only non-stabiliser elements are given by magic states. Hence, in the resource theory of magic, resources are measured through magic monotones which are operationally linked to runtimes of classical simulation algorithms. In this thesis, I discuss different aspects of the resource theory of magic. The mentioned classical simulation algorithms require the computation of magic monotones which is in general a computationally intractable problem. However, I show that the computational complexity can be exponentially reduced for certain classes of symmetric states, such as copies of magic states. To this end, the symmetries of the convex hull of stabiliser states are characterised and linked to their properties as so-called designs. In addition, I study the recently introduced class of completely stabiliser-preserving channels (CSP), which is the class of quantum channels unable to generate magic resources. It is shown that this class is strictly larger than the class of stabiliser operations, composed of Clifford unitaries and Pauli measurements. This finding could have several interesting consequences. First, it implies that there is a class of efficiently simulable quantum channels beyond the Gottesman-Knill theorem. Second, it is possible that optimal magic state distillation rates cannot be achieved via stabiliser operations and this gap is in fact significant. Further applications of the stabiliser formalism come through design theory. A unitary t-design is an ensemble of unitaries which reproduce the first t moments of the Haar measure on the unitary group. Randomness in the form of Haar-random unitaries is an essential building block in many quantum information protocols. Implementing such Haar-random unitaries is however often impractical. Here, designs can exhibit considerably lower resource requirements while still being random enough for most applications. Some of the most prominent examples of such protocols concern the certification and characterisation of quantum systems, such as randomised benchmarking. Interestingly, the group of Clifford unitaries forms a unitary 3-design and is often the prime choice thanks to efficient group operations. In this thesis, I summarise my recent results obtained with collaborators in constructing approximate unitary t-designs from the Clifford group supplemented by only few non-Clifford gates. Intriguingly, this construction uses only O(t^4) single qubit non-Clifford gates and is independent of the number of qubits n. Overall, this yields a gate count which is a significant improvement over for the Brandao-Harrow- Horodecki construction based on local random circuits. To provide context for this result, I review the representation theory of the Clifford group and define the Clifford semigroup. In an attempt to generalise approximations results for the unitary group to the Clifford group, the Clifford semigroup is investigated for suitable approximations of the Clifford twirl.