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:2103.09999 · Physical Review Applied

Lower Bound for the T Count Via Unitary Stabilizer Nullity

Jiaqing Jiang, Xin Wang

Published Mar 15, 2023• 48 citations
arXivHTMLPDF

Abstract

We introduce magic measures to quantify the nonstabilizerness of multiqubit quantum gates and establish lower bounds on the $T$ count for fault-tolerant quantum computation. First, we introduce the stabilizer nullity of multiqubit unitary, which is based on the subgroup of the quotient Pauli group associated with the unitary. This unitary stabilizer nullity extends the state-stabilizer nullity by Beverland et al. [Quantum Sci. Technol. 5, 035009 (2020)] to a dynamic version. In particular, we show this nonstabilizerness measure has desirable properties, such as subadditivity under composition and additivity under tensor product. Second, we prove that a given unitary's stabilizer nullity is a lower bound for the $T$ count, utilizing the above properties in gate synthesis. Third, we compare the state and the unitary stabilizer nullity, proving that the lower bounds for the $T$ count obtained by the unitary stabilizer nullity are never less than the state-stabilizer nullity. Moreover, we show an explicit $n$-qubit unitary family of unitary stabilizer nullity $2n$, which implies that its $T$ count is at least $2n$. This gives an example where the bounds derived by the unitary stabilizer nullity strictly outperform the state-stabilizer nullity by a factor of 2. We finally showcase the advantages of unitary stabilizer nullity in estimating the $T$ count of quantum gates with interests.

DOI
10.1103/physrevapplied.19.034052

Related papers

Lower bounds on the non-Clifford resources for quantum computations

Michael E. Beverland, Earl T. Campbell, Mark Howard +1 more

Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.

arXiv:1904.01124•Quantum Science and Technology•Apr 15, 2020•192 citations

Pauli spectrum of quantum channels and the related magic-channel distillation bounds

Yiran Wang, Yongming Li

Nonstabilizerness (``magic'') is an essential part of quantum computation, so the quantitative study of nonstabilizerness has become a very important issue. Since researchers have defined the Pauli spectrum of quantum states, they can use it to calculate other nonstabilizerness measures such as stabilizer R\'enyi entropy and stabilizer nullity. At the same time, the study of the magic-channel resource theory has become a main direction in recent years. In this article we extend the definition of the Pauli spectrum to quantum channels and define the definitions of stabilizer R\'enyi entropy and stabilizer nullity for quantum channels based on the Pauli spectrum. Meanwhile, we study the properties of stabilizer R\'enyi entropy and stabilizer nullity of quantum channels and give the corresponding proofs. Additionally, this article gives the necessary and sufficient condition that the depolarizing channel is a completely stabilizer-preserving operation (CSPO), and we can calculate other channels. Furthermore, we verify that stabilizer R\'enyi entropy of quantum channels satisfies the amortization inequality so that the maximum value of the distillation bounds of the magic channels provided by the stabilizer R\'enyi entropy can be established. Therefore, we can give an alternative method to calculate the magic-channel distillation bounds. Moreover, we compare the channel distillation rate provided by stabilizer R\'enyi entropy with that provided by thauma and find that the channel distillation rate proposed in this article has higher distillation efficiency. Finally, the nonstabilizerness cost of the gate synthesis is given.

Physical Review A•Jan 3, 2025•3 citations

Nonstabilizerness via Matrix Product States in the Pauli Basis

Poetri Sonya Tarabunga, Emanuele Tirrito, Mari Carmen Bañuls +1 more

Nonstabilizerness, also known as "magic," stands as a crucial resource for achieving a potential advantage in quantum computing. Its connection to many-body physical phenomena is poorly understood at present, mostly due to a lack of practical methods to compute it at large scales. We present a novel approach for the evaluation of nonstabilizerness within the framework of matrix product states (MPSs), based on expressing the MPS directly in the Pauli basis. Our framework provides a powerful tool for efficiently calculating various measures of nonstabilizerness, including stabilizer Rényi entropies, stabilizer nullity, and Bell magic, and enables the learning of the stabilizer group of an MPS. We showcase the efficacy and versatility of our method in the ground states of Ising and XXZ spin chains, as well as in circuits dynamics that has recently been realized in Rydberg atom arrays, where we provide concrete benchmarks for future experiments on logical qubits up to twice the sizes already realized.

arXiv:2401.16498•Physical Review Letters•Jul 1, 2024•103 citations

Lower Bounds for Quantum Circuits

Ravi Rai

In quantum computing, computational tasks are represented by quantum circuits. These circuits are composed of gates whose physical realization comes at a cost. Typically, gates from the so-called Clifford group are considered cheap, while non Clifford gates are considered expensive. Consequently, non-Clifford operations are often seen as a resource whose use should be minimized. In this thesis, following recent work by Beverland and others, we study lower bounds for the number of non-Clifford gates in quantum circuits. We focus on lower bounds that can be derived from monotones, which are real-valued functions of quantum states that are non-increasing under Clifford operations. We first provide a detailed presentation of two recently introduced monotones: the stabilizer nullity and the dyadic monotone. We then discuss how these monotones can be used to give lower bounds for the non-Clifford resources for two important quantum operations: the multiply-controlled Pauli Z gate and the modular adder.

•Aug 20, 2021•0 citations

Exponentially Accelerated Sampling of Pauli Strings for Nonstabilizerness

Zhenyu Xiao, Shinsei Ryu

Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical framework for computing stabilizer Rényi entropies and stabilizer nullity of generic $N$-qubit wavefunctions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from $\mathcal{O}(2^N)$ to $\mathcal{O}(N)$. We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples shows no visible growth with $N$ in our benchmarks. Applying the method to $T$-doped random Clifford circuits, we identify the scrambling ratio $η$ (Clifford gates per $T$ gate) as the key parameter governing magic growth. Each $T$ gate approaches its dilute-limit nonstabilizerness power with only modest Clifford scrambling. Our approach enables quantitative studies of magic in highly entangled states and long-time nonequilibrium dynamics.

quant-pharXiv:2601.00761•Physical Review Letters•Jan 5, 2026•19 citations

Amortized Stabilizer Rényi Entropy of Quantum Dynamics

Chengkai Zhu, Yu-Ao Chen, Zhiping Liu +3 more

Magic states are essential resources for fault-tolerant quantum computation. We introduce the amortized stabilizer Rényi entropy (SRE), which quantifies the largest SRE increase generated by a unitary, including arbitrary pure inputs and reference systems. Initial nonstabilizerness can enhance this increase, whereas analogous amortized logarithmic robustness and extent collapse to stabilizer-input optimizations. We establish structural properties and exact amortized 2-SRE values for the $T$ and $CCZ$ gates. We then derive explicit lower bounds on approximate $T$-state cost, with diamond-distance error, allowing stabilizer ancillary states, Pauli measurements, and classical feedforward. A Choi-state witness gives computable bounds for quantum Fourier transforms, controlled rotations, fractional controlled-SWAP gates, and finite Heisenberg-chain evolutions. We distinguish the unrestricted optimization from its Choi witness and specify the access and precision requirements for estimating Pauli moments. An odd-moment variant yields a confidence-qualified cost witness from ordinary copies.

quant-pharXiv:2409.06659•Sep 11, 2024•5 citations
We introduce magic measures to quantify the nonstabilizerness of multiqubit quantum gates and establish lower bounds on the TTT count for fault-tolerant quantum computation. First, we introduce the stabilizer nullity of multiqubit unitary, which is based on the subgroup of the quotient Pauli group associated with the unitary. This unitary stabilizer nullity extends the state-stabilizer nullity by Beverland et al. [Quantum Sci. Technol. 5, 035009 (2020)] to a dynamic version. In particular, we show this nonstabilizerness measure has desirable properties, such as subadditivity under composition and additivity under tensor product. Second, we prove that a given unitary's stabilizer nullity is a lower bound for the TTT count, utilizing the above properties in gate synthesis. Third, we compare the state and the unitary stabilizer nullity, proving that the lower bounds for the TTT count obtained by the unitary stabilizer nullity are never less than the state-stabilizer nullity. Moreover, we show an explicit nnn-qubit unitary family of unitary stabilizer nullity 2n2n2n, which implies that its TTT count is at least 2n2n2n. This gives an example where the bounds derived by the unitary stabilizer nullity strictly outperform the state-stabilizer nullity by a factor of 2. We finally showcase the advantages of unitary stabilizer nullity in estimating the TTT count of quantum gates with interests.
Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.
Nonstabilizerness (``magic'') is an essential part of quantum computation, so the quantitative study of nonstabilizerness has become a very important issue. Since researchers have defined the Pauli spectrum of quantum states, they can use it to calculate other nonstabilizerness measures such as stabilizer R\'enyi entropy and stabilizer nullity. At the same time, the study of the magic-channel resource theory has become a main direction in recent years. In this article we extend the definition of the Pauli spectrum to quantum channels and define the definitions of stabilizer R\'enyi entropy and stabilizer nullity for quantum channels based on the Pauli spectrum. Meanwhile, we study the properties of stabilizer R\'enyi entropy and stabilizer nullity of quantum channels and give the corresponding proofs. Additionally, this article gives the necessary and sufficient condition that the depolarizing channel is a completely stabilizer-preserving operation (CSPO), and we can calculate other channels. Furthermore, we verify that stabilizer R\'enyi entropy of quantum channels satisfies the amortization inequality so that the maximum value of the distillation bounds of the magic channels provided by the stabilizer R\'enyi entropy can be established. Therefore, we can give an alternative method to calculate the magic-channel distillation bounds. Moreover, we compare the channel distillation rate provided by stabilizer R\'enyi entropy with that provided by thauma and find that the channel distillation rate proposed in this article has higher distillation efficiency. Finally, the nonstabilizerness cost of the gate synthesis is given.
Nonstabilizerness, also known as "magic," stands as a crucial resource for achieving a potential advantage in quantum computing. Its connection to many-body physical phenomena is poorly understood at present, mostly due to a lack of practical methods to compute it at large scales. We present a novel approach for the evaluation of nonstabilizerness within the framework of matrix product states (MPSs), based on expressing the MPS directly in the Pauli basis. Our framework provides a powerful tool for efficiently calculating various measures of nonstabilizerness, including stabilizer Rényi entropies, stabilizer nullity, and Bell magic, and enables the learning of the stabilizer group of an MPS. We showcase the efficacy and versatility of our method in the ground states of Ising and XXZ spin chains, as well as in circuits dynamics that has recently been realized in Rydberg atom arrays, where we provide concrete benchmarks for future experiments on logical qubits up to twice the sizes already realized.
In quantum computing, computational tasks are represented by quantum circuits. These circuits are composed of gates whose physical realization comes at a cost. Typically, gates from the so-called Clifford group are considered cheap, while non Clifford gates are considered expensive. Consequently, non-Clifford operations are often seen as a resource whose use should be minimized. In this thesis, following recent work by Beverland and others, we study lower bounds for the number of non-Clifford gates in quantum circuits. We focus on lower bounds that can be derived from monotones, which are real-valued functions of quantum states that are non-increasing under Clifford operations. We first provide a detailed presentation of two recently introduced monotones: the stabilizer nullity and the dyadic monotone. We then discuss how these monotones can be used to give lower bounds for the non-Clifford resources for two important quantum operations: the multiply-controlled Pauli Z gate and the modular adder.
Quantum magic, quantified by nonstabilizerness, measures departures from stabilizer structure and underlies potential quantum speedups. We introduce an efficient classical framework for computing stabilizer Rényi entropies and stabilizer nullity of generic NNN-qubit wavefunctions. The method combines the fast Walsh-Hadamard transform with an exact partition of Pauli operators, reducing the average cost per sampled Pauli string from O(2N)\mathcal{O}(2^N)O(2N) to O(N)\mathcal{O}(N)O(N). We further develop a Monte Carlo estimator with Clifford preconditioning and find that the required number of samples shows no visible growth with NNN in our benchmarks. Applying the method to TTT-doped random Clifford circuits, we identify the scrambling ratio ηηη (Clifford gates per TTT gate) as the key parameter governing magic growth. Each TTT gate approaches its dilute-limit nonstabilizerness power with only modest Clifford scrambling. Our approach enables quantitative studies of magic in highly entangled states and long-time nonequilibrium dynamics.
Magic states are essential resources for fault-tolerant quantum computation. We introduce the amortized stabilizer Rényi entropy (SRE), which quantifies the largest SRE increase generated by a unitary, including arbitrary pure inputs and reference systems. Initial nonstabilizerness can enhance this increase, whereas analogous amortized logarithmic robustness and extent collapse to stabilizer-input optimizations. We establish structural properties and exact amortized 2-SRE values for the TTT and CCZCCZCCZ gates. We then derive explicit lower bounds on approximate TTT-state cost, with diamond-distance error, allowing stabilizer ancillary states, Pauli measurements, and classical feedforward. A Choi-state witness gives computable bounds for quantum Fourier transforms, controlled rotations, fractional controlled-SWAP gates, and finite Heisenberg-chain evolutions. We distinguish the unrestricted optimization from its Choi witness and specify the access and precision requirements for estimating Pauli moments. An odd-moment variant yields a confidence-qualified cost witness from ordinary copies.