arXiv preprint ·
A Separation Between Types of Quantum Oracle Separations
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
Experimentally Testable Quantum Advantage in Shallow Circuits
Exact $T$-counts of CCZ layers from an isotropy bound
The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.