A Separation Between Types of Quantum Oracle Separations

@misc{aaronson2026separation,
  title = {{A Separation Between Types of Quantum Oracle Separations}},
  author = {Scott Aaronson and Adam Bouland and Jordan Docter and Barak Nehoran},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38704},
  eprint = {2609.38704},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38704},
}

TY  - UNPB
TI  - A Separation Between Types of Quantum Oracle Separations
AU  - Scott Aaronson
AU  - Adam Bouland
AU  - Jordan Docter
AU  - Barak Nehoran
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38704
UR  - https://arxiv.org/abs/2609.38704
AB  - 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 complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show 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 PostBQP and PreciseBQP, the exponentially precise variant of BQP. Both classes equal PP in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.
ER  -