Source-linked AI summary
Quantum Computational Supremacy
Aram W Harrow, Ashley Montanaro
TL;DR
Quantum supremacy proposals require reliable evidence that restricted quantum computations outperform classical simulation, but verification and realistic noise remain unresolved challenges. This paper surveys leading proposals and complexity-theoretic comparisons, finding rapid experimental progress while verification remains the principal unmet requirement.
Problem
Reliable verification of quantum supremacy experiments remains an unresolved challenge because efficient classical simulation is unavailable by definition.
Method
The paper surveys supremacy proposals and develops complexity-theoretic arguments for comparing restricted quantum models with classical simulation.
Results
Quantum supremacy experiments progressed from three-photon boson sampling to a proposed 49-qubit random-circuit implementation, with verification the only unmet requirement.
Takeaways & Limitations
Quantum supremacy experiments occupy an experimentally accessible regime with stronger classical-hardness evidence than full-scale proposals, but require improved verification methods.
Takeaways & Limitations
Establishing quantum supremacy from approximate classical-simulation hardness using well-believed classical complexity assumptions remains a major open problem.
Abstract
from arXiv · showhide
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.
Requirements for quantum supremacy
Quantum supremacy proposals require a defined task, plausible quantum algorithm, bounded classical resources, a complexity assumption, and optionally efficient verification. Candidate demonstrations range from factoring and analog simulation to nonuniversal circuit models believed classically hard to simulate.
- Core requirements: A quantum supremacy experiment requires a well-defined task, plausible quantum algorithm, classical time/space limits, and a complexity-theoretic assumption, with verification optional.The algorithm should ideally be plausible on near-term hardware, while verification must distinguish quantum from classical computation within the allowed resources.
- Scope: The computational task need not have practical interest, and factoring or quantum simulation can themselves serve as routes to quantum supremacy.The paper frames supremacy as a capability milestone rather than requiring an application-driven task.
- Factoring: Factoring offers an easily verifiable route if classical computers cannot factor quickly, but current estimates require ≈4000 qubits and ≈10^9 gates for a 2048-bit number.Fault-tolerance and architectural overheads could further increase the required resources.
- Analog simulation: Analog quantum simulators may already demonstrate supremacy when they estimate properties believed classically hard, although confidence in such hardness conjectures is lower.The paper contrasts this uncertainty with the stronger confidence associated with more established computational assumptions.
- Circuit-based proposals: Modern proposals include constant-depth circuits, boson sampling, and commuting or noncommuting random circuits, whose classical hardness is argued despite lacking universal quantum-computing capability.The commuting model is known as IQP, while boson sampling uses single photons through a linear-optical network.
Specific proposals for quantum supremacy
Proposals for quantum supremacy include boson sampling and random quantum circuits, with experiments targeting output distributions that are difficult to sample or simulate classically.
- Boson sampling: Boson sampling samples photon-detection outcomes after n coincident photons pass through a random linear-optical network on m ≫ n modes.Its output distribution is conjectured to be hard to sample classically.
- Boson sampling: Scattershot boson sampling addresses photon-source scaling by using many probabilistic sources and recording which input modes contain photons.Initial spontaneous-parametric-downconversion sources require exponential time in photon number for each valid experimental run.
- Boson sampling: Boson-sampling implementations must handle realistic network loss and the possibility of more efficient classical sampling techniques.
- Random quantum circuits: IQP proposals use commuting quantum circuits whose gates are diagonal in the X basis and could, in principle, be applied simultaneously.These proposals remain within the standard quantum circuit model.
- Random quantum circuits: Google proposed sampling random-circuit output distributions using superconducting qubits, with depth around 25 and around 49 qubits on a 2d square lattice.The proposal uses noncommuting gates and is intended to approach the limits of current classical simulation or validation.
Why supremacy?
Quantum supremacy is worthwhile because quantum mechanics changes the concepts of information and computation, with philosophical and practical implications. Unlike hard-to-simulate classical systems whose difficulties may scale linearly with system size, even a modest supremacy demonstration could signal much larger future computational separations.
- Why supremacy?: Quantum mechanics changes the definitions of information and computation, with philosophical and practical implications.Entanglement provides a form of correlation absent from classical information theory and can be demonstrated through Bell-inequality experiments.
- Why supremacy?: Hard-to-simulate classical systems such as fluid dynamics or protein folding can, in principle, be simulated with effort linear in the system’s energy and space-time volume.Their difficulty arises from separations of scales in time or space rather than from computational families with unboundedly larger requirements.
- Why supremacy?: A protein-folding problem requiring 1050 steps does not belong to a family including problems requiring 10100 or 101000 steps.The passage contrasts this bounded scaling with quantum supremacy’s implications for computational power.
- Why supremacy?: A quantum supremacy experiment that barely surpasses existing classical computers could imply that vastly greater separations in computational power will soon follow.This prospective significance is presented as a reason to pursue a supremacy demonstration.
Complexity-theoretic basis for quantum supremacy
Quantum supremacy proposals require assumptions about the classical intractability of quantum computation, with sampling-based proposals relying on complexity-theoretic evidence rather than hardness of one specific quantum model. Post-selection connects efficient exact classical simulation of these models to consequences such as polynomial-hierarchy collapse and an unexpected equivalence between exact and approximate counting.
- Complexity-theoretic basis for quantum supremacy: Quantum supremacy requires assuming that quantum mechanical systems cannot be simulated efficiently by classical computers, and each proposal needs its own stronger assumption.Efficient simulation is defined as simulation with polynomial overhead.
- Simulation complexity: Quantum simulation complexity is difficult to characterize because it varies across quantum systems, simulation methods, temperature, coupling strengths, and limits on addressing individual qubits.Analog simulators that cannot address individual qubits also encode a narrower range of problem instances.
- Modern supremacy proposals: Sampling proposals ask quantum computers to output samples from a desired distribution rather than deterministic answers, while using restricted models such as boson sampling and low-depth circuits.Their complexity assumptions need not assert that the specific quantum model is hard to simulate.
- Post-selection: Post-selection conditions on an auxiliary output string taking a fixed value, increasing the power of both classical and quantum computation.A computation outputs strings y and z, with the output represented by y and conditioning performed on z.
- Complexity consequences: Efficient exact classical simulation of restricted quantum models would imply surprises including collapse of the polynomial hierarchy and exact counting being roughly as hard as approximate counting.These consequences are not believed to be true, supporting the absence of efficient exact classical simulation.
Fine-grained complexity assumptions
The assumption PostBPP ≠ PostBQP rules out efficient exact classical simulation when efficiency means polynomial time, but asymptotic statements do not characterize near-term computational capabilities. Concrete bounds therefore require explicit hypotheses, such as ETH with c = 0.386 for random 3-SAT instances with a planted solution.
- Fine-grained complexity assumptions: PostBPP ≠ PostBQP suffices to show that classical computers cannot exactly simulate quantum computers in polynomial time.This conclusion follows from equating “efficient” with “polynomial-time.”
- Fine-grained complexity assumptions: Asymptotic complexity statements reveal little about near-term quantum computers or existing classical competitors’ simulation abilities.The motivating target is a concrete statement about circuits with specified gate and qubit counts.
- Fine-grained complexity assumptions: c = 0.386 is the explicit ETH hypothesis corresponding to the best known algorithm for random 3-SAT instances with a planted solution.Concrete bounds may rely on analyses of the best known algorithm or provable lower bounds for black-box oracle functions.
Average-case assumptions
Average-case assumptions better match the experimental goal of showing that most quantum circuits are hard to simulate and can exclude simulations with additive error, but they are stronger and less transferable than worst-case assumptions. Establishing quantum supremacy from assumptions that connect average-case and worst-case complexity remains a major open problem.
- Worst-case versus average-case: Worst-case hardness only implies that some circuits are hard to simulate, not that an experimental family is typically hard.Equivalently, it says no classical algorithm works for all quantum circuits.
- Worst-case versus average-case: Average-case hardness means no efficient algorithm computes f(x) correctly for most x drawn from a distribution D.These conjectures are stronger, less plausible, and less readily reducible to one another than worst-case conjectures.
- Benefits: Average-case assumptions provide concrete experiments, such as random circuits of a specified size, for which most instances are conjectured hard to simulate.They also rule out a larger class of classical simulations than worst-case assumptions alone.
- Simulation error: Anticoncentration combined with average-case hardness can rule out additive-error simulations, because close output distributions cannot be distinguished without many samples.Anticoncentration means q(z) is reasonably close to uniform and is known for random circuits and IQP circuits.
- Limitations: Average-case hardness may differ across instance distributions, so hardness results do not transfer as broadly as worst-case NP-hardness results.In rare cases average-case and worst-case complexity coincide, but establishing quantum supremacy from such a problem remains a major open question.
Maximal assumptions
The maximal-assumptions strategy improves classical simulations as far as known algorithms allow, then conjectures those simulations are essentially optimal. Its strongest conjectures support semi-efficient verification but have correspondingly low confidence because any non-trivial simulation improvement could refute them.
- Maximal assumptions: The strategy strengthens complexity assumptions by improving often exponential-time classical simulations as far as possible and conjecturing they are essentially optimal.Aaronson and Chen developed simulations for n-qubit, depth-d circuits calculating matrix elements in time O((2d)n) and nearly linear space.
- Maximal assumptions: The QUATH conjecture asserts that polynomial-time classical algorithms cannot distinguish likely from unlikely quantum-circuit outcomes with an exponentially small advantage when d = Ω(n).This task is easier than full classical simulation and involves distinguishing outcomes from random guessing.
- Maximal assumptions: These strong conjectures enable a semi-efficient verification procedure that uses the quantum device only sparingly.The supplied passage truncates the description of how much the device is used.
- Maximal assumptions: Because any non-trivial improvement in simulating quantum mechanics could refute them, making the conjectures as strong as possible makes confidence in them as low as possible.The paper treats hardness conjectures as revisable estimates of the complexity of simulating quantum systems.
Physical noise and simulation errors
Physical noise challenges both quantum experiments and their classical simulation, while fault-tolerance can protect computations only below sufficiently small noise levels. Noisy quantum-supremacy claims therefore depend on subtle approximate-simulation models, hardness conjectures, and potentially simpler error-correction methods.
- Physical noise and simulation errors: Physical noise is a major challenge, although quantum fault-tolerance protects computations against sufficiently small physically reasonable noise.Its asymptotic overhead is relatively minor, but the constant factors involved are daunting.
- Physical noise and simulation errors: Classical quantum-circuit simulations also incur errors, which may be multiplicative or additive; exact-state methods can achieve low multiplicative error, whereas sampling methods naturally achieve additive error.The passage frames simulation error as analogous to imperfect implementation of ideal quantum circuits by realistic quantum computers.
- Approximate-simulation hardness: Boson-sampling hardness under approximate classical sampling was argued from two reasonable but currently unproven conjectures, including anticoncentration and average-case permanent hardness.The classical sampler may output a distribution with small total variation distance from the true distribution.
- Approximate-simulation hardness: IQP sampling has an analogous hardness result, with provable anticoncentration and alternative conjectures concerning approximate partition-function or low-degree-polynomial hardness.The relevant alternatives involve the Ising model or a natural property of low-degree polynomials over finite fields.
- Noisy simulability: Noise complicates simulability models: arbitrarily small constant noise on each qubit can permit efficient classical simulation of the noisy distribution, while small-relative-error simulation can remain hard.The question of modeling noisy simulability remains subtle and under debate.
- Noisy simulability: Noisy quantum-supremacy experiments may need error-correction, though correcting noise at the end of an IQP circuit can use simple classical techniques with low overhead.This may be substantially simpler than the machinery required for full quantum fault-tolerance.
Verification
Verification is essential because quantum supremacy experiments are, by definition, classically hard to simulate efficiently, so their success cannot be checked directly by classical simulation. Known approaches test smaller computations, analyze output distributions, hide predetermined answers, or directly certify computations, but all have significant drawbacks.
- Verification: Verification is essential because supremacy experiments cannot be efficiently simulated classically, requiring another way to establish that the experiment performed a classically hard task.The paper identifies verification as a key issue in claiming quantum supremacy.
- Verification: Testing smaller circuit components or classically simulable computations can build confidence that an experiment is functioning correctly without testing it in its entirety.Examples include testing individual components and mostly or entirely Clifford-group computations.
- Verification: Statistical output-distribution tests may require calculating individual probabilities that are themselves classically hard, limiting efficient verification based only on the device’s input and output.Different verification procedures relax these constraints by avoiding particular hardness assumptions, allowing exponential classical time, or using a secret string and derived input.
- Verification: Hiding a known answer from the quantum device can enable verification, as in IQP proposals that conceal a bit string within a seemingly random linear code.The verifier knows how the code was scrambled, while the quantum device or classical simulator sees only the derived instance.
- Verification: Direct certification is the gold standard, but every known example requires more resources than the original computation, including proposed verification of IQP computations via local-Hamiltonian ground states.Direct certification may use information beyond the experiment’s classical output.
- Verification: All known verification techniques are inefficient, rely on assumptions about experimental behavior, or use poorly understood computational-hardness assumptions, making improved verification an open research problem.The paper describes avoiding these issues as a pressing open question in quantum supremacy research.
Outlook · Selected references
Quantum-supremacy experiments have advanced rapidly, but verification remains the principal unmet requirement. Open questions concern efficient verification, classical simulation, stronger hardness assumptions, and the role of supremacy as a developmental milestone.
- Outlook: Experiments progressed from boson sampling with 3 photons to a proposed random-circuit implementation on 49 qubits.The passage describes this as progress over just a few years.
- Outlook: Each diverse quantum-supremacy proposal satisfies the article’s five initial requirements except verification.Verification is identified as the common outstanding requirement.
- Outlook: The most pressing theoretical question is developing a scheme that can be efficiently verified, analogous to easily checked Bell-test statistics.The proposed analogy is with the verification of Bell-test statistics.
- Outlook: Better classical simulations could clarify the quantum/classical boundary, even if attempts to simulate the systems fail.The passage presents both successful simulations and failed attempts as informative.
- Outlook: The field could simplify and strengthen its hardness assumptions, including by relating low variational-distance simulation to a collapse result.This is described as an ambitious goal rather than an established result.
- Outlook: Quantum supremacy is viewed as a necessary developmental step rather than a long-term goal for quantum computers.The eventual justification is expected to come from solving important problems otherwise unknown to be solvable.
- Outlook: Early emphasis on supremacy helps ensure that quantum computers solve clearly defined problems with well-understood classical competition.The passage contrasts this early focus with the field’s eventual aim of solving important problems.