Improved classical simulation of quantum circuits dominated by Clifford gates

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 $poly(n,m)+2^{0.5t}{t}^3$ and $poly(n,m)+2^{0.23t}{t}^3{w}^3$ 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 $\chi$ stabilizer states. The subroutine runs in time $\chi n^3{\epsilon }^{-2}$, where $\epsilon$ 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.

v3 includes a correction to the description of the hidden shift algorithm

References in corpus (3)

• Surface codes: Towards practical large-scale quantum computation
• Topological Quantum Distillation
• Fault-tolerant logical gates in quantum error-correcting codes

Cited by in corpus (216)

• 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
• 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
• Transversality and lattice surgery: exploring realistic routes towards coupled logical qubits with trapped-ion quantum processors
• Unbiased Simulation of Near-Clifford Quantum Circuits
• qTorch: The Quantum Tensor Contraction Handler
• Non-stabilizerness versus entanglement in matrix product states
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• From estimation of quantum probabilities to simulation of quantum circuits
• 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
• Formal Verification of Quantum Programs: Theory, Tools and Challenges
• Quantum Entropy and Central Limit Theorem
• Lower bound for the T count via unitary stabilizer nullity
• Pseudomagic Quantum States
• Learning efficient decoders for quasi-chaotic quantum scramblers
• 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
• 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 $T$ gates
• Quantifying Qubit Magic Resource with Gottesman-Kitaev-Preskill Encoding
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• Fast estimation of outcome probabilities for quantum circuits
• Stabilizer extent is not multiplicative
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Unscrambling Quantum Information with Clifford decoders
• A brief introduction to quantum algorithms
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• A single $T$-gate makes distribution learning hard
• 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
• Fast Stabiliser Simulation with Quadratic Form Expansions
• How to simulate quantum measurement without computing marginals
• Scrambling and quantum chaos indicators from long-time properties of operator distributions
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Nonstabilizerness of Permutationally Invariant Systems
• 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
• A quantum primality test with order finding
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Robustness of QMA against witness noise
• Magic Resources of the Heisenberg Picture
• Classically estimating observables of noiseless quantum circuits
• Probing quantum complexity via universal saturation of stabilizer entropies
• Quantifying dynamical magic with completely stabilizer preserving operations as free
• Contextuality bounds the efficiency of classical simulation of quantum processes
• Classical simulation of non-Gaussian fermionic circuits
• Synthesizing efficient circuits for Hamiltonian simulation
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Opening the Black Box Inside Grover's Algorithm
• Gravitational back-reaction is magical
• Computational power of matchgates with supplementary resources
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Experimental demonstration of scalable cross-entropy benchmarking to detect measurement-induced phase transitions on a superconducting quantum processor
• Quantum Non-Local Nonstabilizerness
• Classical simulation of quantum circuits by half Gauss sums
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Doped stabilizer states in many-body physics and where to find them
• Chaos and magic in the dissipative quantum kicked top
• Qibolab: an open-source hybrid quantum operating system
• Stabilizer Tensor Networks with Magic State Injection
• Stabilizer rank and higher-order Fourier analysis
• Error mitigation by training with fermionic linear optics
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Pauli path simulations of noisy quantum circuits beyond average case
• Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Simulation of quantum optics by coherent state decomposition
• Spectral Properties Versus Magic Generation in $T$-doped Random Clifford Circuits
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• 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
• 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
• 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
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Supervised learning of random quantum circuits via scalable neural networks
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Classical simulation of non-Gaussian bosonic circuits
• Nonstabilizerness of a Boundary Time Crystal
• Classical simulation of quantum circuits by dynamical localization: analytic results for Pauli-observable scrambling in time-dependent disorder
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus
• Interplay of entanglement structures and stabilizer entropy in spin models
• Extracting randomness from magic quantum states
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• A Case for Synthesis of Recursive Quantum Unitary Programs
• Zero and Finite Temperature Quantum Simulations Powered by Quantum Magic
• On Classical and Hybrid Shadows of Quantum States
• Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Lower Bounds on Stabilizer Rank
• Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications
• Scalable evaluation of quantum-circuit error loss using Clifford sampling
• Faster Born probability estimation via gate merging and frame optimisation
• Fermionic Magic Resources of Quantum Many-Body Systems
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
• Quantum Ruzsa Divergence to Quantify Magic
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Classification of joint quantum measurements based on entanglement cost of localization
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
• Efficient witnessing and testing of magic in mixed quantum states
• Simulating Quantum Computations with Tutte Polynomials
• Designs from magic-augmented Clifford circuits
• New techniques for bounding stabilizer rank
• Fast simulation of planar Clifford circuits
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Computing quantum magic of state vectors
• Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions
• Classical simulation and quantum resource theory of non-Gaussian optics
• Comparative Study of Sampling-Based Simulation Costs of Noisy Quantum Circuits
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Certifying nonstabilizerness in quantum processors
• The 7 faces of quantum NP
• Non-Clifford Cost of Random Unitaries
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• A trace distance-based geometric analysis of the stabilizer polytope for few-qubit systems
• Lower T-count with faster algorithms
• Local spreading of stabilizer Rényi entropy in a brickwork random Clifford circuit
• Faster computation of nonstabilizerness
• Possibilistic simulation of quantum circuits by classical circuits
• The Future of Computing: Bits + Neurons + Qubits
• Leveraging commuting groups for an efficient variational Hamiltonian ansatz
• 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
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• HybridQ: A Hybrid Simulator for Quantum Circuits
• Straddling-gates problem in multipartite quantum systems
• Invested and Potential Magic Resources in Measurement-Based Quantum Computation
• Non-stabilizerness and entanglement from cat-state injection
• On Classical Simulation of Quantum Circuits Composed of Clifford Gates
• Robustness of Magic in the quantum Ising chain via Quantum Monte Carlo tomography
• PAC-learning of free-fermionic states is NP-hard
• Improved Strong Simulation of Universal Quantum Circuits
• Efficient simulation of logical magic state preparation protocols
• Characterization of non-adaptive Clifford channels
• Artificial intelligence for representing and characterizing quantum systems
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Stabilizer Rényi Entropy for Translation-Invariant Matrix Product States
• Unified Architecture for Quantum Lookup Tables
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• On The Stabilizer Formalism And Its Generalization
• GCAMPS: A Scalable Classical Simulator for Qudit Systems
• No-cost Bell nonlocality certification from quantum tomography and its applications in quantum-magic-resource witnessing
• Limits of Clifford Disentangling in Tensor Network States
• Convexity of noncontextual wirings and how they order the set of correlations
• Fine-grained quantum computational supremacy
• Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling
• On the extremal points of the $\Lambda$-polytopes and classical simulation of quantum computation with magic states
• Pseudoentanglement Ain't Cheap
• Simulating Quantum Circuits by Shuffling Paulis
• Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
• A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Noncontextual Pauli Hamiltonians
• Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Classical algorithms for measurement-adaptive Gaussian circuits
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits