Magic State Distillation: Not as Costly as You Think

Abstract

Despite significant overhead reductions since its first proposal, magic state distillation is often considered to be a very costly procedure that dominates the resource cost of fault-tolerant quantum computers. The goal of this work is to demonstrate that this is not true. By writing distillation circuits in a form that separates qubits that are capable of error detection from those that are not, most logical qubits used for distillation can be encoded at a very low code distance. This significantly reduces the space-time cost of distillation, as well as the number of qubits. In extreme cases, it can cost less to distill a magic state than to perform a logical Clifford gate on full-distance logical qubits.

arXiv comment22 pages, 22 figures; Supplementary Material can be found at https://github.com/litinski/magicstates ; v2: Fixed a mistake in the protocol and updated overhead estimates; v3: Added Appendix on faulty T measurements

References in corpus (36)

• Fault-tolerant quantum computation by anyons
• Surface codes: Towards practical large-scale quantum computation
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Error Correction for Quantum Memories
• Reliable Quantum Computers
• Roads towards fault-tolerant universal quantum computation
• Surface code quantum computing by lattice surgery
• Benchmarking an 11-qubit quantum computer
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• 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
• Quantum computation with realistic magic state factories
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Multilevel distillation of magic states for quantum computing
• Surface code implementation of block code state distillation
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• A magic state's fidelity can be superior to the operations that created it
• Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes
• Fault-tolerant magic state preparation with flag qubits
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• A fault-tolerant non-Clifford gate for the surface code in two dimensions
• Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count
• Low overhead quantum computation using lattice surgery
• Unifying gate-synthesis and magic state distillation
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• T-count optimization and Reed-Muller codes
• Stacked codes: universal fault-tolerant quantum computation in a two-dimensional layout
• Reducing the quantum computing overhead with complex gate distillation
• Quantum computing by color-code lattice surgery
• Gauge color codes in two dimensions
• Simple scheme for encoding and decoding a qubit in unknown state for various topological codes
• 2D quantum computation with 3D topological codes
• Doubled Color Codes

Cited by in corpus (128)

• Quantum computational chemistry
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Quantum Error Mitigation
• The Future of Quantum Computing with Superconducting Qubits
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Building a fault-tolerant quantum computer using concatenated cat codes
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• A perspective on the current state-of-the-art of quantum computing for drug discovery applications
• Encoding a magic state with beyond break-even fidelity
• Efficient classical simulation of noisy random quantum circuits in one dimension
• A fault-tolerant continuous-variable measurement-based quantum computation architecture
• Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
• Early Fault-Tolerant Quantum Computing
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• The cost of universality: A comparative study of the overhead of state distillation and code switching with color codes
• Error mitigation for universal gates on encoded qubits
• Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
• Benchmarking quantum computers
• Logical blocks for fault-tolerant topological quantum computation
• Error Rates and Resource Overheads of Repetition Cat Qubits
• Experimental Demonstration of Logical Magic State Distillation
• Fault-Tolerant Quantum Gates with Defects in Topological Stabiliser Codes
• The Impact of Hardware Specifications on Reaching Quantum Advantage in the Fault Tolerant Regime
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Partitioning qubits in hypergraph product codes to implement logical gates
• Morphing quantum codes
• Techniques for combining fast local decoders with global decoders under circuit-level noise
• Scalable Networking of Neutral-Atom Qubits: Nanofiber-Based Approach for Multiprocessor Fault-Tolerant Quantum Computer
• A High Performance Compiler for Very Large Scale Surface Code Computations
• A Family of Quantum Codes with Exotic Transversal Gates
• Universal Fault-Tolerant Quantum Computing with Stabiliser Codes
• Universal limitations on implementing resourceful unitary evolutions
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• Constraints on magic state protocols from the statistical mechanics of Wigner negativity
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code
• A diagrammatic approach to variational quantum ansatz construction
• Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus
• Reducing 2-QuBit Gate Count for ZX-Calculus based Quantum Circuit Optimization
• Resource theory of superposition: State transformations
• Efficient Magic State Distillation by Zero-Level Distillation
• Fault-tolerant Post-Selection for Low Overhead Magic State Preparation
• Classification of Small Triorthogonal Codes
• Quantum Simulations of Chemistry in First Quantization with any Basis Set
• Architecture aware compilation of quantum circuits via lazy synthesis
• Error-corrected Hadamard gate simulated at the circuit level
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Color code decoder with improved scaling for correcting circuit-level noise
• Fermion-Parity-Based Computation and its Majorana-Zero-Mode Implementation
• Realistic Cost to Execute Practical Quantum Circuits using Direct Clifford+T Lattice Surgery Compilation
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories
• Scalable noise characterization of syndrome-extraction circuits with averaged circuit eigenvalue sampling
• Long-range nonstabilizerness and phases of matter
• Comparative study of quantum error correction strategies for the heavy-hexagonal lattice
• Compilation of a simple chemistry application to quantum error correction primitives
• Experimental Demonstration of High-Fidelity Logical Magic States from Code Switching
• Stabilizer Rényi Entropy and Conformal Field Theory
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz
• Non-Pauli topological stabilizer codes from twisted quantum doubles
• Quantum Codes from Twisted Unitary $t$-groups
• Sufficient condition for universal quantum computation using bosonic circuits
• Universal resource-efficient topological measurement-based quantum computation via color-code-based cluster states
• A nonstabilizerness monotone from stabilizerness asymmetry
• Mitigating errors in logical qubits
• A SAT Scalpel for Lattice Surgery: Representation and Synthesis of Subroutines for Surface-Code Fault-Tolerant Quantum Computing
• Distributed Quantum Computing with QMPI
• Low-overhead quantum computing with the color code
• Concatenation Schemes for Topological Fault-tolerant Quantum Error Correction
• Code switching revisited: Low-overhead magic state preparation using color codes
• Accelerating Quantum Algorithms with Precomputation
• Low-overhead magic state distillation with color codes
• Efficient witnessing and testing of magic in mixed quantum states
• Bulk-to-boundary anyon fusion from microscopic models
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
• Quantum Computation of Electronic Structure with Projector Augmented-Wave Method and Plane Wave Basis Set
• Realizing Lattice Surgery on Two Distance-Three Repetition Codes with Superconducting Qubits
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Fault-Tolerant Preparation of Quantum Polar Codes Encoding One Logical Qubit
• Code conversion with the quantum Golay code for a universal transversal gate set
• Leveraging Zero-Level Distillation to Generate High-Fidelity Magic States
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Classical product code constructions for quantum Calderbank-Shor-Steane codes
• A new twist on the Majorana surface code: Bosonic and fermionic defects for fault-tolerant quantum computation
• Low-overhead non-Clifford fault-tolerant circuits for all non-chiral abelian topological phases
• Synchronization for Fault-Tolerant Quantum Computers
• Locality-aware Pauli-based computation for local magic state preparation
• Certifying nonstabilizerness in quantum processors
• Measurement sequences for magic state distillation
• Rescaling decoder for 2D topological quantum color codes on 4.8.8 lattices
• LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
• The resource cost of large scale quantum computing
• Magic State Injection with Erasure Qubits
• End-to-end switchless architecture for fault-tolerant photonic quantum computing
• Almost fault-tolerant quantum machine learning with drastic overhead reduction
• Non-stabilizerness and entanglement from cat-state injection
• Color codes with twists: construction and universal gate set implementation
• Phase estimation with partially randomized time evolution
• Low Overhead Qutrit Magic State Distillation
• Superconducting qubits in the millions: the potential and limitations of modularity
• Measurement-free code-switching for low overhead quantum computation using permutation invariant codes
• Optimal Scheduling of Graph States via Path Decompositions
• Logical Noise Bias in Magic State Injection
• General entropic constraints on CSS codes within magic distillation protocols
• Measurement Schemes for Quantum Linear Equation Solvers
• High-fidelity initialization a logical qubit with multiple injections
• Noise-Agnostic Unbiased Quantum Error Mitigation for Logical Qubits
• Catalytic $z$-rotations in constant $T$-depth
• Noise-Canceling Quantum Feedback: non-Hermitian Dynamics with Applications to State Preparation and Magic State Distillation
• Unfolded distillation: very low-cost magic state preparation for biased-noise qubits
• Entanglement boosting: Low-volume logical Bell pair preparation for distributed fault-tolerant quantum computation
• Error-mitigated initialization of surface codes with non-Pauli stabilizers
• Weakly Fault-Tolerant Computation in a Quantum Error-Detecting Code
• Comparison of spin-qubit architectures for quantum error-correcting codes
• Measurement-Driven Adaptive Low-Overhead Implementation of Multi-Controlled Toffoli Gates
• RESCQ: Realtime Scheduling for Continuous Angle Quantum Error Correction Architectures
• General many-body entanglement swapping protocol: opportunities for distributed quantum computing
• Managing Classical Processing Requirements for Quantum Error Correction
• Efficient decoding of stabilizer code by single-qubit local operations and classical communication
• Benchmarking fault-tolerant quantum computing hardware via QLOPS
• qSIEVE: Efficient qLDPC Memory via Systolic Movement in Atom Arrays
• Network Requirements for Distributed Quantum Computation
• iSwitch: QEC on Demand via In-Situ Encoding of Bare Qubits for Ion Trap Architectures
• Universal quantum computation via scalable measurement-free error correction
• Flexible Fault Tolerant Gate Gadgets
• Planar fault-tolerant circuits for non-Clifford gates on the 2D color code