Lower bound for the T count via unitary stabilizer nullity

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 multi-qubit 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. 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.

arXiv comment21 pages including appendix, v2 is closed to the published version

References in corpus (34)

• Surface codes: Towards practical large-scale quantum computation
• Quantum Teleportation is a Universal Computational Primitive
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Quantum Resource Theories
• Roads towards fault-tolerant universal quantum computation
• The Resource Theory of Stabilizer Computation
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Magic state distillation with low overhead
• Methodology for quantum logic gate constructions
• Hudson's Theorem for finite-dimensional quantum systems
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum computation with realistic magic state factories
• Exact synthesis of multiqubit Clifford+T circuits
• Lower bounds on the non-Clifford resources for quantum computations
• Quantifying the magic of quantum channels
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Quantifying magic for multi-qubit operations
• No-Go Theorems for Quantum Resource Purification
• Efficiently computable bounds for magic state distillation
• Convex geometry of quantum resource quantification
• A resource theory of quantum memories and their faithful verification with minimal assumptions
• Using and reusing coherence to realize quantum processes
• Fault-tolerant magic state preparation with flag qubits
• Benchmarking one-shot distillation in general quantum resource theories
• Resource theory of asymmetric distinguishability for quantum channels
• Towards low overhead magic state distillation
• Distillation with sublogarithmic overhead
• Fundamental limitations on distillation of quantum channel resources
• Quantifying the resource content of quantum channels: An operational approach
• Exact entanglement cost of quantum states and channels under PPT-preserving operations

Cited by in corpus (23)

• Stabilizer entropies and nonstabilizerness monotones
• Measuring nonstabilizerness via multifractal flatness
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Efficient quantum algorithms for stabilizer entropies
• Entanglement-magic separation in hybrid quantum circuits
• Learning t-doped stabilizer states
• Pseudomagic Quantum States
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Magic-induced computational separation in entanglement theory
• Nonstabilizerness of Permutationally Invariant Systems
• Magic Resources of the Heisenberg Picture
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Chaos and magic in the dissipative quantum kicked top
• Magic of Random Matrix Product States
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Nonstabilizerness of a Boundary Time Crystal
• Bridging Entanglement and Magic Resources within Operator Space
• Disentangling magic states with classically simulable quantum circuits
• Certifying nonstabilizerness in quantum processors
• Rise and fall of nonstabilizerness via random measurements
• Enhancement of non-Stabilizerness within Indefinite Causal Order