Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness
Abstract
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(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 Θ(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.
Related
- Metasurface quantum graphs for polarization-independent certified randomness
- Certified Randomness Generation against Quantum Adversaries via Energy Constraints
- Randomness can be certified in energy-constrained semi-device-independent scenarios
- Classical Verification of a Remote Quantum Processor via Degenerate Concordant Computations: An Application to Randomness Generation
- Unconditional Certified Randomness without Structure
BibTeX
@misc{bhateja2026tight,
title = {{Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness}},
author = {Keshav Bhateja and Mehdi Esmaili and Atul Mantri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06721},
eprint = {2610.06721},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06721},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness
AU - Keshav Bhateja
AU - Mehdi Esmaili
AU - Atul Mantri
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06721
UR - https://arxiv.org/abs/2610.06721
AB - 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.
ER -