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 (36)

• 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
• Strong quantum computational advantage using a superconducting quantum processor
• 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
• 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
• Massive Parallel Quantum Computer Simulator
• Emergence of coherence and the dynamics of quantum phase transitions
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• What can quantum optics say about computational complexity theory?
• Experimental statistical signature of many-body quantum interference
• Quantum simulators, continuous-time automata, and translationally invariant systems
• Hamiltonian Quantum Cellular Automata in 1D
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
• Training Gaussian Boson Sampling Distributions
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
• Quantum circuits and low-degree polynomials over F_2
• Exact Boson Sampling using Gaussian continuous variable measurements
• Cryptographic One-way Function Based on Boson Sampling
• Experimental demonstration of Gaussian boson sampling with displacement
• Fault-tolerant quantum speedup from constant depth quantum circuits

Cited by in corpus (80)

• 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
• Learning shallow quantum circuits
• Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators
• Stochastic noise can be helpful for variational quantum algorithms
• Probing coherent quantum thermodynamics using a trapped ion
• On the expressivity of embedding quantum kernels
• 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
• Efficient Verification of Ground States of Frustration-Free Hamiltonians
• Noise-induced shallow circuits and absence of barren plateaus
• QAOA-MC: Markov chain Monte Carlo enhanced by Quantum Alternating Operator Ansatz
• Quantum computational advantage with constant-temperature Gibbs sampling
• Quantifying Quantum Computational Advantage on a Processor of Ultracold Atoms
• Complexity-constrained quantum thermodynamics
• Unveiling quantum phase transitions from traps in variational quantum algorithms
• Fermionic Magic Resources of Quantum Many-Body Systems
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Verifiable measurement-based quantum random sampling with trapped ions
• Hamiltonian learning for 300 trapped ion qubits with long-range couplings
• Photon-number moments and cumulants of Gaussian states
• Verification of Bell Nonlocality by Violating Quantum Monogamy Relations
• 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
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Optimal estimates of trace distance between bosonic Gaussian states and applications to learning
• Statistical mechanical mapping and maximum-likelihood thresholds for the surface code under generic single-qubit coherent errors
• Power of quantum measurement in simulating unphysical operations
• Transition of Anticoncentration in Gaussian Boson Sampling
• The Second Moment of Hafnians in Gaussian Boson Sampling
• Finite temperature tensor network algorithm for frustrated two-dimensional quantum materials
• Learning quantum states prepared by shallow circuits in polynomial time
• Entanglement dynamics and Page curves in random permutation circuits
• Quantum Bayesian Inference with Renormalization for Gravitational Waves
• A quantum tug of war between randomness and symmetries on homogeneous spaces
• Error Mitigation Thresholds in Noisy Random Quantum Circuits
• The surface code beyond Pauli channels: Logical noise coherence, information-theoretic measures, and errorfield-double phenomenology
• Tailoring nuclear spins order with defects: a Quantum Technology CAD study
• Scalable projected entangled-pair state representation of random quantum circuit states
• Secret extraction attacks against obfuscated IQP circuits
• Bosonic randomized benchmarking with passive transformations
• Optimal Fermionic Joint Measurements for Estimating Non-Commuting Majorana Observables
• Loss-induced quantum nonreciprocity and entanglement in superconducting qubits
• Quantum-inspired dynamical models on quantum and classical annealers
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Configurable photonic simulator for quantum field dynamics
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Stability of emergent time periodicity in a few-body interacting system
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Average Rényi Entanglement Entropy in Gaussian Boson Sampling
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Complexity of Gaussian quantum optics with a limited number of non-linearities
• Computational indistinguishability and boson sampling
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation
• Resourcefulness of non-classical continuous-variable quantum gates
• More global randomness from less-random local gates
• Quantum community detection via deterministic elimination
• Optimal randomized measurements for a family of non-linear quantum properties
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Doubling Qubits in a Trapped-Ion System via Vibrational Dual-Rail Encoding
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Classical algorithms for measurement-adaptive Gaussian circuits
• Measurement-induced entanglement in noisy 2D random circuits
• Anti-concentration is (almost) all you need