Application of a resource theory for magic states to fault-tolerant quantum computing

Abstract

Motivated by their necessity for most fault-tolerant quantum computation schemes, we formulate a resource theory for magic states. We first show that robustness of magic is a well-behaved magic monotone that operationally quantifies the classical simulation overhead for a Gottesman-Knill type scheme using ancillary magic states. Our framework subsequently finds immediate application in the task of synthesizing non-Clifford gates using magic states. When magic states are interspersed with Clifford gates, Pauli measurements and stabilizer ancillas - the most general synthesis scenario - then the class of synthesizable unitaries is hard to characterize. Our techniques can place non-trivial lower bounds on the number of magic states required for implementing a given target unitary. Guided by these results we have found new and optimal examples of such synthesis.

arXiv commentV2: Author's final copy. Minor corrections vs version 1. 5+5 pages, Supplementary Material available at http://tinyurl.com/jygz3zx

References in corpus (34)

• Quantum Teleportation is a Universal Computational Primitive
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Quantum Computing with Very Noisy Devices
• Contextuality supplies the magic for quantum computation
• Robustness of entanglement
• Robustness of coherence: An operational and observable measure of quantum coherence
• The Resource Theory of Stabilizer Computation
• Positive Wigner functions render classical simulation of quantum computation efficient
• Negative Quasi-Probability as a Resource for Quantum Computation
• The general structure of quantum resource theories
• Methodology for quantum logic gate constructions
• Hudson's Theorem for finite-dimensional quantum systems
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• A mathematical theory of resources
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• (Quantumness in the context of) Resource Theories
• Quantum circuits of T-depth one
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Novel constructions for the fault-tolerant Toffoli gate
• How robust is a quantum gate in the presence of noise?
• Wigner function negativity and contextuality in quantum computation on rebits
• Universal quantum computation with little entanglement
• Quantifying Contextuality
• Catalysis and activation of magic states in fault tolerant architectures
• Efficient Decomposition of Single-Qubit Gates into $V$ Basis Circuits
• Quantum interference as a resource for quantum speedup
• Classical simulatability, entanglement breaking, and quantum computation thresholds
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• Noise Thresholds for Higher Dimensional Systems using the Discrete Wigner Function
• An efficient magic state approach to small angle rotations
• States that are far from being stabilizer states
• Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers

Cited by in corpus (250)

• Quantum Resource Theories
• Practical Quantum Error Mitigation for Near-Future Applications
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Halving the cost of quantum addition
• Resource theory of quantum non-Gaussianity and Wigner negativity
• The SIC Question: History and State of Play
• General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
• Convex resource theory of non-Gaussianity
• Many-body quantum magic
• A resource theory of superposition
• Operational Advantage of Quantum Resources in Subchannel Discrimination
• Quantifying the Imaginarity of Quantum Mechanics
• Lower bounds on the non-Clifford resources for quantum computations
• Quantifying the magic of quantum channels
• Operational Resource Theory of Quantum Channels
• Quantifying nonstabilizerness of matrix product states
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Stabilizer entropies and nonstabilizerness monotones
• Quantifying magic for multi-qubit operations
• Contextuality and Wigner function negativity in qubit quantum computation
• Measuring magic on a quantum processor
• Scalable measures of magic resource for quantum computers
• Robustness of Magic and Symmetries of the Stabiliser Polytope
• Circuit knitting with classical communication
• One-Shot Operational Quantum Resource Theory
• No-Go Theorems for Quantum Resource Purification
• Conformal field theories are magical
• Efficiently computable bounds for magic state distillation
• Convex geometry of quantum resource quantification
• Stabilizer entropies are monotones for magic-state resource theory
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Nonstabilizerness via matrix product states in the Pauli basis
• Application of the Resource Theory of Channels to Communication Scenarios
• Benchmarking one-shot distillation in general quantum resource theories
• Phase space simulation method for quantum computation with magic states on qubits
• Measuring nonstabilizerness via multifractal flatness
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• Optimal resource cost for error mitigation
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Pauli Spectrum and Non-stabilizerness of Typical Quantum Many-Body States
• Efficient quantum algorithms for stabilizer entropies
• Operational interpretation of weight-based resource quantifiers in convex quantum resource theories of states
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Dynamical Entanglement
• On the statistical complexity of quantum circuits
• Resource theory of quantum scrambling
• Fundamental limitations on distillation of quantum channel resources
• Skew informations from an operational view via resource theory of asymmetry
• Quantifying the resource content of quantum channels: An operational approach
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Axiomatic and operational connections between the $l_1$-norm of coherence and negativity
• Physical Implementability of Linear Maps and Its Application in Error Mitigation
• Unbiased Simulation of Near-Clifford Quantum Circuits
• Non-stabilizerness versus entanglement in matrix product states
• Coherence requirements for quantum communication from hybrid circuit dynamics
• Complexity of frustration: a new source of non-local non-stabilizerness
• From estimation of quantum probabilities to simulation of quantum circuits
• Quantification and manipulation of magic states
• Resource speed limits: Maximal rate of resource variation
• Probabilistic transformations of quantum resources
• Cost-Reduced All-Gaussian Universality with the Gottesman-Kitaev-Preskill Code: Resource-Theoretic Approach to Cost Analysis
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Stabilizer entropy dynamics after a quantum quench
• A hidden variable model for universal quantum computation with magic states on qubits
• No-go theorems for quantum resource purification II: new approach and channel theory
• Symmetric Informationally Complete Measurements Identify the Irreducible Difference between Classical and Quantum Systems
• Symmetry-protected sign problem and magic in quantum phases of matter
• Entanglement-magic separation in hybrid quantum circuits
• Lower bound for the T count via unitary stabilizer nullity
• Quantum Entropy and Central Limit Theorem
• Pseudomagic Quantum States
• Magic in generalized Rokhsar-Kivelson wavefunctions
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Characterization of an operational quantum resource in a critical many-body system
• Framework for resource quantification in infinite-dimensional general probabilistic theories
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Learning quantum circuits of some $T$ gates
• Stabilizer extent is not multiplicative
• Fast estimation of outcome probabilities for quantum circuits
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Fisher information universally identifies quantum resources
• Tight constraints on probabilistic convertibility of quantum states
• Quantification of quantum dynamics with input-output games
• All states are universal catalysts in quantum thermodynamics
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Stabilizer entropy in non-integrable quantum evolutions
• General Quantum Resource Theories: Distillation, Formation and Consistent Resource Measures
• Resource theory of quantum uncomplexity
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Nonstabilizerness of Permutationally Invariant Systems
• Virtual quantum resource distillation
• Retrieving information from a black hole using quantum machine learning
• Qutrit and Ququint Magic States
• Magic of quantum hypergraph states
• Universal limitations on implementing resourceful unitary evolutions
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Magic Resources of the Heisenberg Picture
• Quantifying non-stabilizerness via information scrambling
• Probing quantum complexity via universal saturation of stabilizer entropies
• Doubly optimal parallel wire cutting without ancilla qubits
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Hybrid Stabilizer Matrix Product Operator
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Magic State Distillation from Entangled States
• Resource theory of superposition: State transformations
• Classical simulation of non-Gaussian fermionic circuits
• Multi-object operational tasks for convex quantum resource theories
• Stabilizer disentangling of conformal field theories
• One-Shot Yield-Cost Relations in General Quantum Resource Theories
• Handbook for Quantifying Robustness of Magic
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Efficient mutual magic and magic capacity with matrix product states
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Quantum Non-Local Nonstabilizerness
• Effects of quantum resources on the statistical complexity of quantum circuits
• The role of cohomology in quantum computation with magic states
• Coherence makes quantum systems 'magical'
• Stabilizer entropy of quantum tetrahedra
• Chaos and magic in the dissipative quantum kicked top
• Non-stabilizerness in kinetically-constrained Rydberg atom arrays
• Resource theory of quantum coherence with probabilistically non-distinguishable pointers and corresponding wave-particle duality
• Arbitrary Amplification of Quantum Coherence in Asymptotic and Catalytic Transformation
• Entanglement and Stabilizer entropies of random bipartite pure quantum states
• The operational advantages provided by non-classical teleportation
• Virtual quantum resource distillation: General framework and applications
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Characterisation of quantum betting tasks in terms of Arimoto mutual information
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
• Magic of Random Matrix Product States
• Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions
• Pseudorandom density matrices
• Clifford recompilation for faster classical simulation of quantum circuits
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• The operational significance of the quantum resource theory of Buscemi nonlocality
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Long-range nonstabilizerness and phases of matter
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Stabilizer Rényi Entropy and Conformal Field Theory
• On Groups in the Qubit Clifford Hierarchy
• Bridging Entanglement and Magic Resources within Operator Space
• Nonstabilizerness of a Boundary Time Crystal
• Coherence manipulation in asymmetry and thermodynamics
• Interplay of entanglement structures and stabilizer entropy in spin models
• Measurement-Induced Entanglement Phase Transition in Free Fermion Systems
• Asymptotically Consistent Measures of General Quantum Resources: Discord, Non-Markovianity, and Non-Gaussianity
• Zero and Finite Temperature Quantum Simulations Powered by Quantum Magic
• Sufficient condition for universal quantum computation using bosonic circuits
• Stoquasticity in circuit QED
• Stability of classical shadows under gate-dependent noise
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Extracting randomness from magic quantum states
• A nonstabilizerness monotone from stabilizerness asymmetry
• Mixed-state additivity properties of magic monotones based on quantum relative entropies for single-qubit states and beyond
• Pauli-based model of quantum computation with higher-dimensional systems
• Quantifying fermionic nonlinearity of quantum circuits
• The non-stabilizerness of fermionic Gaussian states
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Fermionic Magic Resources of Quantum Many-Body Systems
• Geometric-Like imaginarity: quantification and state conversion
• Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications
• Faster Born probability estimation via gate merging and frame optimisation
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Optimal wire cutting with classical communication
• Rademacher complexity of noisy quantum circuits
• Unlocking early fault-tolerant quantum computing with mitigated magic dilution
• Efficient witnessing and testing of magic in mixed quantum states
• Quantum Ruzsa Divergence to Quantify Magic
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Maximal Magic for Two-qubit States
• Computing quantum magic of state vectors
• Clifford operations and homological codes for rotors and oscillators
• Building Qutrit Diagonal Gates from Phase Gadgets
• Black Box Work Extraction and Composite Hypothesis Testing
• Non-stabilizerness in quantum-enhanced metrological protocols
• Prepare-and-Magic: Semi-Device Independent Magic Certification in the Prepare-and-Measure Scenario
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• Infinitesimal reference frames suffice to determine the asymmetry properties of a quantum system
• Non-stabilizerness of Neural Quantum States
• Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search
• Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits
• Counting stabiliser codes for arbitrary dimension
• Resource Theory of Non-absolute Separability
• A Compendious Review of Majorization-Based Resource Theories: Quantum Information and Quantum Thermodynamics
• Automatic Test Pattern Generation for Robust Quantum Circuit Testing
• A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
• Unified Framework for Calculating Convex Roof Resource Measures
• Covariant influences for finite discrete dynamical systems
• Role of quantum state texture in probing resource theories and quantum phase transition
• Hidden variable model for quantum computation with magic states on qudits of any dimension
• Local spreading of stabilizer Rényi entropy in a brickwork random Clifford circuit
• Unconditional quantum magic advantage in shallow circuit computation
• Faster computation of nonstabilizerness
• Quantifying the imaginarity via different distance measures
• Nonstabilizerness and Error Resilience in Noisy Quantum Circuits
• One-Shot Static Entanglement Cost of Bipartite Quantum Channels
• Projective robustness for quantum channels and measurements and their operational significance
• Quantum coherence with incomplete set of pointers and corresponding wave-particle duality
• Gleipnir: Toward Practical Error Analysis for Quantum Programs (Extended Version)
• Wasserstein Complexity of Quantum Circuits
• Fundamental limits on concentrating and preserving tensorized quantum resources
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Rise and fall of nonstabilizerness via random measurements
• Choi-Defined Resource Theories
• Wigner's Theorem for stabilizer states and quantum designs
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Invariant Off-Diagonality: SICs as Equicoherent Quantum States
• Improved Strong Simulation of Universal Quantum Circuits
• Non-stabilizerness and entanglement from cat-state injection
• Low Overhead Qutrit Magic State Distillation
• Invested and Potential Magic Resources in Measurement-Based Quantum Computation
• Multi-object operational tasks for measurement incompatibility
• Improving quantum channel discrimination with resourceful states
• Experimentally validated quantum-secure federated learning over a multi-user quantum network
• Grand Unification of All Discrete Wigner Functions on $d\times d$ Phase Space
• Scalable projected entangled-pair state representation of random quantum circuit states
• Analyzing the free states of one quantum resource theory as resource states of another
• Perspectives on Utilization of Measurements in Quantum Algorithms
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• On the Hardness of Measuring Magic
• Characterization of non-adaptive Clifford channels
• Sampling-based quasiprobability simulation for fault-tolerant quantum error correction on the surface codes under coherent noise
• Enhancement of non-Stabilizerness within Indefinite Causal Order
• Coherence-induced deep thermalization transition in random permutation quantum dynamics
• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• Connecting Magic Dynamics in Thermofield Double States to Spectral Form Factors
• Spectral signatures of nonstabilizerness and criticality in infinite matrix product states
• Complexity of Quantum Trajectories
• Quantifying magic via quantum $(\alpha ,\beta )$ Jensen-Shannon divergence
• Circuit cutting with classical side information
• General entropic constraints on CSS codes within magic distillation protocols
• Harvesting stabilizer entropy and non-locality from a quantum field
• Halving the cost of quantum multiplexed rotations
• Stabilizer Rényi Entropy for Translation-Invariant Matrix Product States
• Mathematical methods for resource-based type theories
• Exact and Efficient Stabilizer Simulation of Thermal-Relaxation Noise for Quantum Error Correction
• Equivalence of Stabilizer and Shannon Rényi Entropies: Exact Results for Quantum Critical Chains
• A Study on Stabilizer Rényi Entropy Estimation using Machine Learning
• On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states
• Van Hove singularities in stabilizer entropy densities
• Constructing all qutrit controlled Clifford+T gates in Clifford+T
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
• Scalable protocol to coherence estimation from scarce data: Theory and experiment
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• No-cost Bell nonlocality certification from quantum tomography and its applications in quantum-magic-resource witnessing