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:2311.17384 · Quantum Science and Technology

Bases for optimising stabiliser decompositions of quantum states

Nadish de Silva, Ming Yin, Sergii Strelchuk

Published Jun 4, 2024• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/2058-9565/ad53fc

Related papers

Fast algorithms for classical specifications of stabiliser states and Clifford gates

Nadish de Silva, Wilfred Salmon, Ming Yin

The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism.We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau.For example, we extract the stabiliser tableau of a 2n×2n matrix, promised to be a Clifford gate, in O(n2n) time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits.We provide implementations of our algorithms in Python and C++ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.

arXiv:2311.10357•Quantum•Jan 8, 2025•10 citations

Classical simulations of quantum systems using stabilizer decompositions

Hammam Qassim

One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from $O(\\ell n^2)$ to $O(m n^2)$, where $\\ell$ is the total number of gates in the circuit, and $m$ is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever $\\ell \\gg m$. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of $\\ket{\\psi}^{\\otimes m}$, where $\\ket{\\psi}$ is either a magic state or an equatorial state. \nFor any single qubit magic state $\\ket{\\psi}$, we find stabilizer decompositions of $\\ket{\\psi}^{\\otimes m}$ with $2^{m\\log_2(3)/4}$ terms. This improves on the best known bound of $2^{m \\log_2(7)/6}$. \nSimilarly, for any single qubit equatorial state $\\ket{\\psi}$, we give a stabilizer decomposition of $\\ket{\\psi}^{\\otimes m}$ with $2^{m/2}$ terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail, $d$-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo $d > 2$. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd $d$, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even $d$ case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.

•Feb 19, 2021•4 citations

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

Unextendible stabiliser bases

Markus Frembs

We study incomplete sets of orthogonal stabiliser states that cannot be extended by a further stabiliser state orthogonal to all of its members. Such sets are the stabiliser analogue of unextendible product bases (UPBs), and we thus call them unextendible stabiliser bases (USBs). Leveraging the symplectic geometry underlying the $n$-qudit Pauli group in prime local dimension, we explicitly construct USBs for systems of four qubits and three qudits of odd prime local dimension. Moreover, we show that these are the respective minimal qubit, respectively qudit numbers for which such bases exist, and that USBs exist for all $n\geq4$ qubit and for all $n\geq3$ odd-prime-dimensional qudit systems. Finally, we compare the resource-theoretic aspects of USBs with those of UPBs. We establish that, analogous to the case of UPBs, the orthogonal complement of every unextendible stabiliser set is a stabiliser-free subspace, and its normalised projector is necessarily magic; moreover, it is bound magic in odd prime dimension, yet need not be for qubits. We also show that USB unextendibility alone imposes no uniform quantitative obstruction to discrimination by stabiliser operations.

quant-pharXiv:2608.10202•Aug 12, 2026•2 citations

Multiple-basis representation of quantum states

Adrián Pérez-Salinas, Patrick Emonts, Jordi Tura +1 more

Classical simulation of quantum physics is a central approach to investigating physical phenomena. Quantum computers enhance computational capabilities beyond those of classical resources, but it remains unclear to what extent existing limited quantum computers can contribute to this enhancement. In this work, we explore a new hybrid, efficient quantum-classical representation of quantum states, the multiple-basis representation. This representation consists of a linear combination of states that are sparse in some given and different bases, specified by quantum circuits. Such representation is particularly appealing when considering depth-limited quantum circuits within reach of current hardware. We analyze the expressivity of multiple-basis representation states depending on the classical simulability of their quantum circuits. In particular, we show that multiple-basis representation states include, but are not restricted to, both matrix-product states and stabilizer states. Furthermore, we find cases in which this representation can be used, namely approximation of ground states, simulation of deeper computations by specifying bases with shallow circuits, and a tomographical protocol to describe states as multiple-basis representations. We envision this work to open the path of simultaneous use of several hardware-friendly bases, a natural description of hybrid computational methods accessible for near-term hardware.

arXiv:2411.03110•Nov 5, 2024•1 citation

Fast Stabiliser Simulation with Quadratic Form Expansions

Niel de Beaudrap, Steven Herbert

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.

arXiv:2109.08629•Quantum•Sep 15, 2022•28 citations
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 stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism.We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau.For example, we extract the stabiliser tableau of a 2n×2n matrix, promised to be a Clifford gate, in O(n2n) time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits.We provide implementations of our algorithms in Python and C++ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.
One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from O(elln2)O(\\ell n^2)O(elln2) to O(mn2)O(m n^2)O(mn2), where ell\\ellell is the total number of gates in the circuit, and mmm is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever ellggm\\ell \\gg mellggm. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of ketpsiotimesm\\ket{\\psi}^{\\otimes m}ketpsiotimesm, where ketpsi\\ket{\\psi}ketpsi is either a magic state or an equatorial state. \nFor any single qubit magic state ketpsi\\ket{\\psi}ketpsi, we find stabilizer decompositions of ketpsiotimesm\\ket{\\psi}^{\\otimes m}ketpsiotimesm with 2mlog2(3)/42^{m\\log_2(3)/4}2mlog2​(3)/4 terms. This improves on the best known bound of 2mlog2(7)/62^{m \\log_2(7)/6}2mlog2​(7)/6. \nSimilarly, for any single qubit equatorial state ketpsi\\ket{\\psi}ketpsi, we give a stabilizer decomposition of ketpsiotimesm\\ket{\\psi}^{\\otimes m}ketpsiotimesm with 2m/22^{m/2}2m/2 terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail, ddd-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo d>2d > 2d>2. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd ddd, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even ddd case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.
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.
We study incomplete sets of orthogonal stabiliser states that cannot be extended by a further stabiliser state orthogonal to all of its members. Such sets are the stabiliser analogue of unextendible product bases (UPBs), and we thus call them unextendible stabiliser bases (USBs). Leveraging the symplectic geometry underlying the nnn-qudit Pauli group in prime local dimension, we explicitly construct USBs for systems of four qubits and three qudits of odd prime local dimension. Moreover, we show that these are the respective minimal qubit, respectively qudit numbers for which such bases exist, and that USBs exist for all n≥4n\geq4n≥4 qubit and for all n≥3n\geq3n≥3 odd-prime-dimensional qudit systems. Finally, we compare the resource-theoretic aspects of USBs with those of UPBs. We establish that, analogous to the case of UPBs, the orthogonal complement of every unextendible stabiliser set is a stabiliser-free subspace, and its normalised projector is necessarily magic; moreover, it is bound magic in odd prime dimension, yet need not be for qubits. We also show that USB unextendibility alone imposes no uniform quantitative obstruction to discrimination by stabiliser operations.
Classical simulation of quantum physics is a central approach to investigating physical phenomena. Quantum computers enhance computational capabilities beyond those of classical resources, but it remains unclear to what extent existing limited quantum computers can contribute to this enhancement. In this work, we explore a new hybrid, efficient quantum-classical representation of quantum states, the multiple-basis representation. This representation consists of a linear combination of states that are sparse in some given and different bases, specified by quantum circuits. Such representation is particularly appealing when considering depth-limited quantum circuits within reach of current hardware. We analyze the expressivity of multiple-basis representation states depending on the classical simulability of their quantum circuits. In particular, we show that multiple-basis representation states include, but are not restricted to, both matrix-product states and stabilizer states. Furthermore, we find cases in which this representation can be used, namely approximation of ground states, simulation of deeper computations by specifying bases with shallow circuits, and a tomographical protocol to describe states as multiple-basis representations. We envision this work to open the path of simultaneous use of several hardware-friendly bases, a natural description of hybrid computational methods accessible for near-term hardware.
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.