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

Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes…