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. 1Theoretical 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, 20050 citations

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.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.11952Apr 15, 20260 citations

$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize

Adam Bouland, Andrew Huang, Anand Natarajan +2 more

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$ , resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$ , answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$ , the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$ . While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

quant-pharXiv:2609.25680Sep 23, 20260 citations

Oracles Are Subtle But Not Malicious

Scott Aaronson

Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper 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 first provably 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 nkfor any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size nkwith quantum advice. To our knowledge, this is the first 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 ZPPNPparand even BPPNPparhave linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P = NP. Thus, classes such as ZPPNPparinhabit 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 problemTheoretical computer scientists have been debating the role of oracles since the 1970's. This paper 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 first provably 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 nkfor any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size nkwith quantum advice. To our knowledge, this is the first 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 ZPPNPparand even BPPNPparhave linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P = NP. Thus, classes such as ZPPNPparinhabit 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

IEEE Conference on Computational Complexity (CCC)Aug 8, 200623 citations

Promises should be taken seriously: On relativization with promise problems

David Miloschewsky, Supartha Podder, Dorian Rudolph

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

cs.CCCross-listedarXiv:2609.07945Sep 9, 20260 citations

Oracle Separations in the Fourier Hierarchy

Atul Mantri

The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$ , introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$ , while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$ . We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$ . The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.

quant-pharXiv:2609.11830Sep 11, 20260 citations

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.

\mathsf{BQP} \subseteq \mathsf{IP}

Does Not Relativize

We construct an oracle relative to which

\mathsf{BQP} \not\subseteq \mathsf{IP}

, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between

\mathsf{IP}

and

\mathsf{MIP}

, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions

f

and

g

, the goal is to determine if

f

is correlated with the Fourier spectrum of

g

. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for

\mathsf{BQP}

must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

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

\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}

The Fourier hierarchy

\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots

, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly

\mathrm{BPP}

, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level

k\ge2

. We prove that for every constant

k\ge2

there is an oracle relative to which

\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}

. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level

k

it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from

\mathrm{BQP}

relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with

k

layers is reproduced exactly by an algorithm making only

k-1

rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.