Source-linked AI summary
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
Scott Aaronson, Sam Gunn
TL;DR
The paper studies whether a classical computer can spoof Linear XEB, since sampling hardness alone does not settle the difficulty of passing this test. It adapts Aaronson and Chen’s analysis to formulate XQUATH and proves conditional hardness of spoofing Linear XEB, including noisy-circuit settings. The result leaves open improvements to amplitude-estimation algorithms and notes finite-experiment limitations when circuit noise makes b−1 very small.
Problem
The central question is whether spoofing Linear XEB is classically hard, because hardness of sampling does not by itself establish hardness of passing this test.
Source: §1 · pp. 1–2Method
Results
Takeaways & Limitations
The result indicates that spoofing Linear XEB has no special advantage over nontrivially estimating quantum-circuit amplitudes.
Source: §1 · p. 2The argument is conditional, and without fault tolerance b−1 can become very small for circuits beyond finite experiments’ usable size.
Source: §2 · p. 3
Abstract
from arXiv · showhide
Recently, Google announced the first demonstration of quantum computational supremacy with a programmable superconducting processor. Their demonstration is based on collecting samples from the output distribution of a noisy random quantum circuit, then applying a statistical test to those samples called Linear Cross-Entropy Benchmarking (Linear XEB). This raises a theoretical question: how hard is it for a classical computer to spoof the results of the Linear XEB test? In this short note, we adapt an analysis of Aaronson and Chen [2017] to prove a conditional hardness result for Linear XEB spoofing. Specifically, we show that the problem is classically hard, assuming that there is no efficient classical algorithm that, given a random n-qubit quantum circuit C, estimates the probability of C outputting a specific output string, say 0^n, with variance even slightly better than that of the trivial estimator that always estimates 1/2^n. Our result automatically encompasses the case of noisy circuits.
1. Introduction
The paper asks whether classical computers can spoof Linear XEB, a question not settled by hardness results for sampling alone. It formulates XQUATH and shows that this amplitude-estimation assumption implies hardness of spoofing Linear XEB, while explaining why recent classical improvements target amplitude estimation instead.
Background
- Quantum computational supremacy via random-circuit sampling uses a universal quantum computer to outperform existing classical computers on a computational task.The paper places Linear XEB within Google’s demonstration based on samples from random quantum circuits.Source: §1 · p. 1
Motivation
- Linear XEB tests whether observed samples concentrate on outputs with higher ideal probabilities, but good XEB scores need not imply correct sampling in total variation distance.A device could score well by always outputting the k highest-probability outputs.Source: §1 · pp. 1–2
- Sampling-hardness results do not directly establish the classical hardness of spoofing Linear XEB.The paper distinguishes hardness of sampling from hardness of passing this specific statistical test.Source: §1 · p. 2
Contribution
- The paper introduces XQUATH and shows that it implies the hardness of spoofing Linear XEB without referring to sampling.The assumption concerns efficiently estimating the probability of a specific output of a random quantum circuit.Source: §1 · p. 2
- The result says that spoofing Linear XEB offers no special shortcut beyond nontrivially estimating circuit amplitudes, without ruling out improved amplitude-estimation algorithms.This distinguishes the paper’s conditional hardness result from a claim that amplitude-estimation algorithms cannot improve.Source: §1 · p. 2
Related work
- Recent classical advances targeted general amplitude estimation or approximate circuit simulation, rather than a method specific to spoofing Linear XEB.These include tensor-network optimization, secondary-storage simulation, and an average-case constant-depth simulation algorithm; the latter does not apply to circuits as deep as Google’s.Source: §1 · pp. 2–3
2. Preliminaries
The paper defines XQUATH as the inability of efficient classical algorithms to improve meaningfully on the trivial estimate 1/2^n for a random circuit’s probability of outputting 0^n, and relates it to XHOG hardness.
XQUATH
- XQUATH assumes no polynomial-time classical algorithm can estimate Pr[C outputs 0^n] with mean squared error even slightly below the trivial 1/2^n estimator.The expectations include both the random circuit and the algorithm’s internal randomness.Source: §2 · p. 3
Circuit distributions
- The framework applies to circuit distributions invariant under appending NOT gates, although Google’s experiment did not satisfy this property exactly.The discrepancy is not physical because final NOT gates merely relabel outputs.Source: §2 · p. 3
Attempted refutations
- The analysis notes that Feynman-path estimators improve mean squared error only exponentially in gate count, which is inadequate for circuits with many more gates than 3^n.Existing simulation algorithms likewise do not appear to refute XQUATH for reasonable circuit distributions.Source: §2 · p. 3
XHOG
- XHOG asks for k distinct circuit outputs whose average squared-magnitude amplitude is at least b/2^n.The distinctness requirement is needed for the reduction.Source: §2 · p. 3
Finite-experiment boundary
- Applying the hardness claim to finite experiments is difficult because b − 1 becomes very small for circuits beyond experimental fault-tolerance.The paper treats b > 1 as the interesting regime and generally regards b as a constant.Source: §2 · p. 3
Expected performance
- For ideal circuits, the expected XHOG parameter is b ≈ 2, while noisy circuits are expected to achieve b slightly larger than 1.Theorem 1 consequently targets classical hardness whenever b > 1.Source: §2 · p. 4
3. Proof of the Reduction
The reduction transforms an XHOG solver into an estimator for a circuit’s output probability, showing that XHOG success beyond the baseline would contradict XQUATH under suitable sample conditions.
Reduction cost
- The reduction calls an XHOG algorithm once, so solving XHOG requires essentially the computational effort of solving XQUATH, minus O(k).All other reduction steps are efficient.Source: §3 · p. 4
Theorem 1
- Assuming XQUATH, no polynomial-time classical algorithm can solve XHOG with success probability s > 1/2^b + ϵ.The theorem’s quantitative bound is approximately 1/2^ϵδ in the stated parameterization.Source: §3 · p. 4
Randomized reduction
- The reduction randomizes a target output z by appending NOT gates, preserving the circuit distribution while mapping Pr[C outputs 0^n] to Pr[C′ outputs z].This symmetry lets the estimator use whether z appears among the XHOG outputs.Source: §3 · p. 4
Estimator construction
- When the randomized target z is among the solver’s outputs, the estimator returns b2^-n; otherwise it returns the trivial estimate 2^-n.The construction uses the XHOG heavy-output guarantee to distinguish the two estimates.Source: §3 · p. 4
Error analysis
- The proof bounds the estimator’s mean-squared improvement through separate cases for XHOG success and failure, while targets outside the generated set contribute zero.Combining these cases yields an Ω(2^-3n) improvement when the sample condition holds.Source: §3 · pp. 4–5
Sample requirement
- The argument requires at least k ≥ (b − 1)^−2 samples, because substantially fewer samples let uniform random sampling pass XHOG with non-negligible probability.A concrete theorem instance sets s = 3.Source: §3 · p. 5
4. Open Problems
The note closes by identifying unresolved questions about whether stronger assumptions can establish Linear XEB spoofing hardness and how XQUATH relates to QUATH.
- The authors ask whether classical hardness of spoofing Linear XEB can be based on a more secure assumption.Source: §4 · p. 5
- They also ask whether an assumption equivalent to the classical hardness of XHOG exists.Source: §4 · p. 5
- The status of XQUATH and its relationship to QUATH remain open problems.Source: §4 · p. 5
Probability of Failing XHOG.
The analysis bounds the probability of solving XHOG from estimated fidelity and sample averages, including a depolarizing-noise calculation tied to Google’s experiment.
- For the restricted parameters s = 3/4 + 1/4b and k = 4(b−1)^−2, the calculation applies Chebyshev’s inequality to bound success probability.Source: Probability of Failing XHOG · p. 6
- An estimated fidelity E[Y] ≥ (2b −1)/2^n implies solving XHOG with probability s = 3/4 + 1/4b.Source: Probability of Failing XHOG · p. 6
- The calculation covers ideal, uniform, and depolarizing-noise sampling cases when bounding the variance of the sample average.Source: Probability of Failing XHOG · p. 6
- Google’s estimated fidelity required 4 million samples for b = 1.001 and s = 3/4 + 1/4b, below the 30 million samples collected.Source: Probability of Failing XHOG · p. 6
Uniformly-Random Sampling.
The section shows that distinguishing XHOG samples from uniform samples requires about (b−1)^−2 samples when b is close to one.
- About (b−1)^−2 samples are needed before amplitude-squared values can distinguish uniform sampling from passing XHOG.Source: Uniformly-Random Sampling · p. 7
- The single-sample KL divergence expands around b = 1 as (b−1)^2/2 + O((b−1)^3), giving approximately k(b−1)^2/2 for k samples.Source: Uniformly-Random Sampling · p. 7
- A total variation distance independent of b therefore requires k ≈ (b−1)^−2.Source: Uniformly-Random Sampling · p. 7