5 papers · 1 filter
Certified Randomness without Structure Against Shallow-Query Adversaries
Dakshita Khurana, Bhaskar Roberts, Avishay Tal
In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a code…
Improved Lower Bounds for QAC0
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos +1
In this work, we prove the strongest known lower bounds for QAC, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC circuits cannot…
A Relativizing MIP for BQP
Scott Aaronson, Anand Natarajan, Avishay Tal +1
Complexity class containments involving interactive proof classes are famously nonrelativizing: although , Fortnow and Sipser showed that that there…
On Certified Randomness from Fourier Sampling or Random Circuit Sampling
Roozbeh Bassirian, Adam Bouland, Bill Fefferman +2
Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson (2018, 2020) proposed a novel public certified randomness protoc…
Quantum-Computable One-Way Functions without One-Way Functions
William Kretschmer, Luowen Qian, Avishay Tal
We construct a classical oracle relative to which but quantum-computable quantum-secure trapdoor one-way functions exist. This is a substantial strengthe…