Lower bounds on the non-Clifford resources for quantum computations
arXiv:1904.01124 · doi:10.1088/2058-9565/ab8963
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 requires at least -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 or states needed to implement the ubiquitous modular adder and multiply-controlled- operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.
arXiv comment62 pages
References in corpus (30)
- Elementary gates for quantum computation
- 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
- Quantum Computing with Very Noisy Devices
- Synthesis of Quantum Logic Circuits
- Scalable Designs for Quasiparticle-Poisoning-Protected Topological Quantum Computation with Majorana Zero Modes
- Roads towards fault-tolerant universal quantum computation
- 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
- Minimal Universal Two-qubit Quantum Circuits
- Halving the cost of quantum addition
- Quantum circuits of T-depth one
- Quantum Circuits for Isometries
- Novel constructions for the fault-tolerant Toffoli gate
- Classification of topologically protected gates for local stabilizer codes
- Approximation by Quantum Circuits
- Multilevel distillation of magic states for quantum computing
- Efficient Computations of Encodings for Quantum Error Correction
- Fault-tolerant logical gates in quantum error-correcting codes
- Convex geometry of quantum resource quantification
- A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
- Catalysis and activation of magic states in fault tolerant architectures
- Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count
- Shorter gate sequences for quantum computing by mixing unitaries
- Protected gates for topological quantum field theories
- T-count optimization and Reed-Muller codes
- Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
Cited by in corpus (28)
- 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
- Grid-based methods for chemistry simulations on a quantum computer
- Improved upper bounds on the stabilizer rank of magic states
- 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 Classification of Clifford Gates over Qubits
- 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