Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count

Abstract

We present an infinite family of protocols to distill magic states for $T$-gates that has a low space overhead and uses an asymptotic number of input magic states to achieve a given target error that is conjectured to be optimal. The space overhead, defined as the ratio between the physical qubits to the number of output magic states, is asymptotically constant, while both the number of input magic states used per output state and the $T$-gate depth of the circuit scale linearly in the logarithm of the target error $\delta$ (up to $\log \log 1/\delta$). Unlike other distillation protocols, this protocol achieves this performance without concatenation and the input magic states are injected at various steps in the circuit rather than all at the start of the circuit. The protocol can be modified to distill magic states for other gates at the third level of the Clifford hierarchy, with the same asymptotic performance. The protocol relies on the construction of weakly self-dual CSS codes with many logical qubits and large distance, allowing us to implement control-SWAPs on multiple qubits. We call this code the "inner code". The control-SWAPs are then used to measure properties of the magic state and detect errors, using another code that we call the "outer code". Alternatively, we use weakly-self dual CSS codes which implement controlled Hadamards for the inner code, reducing circuit depth. We present several specific small examples of this protocol.

39 pages, (v2) renamed "odd" and "even" weakly self-dual CSS codes of (v1) to "normal" and "hyperbolic" codes, respectively. (v3) published in Quantum

References in corpus (14)

• Surface codes: Towards practical large-scale quantum computation
• Topological Quantum Distillation
• Topological fault-tolerance in cluster state quantum computation
• Restrictions on Transversal Encoded Quantum Gate Sets
• Magic state distillation with low overhead
• Novel constructions for the fault-tolerant Toffoli gate
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Quantum computation with realistic magic state factories
• Improved magic states distillation for quantum universality
• Multilevel distillation of magic states for quantum computing
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• Distilling one-qubit magic states into Toffoli states
• Reducing the quantum computing overhead with complex gate distillation

Cited by in corpus (45)

• The Future of Quantum Computing with Superconducting Qubits
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Building a fault-tolerant quantum computer using concatenated cat codes
• Magic State Distillation: Not as Costly as You Think
• Lower bounds on the non-Clifford resources for quantum computations
• Quantifying the magic of quantum channels
• Quantifying magic for multi-qubit operations
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• No-Go Theorems for Quantum Resource Purification
• Efficiently computable bounds for magic state distillation
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Fault-tolerant magic state preparation with flag qubits
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
• Nontrivial Quantum Cellular Automata in Higher Dimensions
• Cost-Reduced All-Gaussian Universality with the Gottesman-Kitaev-Preskill Code: Resource-Theoretic Approach to Cost Analysis
• Clifford Quantum Cellular Automata: Trivial group in 2D and Witt group in 3D
• Robust Majorana magic gates via measurements
• A Family of Quantum Codes with Exotic Transversal Gates
• Qutrit and Ququint Magic States
• Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Magic State Distillation from Entangled States
• Logical Clifford Synthesis for Stabilizer Codes
• Fault-tolerant Post-Selection for Low Overhead Magic State Preparation
• Classification of Small Triorthogonal Codes
• Towers of generalized divisible quantum codes
• Fermion-Parity-Based Computation and its Majorana-Zero-Mode Implementation
• Quantum Pin Codes
• Fractional Chern insulator edges and layer-resolved lattice contacts
• Quantum Codes from Twisted Unitary $t$-groups
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Everything You Always Wanted to Know About Quantum Circuits
• A new twist on the Majorana surface code: Bosonic and fermionic defects for fault-tolerant quantum computation
• Measurement sequences for magic state distillation
• Rigorous noise reduction with quantum autoencoders
• Efficient fault-tolerant implementations of non-Clifford gates with reconfigurable atom arrays
• Color codes with twists: construction and universal gate set implementation
• Low Overhead Qutrit Magic State Distillation
• On the Hardness of Measuring Magic
• General entropic constraints on CSS codes within magic distillation protocols
• Logical Noise Bias in Magic State Injection