Keshav Bhateja

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

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 sho...