Preprint
Oct 2026
Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness
In the quantum query model, it is shown that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness and proves an earlier conjecture for Haar-random states and extends it to Fourier sampling.
Keshav Bhateja, Mehdi Esmaili, A. Mantri
· 0 citations