Preprint
Sep 2026
A Separation Between Types of Quantum Oracle Separations
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum compl...
S. Aaronson, Adam Bouland, Jordan Docter et al.
· 0 citations