Lower bounds on the non-Clifford resources for quantum computations

Abstract

We establish lower-bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks, treating stabilizer operations as free. Our bounds apply to adaptive computations using measurements and an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational tasks. 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 close to optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision $\epsilon$ requires at least $1/7\cdot {\log }_2(1/\epsilon )-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 $\epsilon$. 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.

62 pages

References in corpus (12)

• Surface codes: Towards practical large-scale quantum computation
• Synthesis of Quantum Logic Circuits
• Restrictions on Transversal Encoded Quantum Gate Sets
• Application of a resource theory for magic states to fault-tolerant quantum computing
• A random compiler for fast Hamiltonian simulation
• Magic state distillation with low overhead
• Halving the cost of quantum addition
• Quantum circuits of T-depth one
• Novel constructions for the fault-tolerant Toffoli gate
• Multilevel distillation of magic states for quantum computing
• Fault-tolerant logical gates in quantum error-correcting codes
• Catalysis and activation of magic states in fault tolerant architectures

Cited by in corpus (27)

• Stabilizer Rényi entropy
• Quantifying nonstabilizerness of matrix product states
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Scalable measures of magic resource for quantum computers
• Measuring magic on a quantum processor
• No-Go Theorems for Quantum Resource Purification
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Early fault-tolerant simulations of the Hubbard model
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Resources for bosonic quantum computational advantage
• Complexity of frustration: a new source of non-local non-stabilizerness
• Improved upper bounds on the stabilizer rank of magic states
• Grid-based methods for chemistry simulations on a quantum computer
• Lower bound for the T count via unitary stabilizer nullity
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Shorter quantum circuits via single-qubit gate approximation
• Qutrit and Ququint Magic States
• Holomorphic representation of quantum computations
• Quantifying non-stabilizerness via information scrambling
• Magic State Distillation from Entangled States
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• New techniques for bounding stabilizer rank
• Non-Pauli Errors in the Three-Dimensional Surface Code
• Notes on distinguishability of postselected computations
• Constructing all qutrit controlled Clifford+T gates in Clifford+T