Closing gaps of a quantum advantage with short-time Hamiltonian dynamics

Abstract

Demonstrating a quantum computational speedup is a crucial milestone for near-term quantum technology. Recently, quantum simulation architectures have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme - as of other comparable schemes such as boson sampling - is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for these architectures for Hamiltonian quantum simulators: Anticoncentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we develop new techniques that exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We prove that the 2D translation-invariant, constant depth architectures of quantum simulation form approximate 2-designs in a specific sense, thus obtaining a significantly stronger result. Our work provides the strongest evidence to date that Hamiltonian quantum simulation architectures are classically intractable.

arXiv comment21 pages, 4 figures. Minor typographic errors corrected. The term "quantum advantage" is synonymously used with "quantum supremacy"

References in corpus (42)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Probing many-body dynamics on a 51-atom quantum simulator
• Characterizing Quantum Supremacy in Near-Term Devices
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
• Exploring the many-body localization transition in two dimensions
• Quantum Computational Supremacy
• Probing the Superfluid to Mott Insulator Transition at the Single Atom Level
• Entanglement of atoms via cold controlled collisions
• Elucidating Reaction Mechanisms on Quantum Computers
• Scalable Noise Estimation with Random Unitary Operators
• Spectral signatures of many-body localization with interacting photons
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Quantum certification and benchmarking
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Undecidability of the Spectral Gap (short version)
• Probing Slow Relaxation and Many-Body Localization in Two-Dimensional Quasi-Periodic Systems
• Emergence of coherence and the dynamics of quantum phase transitions
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Coherent collisional spin dynamics in optical lattices
• One-shot decoupling
• The spectral gap for some spin chains with discrete symmetry breaking
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Direct certification of a class of quantum simulations
• Decoupling with unitary approximate two-designs
• Applying quantum algorithms to constraint satisfaction problems
• Recovering quantum gates from few average gate fidelities
• Anticoncentration theorems for schemes showing a quantum speedup
• Contracting projected entangled pair states is average-case hard
• Efficient Quantum Pseudorandomness
• Sample complexity of device-independently certified "quantum supremacy"
• Undecidability of the Spectral Gap in One Dimension
• A simple proof of the detectability lemma and spectral gap amplification
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Efficient quantum pseudorandomness with simple graph states
• Quantum pseudo-randomness from cluster-state quantum computation

Cited by in corpus (24)

• Preparing random states and benchmarking with many-body quantum chaos
• Computational advantage of quantum random sampling
• Exact emergent quantum state designs from quantum chaotic dynamics
• A tweezer array with 6100 highly coherent atomic qubits
• Random quantum circuits anti-concentrate in log depth
• Dynamical purification and the emergence of quantum state designs from the projected ensemble
• Scalable Hamiltonian learning for large-scale out-of-equilibrium quantum dynamics
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• A quantum hamiltonian simulation benchmark
• Learning shallow quantum circuits
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Integration of Quantum Accelerators with High Performance Computing -- A Review of Quantum Programming Tools
• A game of quantum advantage: linking verification and simulation
• Verifiable measurement-based quantum random sampling with trapped ions
• Quantum advantage from energy measurements of many-body quantum systems
• Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs
• Unitary $t$-designs from $relaxed$ seeds
• Boson Sampling for Generalized Bosons
• High performance Boson Sampling simulation via data-flow engines
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Low overhead universality and quantum supremacy using only $Z$-control
• Sampling and the complexity of nature
• Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
• Efficient classical simulation of cluster state quantum circuits with alternative inputs