Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.07945

Promises should be taken seriously: On relativization with promise problems

David Miloschewsky, Supartha Podder, Dorian Rudolph

cs.CCquant-phSubmitted Sep 7, 2026• Announced Sep 9, 2026• 1 citation
arXivHTMLPDF

Abstract

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}$.

Comments
21 pages, 1 figure

Related papers

BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting

Sevag Gharibian, Jonas Kamminga

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 $Θ(\log n)$ 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 $Ω(\log n)$ 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 $Ω(\log n)$ 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(log n)$ NP queries, then $\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$ contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is quantum.

arXiv:2401.03943•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

Oracles Are Subtle But Not Malicious

Scott Aaronson

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

•Apr 12, 2005•1 citation

A Relativizing MIP for BQP

Scott Aaronson, Anand Natarajan, Avishay Tal +1 more

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ 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 $\mathsf{IP}$ for $\mathsf{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.

quant-pharXiv:2604.11952•Apr 15, 2026•2 citations

P(APP) = P(prBPP)

Philippe Moser

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.

•Jan 1, 2002•0 citations

Classical versus quantum queries in quantum PCPs with classical proofs

Harry Buhrman, François Le Gall, Jordi R. Weggemans

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 ($\mathsf{QCPCP}_{Q,c,s}[q]$). Exploiting a connection with the polynomial method, we prove that for any constant $q$, promise gap $c-s = Ω(1/\text{poly}(n))$ and $δ>0$, we have $\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-δ,1/2+δ}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, where $\mathsf{BQ} \cdot \mathsf{NP}$ is the class of promise problems with quantum reductions to an $\mathsf{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 $\mathsf{QCMA}$, as it is unlikely that $\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{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 $\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]$, 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.

arXiv:2411.00946•Nov 1, 2024•6 citations

A Separation Between Types of Quantum Oracle Separations

Scott Aaronson, Adam Bouland, Jordan Docter +1 more

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.

quant-pharXiv:2609.38704•Oct 1, 2026•0 citations
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 OOO such that PO=BQPO=AWPPO\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^OPO=BQPO=AWPPO, but PromiseBQPO⊈PromiseP/polyO\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}PromiseBQPO⊆PromiseP/polyO​. In particular, BPPO=BQPO\mathsf{BPP}^O = \mathsf{BQP}^OBPPO=BQPO, but PromiseBQPO≠PromiseBPPO\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^OPromiseBQPO=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\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}PPPPP to QCPH⊆BP⋅PP⊆PromiseBPPPP\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}QCPH⊆BP⋅PP⊆PromiseBPPPP. The same proof also shows PPPromiseBQP=PP\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}PPPromiseBQP=PP. Additionally, we show that PromiseBQP\mathsf{PromiseBQP}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\mathsf{AWPP}AWPP and APP\mathsf{APP}APP are low for PP\mathsf{PP}PP, a corresponding promise analogue would collapse the counting hierarchy as GapP⊆FPPromiseAWPP\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}GapP⊆FPPromiseAWPP. This motivates the introduction of PromisePostBQP∗\mathsf{PromisePostBQP^*}PromisePostBQP∗, which restricts PostBQP\mathsf{PostBQP}PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PPPromiseYQP∗=PP\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}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)Θ(n)Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(log⁡n)Θ(\log n)Θ(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 Ω(log⁡n)Ω(\log n)Ω(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 Ω(log⁡n)Ω(\log n)Ω(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)o(log n)o(logn) NP queries, then BPPNP[o(n)]\text{BPP}^{\text{NP}[o(n)]}BPPNP[o(n)] contains a PNP\text{P}^{\text{NP}}PNP-complete problem if the algorithm is classical and FBQPNP[o(n)]\text{FBQP}^{\text{NP}[o(n)]}FBQPNP[o(n)] contains an FPNP\text{FP}^{\text{NP}}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\mathsf{IP} = \mathsf{PSPACE}IP=PSPACE, Fortnow and Sipser showed that that there exists an oracle relative to which coNP⊈IP\mathsf{coNP} \not\subseteq \mathsf{IP}coNP⊆IP. In contrast, the question of whether the containment BQP⊆IP\mathsf{BQP} \subseteq \mathsf{IP}BQP⊆IP is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment BQP⊆MIP\mathsf{BQP} \subseteq \mathsf{MIP}BQP⊆MIP holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle OOO, a PCP\mathsf{PCP}PCP proof system for BQPO\mathsf{BQP}^{O}BQPO where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle OOO. 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\mathsf{IP}IP for BQP\mathsf{BQP}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 qqq quantum queries to a polynomially-sized classical proof (QCPCPQ,c,s[q]\mathsf{QCPCP}_{Q,c,s}[q]QCPCPQ,c,s​[q]). Exploiting a connection with the polynomial method, we prove that for any constant qqq, promise gap c−s=Ω(1/poly(n))c-s = Ω(1/\text{poly}(n))c−s=Ω(1/poly(n)) and δ>0δ>0δ>0, we have QCPCPQ,c,s[q]⊆QCPCP1−δ,1/2+δ[3]⊆BQ⋅NP\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-δ,1/2+δ}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}QCPCPQ,c,s​[q]⊆QCPCP1−δ,1/2+δ​[3]⊆BQ⋅NP, where BQ⋅NP\mathsf{BQ} \cdot \mathsf{NP}BQ⋅NP is the class of promise problems with quantum reductions to an NP\mathsf{NP}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\mathsf{QCMA}QCMA, as it is unlikely that QCMA⊆BQ⋅NP\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{NP}QCMA⊆BQ⋅NP, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer ccc, there exists an oracle relative to which QCPCP[O(log⁡cn)]⊊QCPCPQ[O(log⁡cn)]\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]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\mathsf{PostBQP}PostBQP and PreciseBQP\mathsf{PreciseBQP}PreciseBQP, the exponentially precise variant of BQP\mathsf{BQP}BQP. Both classes equal PP\mathsf{PP}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.