What was the exact problem solved in the quantum supremacy achievement?
Quantum supremacy is a milestone that refers to an experimental demonstration where a programmable quantum processor performs a well-defined computational task in a time that is infeasible for any known classical computer. The experiment reported by Google in 2019, carried out on the 53-qubit superconducting processor named “Sycamore”, is the first accepted demonstration of that milestone. The task that Sycamore executed is often paraphrased as “sampling from the output distribution of a random quantum circuit”. The exact computational problem, its formal statement, and the reasons it is believed to be out of practical reach for classical machines are examined below in a step-by-step manner.
1. Theoretical framing of Random Circuit Sampling (RCS)
1.1. Formal definition
A random quantum circuit C acting on n qubits is drawn from a publicly known distribution D of circuits. Each circuit has a fixed depth d (number of cycles of gates) and a prescribed gate set; for Sycamore’s demonstration, d = 20 cycles and the gate set consisted of arbitrary single-qubit rotations and two-qubit fSIM gates arranged on a two-dimensional grid. The computational problem is the following:
Input: a description of the circuit C ∼ D on n qubits.
Task: produce m independent bitstrings s₁, …, s_m ∈ {0,1}ⁿ whose joint distribution is ε-close (in total variation distance) to the quantum output distribution P_C(z) = |⟨z|C|0ⁿ⟩|².
The requirement “ε-close” forbids trivial or obviously wrong solutions such as outputting a uniform random string. It is explicit: the output distribution must have a statistical distance to P_C that passes specified fidelity tests (linear cross-entropy benchmarking in the Google experiment).
1.2. Complexity classification
Sampling problems are usually analyzed in the framework of distributional complexity classes. RCS can be phrased as a promise problem in the class BQP over distributions (BQPSamp). The important conjecture is that approximating P_C to multiplicative error up to 1/ poly(n) is #P-hard on average. Under Stockmeyer’s counting theorem, an efficient classical sampler that gives even modest multiplicative approximations would collapse the Polynomial Hierarchy (PH) to its third level. The standing assumption that PH does not collapse leads the community to regard RCS as classically intractable at large n and d.
2. Experimental realisation on Sycamore
2.1. Hardware
Sycamore employs planar superconducting transmon qubits. Each qubit couples capacitively to four nearest neighbours arranged on a semi-rectangular lattice. Voltage and microwave pulses provide single-qubit rotations around arbitrary axes, while tunable couplers enact the fSIM two-qubit entangling gate (a generalized √iSWAP followed by controlled-phase terms).
2.2. Circuit construction
Twenty cycles were performed, each cycle containing:
• For every qubit, a single-qubit rotation parameterized as Rz(θ₁)Rx(θ₂)Rz(θ₃). The angles were drawn pseudorandomly with high-precision rational values known to both experimentalists and verifiers.
• On alternate cycles, a pattern of fSIM gates was applied between disjoint sets of neighbouring qubits, such that every edge of the lattice was activated twice across the 20 cycles.
The result is a “high-depth, low-locality” circuit exhibiting a Porter-Thomas distribution of output probabilities.
2.3. Sampling procedure
After executing the 20-cycle circuit, all 53 qubits were measured in the computational basis. Each run delivered a 53-bit binary string. The sequence of experimental bitstrings is the sample from P_C.
3. Verification of correct sampling
3.1. Cross-entropy benchmarking (XEB)
For circuits up to 14 qubits, classical simulation is still possible. Google measured the linear cross-entropy fidelity F_XEB = (2ⁿ)〈P_C(s)〉_m − 1, where 〈·〉_m denotes the empirical mean over m samples. An ideal quantum device sampling perfectly from P_C would yield F_XEB = 1. A uniformly random sampler gives F_XEB ≈ 0. The Sycamore device achieved F_XEB ≈ 0.002 for the full 53-qubit circuits, consistent with a per-cycle gate fidelity above 99.9 %.
3.2. Cycle slice verification
By truncating the last few cycles, the team created shallower versions of the circuits that were still simulable classically and confirmed that the XEB extrapolated smoothly with depth, lending confidence in the fidelity estimates for the full-depth experiment.
4. Classical simulation effort
4.1. Schrödinger-Feynman hybrid algorithm
Google’s own simulators exploited 4-petabyte memory footprints distributed across 512 TPU cores and 4096 nodes of the Summit supercomputer to compute ideal amplitudes for up to 42-qubit, 20-cycle circuits. Extrapolating resource usage suggested that simulating 53 qubits at full depth would require days to months on existing exascale systems and hundreds of petabytes of RAM.
4.2. Competing simulations (IBM, Alibaba, etc.)
IBM researchers employed a tensor-network contraction strategy and claimed the same distribution could be sampled in roughly 2.5 days on Summit. That estimate omitted the I/O cost of writing terabytes of amplitude data and relied on partitioning tricks that fail for circuits of slightly higher depth or irregular qubit layouts. Follow-up benchmarks corroborated Google’s estimate that a direct classical simulation at comparable fidelity would take centuries on current supercomputers if conducted naively. Even if tuned algorithms reduce 10¹¹ s by two orders of magnitude, the runtime gap remains several million-fold against Sycamore’s 200-second wall-clock.
5. Why Random Circuit Sampling is thought to be hard
5.1. Porter-Thomas sparsity
The output amplitudes of chaotic quantum circuits follow an exponential distribution; thus, minuscule changes in amplitudes greatly alter probabilities, rendering approximate sampling extremely sensitive to computational noise.
5.2. Average-case hardness
Jozsa and Van den Nest showed that classically simulating a randomly drawn circuit from universal gate sets is as difficult on average as simulating the hardest circuits, assuming the anti-concentration property. Aaronson and Chen further proved that multiplicative approximations of amplitudes remain #P-hard in the average-case for circuits exhibiting anti-concentration, which RCS satisfies.
5.3. Fine-grained complexity
Assuming no 2^{αn}-time classical algorithm exists for approximate output distributions at constant depth beyond 40–50 cycles, a conjecture that parallels the Exponential Time Hypothesis, explains the exponential scaling observed in both tensor-network and Feynman-path classical approaches.
6. Didactic miniature example
6.1. Three-qubit random circuit
Choose circuit depth d = 2 cycles:
Cycle 1: random single-qubit rotations on each qubit followed by CZ gate between q₀-q₁.
Cycle 2: new single-qubit rotations followed by CZ between q₁-q₂.
Classically computing all eight amplitudes requires 2³ = 8 complex numbers, trivial for modern computers. Sampling 1000 bitstrings is immediate. For 53 qubits, one needs 2⁵³ ≈ 9×10¹⁵ amplitudes; caching only the non-negligible ones is impossible because the Porter-Thomas distribution ensures most amplitudes lie above 2^{−53}. Thus, the three-qubit toy highlights the exponential blow-up while keeping the circuit structure analogous.
6.2. Tensor-network scaling illustration
The contraction of a 3×3 lattice atop the three-qubit example splits into nine rank-2 tensors; movie to 53 qubits on a non-square grid inflates indices and bonds, with contraction cost scaling ~χ^w where χ is bond dimension (~2) and w is tree-width (≈n). This translates to 2^{53} after eliminating constant-factor optimisations.
7. Relationship with TensorFlow Quantum (TFQ) and machine learning
Sycamore’s accomplishment did not employ machine-learning techniques in the core sampling task, yet its methodology strongly influenced hybrid classical-quantum workflows exposed in frameworks such as TFQ. Random circuit sampling has become a standard benchmark layer in TFQ, useful for:
• Stress-testing stochastic gradient optimisers operating on variational quantum circuits under hardware noise.
• Generating synthetic datasets to calibrate quantum generative adversarial networks, exploiting the Porter-Thomas distribution as a target.
• Producing feature maps whose kernel values approximate high-degree polynomial kernels classically inaccessible, favourable for certain support-vector machine constructs.
Researchers can therefore examine how training metrics degrade with increasing depth, mirroring the fidelity decay observed in the supremacy experiment.
8. Common misconceptions, clarifications and limits
8.1. Utility of the solved problem
RCS has no direct industrial application. Its significance is foundational: it benchmarks the crossover point where quantum devices surpass classical counterparts for at least one explicit computational task.
8.2. “Solve” versus “sample”
Sycamore did not compute an answer to an algebraic or optimisation problem; it generated samples. The validation relied on statistical properties, not deterministic equality.
8.3. “53-qubit quantum computer beats supercomputer”
The narrative is frequently overstated. The supremacy claim holds under the assumption of no unknown, drastically better classical algorithm for approximate RCS and under the error thresholds set by the experiment. Practical, error-corrected quantum computers for broad applications still require orders of magnitude more logical qubits.
9. Post-supremacy developments
9.1. Cross-platform replications
Photonic ensembles (e.g., USTC’s Jiuzhang series) performed Gaussian Boson Sampling with 100+ photons, illustrating that the supremacy benchmark can be met in multiple physical modalities by tailoring the sampling task to the hardware’s native strengths.
9.2. Incremental improvements in classical simulators
Tensor-network condensation, low-rank stabiliser decompositions and amplitude embedding methods extended feasible simulation sizes, pushing the classical boundary from roughly 43 to 48 qubits at similar depths. Each advance narrows but does not close the gap.
9.3. Towards quantum advantage for useful algorithms
Efforts are underway to port chemistry and combinatorial optimisation workflows onto Noisy Intermediate-Scale Quantum (NISQ) hardware. Supremacy has motivated refined error-mitigation techniques, e.g., probabilistic error cancellation and symmetry verification, which were first stress-tested on random circuits.
10. Key takeaways for practitioners
• The computational problem in quantum supremacy is Random Circuit Sampling: producing bitstrings from the exact output distribution of a publicly specified, pseudo-random quantum circuit.
• Formal hardness stems from average-case #P-hardness and the presumed stability of the Polynomial Hierarchy.
• Sycamore’s 53-qubit processor executed 20-cycle circuits in about 200 s, while best-known classical algorithms require astronomical time and memory at comparable fidelity.
• Verification involves cross-entropy benchmarking rather than pairwise comparison of bitstrings.
• The problem is valuable as a benchmark and methodological stepping stone, even though it does not execute a classically useful computation.
Other recent questions and answers regarding EITC/AI/TFQML TensorFlow Quantum Machine Learning:
- What are the main differences between classical and quantum neural networks?
- What are the consequences of the quantum supremacy achievement?
- What are the advantages of using the Rotosolve algorithm over other optimization methods like SPSA in the context of VQE, particularly regarding the smoothness and efficiency of convergence?
- How does the Rotosolve algorithm optimize the parameters ( θ ) in VQE, and what are the key steps involved in this optimization process?
- What is the significance of parameterized rotation gates ( U(θ) ) in VQE, and how are they typically expressed in terms of trigonometric functions and generators?
- How is the expectation value of an operator ( A ) in a quantum state described by ( ρ ) calculated, and why is this formulation important for VQE?
- What is the role of the density matrix ( ρ ) in the context of quantum states, and how does it differ for pure and mixed states?
- What are the key steps involved in constructing a quantum circuit for a two-qubit Hamiltonian in TensorFlow Quantum, and how do these steps ensure the accurate simulation of the quantum system?
- How are the measurements transformed into the Z basis for different Pauli terms, and why is this transformation necessary in the context of VQE?
- What role does the classical optimizer play in the VQE algorithm, and which specific optimizer is used in the TensorFlow Quantum implementation described?
View more questions and answers in EITC/AI/TFQML TensorFlow Quantum Machine Learning