Computational advantage of quantum random sampling
arXiv:2206.04079 · doi:10.1103/RevModPhys.95.035001
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.
arXiv comment87 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 (239)
- Many-Body Physics with Ultracold Gases
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A variational eigenvalue solver on a quantum processor
- Cold bosonic atoms in optical lattices
- Quantum algorithm for solving linear systems of equations
- The density-matrix renormalization group
- Cavity quantum electrodynamics for superconducting electrical circuits: an architecture for quantum computation
- Review article: Linear optical quantum computing
- Experimental loophole-free violation of a Bell inequality using entangled electron spins separated by 1.3 km
- Probing many-body dynamics on a 51-atom quantum simulator
- Supervised learning with quantum enhanced feature spaces
- Entanglement detection
- Quantum computational advantage using photons
- The theory of variational hybrid quantum-classical algorithms
- Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Measurement-based quantum computation with cluster states
- Significant-loophole-free test of Bell's theorem with entangled photons
- Improved Simulation of Stabilizer Circuits
- A strong loophole-free test of local realism
- Silicon Quantum Electronics
- Characterizing Quantum Supremacy in Near-Term Devices
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Strong quantum computational advantage using a superconducting quantum processor
- Quantum algorithms: an overview
- Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
- Exploring the many-body localization transition in two dimensions
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Hamiltonian Simulation by Qubitization
- Boson Sampling on a Photonic Chip
- Quantum Computational Supremacy
- Controlled Collisions for Multiparticle Entanglement of Optically Trapped Atoms
- Demonstration of a small programmable quantum computer with atomic qubits
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Experimental Boson Sampling
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Realizing Repeated Quantum Error Correction in a Distance-Three Surface Code
- Efficient quantum state tomography
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Witnessing multipartite entanglement
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- Theory of the phase transition in random unitary circuits with measurements
- Gaussian Boson Sampling
- Measurement-induced criticality in random quantum circuits
- A Theory of Trotter Error
- Direct Fidelity Estimation from Few Pauli Measurements
- Simulating quantum computation by contracting tensor networks
- Universal blind quantum computation
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Unknown Quantum States: The Quantum de Finetti Representation
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Qubit-photon interactions in a cavity: Measurement induced dephasing and number splitting
- 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
- Quantum advantage with shallow circuits
- Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
- Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography
- A fault-tolerant one-way quantum computer
- A Grand Unification of Quantum Algorithms
- Observation of Entangled States of a Fully Controlled 20-Qubit System
- Boson Sampling for Molecular Vibronic Spectra
- Quantum certification and benchmarking
- Random Quantum Circuits are Approximate 2-designs
- Improved classical simulation of quantum circuits dominated by Clifford gates
- The computational complexity of PEPS
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Local random quantum circuits are approximate polynomial-designs
- Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
- Certified randomness in quantum physics
- Boson Sampling from Gaussian States
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Self-Consistent Quantum Process Tomography
- Demonstration of Universal Parametric Entangling Gates on a Multi-Qubit Lattice
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Experimental Analysis of a 4-Qubit Cluster State
- Diagrammatic method of integration over the unitary group, with applications to quantum transport in mesoscopic systems
- Entanglement Detection in the Stabilizer Formalism
- Emergent statistical mechanics of entanglement in random unitary circuits
- Unconditionally verifiable blind computation
- Soundness and completeness of quantum root-mean-square errors
- Characterizing large-scale quantum computers via cycle benchmarking
- Experimental Scattershot Boson Sampling
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Generation and sampling of quantum states of light in a silicon chip
- On the experimental verification of quantum complexity in linear optics
- Massive Parallel Quantum Computer Simulator
- BosonSampling with single-photon Fock states from a bright solid-state source
- Long-range quantum entanglement in noisy cluster states
- Suppression of the critical temperature for superfluidity near the Mott transition: validating a quantum simulator
- What limits the simulation of quantum computers?
- Emergence of coherence and the dynamics of quantum phase transitions
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Hyper-optimized tensor network contraction
- 0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit
- Quantum Sampling Problems, BosonSampling and Quantum Supremacy
- A detailed study of Gaussian Boson Sampling
- No imminent quantum supremacy by boson sampling
- Instantaneous Quantum Computation
- Preparing random states and benchmarking with many-body quantum chaos
- Quantum computation with realistic magic state factories
- Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer
- Molecular Docking with Gaussian Boson Sampling
- Efficient classical simulation of random shallow 2D quantum circuits
- Efficient multiphoton sampling of molecular vibronic spectra on a superconducting bosonic processor
- Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
- Solving the sampling problem of the Sycamore quantum circuits
- Quantum advantage with noisy shallow circuits in 3D
- Using Gaussian Boson Sampling to Find Dense Subgraphs
- 64-Qubit Quantum Circuit Simulation
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- Perfect Sampling with Unitary Tensor Networks
- Theory of quantum system certification: a tutorial
- A general framework for randomized benchmarking
- Stringent and efficient assessment of Boson-Sampling devices
- Optimal verification of entangled states with local measurements
- Gaussian Boson Sampling using threshold detectors
- Approximate unitary -designs by short random quantum circuits using nearest-neighbor and long-range gates
- A de Finetti representation for finite symmetric quantum states
- Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
- Massively parallel quantum computer simulator, eleven years later
- Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
- Reliable quantum certification for photonic quantum technologies
- How many entries of a typical orthogonal matrix can be approximated by independent normals?
- Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
- Efficient algorithm for boson sampling with partially distinguishable photons
- The spectral gap for some spin chains with discrete symmetry breaking
- Simulating boson sampling in lossy architectures
- Gaussian Boson Sampling for perfect matchings of arbitrary graphs
- On the hardness of classically simulating the one clean qubit model
- Architectures for quantum simulation showing a quantum speedup
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Interference of Identical Particles from Entanglement to Boson-Sampling
- The Boundary for Quantum Advantage in Gaussian Boson Sampling
- A quantum hardware-induced graph kernel based on Gaussian Boson Sampling
- What can quantum optics say about computational complexity theory?
- Post hoc verification of quantum computation
- Post hoc verification with a single prover
- Regimes of classical simulability for noisy Gaussian boson sampling
- Random quantum circuits are approximate unitary -designs in depth
- A Statistical Benchmark for BosonSampling
- Random bosonic states for robust quantum metrology
- Experimental statistical signature of many-body quantum interference
- Verification of Many-Qubit States
- Random quantum circuits anti-concentrate in log depth
- General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
- Classical simulation of photonic linear optics with lost particles
- BosonSampling with Lost Photons
- Certifying the building blocks of quantum computers from Bell's theorem
- How many qubits are needed for quantum computational supremacy?
- Simulating realistic non-Gaussian state preparation
- Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
- General method for extracting the quantum efficiency of dispersive qubit readout in circuit QED
- Liquid state NMR simulations of quantum many-body problems
- Efficient Verification of Hypergraph States
- Direct certification of a class of quantum simulations
- Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
- Nonstabilizerness determining the hardness of direct fidelity estimation
- Verified measurement-based quantum computing with hypergraph states
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Hamiltonian Quantum Cellular Automata in 1D
- Quantum simulators, continuous-time automata, and translationally invariant systems
- Quantum approximate optimization with Gaussian boson sampling
- Anticoncentration theorems for schemes showing a quantum speedup
- Exact simulation of Gaussian Boson Sampling in polynomial space and exponential time
- A Benchmark Test of Boson Sampling on Tianhe-2 Supercomputer
- Contracting projected entangled pair states is average-case hard
- Fidelity witnesses for fermionic quantum simulations
- Boson sampling with Gaussian measurements
- Tight bounds on the convergence of noisy random circuits to the uniform distribution
- Classically-Verifiable Quantum Advantage from a Computational Bell Test
- Unbiased Simulation of Near-Clifford Quantum Circuits
- Boundaries of quantum supremacy via random circuit sampling
- Dynamical phase transitions in sampling complexity
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Classical simulation of lossy boson sampling using matrix product operators
- Point Processes with Gaussian Boson Sampling
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- 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
- Sample complexity of device-independently certified "quantum supremacy"
- 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
- Validating Quantum-Classical Programming Models with Tensor Network Simulations
- Quantum advantage of unitary Clifford circuits with magic state inputs
- All pure fermionic non-Gaussian states are magic states for matchgate computations
- Benchmarking of Gaussian boson sampling using two-point correlators
- Approximating Vibronic Spectroscopy with Imperfect Quantum Optics
- Noise and the frontier of quantum supremacy
- Generating a state -design by diagonal quantum circuits
- Quantum simulation of thermodynamics in an integrated quantum photonic processor
- Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
- Training Gaussian Boson Sampling Distributions
- 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
- Simulability of Imperfect Gaussian and Superposition Boson Sampling
- Dynamical structure factors of dynamical quantum simulators
- Noise in BosonSampling and the threshold of efficient classical simulatability
- Quantum algorithms for classical lattice models
- Classically simulating near-term partially-distinguishable and lossy boson sampling
- A simple proof of the detectability lemma and spectral gap amplification
- Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
- Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
- Quantum machine learning with adaptive linear optics
- Verifying commuting quantum computations via fidelity estimation of weighted graph states
- Quantum circuits and low-degree polynomials over F_2
- Generalized concurrence in boson sampling
- Exact Boson Sampling using Gaussian continuous variable measurements
- Universal 2-local Hamiltonian Quantum Computing
- Compressive gate set tomography
- Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
- Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
- Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians
- Cryptographic One-way Function Based on Boson Sampling
- Distinguishing noisy boson sampling from classical simulations
- Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
- Randomized Benchmarking under Different Gatesets
- Experimental demonstration of Gaussian boson sampling with displacement
- Self-Consistent Calibration of Quantum Gate Sets
- Depth-efficient proofs of quantumness
- Validating and Certifying Stabilizer States
- Nonadaptive fault-tolerant verification of quantum supremacy with noise
- Fault-tolerant quantum speedup from constant depth quantum circuits
- Classical simulation of boson sampling with sparse output
- Photonic quantum data locking
- A game of quantum advantage: linking verification and simulation
- Quantum advantage from energy measurements of many-body quantum systems
- Multimode Metrology via Scattershot Sampling
- Fault tolerant quantum data locking
- Test of Quantumness with Small-Depth Quantum Circuits
- 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
- Anticoncentration 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