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.

21 pages including appendix, v2 is closed to the published version

References in corpus (5)

• Surface codes: Towards practical large-scale quantum computation
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Magic state distillation with low overhead
• Novel constructions for the fault-tolerant Toffoli gate
• Exact synthesis of multiqubit Clifford+T circuits

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