Quantum oracle types shape complexity class separations differently
A Separation Between Types of Quantum Oracle Separations
Computational Complexity
Summary
Some problems in quantum computing involve different categories called complexity classes that describe how hard tasks are. This paper finds that the kind of quantum oracle—or special query tool—used can change whether two classes are considered the same or different. The authors classify various types of quantum oracles and show that some make two particular classes, PostBQP and PreciseBQP, appear equal, while others can separate them. This shows that the details of quantum oracles matter a lot when studying quantum complexity.
What this means in practice
- •For quantum algorithm designers: Recognize when certain oracle models can or cannot separate complexity classes in quantum algorithm studies, influencing both design and analysis.
- •For quantum hardware architects: Inform choices about accessibility of oracle operations such as inverse or conjugate queries, which affect the theoretical power of quantum computations supported.
A theory result. No direct application yet.
Authors
Scott Aaronson, Adam Bouland, Jordan Docter, Barak Nehoran
Abstract
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 $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{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.