Quantum advantage of unitary Clifford circuits with magic state inputs

Abstract

We study the computational power of unitary Clifford circuits with solely magic state inputs (CM circuits), supplemented by classical efficient computation. We show that CM circuits are hard to classically simulate up to multiplicative error (assuming PH non-collapse), and also up to additive error under plausible average-case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply. Along the way we give an extension of the Gottesman-Knill theorem that applies to universal computation, showing that for Clifford circuits with joint stabiliser and non-stabiliser inputs, the stabiliser part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabiliser part. Finally we discuss implementational advantages of CM circuits.

25 pages. 3 figures. Accepted manuscript. To appear in Proc. Roy. Soc. (Lond) A

References in corpus (13)

• Measurement-based quantum computation with cluster states
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Computational Supremacy
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Anticoncentration theorems for schemes showing a quantum speedup
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification

Cited by in corpus (34)

• Computational advantage of quantum random sampling
• Quantifying magic for multi-qubit operations
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Optimized compiler for Distributed Quantum Computing
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Error mitigation and quantum-assisted simulation in the error corrected regime
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Holomorphic representation of quantum computations
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Quantum Non-Local Nonstabilizerness
• Experimental demonstration of scalable cross-entropy benchmarking to detect measurement-induced phase transitions on a superconducting quantum processor
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
• Zero-temperature entanglement membranes in quantum circuits
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Magic of Random Matrix Product States
• Fermion-Parity-Based Computation and its Majorana-Zero-Mode Implementation
• Improved simulation of quantum circuits dominated by free fermionic operations
• Limitations of Classically-Simulable Measurements for Quantum State Discrimination
• Pauli-based model of quantum computation with higher-dimensional systems
• Faster Born probability estimation via gate merging and frame optimisation
• Disentangling magic states with classically simulable quantum circuits
• A new twist on the Majorana surface code: Bosonic and fermionic defects for fault-tolerant quantum computation
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Boson Sampling for Generalized Bosons
• Entanglement dynamics and Page curves in random permutation circuits
• Wasserstein Complexity of Quantum Circuits
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• On the Hardness of Measuring Magic
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Reducing depth and measurement weights in Pauli-based computation