6 papers
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…
Quantum Advantage in Tolerant Junta Testing
Avishay Tal, Weiqiang Yuan
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regi…
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…
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
Yuval Filmus, Or Meir, Avishay Tal
HÃ¥stad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of under a random restrictio…
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…