Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires $Ω(N^{1/3})$ queries for the Haar and Fourier oracle ensembles with $N$ outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, 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; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity $Θ(N^{1/3})$, and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. 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 measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is 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.
AI Summary
The paper asks what a high linear cross-entropy benchmark (XEB) score certifies about an untrusted quantum sampler, particularly whether a near-ideal score guarantees randomness against quantum side information. It studies random Boolean-function Fourier sampling and Haar-random state sampling in the quantum query model, with $N=2^n$ outcomes.
Exceeding the honest sampler’s expected score—$3-2/N$ for Fourier sampling and $2N/(N+1)$ for Haar states—by a fixed constant requires $\Theta(N^{1/3})$ queries. This closes the previous Haar gap between roughly $N^{1/4}$ and $N^{1/3}$ and extends the Fourier lower bound beyond one query. Score upper bounds have excess $O(q^{3/2}/\sqrt N+q^3/N)$, with an additional $O(q\log N/\sqrt N)$ for Haar-unitary access. A matching “squaring” algorithm samples the distribution proportional to $p(z)^2$, attaining scores approaching $5$ and $3$, respectively.
For Fourier sampling and canonical Haar state-preparation access, a polynomial-query device scoring within deficit $\delta=o(1)$ of ideal has $n-O(\log n)$ bits of smooth min-entropy, even when an entangled adversary subsequently learns the oracle. Smoothing is $O(\sqrt\delta+q^{3/4}N^{-1/4})$. Proofs track coherent pair removal for Fourier oracles and orthogonal-polynomial levels under Dirichlet measures for Haar states; near-saturation yields entropy bounds.
The guarantees concern single-round expected scores, not finite empirical tests or acceptance-conditioned multi-round protocols. They require truly random oracles, establish no randomness expansion, and target near-ideal scores rather than current experimental fidelities. The Haar entropy result does not cover full unitary access.
No sign of AI-generated text
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires Ω(N1/3) queries for the Haar and Fourier oracle ensembles with N outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, 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(logn) bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity Θ(N1/3), and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. 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 measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is 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 asks what a high linear cross-entropy benchmark (XEB) score certifies about an untrusted quantum sampler, particularly whether a near-ideal score guarantees randomness against quantum side information. It studies random Boolean-function Fourier sampling and Haar-random state sampling in the quantum query model, with N=2n outcomes.
Exceeding the honest sampler’s expected score—3−2/N for Fourier sampling and 2N/(N+1) for Haar states—by a fixed constant requires Θ(N1/3) queries. This closes the previous Haar gap between roughly N1/4 and N1/3 and extends the Fourier lower bound beyond one query. Score upper bounds have excess O(q3/2/N+q3/N), with an additional O(qlogN/N) for Haar-unitary access. A matching “squaring” algorithm samples the distribution proportional to p(z)2, attaining scores approaching 5 and 3, respectively.
For Fourier sampling and canonical Haar state-preparation access, a polynomial-query device scoring within deficit δ=o(1) of ideal has n−O(logn) bits of smooth min-entropy, even when an entangled adversary subsequently learns the oracle. Smoothing is O(δ+q3/4N−1/4). Proofs track coherent pair removal for Fourier oracles and orthogonal-polynomial levels under Dirichlet measures for Haar states; near-saturation yields entropy bounds.
The guarantees concern single-round expected scores, not finite empirical tests or acceptance-conditioned multi-round protocols. They require truly random oracles, establish no randomness expansion, and target near-ideal scores rather than current experimental fidelities. The Haar entropy result does not cover full unitary access.
A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit C on n qubits and a sample z∈{0,1}n , the benchmark involves computing |⟨z|C|0n⟩|2 , i.e. the probability of measuring z from the output distribution of C on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomial-time classical algorithm given C can output a string z such that |⟨z|C|0n⟩|2 is substantially larger than 12n (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit C , sampling z from the output distribution of C achieves |⟨z|C|0n⟩|2≈22n on average (Arute et al., 2019).In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomial-time quantum algorithm do substantially better than 22n ? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to C . We show that, for any ε≥1poly(n) , outputting a sample z such that |⟨z|C|0n⟩|2≥2+ε2n on average requires at least Ω(2n/4poly(n)) queries to C , but not more than O(2n/3) queries to C , if C is either a Haar-random n -qubit unitary, or a canonical state preparation oracle for a Haar-random n -qubit state. We also show that when C samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from C is the optimal 1-query algorithm for maximizing |⟨z|C|0n⟩|2 on average.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
Demonstrating quantum advantage requires experimental implementation of a computational task that is hard to achieve using state-of-the-art classical systems. One approach is to perform sampling from a probability distribution associated with a certain class of highly entangled many-body wave functions. It has been suggested that such a quantum advantage can be certified with the (XEB). We critically examine this notion. First, we consider a “benign” setting, where an honest implementation of a noisy quantum circuit is assumed, and characterize the conditions under which the XEB approximates the of quantum dynamics. Second, we assume an “adversarial” setting, where all possible classical algorithms are considered for comparisons, and show that achieving relatively high XEB values does not imply faithful simulation of quantum dynamics. Specifically, we present an efficient classical algorithm that achieves high XEB values, namely 5–12% of those obtained in the state-of-the-art experiments, within just a few seconds using a single GPU machine. This is made possible by identifying and exploiting several vulnerabilities of the XEB, which allows us to achieve high XEB values without simulating a full quantum circuit. Remarkably, our algorithm features with the system size than a noisy quantum device for commonly studied random circuit ensembles in various architecture. We quantitatively explain the success of our algorithm and the limitations of the XEB by using a theoretical framework, in which the dynamics of the average XEB and fidelity are mapped to classical statistical mechanics models. Using this framework, we illustrate the relation between the XEB and the fidelity for quantum circuits in various architectures, with different choices of gate sets, and in the presence of noise. Taken together, our results demonstrate that XEB’s utility as a proxy for fidelity hinges on several conditions, which should be independently checked in the benign setting, but cannot be assumed in the general adversarial setting. Therefore, the XEB on its own has a limited utility as a benchmark for quantum advantage. We briefly discuss potential ways to overcome these limitations. Published by the American Physical Society 2024
We define a canonical version of the recursive Fourier sampling problem from quantum complexity theory, and systematically address a variety of its computational properties, including quantum query complexity, classical randomized query complexity, polynomial degree, and circuit size. Our analysis yields improvements for several of the known upper and lower bounds with regard to these complexity measures.
For quantum query complexity, we define an explicit reduced-query quantum algorithm for the problem, and recursively construct a quantum circuit that implements the algorithm. For classical query complexity, we give new proofs of the known lower bounds that improve the constants, and we give complete proofs of the complexity class separations relative to oracles, that follow from these bounds. For polynomial degree, we construct an exactly representing real polynomial of extremely low degree, and extend it to representations over other Fields. We show that this degree is exactly optimal, even for a 2 weakly-representing polynomial. For circuit size, we construct a small depth-two circuit for the non-recursive version of the problem, and we show that the size is optimal even if the depth is not restricted. We also prove asymptotically matching upper and lower bounds on circuit size for the full recursive version of the problem when the depth is restricted to two.
To prove the tight results for polynomial degree and circuit size we introduce and define a general notion of reduction for both polynomials and circuits that represent boolean functions on a partial domain. We also introduce and define, separately, a new measure of circuit complexity called effort.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model:
(i) (Unbiased) Phase estimation up to a precision ε requires Θ(qε21) queries;
(ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(qε2p(1−p)) queries;
(iii) Search among N items requires Θ(qN) queries;
(iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(qnm) queries.
All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor.
Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a T-query adversary with S qubits of non-uniform advice can recover a random key k from the n-qubit binary phase state ∣ψk⟩∝∑xR(k,x)∣x⟩ with probability at most O(NT2+ST) for N=2n. In contrast, the best known bound for post-quantum one-way functions is O(NT2+ST), with a trivial attack at S=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: n qubits of communication suffice for security against preprocessing attacks with space up to N2 rather than N. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(NT2+NST). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(NS) bound for the pseudorandomness of random binary phase states against space S distinguishers.