Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries.
Our first result separates the language and promise settings. Namely, we construct an oracle $O$ such that $\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^O$, but $\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}$. In particular, $\mathsf{BPP}^O = \mathsf{BQP}^O$, but $\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^O$, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from $\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$ to $\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}$. The same proof also shows $\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}$. Additionally, we show that $\mathsf{PromiseBQP}$, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although $\mathsf{AWPP}$ and $\mathsf{APP}$ are low for $\mathsf{PP}$, a corresponding promise analogue would collapse the counting hierarchy as $\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}$. This motivates the introduction of $\mathsf{PromisePostBQP^*}$, which restricts $\mathsf{PostBQP}$ to input-indepencent postselection. By showing that it is low for \PP, we obtain $\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}$.
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries.
Our first result separates the language and promise settings. Namely, we construct an oracle O such that PO=BQPO=AWPPO, but PromiseBQPO⊆PromiseP/polyO. In particular, BPPO=BQPO, but PromiseBQPO=PromiseBPPO, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from PPPPP to QCPH⊆BP⋅PP⊆PromiseBPPPP. The same proof also shows PPPromiseBQP=PP. Additionally, we show that PromiseBQP, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although AWPP and APP are low for PP, a corresponding promise analogue would collapse the counting hierarchy as GapP⊆FPPromiseAWPP. This motivates the introduction of PromisePostBQP∗, which restricts PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PPPromiseYQP∗=PP.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.
Theoretical computer scientists have been debating the role of oracles since the 1970's. This pa-per illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems. First, we give an oracle relative to which PP has linear-sized circuits, by proving a new lower bound for perceptrons and low-degree threshold polynomials. This oracle settles a longstanding open question, and generalizes earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More importantly, it implies the rst nonrelativizing separation of \\traditional " complexity classes, as opposed to interactive proof classes such as MIP and MAEXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does not have circuits of size nk for any xed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size nk with quantum advice. To our knowledge, this is the rst nontrivial lower bound on quantum circuit size. Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean circuits in ZPPNP. We show that the NP queries in this algorithm cannot be parallelized by any relativizing technique, by giving an oracle relative to which ZPPNPjj and even BPP NP jj have linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P = NP. Thus, classes such as ZPPNPjj inhabit a \\twilight zone, " where we need to distinguish between relativizing and black-box techniques. Our results on this subject have implications for computational learning theory as well as for the circuit minimization problem. 1
Complexity class containments involving interactive proof classes are famously nonrelativizing: although IP=PSPACE, Fortnow and Sipser showed that that there exists an oracle relative to which coNP⊆IP. In contrast, the question of whether the containment BQP⊆IP is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment BQP⊆MIP holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle O, a PCP proof system for BQPO where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle O. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an IP for BQP in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.
We show that for deterministic polynomial time computations, oracle access to
APP, the class of real functions
approximable by probabilistic Turing machines, is the same as having oracle access to
promise-BPP. First,
we construct a mapping that maps every function in APP to a promise problem
in prBPP, and that preserves completeness, i.e. maps complete functions to complete promise problems.
Next, we construct
a mapping from
prBPP into APP, that maps every promise problem to a function
in APP, and which preserves completeness.
Then, we prove that PAPP=PprBPP.
Finally, we use our results to simplify proofs of important results on APP, such as
the APP-completeness of the function fCAPP,
which approximates the acceptance
probability of a Boolean circuit, the error probability reduction Theorem
for APP functions, and the conditional derandomization result
APP=AP iff prBPP is easy.
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for q quantum queries to a polynomially-sized classical proof (QCPCPQ,c,s[q]). Exploiting a connection with the polynomial method, we prove that for any constant q, promise gap c−s=Ω(1/poly(n)) and δ>0, we have QCPCPQ,c,s[q]⊆QCPCP1−δ,1/2+δ[3]⊆BQ⋅NP, where BQ⋅NP is the class of promise problems with quantum reductions to an NP-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for QCMA, as it is unlikely that QCMA⊆BQ⋅NP, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer c, there exists an oracle relative to which QCPCP[O(logcn)]⊊QCPCPQ[O(logcn)], contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.
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.