Anticoncentration theorems for schemes showing a quantum speedup

Abstract

One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes "quantum computational supremacy". The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.

arXiv comment12+2 pages, added applications section

References in corpus (35)

• Nonequilibrium dynamics of closed interacting quantum systems
• Quantum Teleportation is a Universal Computational Primitive
• Measurement-based quantum computation with cluster states
• Strengths and Weaknesses of Quantum Computing
• Characterizing Quantum Supremacy in Near-Term Devices
• Exploring the many-body localization transition in two dimensions
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Evenly distributed unitaries: on the structure of unitary designs
• Resilient Quantum Computation: Error Models and Thresholds
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Universal fault-tolerant quantum computation with only transversal gates and error correction
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Emergence of coherence and the dynamics of quantum phase transitions
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Composed ensembles of random unitary matrices
• Universal Quantum Computation with Metaplectic Anyons
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Novikov's Conjecture
• How to efficiently select an arbitrary Clifford group element
• Direct certification of a class of quantum simulations
• Efficient synthesis of probabilistic quantum circuits with fallback
• Mixing properties of stochastic quantum Hamiltonians
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Generating a state $t$-design by diagonal quantum circuits
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Quantum pseudo-randomness from cluster-state quantum computation
• Matrix Element Distribution as a Signature of Entanglement Generation

Cited by in corpus (46)

• Logical quantum processor based on reconfigurable atom arrays
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Computational advantage of quantum random sampling
• Theory of quantum system certification: a tutorial
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Random quantum circuits anti-concentrate in log depth
• Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter
• How many qubits are needed for quantum computational supremacy?
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Sample complexity of device-independently certified "quantum supremacy"
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Expressibility and trainability of parameterized analog quantum systems for machine learning applications
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Computing exact moments of local random quantum circuits via tensor networks
• Protocols for classically training quantum generative models on probability distributions
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Quantum supremacy and quantum phase transitions
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• A game of quantum advantage: linking verification and simulation
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Quantum advantage from energy measurements of many-body quantum systems
• Quantum supremacy in driven quantum many-body systems
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Universal distributions of overlaps from generic dynamics in quantum many-body systems
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Random Projection using Random Quantum Circuits
• Architectures and random properties of symplectic quantum circuits
• A quantum tug of war between randomness and symmetries on homogeneous spaces
• Estimation of mutual information via quantum kernel method
• Low overhead universality and quantum supremacy using only $Z$-control
• Mixed symmetries of S_n: immanants in the sampling of U(d) submatrices
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• More global randomness from less-random local gates
• Anticoncentration is (almost) all you need
• Hardness of efficiently generating ground states in postselected quantum computation