⚛️ quantum physics

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

This paper establishes tight quantum query lower bounds for achieving high linear cross-entropy benchmark scores in random circuit sampling, proving that exceeding ideal performance requires $\Omega(N^{1/3})$ queries and certifying nearly optimal smooth min-entropy for outputs, thereby providing rigorous security guarantees for certified randomness against entangled adversaries.

Original authors: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Published 2026-10-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the race to prove that quantum computers can do things impossible for classical machines, scientists have turned to a specific kind of experiment: asking a quantum device to generate a list of random numbers. These numbers are not just any random strings; they are drawn from a complex, invisible pattern created by a random quantum circuit. To check if the device is working correctly, researchers use a scoring system called the linear cross-entropy benchmark. This score measures how often the device picks numbers that the ideal quantum machine would pick most frequently. If the device is honest and working perfectly, it achieves a specific, high score. If it is just guessing randomly, it gets a much lower score. For years, this test has been the gold standard for claiming "quantum advantage," but a critical question remained unanswered: does a high score actually prove the device is generating true, unpredictable randomness? A clever adversary could potentially rig a device to score highly by simply memorizing the most likely answers, making the output predictable even though the score looks good.

A team of researchers at Virginia Tech has now answered this question with mathematical certainty, establishing a strict boundary for what a high score can and cannot certify. They proved that for a quantum device to score even slightly better than the best possible honest machine, it must perform a vast number of internal operations, far more than any efficient classical computer could manage. Specifically, they showed that to exceed the ideal score by a fixed amount, a device needs to make a number of queries proportional to the cube root of the total number of possible outcomes. This result acts as a fundamental limit, similar to a speed limit on a highway, ensuring that no efficient trick can fake a high score. Furthermore, they demonstrated that if a device stays within a tiny margin of this ideal score, its output is genuinely unpredictable. Even if an adversary built the device, shares a secret quantum link with it, and learns the entire setup afterward, they cannot guess the output with any significant accuracy. The device effectively produces nearly the maximum amount of randomness possible, with only a small, unavoidable loss of information.

The researchers arrived at these conclusions by developing a new way to track the "progress" a quantum algorithm makes as it queries an unknown system. Imagine a quantum computer trying to learn the shape of a hidden object by poking it with a probe. The team created a mathematical measure that starts at zero for a device that is simply following the rules honestly. They proved that every time the device makes a query to learn more about the system, this progress measure can only grow by a very small amount. To reach a score that beats the honest machine, the device would need to accumulate enough progress to break through a barrier, but the math shows this requires an impractical number of steps. This method allowed them to close the gap between what was theoretically possible and what was proven necessary, confirming a long-standing guess about the difficulty of faking these results.

Beyond just proving the limits of faking results, the paper also describes a specific algorithm that can actually achieve these high scores, but only by using the maximum allowed number of queries. This "squaring algorithm" works by taking several samples, storing them, and then using a technique called amplitude amplification to boost the probability of finding a match among them. This process effectively squares the probability distribution, favoring the most likely outcomes even more strongly than the honest machine does. The existence of this algorithm proves that the lower bound they found is tight; it is not just a theoretical wall, but a reachable peak that requires a specific, resource-intensive climb. This duality—proving that you cannot fake results easily, but also showing exactly how hard it is to win legitimately—provides a complete picture of the landscape.

The implications for certified randomness are profound. In many security applications, we need to generate random numbers that even the person who built the generator cannot predict. The study confirms that if a quantum device passes the standard test with a score very close to the ideal, it is generating a string of bits that contains almost as much randomness as the length of the string itself. For a device working with sixty qubits, which can produce strings of sixty bits, a near-perfect score guarantees that the output contains roughly fifty-four bits of true, certified randomness. This holds true even against an adversary who might be entangled with the device and knows every detail of its construction. The only information lost is a small amount related to the number of queries the device makes, which is negligible for practical purposes.

This work also extends to other types of quantum sampling, including those used in photonic experiments with light particles. The researchers showed that the same rules apply: to beat the ideal score, a device must perform a specific, large number of operations, and to stay near the ideal score, it must produce genuine randomness. They even connected these findings to a different problem: creating a "collision distribution," where the device is asked to output pairs of numbers that are more likely to be the same. They found that generating this specific type of distribution also requires the same cube-root number of queries, linking these seemingly different tasks under a single mathematical law.

The study does not claim that current quantum computers are already perfect at this. Real-world devices often score much lower than the ideal due to noise and errors. However, the paper establishes the theoretical ceiling and floor for what is possible. It tells us that if we ever see a device scoring near the top, we can trust that it is doing something genuinely quantum and producing real randomness. Conversely, if a device claims to be generating randomness but cannot reach this score without an unreasonable number of steps, we know it is not doing what it claims. The research provides the rigorous foundation needed to move from experimental demonstrations to reliable, certified quantum randomness, ensuring that the future of quantum security rests on solid, proven ground.

Technical Summary: Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Problem Statement
Random circuit sampling experiments are the leading demonstrations of quantum computational advantage, typically verified using the linear cross-entropy benchmark (XEB). The XEB score measures how well a device's output distribution aligns with the ideal distribution $p$ by calculating the average of $N p(z)$ for the returned strings $z$ , where $N=2^n$ . While a high score suggests quantum advantage, it does not inherently certify that the device sampled from $p$ or that the output is random. A device could achieve a high score by deterministically outputting the most likely string (which an adversary might know), thereby failing to produce certified randomness.

This paper addresses two fundamental questions in the quantum query model:

Score Limits: How high can an efficient quantum device score relative to the ideal score? Specifically, can an efficient device exceed the ideal score by a constant?
Randomness Certification: If a device achieves a score near the ideal, how much smooth min-entropy (certified randomness) does its output contain, even against an adversary (Eve) who may be entangled with the device and learns the oracle (the circuit or function) afterward?

Methodology
The authors work in the query model, where the circuit is replaced by an oracle drawn from a known ensemble. They analyze two specific ensembles:

Fourier Sampling: The oracle is a uniformly random function $f: \{0,1\}^n \to \{\pm 1\}$ . The honest sampler scores approximately 3.
Haar-Random States: The oracle hides a uniformly random unit vector $|\phi\rangle$ (accessed via a canonical state-preparation oracle or Haar-random unitary access). The honest sampler scores approximately 2.

The core methodology involves defining a progress measure $\lambda$ that quantifies the deviation of a device's state from the "honest" state (which makes a single query). The analysis follows a three-step framework:

Score Bound: The expected score $B(A)$ is bounded in terms of the progress measure: $B(A) \leq \text{Ideal Score} + O(\lambda + \lambda^2)$ .
Growth Bound: It is shown that each query increases $\lambda$ by only $O(\sqrt{(t+1)/N})$ , where $t$ is the number of previous queries. Consequently, after $q$ queries, $\lambda = O(q^{3/2}/\sqrt{N})$ .
Randomness Extraction: For devices with scores near the ideal (small deficit $\delta$ ), the proof of the score bound is refined to show that the device's output branches are close to specific auxiliary vectors. These vectors are generated by operators acting solely on the device, with norms bounded by $\text{poly}(q)\sqrt{p(z)}$ . This structure implies that Eve's ability to guess the output is limited, even if she knows the oracle.

Key Contributions and Results

1. Tight Lower Bounds for Exceeding the Ideal Score
The paper establishes that the ideal score acts as a "Tsirelson bound" for efficient quantum devices in these sampling tasks.

Query Complexity: To exceed the ideal score by a constant $\epsilon$ $ϵ$ , a quantum algorithm requires $\Omega(N^{1/3})$ $Ω (N^{1/3})$ queries.
- For Fourier sampling, an expected score of $3 + \epsilon$ requires $q \geq \Omega(N^{1/3})$ .
- For Haar-random states, an expected score of $2 + \epsilon$ requires $q \geq \Omega(N^{1/3})$ .
Upper Bounds: The authors confirm that $O(N^{1/3})$ queries are sufficient to exceed the ideal score by a constant using a "squaring algorithm" (a variant of the collision-finding algorithm). This algorithm stores $m \approx N^{1/3}$ ideal samples and uses amplitude amplification to bias the output toward the square of the ideal distribution, $p(z)^2$ .
Tightness: These bounds are tight; the gap between the honest sampler (1 query) and the ability to significantly exceed the ideal score is exactly characterized by the $N^{1/3}$ threshold.

2. Certified Randomness at the Ideal Score
The paper proves that a device making polynomially many queries and achieving a score within $o(1)$ of the ideal score produces output with nearly maximal randomness.

Min-Entropy: For both Fourier sampling and Haar-random states (via the canonical oracle), the output $Z$ has smooth min-entropy $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$ , where $R$ is the oracle and $E$ is Eve's register.
Adversarial Model: This holds even if Eve is entangled with the device and learns the full description of the oracle (the function $f$ or the vector $\phi$ ) after the device outputs $Z$ .
Parameters: The smoothing parameter $\eta$ scales as $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$ . If the deficit $\delta$ is negligible and $q$ is polynomial in $n$ , the smoothing is negligible, certifying $n - O(\log n)$ bits of randomness.
Optimality: The $O(\log n)$ loss is shown to be nearly optimal. The paper constructs devices using amplitude amplification that achieve near-ideal scores but restrict the output to a known set of size $N/q^2$ , limiting the min-entropy to $n - 2\log q$ .

3. Additional Results

Collision Distribution: The paper shows that sampling the collision distribution (proportional to $p(z)^2$ ) has a query complexity of $\Theta(N^{1/3})$ .
Quantum Hadamard Products: A coherent version of the squaring algorithm is presented to prepare the quantum Hadamard product of two states with uniform amplitude magnitudes. This algorithm achieves a trace distance error of $O(N^{-1/6})$ using $O(N^{1/3})$ queries, improving upon the $\sqrt{N}$ queries required by standard amplitude amplification.

Significance and Claims
The paper claims to provide unconditional, information-theoretic guarantees for quantum sampling tasks, resolving open questions regarding the "quantum supremacy Tsirelson inequality."

Analogy to CHSH: The results draw a direct parallel to the CHSH game. Just as Tsirelson's bound ( $\cos^2(\pi/8)$ ) limits the winning probability of quantum strategies and certifies randomness at that bound, the ideal XEB score limits the performance of efficient quantum samplers and certifies randomness near that score.
Unconditional Security: Unlike previous results that relied on computational hardness assumptions or restricted the adversary's knowledge (e.g., not learning the full oracle), this work provides unconditional bounds against an adversary who learns the oracle and holds arbitrary entanglement.
Limitations: The authors note that their results apply to the oracle model. For real-world devices (like those in [AAB+19]), the scores are currently far from the ideal (e.g., 1.002 vs. 2), meaning the current guarantees for certified randomness in experimental settings rely on different, weaker assumptions (e.g., [AH23]). Furthermore, for Haar-random states, the result requires the canonical state-preparation oracle rather than full unitary access, as an adversary learning a full Haar-random unitary could potentially correlate outputs with the unitary's columns.

In summary, the paper rigorously defines the limits of efficient quantum sampling, proving that the ideal score is a hard barrier for efficient devices and that approaching this barrier certifies nearly all possible randomness, even against powerful quantum adversaries.

More like this