What does a high XEB score certify about an untrusted quantum sampler?

A high score is not the same as correct sampling

Random circuit sampling experiments give a device a random circuit C on n qubits and ask it to return strings z drawn from the ideal output distribution p(z) = |<z|C|0^n>|^2 over N = 2^n outcomes. Because checking a few samples against a full distribution is infeasible, the samples are scored by the linear cross-entropy benchmark (XEB): a classical computer computes the ideal probabilities of the returned strings z1,...,zk and reports the average (N/k) sum_i p(zi). The paper uses the unshifted convention B = 1 + F_XEB, where F_XEB is the experimental XEB fidelity.

Two reference scores anchor the scale. Uniformly random strings have expected score 1, because the ideal probabilities sum to 1. An honest sampler has expected score N sum_z p(z)^2, the ideal score, which is about 2 for random circuits. The 2019 experiment reported about 1.002.

The gap that motivates the paper is that scoring well is not the same as sampling correctly. A device that knew p and always returned the most likely string would score far above an honest sampler — for a Haar-random state about ln N, roughly 42 when n = 60, compared with about 2 — even though its output would be completely predictable. The paper therefore asks what a high cross-entropy score actually certifies about an untrusted quantum device, focusing on certified randomness.

The ideal score acts as a Tsirelson bound

The paper works in the quantum query model and frames the ideal score as a Tsirelson bound for efficient devices. In a Bell experiment, quantum strategies win the CHSH game with probability at most cos^2(pi/8) ≈ 0.854, Tsirelson's bound, and at that bound either party's output bit still carries one bit of min-entropy even conditioned on the public inputs and an adversary's quantum register. The drawback is that the two devices must not communicate, a condition a user receiving only the bits cannot verify.

The alternative studied here certifies randomness with a single device by reusing the sampling experiment. A verifier sends challenge circuits, the device must answer quickly with samples, and the verifier later checks their XEB score. The adversary, called Eve, may have built the device, may share entanglement with it, and may learn the circuits afterward. Even an ideal sample is not perfectly unpredictable to Eve, since knowing the circuit lets her guess its most likely output.

The paper's results follow the CHSH analogy closely. For algorithms making o(N^(1/3)) queries, the ideal score behaves like a Tsirelson bound: no such algorithm exceeds it by more than o(1), while O(N^(1/3)) queries suffice to exceed it by a constant. The honest sampler, which makes a single query, remains optimal up to o(1) until an algorithm makes about N^(1/3) queries.

Beating the ideal score by a constant needs N^(1/3) queries

Theorem 1.1 gives the query cost of exceeding the ideal score. For Fourier sampling with N outcomes, B(A) ≤ 3 + O(q^(3/2)/sqrt(N) + q^3/N) for an algorithm making at most q queries. In particular, an expected score of 3 + epsilon, for 0 < epsilon ≤ 4, requires q ≥ (3 epsilon / 16)^(2/3) N^(1/3). For a Haar-random state accessed through the canonical oracle O_phi, B(A) ≤ 2N/(N+1) + O(q^(3/2)/sqrt(N) + q^3/N), and under Haar-random unitary access the same bound holds with an additional term O(q log N / sqrt(N)). An expected score of 2 + epsilon with 0 < epsilon ≤ 1 therefore requires Omega(epsilon^(2/3) N^(1/3)) queries with the canonical oracle, and also with Haar-random unitary access once N is large enough in terms of epsilon.

The bounds are tight. A variant of the O(N^(1/3))-query algorithm of Kre21, which the paper calls the squaring algorithm, makes O(N^(1/3)) queries and has expected score at least 5 - o(1) for Fourier sampling and at least 3 - o(1) for either form of Haar access. Consequently, for every fixed b in (3,5) for Fourier sampling, and every fixed b in (2,3) for either form of Haar access, the query complexity of achieving B(A) ≥ b is Theta(N^(1/3)), with the constant in the lower bound depending on b.

The paper notes that this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. It also gives a concrete scale: at N^(1/4) queries, where the previous lower bound still allowed a constant advantage, the score stays within O(N^(-1/8)) of the ideal score, and an expected Fourier score of 4 requires more than 0.32 N^(1/3) queries, which is more than 3 x 10^5 for n = 60.

The squaring algorithm explains where the 1/3 exponent comes from

The squaring algorithm draws m ideal samples and stores the outcomes. The stored set has total probability of order m/N, and amplitude amplification raises to nearly one the probability that one more ideal sample lies in it. This costs m + O(sqrt(N/m)) queries, which is O(N^(1/3)) for m = N^(1/3). Likely outcomes are stored more often, and the amplified sample, distributed according to p conditioned on lying in the stored set, favors them again. As a result the output z has probability nearly proportional to p(z)^2, which explains the name.

A sampler whose output distribution is proportional to p(z)^2 scores N sum_z p(z)^3 / sum_z p(z)^2, a ratio of consecutive moments, which is 15/3 = 5 for the nearly Gaussian Fourier coefficients and 6/2 = 3 for the nearly exponential Haar probabilities. To reach these scores, the variant runs a fixed number of amplification steps tuned to the typical probability of the stored set. The algorithm has the same structure as the quantum algorithm for finding collisions, whose query complexity is also N^(1/3), but the paper states that it does not know of a reduction between the two problems.

The gain in score does not come from a repeated outcome among the stored samples, which for m = N^(1/3) are distinct with high probability, but from the coincidence of the amplified sample with one of them. The output distribution of the squaring algorithm is close to the collision distribution r_p(z) = p(z)^2 / sum_y p(y)^2, the distribution of the common value of two independent samples from p conditioned on their being equal. The algorithm samples it to within average total variation distance O(N^(-1/3)).

Near-ideal scores certify nearly all output bits

Theorem 1.2 addresses how much randomness a near-ideal score certifies. For Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the n-bit output of a device that makes polynomially many queries and scores within o(1) of the ideal score has n - O(log n) bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle. The paper describes this as nearly optimal.

The guarantee is stated in terms of smooth min-entropy with smoothing o(1), which is the quantity an extractor can use directly. The paper contrasts this with earlier single-round guarantees of about gamma n bits of von Neumann entropy in a nearby state, and with multi-round guarantees that use entropy accumulation. For lists of Fourier samples without quantum side information, the earlier guarantee is n/40 bits for the whole list.

Two differences in setting matter. First, in this paper Eve learns the oracle itself; in the earlier model the device queries C' = VCW, where V applies independent random phases and W is Haar-random on the subspace orthogonal to |0^n> and fixes |0^n>, and Eve learns C while V and W remain secret. The paper states it has no corresponding result for an Eve who learns a full Haar-random unitary. Second, the result covers Fourier sampling against an entangled Eve, which was previously analyzed only for devices that behave as the honest sampler. The paper describes the two sets of results as complementary: the earlier ones certify a constant fraction of the randomness from any violation of the classical bound, while these certify all but O(log n) bits within o(1) of the ideal score.

Progress measures bound how fast a device can gain an edge

Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling, the paper purifies the random choice of function as in the compressed oracle technique. In this representation the basis states of the purifying register are indexed by subsets of {0,1}^n, called recorded sets, and each query changes a recorded set by at most one point. The number of recorded points is not itself a useful measure, since an algorithm can record many points without scoring above the honest sampler; what matters is how the points are arranged.

In the honest sampler, the part of the state with output z records exactly one point in the Hadamard basis state |chi_z> = H^{tensor n}|z> = N^(-1/2) sum_x (-1)^(z·x)|x>. To score more, an output branch must have a nonzero amplitude for removing a pair with the coefficients of its Hadamard basis state. The measure is the norm of the coherent amplitudes for removing such pairs, and comparing pair removal before and after a query leaves one other recorded point to remove, with coefficient O(1/sqrt(N)).

For Haar-random states, the natural analogue would count repeated amplitudes such as alpha_z^2 or |alpha_z|^2, but every term of the normalization sum_z |alpha_z|^2 = 1 repeats an amplitude even though the sum is a constant. The paper instead expands the state in orthogonal polynomials on the probability simplex, an expansion in which the normalization has degree zero, and uses the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation. The paper explains that earlier methods stopped at N^(1/4) because the reduction to ordinary copies of |phi> incurs a quadratic cost in q before any collision is counted; avoiding that loss requires an argument about the queries themselves, whose effect on the state is coherent and leaves no classical record.

Where the certification stops and what to compare

The paper is explicit that several steps separate its theorems from a deployed protocol. Current devices operate far from the regime the randomness theorem needs: the 2019 experiment scored about 1.002 against an ideal score of about 2, whereas Theorem 1.2 needs a deficit small enough that the smoothing parameter eta ≤ 1/2. For such devices, the paper says the guarantees of AH23 are the relevant ones. All results are in the oracle model, which the paper describes as the price of being unconditional. The theorem also assumes a bound on the expected score of the run whose output is certified, whereas a protocol observes the empirical score of finitely many samples, conditions on passing a test, and runs many rounds. In addition, the challenge comes from a truly random oracle rather than from a short seed, so the paper claims no randomness expansion. For Haar-random states the result needs the canonical oracle O_phi rather than unitary access.

The most decision-relevant comparison is between two certification regimes rather than between two scores. A device that makes polynomially many queries and scores within o(1) of the ideal score has n - O(log n) bits of smooth min-entropy with smoothing o(1), so Eve's actual guessing probability is at most 2^(-n + O(log n)) + eta = o(1). A device that makes O(N^(1/3)) queries can instead reach the ideal score while Eve guesses with probability about 1/2, which the paper draws as the analogue of mixing the squaring algorithm with an output known to Eve. The threshold that separates these regimes is the score deficit: the randomness guarantee is stated for a deficit small enough that eta ≤ 1/2, not for the roughly 1.002-versus-2 gap seen in current hardware. Readers comparing sampling experiments should therefore ask which side of that deficit a device sits on, and whether the guarantee being invoked is the constant-fraction certification of AH23 or the near-full-entropy certification proved here.

Sources used in this answer