MathDB

Quantum supremacy conjecture for random circuit sampling

At least 7 years old · documented by

Let A{\cal A} be a circuit architecture, and let HA{\cal H}_{\cal A} be the distribution of circuits in A{\cal A} whose gates are independently drawn from Haar measure. Random circuit sampling (RCS) is the task of receiving a circuit CC sampled from HA{\cal H}_{\cal A} and an error parameter ϵ>0\epsilon>0, then sampling from the distribution induced by CC, namely

Pr⁡(y)=∣⟨y∣C∣0⟩∣2\Pr(y)=|\langle y|C|0\rangle|^2

up to total variation distance ϵ\epsilon in time poly⁡(n,1/ϵ)\operatorname{poly}(n,1/\epsilon). Here nn is the number of qubits.

Quantum supremacy conjecture. There is no classical randomized algorithm that performs RCS to inverse-polynomial total variation-distance error.

This conjecture asserts the classical computational hardness of sampling from random quantum-circuit output distributions and is a central formulation of quantum computational supremacy. The supplied text gives no resolution evidence, so its status remains open.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The quantum supremacy conjecture for random circuit sampling

    Let A\mathcal{A} be an architecture over circuits, let HA\mathcal{H}_{\mathcal{A}} be the distribution over circuits in A\mathcal{A} whose local gates are independently drawn from the Haar measure, and let RCS be the task of, given C∈HAC\in\mathcal{H}_{\mathcal{A}} and parameters ϵ>0\epsilon>0 and δ>0\delta>0, sampling from the output distribution induced by CC with probability 1−δ1-\delta over the choice of CC, up to total variation distance ϵ\epsilon in time poly⁡(n,ϵ−1)\operatorname{poly}(n,\epsilon^{-1}). Quantum supremacy conjecture. There is no classical randomized algorithm that performs RCS in time poly⁡(n,ϵ−1)\operatorname{poly}(n,\epsilon^{-1}), where ϵ\epsilon is the total variation distance error. This conjecture is the average-case hardness assumption underlying random circuit sampling proposals for demonstrating quantum supremacy; the source gives no resolution of it.

    source: Ramis Movassagh, “Quantum supremacy and random circuits”, arXiv:1909.06210 (2020).

References

Primary source

Ramis Movassagh, “Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling”, arXiv:1810.04681 (2018).

computational-complexityquantum-complexityquantum-computingrandom-circuitsrandom-circuit-sampling
Posted · edited

Progress summary

Refreshed
Claimed progress

The conjecture remains unresolved: a 2023 classical method handles many noisy circuits, but no result defeats the claimed hardness of ideal random-circuit sampling.

The conjecture says that no efficient classical randomized method can reproduce the output samples of suitably random quantum circuits to inverse-polynomial accuracy. The cited literature presents evidence for hardness, but does not prove the full sampling claim.

Known results

  • Exact output-probability computation for suitable random circuits is average-case #P\#P-hard, using worst-case-to-average-case reductions and anti-concentration (2018–2019).
  • The required robustness for approximate average-case sampling remains unproved; the known reductions are necessary but not sufficient.
  • Under standard complexity assumptions, sufficiently accurate additive approximation of output probabilities would imply classical sampling hardness.
  • Experimental demonstrations and complexity-theoretic evidence do not establish the conjecture.

January 9, 2023 noisy-circuit simulation

A reported classical algorithm simulates a major class of intermediate-depth circuits with gate errors, narrowing the practical supremacy window. It becomes impractical as errors vanish and fails for error-free circuits, so it neither refutes nor proves the stated ideal-RCS conjecture; some shallower noisy cases also remain unknown.

Current status (as of September 2026): The ideal random-circuit-sampling conjecture remains open; classical hardness has substantial conditional and average-case evidence, while the 2023 noisy-circuit result is only a claimed partial advance and does not settle it.

Sources

Solutions 0

No solutions have been posted yet.