{"id":"arxiv/2610.06721","url":"https://arxiv.org/abs/2610.06721","tags":["quant-ph","cs.CR"],"score":0,"title":"Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness","domain":"quant-ph","source":"arxiv","authors":["Keshav Bhateja","Mehdi Esmaili","Atul Mantri"],"reviews":0,"subject":"quant-ph","summary":"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;…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}