Quantum Computational Supremacy

Abstract

The field of quantum algorithms aims to find ways to speed up the solution of computational problems by using a quantum computer. A key milestone in this field will be when a universal quantum computer performs a computational task that is beyond the capability of any classical computer, an event known as quantum supremacy. This would be easier to achieve experimentally than full-scale quantum computing, but involves new theoretical challenges. Here we present the leading proposals to achieve quantum supremacy, and discuss how we can reliably compare the power of a classical computer to the power of a quantum computer.

review article originally appearing in a Nature Insight collection on "Quantum Software". 15 pages

References in corpus (10)

• Surface codes: Towards practical large-scale quantum computation
• Photonic Boson Sampling in a Tunable Circuit
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• Quantum computing and the entanglement frontier
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• Gaussian Noise Sensitivity and BosonSampling
• Threshold values of Random K-SAT from the cavity method

Cited by in corpus (305)

• Quantum computational advantage using photons
• A Quantum Engineer's Guide to Superconducting Qubits
• Quantum computational chemistry
• Superconducting Qubits: Current State of Play
• Integrated Photonic Quantum Technologies
• Trapped-Ion Quantum Computing: Progress and Challenges
• Parameterized quantum circuits as machine learning models
• Power of data in quantum machine learning
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Random Quantum Circuits
• Theory of variational quantum simulation
• Generalized Unitary Coupled Cluster Wavefunctions for Quantum Computation
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Transfer learning in hybrid classical-quantum neural networks
• Superconducting Quantum Computing: A Review
• The Expressive Power of Parameterized Quantum Circuits
• Hybrid Quantum-Classical Convolutional Neural Networks
• Variational Quantum Monte Carlo Method with a Neural-Network Ansatz for Open Quantum Systems
• Towards real-world quantum networks: a review
• Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography
• Microscopic control and detection of ultracold strontium in optical-tweezer arrays
• Variational Quantum State Diagonalization
• Quantum dots for photonic quantum information technology
• Quantum generative adversarial learning in a superconducting quantum circuit
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Efficient classical simulation of random shallow 2D quantum circuits
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Measuring the Capabilities of Quantum Computers
• Computational advantage of quantum random sampling
• IBM Quantum Computers: Evolution, Performance, and Future Directions
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Efficient measure for the expressivity of variational quantum algorithms
• Measurement reduction in variational quantum algorithms
• Deep Reinforcement Learning for Quantum Gate Control
• Learning Robust and High-Precision Quantum Controls
• Quantum computing models for artificial neural networks
• Nishimori's cat: stable long-range entanglement from finite-depth unitaries and weak measurements
• Variational Quantum Reinforcement Learning via Evolutionary Optimization
• Quantum Machine Learning: from physics to software engineering
• Predicting Research Trends with Semantic and Neural Networks with an application in Quantum Physics
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• Quantum Chaos is Quantum
• Quantum Indistinguishability by Path Identity: The awakening of a sleeping beauty
• Variational Quantum Unsampling on a Quantum Photonic Processor
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Scalable High-Performance Fluxonium Quantum Processor
• Regimes of classical simulability for noisy Gaussian boson sampling
• Calculation of the Green's function on near-term quantum computers
• Natural quantum reservoir computing for temporal information processing
• Enhancing Generative Models via Quantum Correlations
• Experimental statistical signature of many-body quantum interference
• Quantum Assisted Simulator
• An end-to-end trainable hybrid classical-quantum classifier
• Neural-Network Decoders for Quantum Error Correction using Surface Codes:A Space Exploration of the Hardware Cost-Performance Trade-Offs
• Nonstabilizerness via matrix product states in the Pauli basis
• Experimental Gaussian Boson Sampling
• NISQ Computers: A Path to Quantum Supremacy
• Cryogenic operation of silicon photonic modulators based on DC Kerr effect
• Hamiltonian Simulation Algorithms for Near-Term Quantum Hardware
• Genome assembly using quantum and quantum-inspired annealing
• Resources for bosonic quantum computational advantage
• Demonstration of algorithmic quantum speedup
• On the statistical complexity of quantum circuits
• Quantum advantages for Pauli channel estimation
• Dielectrics for Two-Dimensional Transition Metal Dichalcogenide Applications
• Iterative Quantum Assisted Eigensolver
• Training Optimization for Gate-Model Quantum Neural Networks
• Simulating periodic systems on quantum computer
• 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
• Complexity of frustration: a new source of non-local non-stabilizerness
• Reconfigurable continuously-coupled 3D photonic circuit for Boson Sampling experiments
• Cost-Reduced All-Gaussian Universality with the Gottesman-Kitaev-Preskill Code: Resource-Theoretic Approach to Cost Analysis
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• A quantum enhanced finite-time Otto cycle
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Neuromorphic scaling advantages for energy-efficient random walk computation
• Critical behaviors of non-stabilizerness in quantum spin chains
• 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
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Expressibility and trainability of parameterized analog quantum systems for machine learning applications
• Optimizing High-Efficiency Quantum Memory with Quantum Machine Learning for Near-Term Quantum Devices
• Trainability barriers and opportunities in quantum generative modeling
• Neural-network states for the classical simulation of quantum computing
• Transitions in Entanglement Complexity in Random Circuits
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Dissipation as a resource for Quantum Reservoir Computing
• Magic in generalized Rokhsar-Kivelson wavefunctions
• Classical simulation of linear optics subject to nonuniform losses
• Quantum Adiabatic Algorithm Design using Reinforcement Learning
• Anti-Zeno quantum advantage in fast-driven heat machines
• Measurement-Driven Phase Transition within a Volume-Law Entangled Phase
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Quantum Experiments and Hypergraphs: Multi-Photon Sources for Quantum Interference, Quantum Computation and Quantum Entanglement
• Quantum Architecture Search via Deep Reinforcement Learning
• Hybrid Quantum Investment Optimization with Minimal Holding Period
• Fast estimation of outcome probabilities for quantum circuits
• Efficient verification of Boson Sampling
• Quantum Differentially Private Sparse Regression Learning
• Simulability of Imperfect Gaussian and Superposition Boson Sampling
• Classically simulating near-term partially-distinguishable and lossy boson sampling
• Generalized Quantum Assisted Simulator
• Entanglement Accessibility Measures for the Quantum Internet
• Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers
• Protecting Expressive Circuits with a Quantum Error Detection Code
• Dense Quantum Measurement Theory
• An adaptive algorithm for quantum circuit simulation
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
• Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
• Verifying commuting quantum computations via fidelity estimation of weighted graph states
• Quantum criticality using a superconducting quantum processor
• Generating Haar-uniform Randomness using Stochastic Quantum Walks on a Photonic Chip
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Robust Majorana magic gates via measurements
• Remote blind state preparation with weak coherent pulses in the field
• Efficient classical simulation of noisy quantum computation
• Automatically Differentiable Quantum Circuit for Many-qubit State Preparation
• Holomorphic representation of quantum computations
• Experimental demonstration of quantum advantage for one-way communication complexity
• Hybrid Quantum-Classical Graph Convolutional Network
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• Non-linear Boson Sampling
• Information processing at the speed of light
• Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer
• Predicting excited states from ground state wavefunction by supervised quantum machine learning
• Surpassing the Classical Limit in Magic Square Game with Distant Quantum Dots Coupled to Optical Cavities
• Qurzon: A Prototype for a Divide and Conquer Based Quantum Compiler
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Adiabatic Quantum Kitchen Sinks for Learning Kernels Using Randomized Features
• The Landscape of Academic Literature in Quantum Technologies
• Neural Quantum Embedding: Pushing the Limits of Quantum Supervised Learning
• A chip-scale polarization-spatial-momentum quantum SWAP gate in silicon nanophotonics
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• Nonequilibrium dynamics in deconfined quantum critical point revealed by imaginary-time evolution
• Quantum Non-Local Nonstabilizerness
• Networked Quantum Services
• Analytic Filter Function Derivatives for Quantum Optimal Control
• Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits
• Classical simulation of quantum circuits by half Gauss sums
• Conditionally rigorous mitigation of multiqubit measurement errors
• Simulating the Dynamics of Single Photons in BosonSampling Devices with Matrix Product States
• Highly efficient phase-tunable photonic thermal diode
• Depth-efficient proofs of quantumness
• Mitigating errors by quantum verification and post-selection
• A robust W-state encoding for linear quantum optics
• Optimizing spontaneous parametric down-conversion sources for boson sampling
• Theory of Noise-Scaled Stability Bounds and Entanglement Rate Maximization in the Quantum Internet
• Signatures of Many-Particle Interference
• Witnesses of coherence and dimension from multiphoton indistinguishability tests
• Theory of Ergodic Quantum Processes
• Quantum Convolutional Neural Network: A Hybrid Quantum-Classical Approach for Iris Dataset Classification
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Volumetric Benchmarking of Error Mitigation with Qermit
• Digital quantum simulation of linear and nonlinear optical elements
• Clifford recompilation for faster classical simulation of quantum circuits
• Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
• Quantum Advantage for the LOCAL Model in Distributed Computing
• Quantum verification of NP problems with single photons and linear optics
• Observation of exceptional point in a PT broken non-Hermitian system simulated using a quantum circuit
• Controlling chaos in the quantum regime using adaptive measurements
• Local disclosure of quantum memory in non-Markovian dynamics
• The principle of majorization: application to random quantum circuits
• Magic phase transition and non-local complexity in generalized $W$ State
• Postselected quantum hypothesis testing
• State Stabilization for Gate-Model Quantum Computers
• Modular Quantum-to-Quantum Bernoulli Factory in an Integrated Photonic Processor
• Polynomial scaling enhancement in ground-state preparation of Ising spin models via counter-diabatic driving
• Spin-chain-star systems: entangling multiple chains of spin qubits
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Timestamp Boson Sampling
• Magic transition in measurement-only circuits
• Minimal informationally complete measurements for probability representation of quantum dynamics
• Digital quantum simulation of beam splitters and squeezing with IBM quantum computers
• A tensor network discriminator architecture for classification of quantum data on quantum computers
• Quantum supremacy and quantum phase transitions
• Interplay of entanglement structures and stabilizer entropy in spin models
• Fiber Loop Quantum Buffer for Photonic Qubits
• Sufficient condition for universal quantum computation using bosonic circuits
• Certification of Gaussian Boson Sampling via graph theory
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Parametric Probabilistic Quantum Memory
• Cross-verification of independent quantum devices
• Generalized binomial state: Nonclassical features observed through various witnesses and a measure of nonclassicality
• Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight
• Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
• Protocols for Trainable and Differentiable Quantum Generative Modelling
• Symmetry Protected Quantum Computation
• Quantifying Quantum Computational Advantage on a Processor of Ultracold Atoms
• A game of quantum advantage: linking verification and simulation
• Entanglement and complexity of interacting qubits subject to asymmetric noise
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Unextendible entangled bases and more nonlocality with less entanglement
• Self-Adaptive Quantum Kernel Principal Components Analysis for Compact Readout of Chemiresistive Sensor Arrays
• The dilemma of quantum neural networks
• A quantum information theoretic analysis of reinforcement learning-assisted quantum architecture search
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Sample-efficient benchmarking of multi-photon interference on a boson sampler in the sparse regime
• Faster Born probability estimation via gate merging and frame optimisation
• Variational certification of quantum devices
• Calculable lower bounds on the efficiency of universal sets of quantum gates
• Entanglement Scaling in Quantum Advantage Benchmarks
• Hierarchy of quantum operations in manipulating coherence and entanglement
• Quantum advantage from energy measurements of many-body quantum systems
• Surface Code Design for Asymmetric Error Channels
• Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix
• Fidelity-dissipation relations in quantum gates
• Quantum supremacy in driven quantum many-body systems
• Measuring Trotter error and its application to precision-guaranteed Hamiltonian simulations
• The Wave-Particle Duality in a Quantum Heat Engine
• Higher-Order Nonclassicality in Photon Added and Subtracted Qudit States
• In situ characterization of linear-optical networks in randomized boson sampling
• An Exact Link between Nonlocal Nonstabilizerness and Operator Entanglement
• Locality and entanglement of indistinguishable particles
• The superconducting circuit companion -- an introduction with worked examples
• Navigating the noise-depth tradeoff in adiabatic quantum circuits
• Efficient and quantum-adaptive machine learning with fermion neural networks
• Framework for Learning and Control in the Classical and Quantum Domains
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Forging quantum data: classically defeating an IQP-based quantum test
• The Inductive Bias of Quantum Kernels
• Coherence Fraction in Grover Search Algorithm
• A variational quantum algorithm for tackling multi-dimensional Poisson equations with inhomogeneous boundary conditions
• Quantum Computing for Data Centric Engineering and Science
• Quasidistribution of phases in Raman process with weak and strong pumps
• Action in Hamiltonian Models Constructed by Yang-Baxter Equation: Entanglement and Measures of Correlation
• Linear multiport photonic interferometers: loss analysis of temporally-encoded architectures
• Distinguishing Phases via Non-Markovian Dynamics of Entanglement in Topological Quantum Codes under Parallel Magnetic Field
• Non-Randomness of Google's Quantum Supremacy Benchmark
• On-demand continuous-variable quantum entanglement source for integrated circuits
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• A New Fast Computation of a Permanent
• Experimental linear optical computing of the matrix permanent
• Quantum supremacy with analog quantum processors for material science and machine learning
• n-Qubit Operations on Sphere and Queueing Scaling Limits for Programmable Quantum Computer
• A comparison between higher-order nonclassicalities of superposition engineered coherent and thermal states
• Voltage-amplified heat rectification in SIS junctions
• Efficient fidelity estimation: Alternative derivation and related applications
• Long-range Ising interactions mediated by $\lambda {\varphi }^4$ fields: probing the renormalisation of sound in crystals of trapped ions
• Giant shot noise in superconductor/ferromagnet junctions with orbital-symmetry-controlled spin-orbit coupling
• Matrix concentration inequalities and efficiency of random universal sets of quantum gates
• Quantum Computing: an undergraduate approach using Qiskit
• Universal framework for simultaneous tomography of quantum states and SPAM noise
• Postselected communication over quantum channels
• Aircraft Loading Optimization: MemComputing the 5th Airbus Problem
• High performance Boson Sampling simulation via data-flow engines
• Wasserstein Complexity of Quantum Circuits
• Qubit Optimized Quantum Implementation of SLIM
• Quantum-soft QUBO Suppression for Accurate Object Detection
• A Unified Framework for Quantum Supervised Learning
• Improved Strong Simulation of Universal Quantum Circuits
• Detecting Entanglement Generating Circuits in Cloud-Based Quantum Computing
• Passive verification protocol for thermal graph states
• Quantum estimation bound of Gaussian matrix permanent
• Boson sampling with ultracold atoms in a programmable optical lattice
• Measurement-invisible quantum correlations in scrambling dynamics
• Quantum simulations of complex systems
• Accelerating variational quantum algorithms with multiple quantum processors
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Self-attention U-Net decoder for toric codes
• Speedup in Classical Simulation of Gaussian Boson Sampling
• Optimal quantum reservoir learning in proximity to universality
• Information phases of partial projected ensembles generated from random quantum states and scrambling dynamics
• On the Hardness of Measuring Magic
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• Low overhead universality and quantum supremacy using only $Z$-control
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Quantum Sparse Coding and Decoding Based on Quantum Network
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Quantum fidelity kernel with a trapped-ion simulation platform
• Symbolic quantum programming for supporting applications of quantum computing technologies
• Suppressing decoherence in quantum state transfer with unitary operations
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
• Measurement and control of a superconducting quantum processor with a fully-integrated radio-frequency system on a chip
• Quantum Algorithm for Online Convex Optimization
• Finding high-order Hadamard matrices by using quantum computers
• Many-body thermal states on a quantum computer: a variational approach
• Quantum Algorithms in Cybernetics
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation
• Hardness of efficiently generating ground states in postselected quantum computation
• A Novel Bulk-Optics Scheme for Quantum Walk with High Phase Stability
• Qubit Geometry through Holomorphic Quantization
• Toward quantum scaling advantage in approximate optimization
• A New Scaling Function for QAOA Tensor Network Simulations
• Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
• Improved Weak Simulation of Universal Quantum Circuits by Correlated $L_1$ Sampling
• On the Fundamental Resource for Exponential Advantage in Quantum Channel Learning
• Optical Quantum Computing
• Comparing coherence measures for X states: Can quantum states be ordered based on quantum coherence?
• Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
• Resourcefulness of non-classical continuous-variable quantum gates
• Ability of entanglement and purity to help to detect systematic experimental errors
• Teleportation-based squeezer for bosonic cluster states
• Resource complexity of Symmetry Protected Topological phases
• Validating multi-photon quantum interference with finite data
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Quantum Advantage with Timestamp Membosonsampling
• Quantum Computation
• High-performance parallel classical scheme for simulating shallow quantum circuits