Sample complexity of device-independently certified "quantum supremacy"

Abstract

Results on the hardness of approximate sampling are seen as important stepping stones towards a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, IQP circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any non-interactive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results: namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.

17 pages. V2: Minor improvements

References in corpus (35)

• Characterizing Quantum Supremacy in Near-Term Devices
• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Random Quantum Circuits are Approximate 2-designs
• Efficient experimental validation of photonic boson sampling against the uniform distribution
• 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
• On the experimental verification of quantum complexity in linear optics
• Hamiltonian Learning and Certification Using Quantum Resources
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• No imminent quantum supremacy by boson sampling
• Instantaneous Quantum Computation
• Reliable quantum certification for photonic quantum technologies
• How many entries of a typical orthogonal matrix can be approximated by independent normals?
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• A Statistical Benchmark for BosonSampling
• Verification of Many-Qubit States
• Classical simulation of photonic linear optics with lost particles
• Direct certification of a class of quantum simulations
• Anticoncentration theorems for schemes showing a quantum speedup
• Entanglement-ergodic quantum systems equilibrate exponentially well
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Boson-Sampling in the light of sample complexity
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Generating a state $t$-design by diagonal quantum circuits
• Classical simulability of noisy boson sampling
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Power of Quantum Computation with Few Clean Qubits
• Certification of Boson Sampling Devices with Coarse-Grained Measurements
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)

Cited by in corpus (30)

• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Quantum certification and benchmarking
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Computational advantage of quantum random sampling
• Theory of quantum system certification: a tutorial
• Variational Quantum Unsampling on a Quantum Photonic Processor
• On the Quantum versus Classical Learnability of Discrete Distributions
• Benchmarking quantum computers
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Benchmarking of Gaussian boson sampling using two-point correlators
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Simulating complex networks in phase space: Gaussian boson sampling
• Efficient verification of Boson Sampling
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Signatures of Many-Particle Interference
• Efficient validation of Boson Sampling from binned photon-number distributions
• Sample-efficient benchmarking of multi-photon interference on a boson sampler in the sparse regime
• A game of quantum advantage: linking verification and simulation
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Verifiable measurement-based quantum random sampling with trapped ions
• Quantum advantage from energy measurements of many-body quantum systems
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Sample caching Markov chain Monte Carlo approach to boson sampling simulation
• In situ characterization of linear-optical networks in randomized boson sampling
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Sampling and the complexity of nature
• Validating multi-photon quantum interference with finite data