88 citations · 316 across the 17 of their papers we have counts for
4 papers · 1 filter
Black Hole Radiation Decoding in the Haar Random Oracle Model
Ezekiel Cochran, Atul Mantri
We prove optimal query bounds for recovering a single qubit from black-hole radiation in the Haar random oracle model, when the remaining black hole contains at most one sixteenth…
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…
EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
Atul Mantri
EFI pairs (Brakerski, Canetti, and Qian, ITCS 2023) and one-way puzzles (Khurana and Tomer, STOC 2024) are the leading candidates for the minimal assumption of quantum cryptography…
Oracle Separations in the Fourier Hierarchy
Atul Mantri
The Fourier hierarchy , introduced by Shi (TCS 2005), measures a quantum computation by the number of Hada…