Improved classical simulation of quantum circuits dominated by Clifford gates
arXiv:1601.07601 · doi:10.1103/PhysRevLett.116.250501
Abstract
The Gottesman-Knill theorem asserts that a quantum circuit composed of Clifford gates can be efficiently simulated on a classical computer. Here we revisit this theorem and extend it to quantum circuits composed of Clifford and T gates, where T is the single-qubit 45-degree phase shift. We assume that the circuit outputs a bit string x obtained by measuring some subset of w qubits. Two simulation tasks are considered: (1) computing the probability of a given output x, and (2) sampling x from the output probability distribution. It is shown that these tasks can be solved on a classical computer in time and respectively, where t is the number of T-gates, m is the total number of gates, and n is the number of qubits. The proposed simulation algorithms may serve as a verification tool for medium-size quantum computations that are dominated by Clifford gates. The main ingredient of both algorithms is a subroutine for approximating the norm of an n-qubit state which is given as a linear combination of stabilizer states. The subroutine runs in time , where is the relative error. We also develop techniques for approximating tensor products of "magic states" by linear combinations of stabilizer states. To demonstrate the power of the new simulation methods, we performed a classical simulation of a hidden shift quantum algorithm with 40 qubits, a few hundred Clifford gates, and nearly 50 T-gates.
arXiv commentv3 includes a correction to the description of the hidden shift algorithm
References in corpus (12)
- Surface codes: Towards practical large-scale quantum computation
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Improved Simulation of Stabilizer Circuits
- Topological Quantum Distillation
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- Simulating quantum computation by contracting tensor networks
- Methodology for quantum logic gate constructions
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- Classification of topologically protected gates for local stabilizer codes
- Stabilizer states and Clifford operations for systems of arbitrary dimensions, and modular arithmetic
- Fault-tolerant logical gates in quantum error-correcting codes
- Surface code implementation of block code state distillation
Cited by in corpus (218)
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum information processing with superconducting circuits: a review
- Quantum Computational Supremacy
- Quantum Error Mitigation
- Practical Quantum Error Mitigation for Near-Future Applications
- Application of a resource theory for magic states to fault-tolerant quantum computing
- The Future of Quantum Computing with Superconducting Qubits
- Qulacs: a fast and versatile quantum circuit simulator for research purpose
- Information Scrambling in Computationally Complex Quantum Circuits
- Trading classical and quantum computational resources
- Stabilizer Rényi entropy
- Simulation of quantum circuits by low-rank stabilizer decompositions
- QuEST and High Performance Simulation of Quantum Computers
- Quantum machine learning beyond kernel methods
- MQT Bench: Benchmarking Software and Design Automation Tools for Quantum Computing
- Challenges and Opportunities of Near-Term Quantum Computing Systems
- A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
- Many-body quantum magic
- Computational advantage of quantum random sampling
- Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
- Full-State Quantum Circuit Simulation by Using Data Compression
- Qibo: a framework for quantum simulation with hardware acceleration
- Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
- Quantifying quantum speedups: improved classical simulation from tighter magic monotones
- Quantifying magic for multi-qubit operations
- Towards Large-scale Functional Verification of Universal Quantum Circuits
- Robustness of Magic and Symmetries of the Stabiliser Polytope
- Universal Variational Quantum Computation
- No-Go Theorems for Quantum Resource Purification
- Architectures for quantum simulation showing a quantum speedup
- Quantum Chaos is Quantum
- Stabilizer entropies are monotones for magic-state resource theory
- Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
- Cross Entropy Benchmark for Measurement-Induced Phase Transitions
- Error mitigation for universal gates on encoded qubits
- Nonstabilizerness via matrix product states in the Pauli basis
- Fast quantum circuit cutting with randomized measurements
- Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
- Nonstabilizerness determining the hardness of direct fidelity estimation
- Simulation of Qubit Quantum Circuits via Pauli Propagation
- Dynamical Magic Transitions in Monitored Clifford+T Circuits
- Efficient unitary designs with a system-size independent number of non-Clifford gates
- Unbiased Simulation of Near-Clifford Quantum Circuits
- Transversality and lattice surgery: exploring realistic routes towards coupled logical qubits with trapped-ion quantum processors
- Non-stabilizerness versus entanglement in matrix product states
- qTorch: The Quantum Tensor Contraction Handler
- From estimation of quantum probabilities to simulation of quantum circuits
- Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
- Improved upper bounds on the stabilizer rank of magic states
- Efficient classical simulation of Clifford circuits with nonstabilizer input states
- No-go theorems for quantum resource purification II: new approach and channel theory
- Quantum advantage of unitary Clifford circuits with magic state inputs
- Quantum Entropy and Central Limit Theorem
- Pseudomagic Quantum States
- Formal Verification of Quantum Programs: Theory, Tools and Challenges
- Lower bound for the T count via unitary stabilizer nullity
- Artificial Intelligence for Quantum Computing
- Partially Fault-tolerant Quantum Computing Architecture with Error-corrected Clifford Gates and Space-time Efficient Analog Rotations
- Transitions in Entanglement Complexity in Random Circuits
- Magic in generalized Rokhsar-Kivelson wavefunctions
- Learning efficient decoders for quasi-chaotic quantum scramblers
- Error mitigation and quantum-assisted simulation in the error corrected regime
- Optimising Matrix Product State Simulations of Shor's Algorithm
- T-count and T-depth of any multi-qubit unitary
- Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
- Learning quantum circuits of some gates
- Accrediting outputs of noisy intermediate-scale quantum computing devices
- Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
- Classical simulation of Gaussian quantum circuits with non-Gaussian input states
- Fast estimation of outcome probabilities for quantum circuits
- Stabilizer extent is not multiplicative
- Unscrambling Quantum Information with Clifford decoders
- A brief introduction to quantum algorithms
- Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
- A single -gate makes distribution learning hard
- Efficient simulatability of continuous-variable circuits with large Wigner negativity
- A polynomial time and space heuristic algorithm for T-count
- Fourier expansion in variational quantum algorithms
- Quantum circuits and low-degree polynomials over F_2
- Magic-induced computational separation in entanglement theory
- Scrambling and quantum chaos indicators from long-time properties of operator distributions
- How to simulate quantum measurement without computing marginals
- Fast Stabiliser Simulation with Quadratic Form Expansions
- Nonstabilizerness of Permutationally Invariant Systems
- LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
- Phase transition in Stabilizer Entropy and efficient purity estimation
- Simulating quench dynamics on a digital quantum computer with data-driven error mitigation
- Magic of quantum hypergraph states
- Magic-State Functional Units: Mapping and Scheduling Multi-Level Distillation Circuits for Fault-Tolerant Quantum Architectures
- Classically estimating observables of noiseless quantum circuits
- Robustness of QMA against witness noise
- Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
- Magic Resources of the Heisenberg Picture
- A quantum primality test with order finding
- Probing quantum complexity via universal saturation of stabilizer entropies
- Quantifying dynamical magic with completely stabilizer preserving operations as free
- Classical simulation of non-Gaussian fermionic circuits
- Contextuality bounds the efficiency of classical simulation of quantum processes
- Synthesizing efficient circuits for Hamiltonian simulation
- Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
- Magic Resource Can Enhance the Quantum Capacity of Channels
- Gravitational back-reaction is magical
- Opening the Black Box Inside Grover's Algorithm
- Quantum Non-Local Nonstabilizerness
- Computational power of matchgates with supplementary resources
- Experimental demonstration of scalable cross-entropy benchmarking to detect measurement-induced phase transitions on a superconducting quantum processor
- Doped stabilizer states in many-body physics and where to find them
- Chaos and magic in the dissipative quantum kicked top
- Classical simulation of quantum circuits by half Gauss sums
- Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
- Stabilizer Tensor Networks with Magic State Injection
- Stabilizer rank and higher-order Fourier analysis
- Qibolab: an open-source hybrid quantum operating system
- Error mitigation by training with fermionic linear optics
- Pauli path simulations of noisy quantum circuits beyond average case
- Spectral Properties Versus Magic Generation in -doped Random Clifford Circuits
- Simulation of quantum optics by coherent state decomposition
- Continuous Hamiltonian dynamics on digital quantum computers without discretization error
- Quantum circuit compilation and hybrid computation using Pauli-based computation
- Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
- Volumetric Benchmarking of Error Mitigation with Qermit
- Clifford recompilation for faster classical simulation of quantum circuits
- Bridging magic and non-Gaussian resources via Gottesman-Kitaev-Preskill encoding
- Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
- Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
- The axiomatic and the operational approaches to resource theories of magic do not coincide
- Sharp complexity phase transitions generated by entanglement
- Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
- Improved simulation of quantum circuits dominated by free fermionic operations
- Decoding Merged Color-Surface Codes and Finding Fault-Tolerant Clifford Circuits Using Solvers for Satisfiability Modulo Theories
- Classical simulation of quantum circuits by dynamical localization: analytic results for Pauli-observable scrambling in time-dependent disorder
- Supervised learning of random quantum circuits via scalable neural networks
- Nonstabilizerness of a Boundary Time Crystal
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Optimal Hadamard gate count for Clifford synthesis of Pauli rotations sequences
- Classical simulation of non-Gaussian bosonic circuits
- Zero and Finite Temperature Quantum Simulations Powered by Quantum Magic
- Extracting randomness from magic quantum states
- Interplay of entanglement structures and stabilizer entropy in spin models
- The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus
- A Case for Synthesis of Recursive Quantum Unitary Programs
- Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
- On Classical and Hybrid Shadows of Quantum States
- Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
- Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications
- Scalable evaluation of quantum-circuit error loss using Clifford sampling
- Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
- Faster Born probability estimation via gate merging and frame optimisation
- Fermionic Magic Resources of Quantum Many-Body Systems
- Lower Bounds on Stabilizer Rank
- Efficient witnessing and testing of magic in mixed quantum states
- Classification of joint quantum measurements based on entanglement cost of localization
- Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
- Quantum Ruzsa Divergence to Quantify Magic
- Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
- Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
- Fault-tolerant compiling of classically hard IQP circuits on hypercubes
- Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
- New techniques for bounding stabilizer rank
- Fast simulation of planar Clifford circuits
- Feynman-path type simulation using stabilizer projector decomposition of unitaries
- Simulating Quantum Computations with Tutte Polynomials
- Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions
- Computing quantum magic of state vectors
- Classical simulation and quantum resource theory of non-Gaussian optics
- Designs from magic-augmented Clifford circuits
- Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits
- Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
- Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
- Methods for Classically Simulating Noisy Networked Quantum Architectures
- The 7 faces of quantum NP
- Certifying nonstabilizerness in quantum processors
- Faster computation of nonstabilizerness
- Lower T-count with faster algorithms
- A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
- Non-Clifford Cost of Random Unitaries
- Possibilistic simulation of quantum circuits by classical circuits
- Local spreading of stabilizer Rényi entropy in a brickwork random Clifford circuit
- The Future of Computing: Bits + Neurons + Qubits
- Straddling-gates problem in multipartite quantum systems
- HybridQ: A Hybrid Simulator for Quantum Circuits
- Leveraging commuting groups for an efficient variational Hamiltonian ansatz
- Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
- Logical Error Rates for the Surface Code Under a Mixed Coherent and Stochastic Circuit-Level Noise Model Inspired by Trapped Ions
- On the role of coherence for quantum computational advantage
- PAC-learning of free-fermionic states is NP-hard
- Invested and Potential Magic Resources in Measurement-Based Quantum Computation
- Improved Strong Simulation of Universal Quantum Circuits
- On Classical Simulation of Quantum Circuits Composed of Clifford Gates
- Non-stabilizerness and entanglement from cat-state injection
- Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
- Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
- On The Stabilizer Formalism And Its Generalization
- Characterization of non-adaptive Clifford channels
- Resource-efficient shadow tomography using equatorial stabilizer measurements
- Artificial intelligence for representing and characterizing quantum systems
- Unified Architecture for Quantum Lookup Tables
- Stabilizer Rényi Entropy for Translation-Invariant Matrix Product States
- Efficient simulation of logical magic state preparation protocols
- Simulating Quantum Circuits by Shuffling Paulis
- Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
- Classical Clifford+T Sampling without Computing Marginals
- Fine-grained quantum computational supremacy
- A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra
- Classical algorithms for measurement-adaptive Gaussian circuits
- Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
- Improved Weak Simulation of Universal Quantum Circuits by Correlated Sampling
- GCAMPS: A Scalable Classical Simulator for Qudit Systems
- On the extremal points of the -polytopes and classical simulation of quantum computation with magic states
- No-cost Bell nonlocality certification from quantum tomography and its applications in quantum-magic-resource witnessing
- Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
- Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
- Limits of Clifford Disentangling in Tensor Network States
- Convexity of noncontextual wirings and how they order the set of correlations
- Pseudoentanglement Ain't Cheap
- Noncontextual Pauli Hamiltonians
- Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes