Computational advantage of quantum random sampling

Abstract

Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently, first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. In this article, we comprehensively review the theoretical underpinning of quantum random sampling in terms of computational complexity and verifiability, as well as the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. We discuss in detail open questions in the field and provide perspectives for the road ahead, including potential applications of quantum random sampling.

87 pages, 13 figures, 2 tables. Sections II-V build on previously unpublished chapters of arXiv:2012.07905. v2: added some references. v3: small corrections. v4: extended discussion of noisy simulation algorithms + minor changes

References in corpus (77)

• Many-Body Physics with Ultracold Gases
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Probing many-body dynamics on a 51-atom quantum simulator
• Entanglement detection
• Quantum computational advantage using photons
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Realizing Repeated Quantum Error Correction in a Distance-Three Surface Code
• Efficient quantum state tomography
• Photonic Boson Sampling in a Tunable Circuit
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Direct Fidelity Estimation from Few Pauli Measurements
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Qubit-photon interactions in a cavity: Measurement induced dephasing and number splitting
• A Grand Unification of Quantum Algorithms
• Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
• Certified randomness in quantum physics
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Analysis of a 4-Qubit Cluster State
• Entanglement Detection in the Stabilizer Formalism
• Experimental Scattershot Boson Sampling
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Massive Parallel Quantum Computer Simulator
• What limits the simulation of quantum computers?
• Emergence of coherence and the dynamics of quantum phase transitions
• Hyper-optimized tensor network contraction
• Preparing random states and benchmarking with many-body quantum chaos
• Efficient classical simulation of random shallow 2D quantum circuits
• Solving the sampling problem of the Sycamore quantum circuits
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Theory of quantum system certification: a tutorial
• A general framework for randomized benchmarking
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• What can quantum optics say about computational complexity theory?
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Random quantum circuits anti-concentrate in log depth
• Experimental statistical signature of many-body quantum interference
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Quantum simulators, continuous-time automata, and translationally invariant systems
• Hamiltonian Quantum Cellular Automata in 1D
• Boundaries of quantum supremacy via random circuit sampling
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Classical simulation of lossy boson sampling using matrix product operators
• Improved upper bounds on the stabilizer rank of magic states
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
• The Complexity of Bipartite Gaussian Boson Sampling
• Classical simulation of boson sampling based on graph structure
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Noise and the frontier of quantum supremacy
• Training Gaussian Boson Sampling Distributions
• Quantum simulation of thermodynamics in an integrated quantum photonic processor
• Simulating complex networks in phase space: Gaussian boson sampling
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Efficient verification of Boson Sampling
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
• Quantum machine learning with adaptive linear optics
• Quantum circuits and low-degree polynomials over F_2
• Exact Boson Sampling using Gaussian continuous variable measurements
• Compressive gate set tomography
• Cryptographic One-way Function Based on Boson Sampling
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
• Experimental demonstration of Gaussian boson sampling with displacement
• Depth-efficient proofs of quantumness
• A game of quantum advantage: linking verification and simulation
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Multimode Metrology via Scattershot Sampling
• Test of Quantumness with Small-Depth Quantum Circuits
• Fault tolerant quantum data locking
• Gaussian phase sensitivity of boson-sampling-inspired strategies

Cited by in corpus (84)

• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Understanding quantum machine learning also requires rethinking generalization
• Benchmarking quantum computers
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Classical algorithm for simulating experimental Gaussian boson sampling
• The computational power of random quantum circuits in arbitrary geometries
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Bell sampling from quantum circuits
• Estimating gate-set properties from random sequences
• Learning shallow quantum circuits
• Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators
• Stochastic noise can be helpful for variational quantum algorithms
• On the expressivity of embedding quantum kernels
• Probing coherent quantum thermodynamics using a trapped ion
• Fock-space delocalization and the emergence of the Porter-Thomas distribution from dual-unitary dynamics
• Unbiasing Fermionic Auxiliary-Field Quantum Monte Carlo with Matrix Product State Trial Wavefunctions
• Anticoncentration and state design of random tensor networks
• Dynamical simulations of many-body quantum chaos on a quantum computer
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Exploring Unsupervised Anomaly Detection with Quantum Boltzmann Machines in Fraud Detection
• Opportunities and challenges of quantum computing for climate modelling
• Learning quantum states of continuous variable systems
• Exactly solvable many-body dynamics from space-time duality
• Hardware-Tailored Diagonalization Circuits
• Noise-induced shallow circuits and absence of barren plateaus
• Efficient Verification of Ground States of Frustration-Free Hamiltonians
• QAOA-MC: Markov chain Monte Carlo enhanced by Quantum Alternating Operator Ansatz
• Quantum computational advantage with constant-temperature Gibbs sampling
• Complexity-constrained quantum thermodynamics
• Quantifying Quantum Computational Advantage on a Processor of Ultracold Atoms
• Unveiling quantum phase transitions from traps in variational quantum algorithms
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Fermionic Magic Resources of Quantum Many-Body Systems
• Quantum supremacy in driven quantum many-body systems
• Hamiltonian learning for 300 trapped ion qubits with long-range couplings
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Verifiable measurement-based quantum random sampling with trapped ions
• Verification of Bell Nonlocality by Violating Quantum Monogamy Relations
• Photon-number moments and cumulants of Gaussian states
• Phase transitions in sampling and error correction in local Brownian circuits
• BosonSampling.jl: A Julia package for quantum multi-photon interferometry
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Statistical mechanical mapping and maximum-likelihood thresholds for the surface code under generic single-qubit coherent errors
• Quantum Bayesian Inference with Renormalization for Gravitational Waves
• Entanglement dynamics and Page curves in random permutation circuits
• The Second Moment of Hafnians in Gaussian Boson Sampling
• Learning quantum states prepared by shallow circuits in polynomial time
• Transition of Anticoncentration in Gaussian Boson Sampling
• Finite temperature tensor network algorithm for frustrated two-dimensional quantum materials
• Power of quantum measurement in simulating unphysical operations
• A quantum tug of war between randomness and symmetries on homogeneous spaces
• Secret extraction attacks against obfuscated IQP circuits
• Quantum estimation bound of Gaussian matrix permanent
• Scalable projected entangled-pair state representation of random quantum circuit states
• Tailoring nuclear spins order with defects: a Quantum Technology CAD study
• Bosonic randomized benchmarking with passive transformations
• The surface code beyond Pauli channels: Logical noise coherence, information-theoretic measures, and errorfield-double phenomenology
• Error Mitigation Thresholds in Noisy Random Quantum Circuits
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Average Rényi Entanglement Entropy in Gaussian Boson Sampling
• Optimal Fermionic Joint Measurements for Estimating Non-Commuting Majorana Observables
• Stability of emergent time periodicity in a few-body interacting system
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Configurable photonic simulator for quantum field dynamics
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Quantum-inspired dynamical models on quantum and classical annealers
• Loss-induced quantum nonreciprocity and entanglement in superconducting qubits
• Optimal randomized measurements for a family of non-linear quantum properties
• Computational indistinguishability and boson sampling
• Complexity of Gaussian quantum optics with a limited number of non-linearities
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Quantum community detection via deterministic elimination
• Classical algorithms for measurement-adaptive Gaussian circuits
• Resourcefulness of non-classical continuous-variable quantum gates
• Measurement-induced entanglement in noisy 2D random circuits
• Anti-concentration is (almost) all you need
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Doubling Qubits in a Trapped-Ion System via Vibrational Dual-Rail Encoding
• More global randomness from less-random local gates
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation