Sep 2026
A Separation Between Types of Quantum Oracle Separations
The notion of meta-complexity of quantum relativization of oracles is introduced, and it is shown that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes.
S. Aaronson, Adam Bouland, Jordan Docter et al.
· arXiv.org · 0 citations