extfieldsofstudy:
Computer Science
Physics

text:
The Acrobatics of BQP

One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$. Specifically: -There exists an oracle relative to which $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{QCMA}$. -Conversely, there exists an oracle relative to which $\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$. -Relative to a random oracle, $\mathsf{PP}=\mathsf{PostBQP}$ is not contained in the"$\mathsf{QMA}$ hierarchy"$\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$. -Relative to a random oracle, $\mathsf{\Sigma}_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsf{\Sigma}_{k}^\mathsf{P}}$ for every $k$. -There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\# P}}$ and yet $\mathsf{PH}$ is infinite. -There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which $\mathsf{BQP}\not \subset \mathsf{PH}$, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a"quantum-aware"version of the random restriction method, a concentration theorem for the block sensitivity of $\mathsf{AC^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

Introduction
The complexity-theoretic study of quantum computation is often dated from 1993, when Bernstein and Vazirani [BV97] defined BQP, or Bounded-Error Quantum Polynomial-Time: the class of languages that admit efficient quantum algorithms. Then as now, a central concern was how BQP relates to classical complexity classes, such as P, NP, and PH. Among the countless questions that one could raise here, let us single out three as especially fundamental: (1) Can quantum computers efficiently solve any problems that classical computers cannot? In other words, does BPP = BQP?
(2) Can quantum computers solve NP-complete problems in polynomial time? In other words, is NP ⊆ BQP?
(3) What is the best classical upper bound on the power of quantum computation? Is BQP ⊆ NP? Is BQP ⊆ PH?
Three decades later, all three of these still stand as defining questions of the field. Nevertheless, from the early 2000s onwards, it became rare for work in quantum computing theory to address any of these questions directly, perhaps simply because it became too hard to say anything new about them. A major recent exception was the seminal work of Raz and Tal [RT19], who gave an oracle relative to which BQP ⊂ PH, by completing a program proposed by one of us [Aar10]. In this paper, we take the Raz-Tal breakthrough as a starting point. Using it, together with new tools that we develop, we manage to prove many new theorems about the power of BQP-at least in the black-box setting where much of our knowledge of quantum algorithms resides.
Before discussing the black-box setting or Raz-Tal, though, let's start by reviewing what is known in general about BQP. Bernstein and Vazirani [BV97] showed that BPP ⊆ BQP ⊆ P #P , and Adleman, DeMarrais, and Huang [ADH97] improved the upper bound to BQP ⊆ PP, giving us the following chain of inclusions: Fortnow and Rogers [FR98] slightly strengthened the inclusion BQP ⊆ PP, to show for example that PP BQP = PP. This complemented the result of Bennett, Bernstein, Brassard, and Vazirani [BBBV97] that BQP BQP = BQP: that is, BQP is "self-low," or "the BQP hierarchy collapses to BQP."

The Contrast with BPP
Meanwhile, though, the relationships between BQP and complexity classes like NP, PH, and P/poly have remained mysterious. Besides the fundamental questions mentioned above-is NP ⊆ BQP? is BQP ⊆ NP? is BQP ⊆ PH?-one could ask other questions: (i) In a 2005 blog post, Fortnow [For05] raised the question of whether NP BQP ⊆ BQP NP . Do we even have NP BQP ⊆ BQP PH ? I.e., when quantum computation is combined with classical nondeterminism, how does the order of combination matter?
(iii) Suppose NP ⊆ BQP. Does it follow that PH ⊆ BQP as well?
(iv) Suppose NP ⊆ BQP. Does it follow that PH collapses?
(vi) Suppose P = NP. Does it follow that BQP is "small" (say, not equal to EXP)?
(vii) Suppose P = NP. Does it follow that BQP = QCMA, where QCMA (Quantum Classical Merlin Arthur) is the analogue of NP with a BQP verifier?
What is particularly noteworthy about the questions above is that, if we replace BQP by BPP, then positive answers are known to all of them: (ii) BPP NP ⊆ PH = PH BPP .
(iii) If NP ⊆ BPP, then PH = BPP-this is sometimes given as a homework exercise in complexity theory courses, and also follows from (i).
(v) BPP ⊂ P/poly is Adleman's Theorem [Adl78]. So what is it that distinguishes BPP from BQP in these cases? In all of the above examples, the answer turns out to be one of the fundamental properties of classical randomized algorithms: namely, that one can always "pull the randomness out" from such algorithms, viewing them as simply deterministic algorithms that take a uniform random string r as an auxiliary input, in addition to their "main" input x. This, in turn, enables one to play all sorts of tricks with such an algorithm M (x, r)-from using approximate counting to estimate the fraction of r's that cause M (x, r) to accept, to moving r from inside to outside a quantifier, to hardwiring r as advice. By contrast, there is no analogous notion of "pulling the randomness (or quantumness) out of a quantum algorithm." In quantum computation, randomness is just an intrinsic part of the model that rears its head at the end (rather than the beginning) of a computation, when we take the squared absolute values of amplitudes to get probabilities.
This difference between randomized and quantum algorithms is crucial to the analysis of the so-called "sampling-based quantum supremacy experiments"-for example, those recently carried out by Google [AAB + 19] and USTC [ZWD + 20]. The theoretical foundations of these experiments were laid a decade ago, in the work of Aaronson and Arkhipov [AA13] on BosonSampling, and (independently) Bremner, Jozsa, and Shepherd [BJS10] on the commuting Hamiltonians or IQP model. Roughly speaking, the idea is that, by using a quantum computer, one can efficiently sample a probability distribution D over n-bit strings such that even estimating the probabilities of the outcomes is a #P-hard problem. Meanwhile, though, if there were a polynomial-time classical randomized algorithm M (x, r) to sample from the same distribution D, then one could use the "pulling out r" trick to estimate the probabilities of M 's outcomes in PH. But this would put P #P into PH, thereby collapsing PH by Toda's Theorem [Tod91].
More generally, with any of the apparent differences between quantum algorithms and classical randomized algorithms, the question is: how can we prove that the difference is genuine, that no trick will ever be discovered that makes BQP behave more like BPP? For questions like whether NP ⊆ BQP or whether BQP ⊆ NP, the hard truth here is that not only have we been unable to resolve these questions in the unrelativized world, we've been able to say little more about them than certain "obvious" implications. For example, suppose NP ⊆ BQP and BQP ⊆ AM. Then since BQP is closed under complement, we would also have coNP ⊆ BQP, and hence coNP ⊆ AM, which is known to imply a collapse of PH [BHZ87]. And thus, if PH is infinite, then either NP ⊂ BQP or BQP ⊂ AM. How can we say anything more interesting and nontrivial?

Relativization
Since the work of Baker, Gill, and Solovay [BGS75], whenever complexity theorists were faced with an impasse like the one above, a central tool has been relativized or black-box complexity: in other words, studying what happens when all the complexity classes one cares about are fed some speciallyconstructed oracle. Much like perturbation theory in physics, relativization lets us make well-defined progress even when the original questions we wanted to answer are out of reach. It is well-known that relativization is an imperfect tool-the IP = PSPACE [Sha92], MIP = NEXP [BFL91], and more recently, MIP * = RE [JNV + 20] theorems provide famous examples where complexity classes turned out to be equal, even in the teeth of oracles relative to which they were unequal. On the other hand, so far, almost all such examples have originated from a single source: namely, the use of algebraic techniques in interactive proof systems. And if, for example, we want to understand the consequences of NP ⊆ BQP, then arguably it makes little sense to search for nonrelativizing consequences if we don't even understand yet what the relativizing consequences (that is, the consequences that hold relative to all oracles) are or are not.
In quantum complexity theory, even more than in classical complexity theory, relativization has been an inextricable part of progress from the very beginning. The likely explanation is that, even when we just count queries to an oracle, in the quantum setting we need to consider algorithms that query all oracle bits in superposition-so that even in the most basic scenarios, it is already unintuitive what can and cannot be done, and so oracle results must do much more than formalize the obvious.
More concretely, Bernstein and Vazirani [BV97] introduced some of the basic techniques of quantum algorithms in order to prove, for the first time, that there exists an oracle A such that BPP A = BQP A . Shortly afterward, Simon [Sim97] gave a quantitatively stronger oracle separation between BPP and BQP, and then Shor [Sho97] gave a still stronger separation, along the way to his famous discovery that Factoring is in BQP.
On the negative side, Bennett, Bernstein, Brassard, and Vazirani [BBBV97] showed that there exists an oracle relative to which NP ⊂ BQP: indeed, relative to which there are problems that take n time for an NP machine but Ω 2 n/2 time for a BQP machine. Following the discovery of Grover's algorithm [Gro96], which quantumly searches any list of N items in O √ N queries, the result of Bennett, Bernstein, Brassard, and Vazirani gained the interpretation that Grover's algorithm is optimal. In other words, any quantum algorithm for NP-complete problems that gets more than the square-root speedup of Grover's algorithm must be "non-black-box." It must exploit the structure of a particular NP-complete problem much like a classical algorithm would have to, rather than treating the problem as just an abstract space of 2 n possible solutions.
Meanwhile, clearly there are oracles relative to which P = BQP-for example, a PSPACE-complete oracle. But we can ask: would such oracles necessarily collapse the hierarchy of classical complexity classes as well? In a prescient result that provided an early example of the sort of thing we do in this paper, Fortnow and Rogers [FR98] showed that there exists an oracle relative to which P = BQP and yet PH is infinite. In other words, if P = BQP would imply a collapse of the polynomial hierarchy, then it cannot be for a relativizing reason. Aaronson and Chen [AC17] extended this to show that there exists an oracle relative to which sampling-based quantum supremacy is impossible-i.e., any probability distribution approximately samplable in quantum polynomial time is also approximately samplable in classical polynomial time-and yet PH is infinite. In other words, if it is possible to prove the central theoretical conjecture of quantum supremacy-namely, that there are noisy quantum sampling experiments that cannot be simulated in classical polynomial time unless PH collapses-then nonrelativizing techniques will be needed there as well.
What about showing the power of BQP, by giving oracle obstructions to containments like BQP ⊆ NP, or BQP ⊆ PH? There, until recently, the progress was much more limited. Watrous [Wat00] showed that there exists an oracle relative to which BQP ⊂ NP and even BQP ⊂ MA (these separations could also have been shown using the Recursive Fourier Sampling problem, introduced by Bernstein and Vazirani [BV97]). But extending this further, to get an oracle relative to which BQP ⊂ PH or even BQP ⊂ AM, remained an open problem for two decades. Aaronson [Aar10] proposed a program for proving an oracle separation between BQP and PH, involving a new problem he introduced called Forrelation: Problem 1 (Forrelation). Given black-box access to two Boolean functions f, g : {0, 1} n → {1, −1}, and promised that either (i) f and g are uniformly random and independent, or (ii) f and g are uniformly random individually, but g has Ω(1) correlation withf , the Boolean Fourier transform of f (i.e., f and g are "Forrelated"), decide which.
Aaronson [Aar10] showed that Forrelation is solvable, with constant bias, using only a single quantum query to f and g (and O(n) time). By contrast, he showed that any classical randomized algorithm for the problem needs Ω 2 n/4 queries-improved by Aaronson and Ambainis [AA18] to Ω 2 n/2 n queries, which is essentially tight. The central conjecture, which Aaronson left open, said that Forrelation ∈ PH-or equivalently, by the connection between PH machines and AC 0 circuits [FSS84], that there are no AC 0 circuits for Forrelation of constant depth and 2 poly(n) size.
Finally, Raz and Tal [RT19] managed to prove Aaronson's conjecture, and thereby obtain the long-sought oracle separation between BQP and PH. 1 Raz and Tal achieved this by introducing new techniques for constant-depth circuit lower bounds, involving Brownian motion and the L 1 -weight of the low-order Fourier coefficients of AC 0 functions. Relevantly for us, Raz and Tal actually proved the following stronger result: Theorem 2 ([RT19]). A PH machine can guess whether f and g are uniform or Forrelated with bias at most 2 −Ω(n) .
Recall that before Raz and Tal, we did not even have an oracle relative to which BQP ⊂ AM. Notice that, if BQP ⊆ AM, then many other conclusions would follow in a relativizing way. For example, we would have: • P = NP implies P = BQP, • If NP ⊆ BQP, then NP NP ⊆ NP BQP ⊆ BQP NP = BQP BQP = BQP, and • If NP ⊆ BQP, then NP ⊆ coAM, which implies that PH collapses.
Looking at it a different way, our inability even to separate BQP from AM by an oracle served as an obstruction to numerous other oracle separations.
The starting point of this paper was the following question: in a "post-Raz-Tal world," can we at last completely "unshackle" BQP from P, NP, and PH, by showing that there are no relativizing obstructions to any possible answers to questions like the ones we asked in Section 1.1?

Our Results
We achieve new oracle separations that show an astonishing range of possible behaviors for BQP and related complexity classes-in at least one case, resolving a longstanding open problem in this topic. Our title, "The Acrobatics of BQP," comes from a unifying theme of the new results being "freedom." We will show that, as far as relativizing techniques can detect, collapses and separations of classical complexity classes place surprisingly few constraints on the power of quantum computation. In most cases, this can be understood as ultimately stemming from the fact that one cannot "fix the randomness" (or quantumness) used by a quantum algorithm, similarly to how one fixes the randomness used by a randomized algorithm in many complexity-theoretic arguments.
As we alluded to earlier, many of our new results would not have been possible without Raz and Tal's analysis of Forrelation [RT19], which we rely on extensively. We will treat Forrelation no longer as just an isolated problem, but as a sort of cryptographic code, by which an oracle can systematically make certain information available to BQP machines while keeping the information hidden from classical machines.
Having said that, very few of our results will follow from Raz-Tal in any straightforward way. Most often we need to develop other lower bound tools, in addition to or instead of Raz-Tal. Our new tools, which seem likely to be of independent interest, include a random restriction lemma for quantum query algorithms, a concentration theorem for the block sensitivity of AC 0 functions, and a provable analogue of the Aaronson-Ambainis conjecture [AA14] for certain sparse oracles.
Perhaps our single most interesting result is the following.
As mentioned earlier, Theorem 3 resolves an open problem of Fortnow [For05], and demonstrates a clear difference between BPP and BQP that exemplifies the impossibility of pulling the randomness out of a quantum algorithm. Indeed, Theorem 3 shows that there is no general, black-box way to move quantumness past an NP quantifier, like we can do for classical randomness.
As a straightforward byproduct of Theorem 3, we are also able to prove the following: Theorem 4 (Corollary 50, restated). There exists an oracle relative to which P = NP but BQP = QCMA.
Conversely, it will follow from one of our later results, Theorem 9, that there exists an oracle relative to which P = NP and yet BQP = QCMA = QMA. In other words, as far as relativizing techniques are concerned, the classical and quantum versions of the P vs. NP question are completely uncoupled from one another.
Theorem 3 also represents progress toward a proof of the following conjecture, which might be the most alluring open problem that we leave.
Conjecture 5. There exists an oracle relative to which NP ⊆ BQP but PH ⊂ BQP. 2 Indeed, for every k ∈ N, there exists an oracle relative to which Σ P k ⊆ BQP but Σ P k+1 ⊂ BQP. Conjecture 5 would provide spectacularly fine control over the relationship between BQP and PH, going far beyond Raz-Tal to show how BQP could, e.g., swallow the first 18 levels of PH without swallowing the 19th. To see the connection between Theorem 3 and Conjecture 5, suppose NP BQP ⊆ BQP NP , and suppose also that NP ⊆ BQP. Then, as observed by Fortnow [For05], this would imply (and so on, for all higher levels of PH), so that PH ⊆ BQP as well. Hence, any oracle that witnesses Conjecture 5 also witnesses Theorem 3, so our proof of Theorem 3 is indeed a prerequisite to Conjecture 5. At a high level, we prove Theorem 3 by showing that no BQP PH machine can solve the OR • Forrelation problem, in which one is given a long list of Forrelation instances, and is tasked with distinguishing whether (1) all of the instances are uniformly random, or (2) at least one of the instances is Forrelated. A first intuition is that PH machines should gain no useful information from the input, just because Forrelation "looks random" (by Raz-Tal), and hence a BQP PH machine should have roughly the same power as a BQP machine at deciding OR • Forrelation. If one could show this, then completing the theorem would amount to showing that OR•Forrelation is hard for BQP machines, which easily follows from the BBBV Theorem [BBBV97].
Alas, initial attempts to formalize this intuition fail for a single, crucial reason: the possibility of homomorphic encryption! The Raz-Tal Theorem merely proves that Forrelation is a strong form of encryption against PH algorithms. But to rule out a BQP PH algorithm for OR • Forrelation, we also have to show that one cannot take a collection of Forrelation instances and transform them, by means computable in PH, into a single Forrelation instance whose solution is the OR of the solutions to the input instances. Put another way, we must show that AC 0 circuits of constant depth and 2 poly(n) size cannot homomorphically evaluate the OR function, when the encryption is done via the Forrelation problem.
More generally, we even have to show that AC 0 circuits cannot transform the "ciphertext" into any string that could later be decoded by an efficient quantum algorithm. Theorem 3 accomplishes this with the help of an additional structural property of AC 0 circuits: our concentration theorem for block sensitivity. Loosely speaking, the concentration theorem implies that, with overwhelming probability, any small AC 0 circuit is insensitive to toggling between a yes-instance and a neighboring no-instance of the OR • Forrelation problem. This, together with the BBBV Theorem [BBBV97], then implies that such "homomorphic encryption" is impossible.
We also achieve the following converse to Theorem 3: Theorem 6 (Corollary 57, restated). There exists an oracle relative to which BQP NP ⊂ PH BQP , and even BQP NP ⊂ PH PromiseBQP .
Note that an oracle relative to which BQP NP ⊂ NP BQP is almost trivial to achieve, for example by considering a problem in coNP. However, BQP NP ⊂ PH BQP is much harder. At a high level, rather than considering the composed problem OR • Forrelation, we now need to consider the reverse composition: Forrelation • OR, a problem that's clearly in BQP NP , but plausibly not in PH BQP . The key step is to show that, when solving Forrelation • OR, any PH BQP machine can be simulated by a PH machine: the BQP oracle is completely superfluous! Once we've shown that, Forrelation • OR ∈ PH then follows immediately from Raz-Tal.
For our next result, recall that QMA, or Quantum Merlin-Arthur, is the class of problems for which a yes-answer can be witnessed by a polynomial-size quantum state. Perhaps our second most interesting result is this: Theorem 7 (Corollary 71, restated). PP is not contained in the "QMA hierarchy", consisting of constant-depth towers of the form QMA QMA QMA ··· , with probability 1 relative to a random oracle. 3 Note that PP = PostBQP, where PostBQP denotes BQP augmented with the power of postselection [Aar05], and so Theorem 7 contrasts with the classical containment PostBPP ⊆ BPP NP ⊆ PH [HHT97,Kup15]. Nevertheless, before this paper, to our knowledge, it was not even known how to construct an oracle relative to which PP ⊂ BQP NP , let alone classes like BQP NP BQP NP ··· or QCMA QCMA QCMA ··· , which are contained in the QMA hierarchy. The closest result we are aware of is due to Kretschmer [Kre21], who gave a quantum oracle relative to which BQP = QMA = PostBQP.
Perhaps shockingly, our proof of Theorem 7 can be extended even to show that PP is not in, say, QMIP QMIP QMIP ··· relative to a random oracle, where QMIP means Quantum Multi-prover Interactive Proofs with entangled provers. This is despite the breakthrough results of Reichardt, Unger, and Vazirani [RUV13], and more recently Ji, Natarajan, Vidick, Wright, and Yuen [JNV + 20], which showed that in the unrelativized world, QMIP = MIP * = RE (where MIP * means QMIP with classical communication only, and RE means Recursively Enumerable), so in particular, QMIP contains the halting problem. This underscores the dramatic extent to which results like QMIP = RE are nonrelativizing! Theorem 7 can also be understood as showing that in the black-box setting, there is no quantum analogue of Stockmeyer's approximate counting algorithm [Sto83]. For a probabilistic algorithm M that runs in poly(n) time and an error bound ε ≥ 1 poly(n) , the approximate counting problem is to estimate the acceptance probability of M up to a multiplicative factor of 1 + ε. Stockmeyer's algorithm [Sto83] gives a relativizing poly(n)-time reduction from the approximate counting problem to a problem in the third level of the polynomial hierarchy, and crucially relies on pulling the randomness out of M . In structural complexity terms, Stockmeyer's algorithm can be reinterpreted as showing that SBP ⊆ PH relative to all oracles, where SBP is the complexity class defined in [BGM06] that captures approximate counting.
One might wonder: is there a version of Stockmeyer's algorithm for the quantum approximate counting problem, where we instead wish to approximate the acceptance probability of a quantum algorithm? In particular, is SBQP, the complexity class that captures quantum approximate counting [Kup15], contained in the QMA hierarchy? 4 Kuperberg [Kup15] showed that PP ⊆ P SBQP , so it follows that PP ⊆ QMAH if and only if SBQP ⊆ QMAH, where QMAH denotes the QMA hierarchy. Thus, Theorem 7 implies that SBQP ⊂ QMAH relative to a random oracle, implying that such a quantum analogue of Stockmeyer's algorithm does not exist in the black-box setting. 5 This demonstrates yet another case where a classical complexity result that relies on fixing randomness cannot be generalized to the quantum setting.
3 Actually, our formal definition of the QMA hierarchy is more general than the version given here, in order to accommodate recursive queries to QMA promise problems. This only makes our separation stronger. See Section 2.2 for details. 4 We thank Patrick Rall (personal communication) for bringing this question to our attention. 5 Note that this is just one of many possible ways that we could ask whether there exists a quantum analogue of Stockmeyer's algorithm. For example, one might consider alternative definitions of the quantum approximate counting task, such as the problem defined in [BCGW21] of approximating the number of witness states accepted by a QMA verifier. One might also consider other definitions of the "quantum polynomial hierarchy," some of which are explored in [GSS + 18].
Notably, our proof of Theorem 7 does not appeal to Raz-Tal at all, but instead relies on a new random restriction lemma for the acceptance probabilities of quantum query algorithms. Our random restriction lemma shows that if one randomly fixes most of the inputs to a quantum query algorithm, then the algorithm's behavior on the unrestricted inputs can be approximated by a "simple" function (say, a small decision tree or small DNF formula). We then use this random restriction lemma to generalize the usual random restriction proof that, for example, Parity ∈ AC 0 [Hås87].
Here is another noteworthy result that we are able to obtain, by combining random restriction arguments with lower bounds on quantum query complexity: Theorem 8 (Corollary 41, restated). For every k ∈ N, Σ P k+1 ⊂ BQP Σ P k with probability 1 relative to a random oracle.
Theorem 8 extends the breakthrough of Håstad, Rossman, Servedio, and Tan [HRST17], who (solving an open problem from the 1980s) showed that PH is infinite relative to a random oracle with probability 1. Our result shows, not only that a random oracle creates a gap between every two successive levels of PH, but that quantum computing fails to bridge that gap.
Again, Theorem 8 represents a necessary step toward a proof of Conjecture 5, because if we had Our last two theorems return to the theme of the autonomy of BQP.
Theorem 9 (Theorem 29, restated). There exists an oracle relative to which NP ⊆ BQP, and indeed BQP = P #P , and yet PH is infinite.
For three decades, one of the great questions of quantum computation has been whether it can solve NP-complete problems in polynomial time. Many experts guess that the answer is no, for similar reasons as they guess that P = NP-say, the BBBV Theorem [BBBV97], combined with our failure to find any promising leads for evading that theorem's assumptions in the worst case. But the fact remains that we have no structural evidence connecting the NP ⊂ BQP conjecture to any "pre-quantum" beliefs about complexity classes. No one has any idea how to show, for example, that if NP ⊆ BQP then P = NP as well, or anything even remotely in that direction.
Given the experience of classical complexity theory, it would be reasonable to hope for a theorem showing that, if NP ⊆ BQP, then PH collapses-analogous to the Karp-Lipton Theorem [KL80], that if NP ⊂ P/poly then PH collapses, or the Boppana-Håstad-Zachos Theorem [BHZ87], that if NP ⊆ coAM then PH collapses. No such result is known for NP ⊆ BQP, once again because of the difficulty that there is no known way to pull the randomness out of a BQP algorithm. Theorem 9 helps to explain this situation, by showing that any proof of such a conditional collapse would have to be nonrelativizing. The proof of Theorem 9 builds, again, on the Raz-Tal Theorem. And this is easily seen to be necessary, since as we pointed out earlier, if BQP ⊆ AM, then NP ⊆ BQP really would imply a collapse of PH.
Theorem 10 says, in effect, that there is no relativizing obstruction to BQP being inordinately powerful even while NP is inordinately weak. It substantially extends the Raz-Tal Theorem, that there is an oracle relative to which BQP ⊂ PH, to show that in some oracle worlds, BQP doesn't go just slightly beyond the power of PH (which, if P = NP, is simply the power of P), but vastly beyond it. Once again, this illustrates the difference between randomness and quantumness, because if P = NP, then P = BPP for relativizing reasons.
We conjecture that Theorem 10 could be extended yet further, to give an oracle relative to which P = NP and yet BQP = EXP, but we leave that problem to future work.

Proof Techniques
We now give rough sketches of the important ideas needed to prove our results. Here, in contrast to Section 1.3, we present the results in the order that they appear in the main text, which is roughly in order of increasing technical difficulty.
Our proofs of Theorem 9 and Theorem 10 serve as useful warm-ups, giving a flavor for how we use the Raz-Tal Theorem and oracle construction techniques in later proofs. In Theorem 9, to construct an oracle where BQP = P #P but PH is infinite, we start by taking a random oracle, which by the work of Håstad, Rossman, Servedio, and Tan [HRST17,RST15] is known to make PH infinite. Then, for each P #P machine M , we add to the oracle an instance of the Forrelation problem that encodes the behavior of M : if M accepts, we choose a Forrelated instance, while if M rejects, we choose a uniformly random instance. This gives a BQP machine the power to decide any P #P language. 6 It remains to argue that adding these Forrelation instances does not collapse PH. We want to show that relative to our oracle, for every k, there exists a language in Σ P k+1 that is not in Σ P k . This is where we leverage the Raz-Tal Theorem: because the Forrelation instances look random to PH, we can show, by a hybrid argument, that a Σ P k algorithm's probability of correctly deciding a target function in Σ P k+1 is roughly unchanged if we replace the Forrelation instances with uncorrelated, uniformly random bits. But auxiliary random bits cannot possibly improve the success probability, and so a simple appeal to [HRST17] implies that the Σ P k+1 language remains hard for Σ P k .
The proof of Theorem 10, giving an oracle where P = NP = BQP = P #P , follows a similar recipe to the proof of Theorem 9. We start with a random oracle, which separates PH from P #P , and then we add a second region of the oracle that puts P #P into BQP by encoding all P #P queries in instances of the Forrelation problem. Next, we add a third region of the oracle that answers all NP queries, which has the effect of collapsing PH to P. Finally, we again leverage the Raz-Tal Theorem to argue that the Forrelation instances have no effect on the separation between PH and P #P , because the Forrelation instances look random to PH algorithms.
We next prove Theorem 8, that Σ P k+1 ⊂ BQP Σ P k relative to a random oracle. Our proof builds heavily on the proof by [HRST17] that Σ P k+1 ⊂ Σ P k relative to a random oracle. Indeed, our proof is virtually identical, except for a single additional step.
[HRST17]'s proof involves showing that there exists a function Sipser d that is computable by a small AC 0 circuit of depth d (which corresponds to a Σ P d−1 algorithm), but such that any small AC 0 circuit of depth d − 1 (which corresponds to a Σ P d−2 algorithm) computes Sipser d on at most a 1 2 + o(1) fraction of random inputs. This proof uses random restrictions, or more accurately, a generalization of random restrictions called random projections by [HRST17]. Roughly speaking, the proof constructs a distribution R over random projections with the following properties: (i) Any small AC 0 circuit C of depth d − 1 "simplifies" with high probability under a random projection drawn from R, say, by collapsing to a low-depth decision tree.
(ii) The target Sipser d function "retains structure" with high probability under a random projection drawn from R.
(iii) The structure retained in (ii) implies that the original unrestricted circuit C fails to compute the Sipser d function on a large fraction of inputs.
To prove Theorem 8, we generalize step (i) above from Σ P d−2 algorithms to BQP Σ P d−2 algorithms. That is, if we have a quantum algorithm that queries arbitrary depth-(d − 1) AC 0 functions of the input, then we show that this algorithm's acceptance probability also "simplifies" under a random projection from R. We prove this by combining the BBBV Theorem [BBBV97] with [HRST17]'s proof of step (i).
We next move on to the proof of Theorem 3, where we construct an oracle relative to which NP BQP ⊂ BQP PH . Recall that we prove Theorem 3 by showing that no BQP PH machine can solve the OR • Forrelation problem. To establish this, imagine that we fix a "no" instance x of the OR • Forrelation problem, meaning that x consists of a list of ∼ 2 n Forrelation instances that are all uniformly random (i.e. non-Forrelated). We can turn x into an adjacent "yes" instance y by randomly choosing one of the Forrelation instances of x and changing it to be Forrelated.
Our proof amounts to showing that with high probability over x, an AC 0 circuit of size 2 poly(n) is unlikely (over y) to distinguish x from y. Then, applying the BBBV Theorem [BBBV97], we can show that for most choices of x, a BQP PH algorithm is unlikely to distinguish x from y, implying that it could not have solved the OR • Forrelation problem.
Next, we notice that it suffices to consider what happens when, instead of choosing y by randomly flipping one of the Forrelation instances of x from uniformly random to Forrelated, we instead choose a string z by randomly resampling one of the instances of x from the uniform distribution. This is because, as a straightforward consequence of the Raz-Tal Theorem (Theorem 2), if f is an AC 0 circuit of size 2 poly(n) , then |Pr Our key observation is that the quantity Pr z [f (x) = f (z)] is proportional to a sort of "block sensitivity" of f on x. More precisely, it is proportional to an appropriate averaged notion of block sensitivity, where the average is taken over collections of blocks that respect the partition into separate Forrelation instances. This is where our block sensitivity concentration theorem comes into play: where bs x B (f ) denotes the block sensitivity of f on x with respect to B.
Informally, Theorem 11 says that the probability that an AC 0 circuit has B-block sensitivity t polylog(N ) on a random input x decays exponentially in t. This generalizes the result of Linial, Mansour, and Nisan [LMN93] that the average sensitivity of AC 0 circuits is at most polylog(N ). It also generalizes a concentration theorem for the sensitivity of AC 0 circuits that appeared implicitly in the work of Gopalan, Servedio, Tal, and Wigderson [GSTW16], by taking B to be the partition into singletons. 7 In fact, we derive Theorem 11 as a simple corollary of such a sensitivity tail bound for AC 0 . For completeness, we will also prove our own sensitivity tail bound, rather than appealing to [GSTW16]. Our sensitivity tail bound follows from an AC 0 random restriction lemma due to Rossman [Ros17].
To prove Theorem 4, which gives an oracle relative to which P = NP but BQP = QCMA, we use a similar technique to the proof of Theorem 10. We first take the oracle constructed in Theorem 3 that contains instances of the OR • Forrelation problem. Next, we add a second region of the oracle that answers all NP queries. This collapses PH to P. Finally, we use Theorem 3 to argue that these NP queries do not enable a BQP machine to solve the OR • Forrelation problem, which is in QCMA.
We now move on to the proof of Theorem 6, that there exists an oracle relative to which BQP NP ⊂ PH BQP . Recall that our strategy is to show that no PH BQP machine can solve the Forrelation • OR problem. We prove this by showing that with high probability, a PH BQP machine on a random instance of the Forrelation • OR problem can be simulated by a PH machine, from which a lower bound easily follows from the Raz-Tal Theorem. This simulation hinges on the following theorem, which seems very likely to be of independent interest: Theorem 12 (Theorem 53, informal). Consider a quantum algorithm Q that makes T queries to an M × N array of bits x, where each length-N row of x contains a single uniformly random 1 and 0s everywhere else. Then for any ε T √ N and δ > 0, there exists a deterministic classical algorithm that makes O T 5 ε 4 log T δ queries to x, and approximates Q's acceptance probability to within additive error ε on a 1 − δ fraction of such randomly chosen x's.
Informally, Theorem 12 says that any fast enough quantum algorithm can be simulated by a deterministic classical algorithm, with at most a polynomial blowup in query complexity, on almost all sufficiently sparse oracles. The crucial point here is that the classical simulation still needs to work, even in most cases where the quantum algorithm is lucky enough to find many '1' bits. We prove Theorem 12 via a combination of tail bounds and the BBBV hybrid argument [BBBV97].
In the statement of Theorem 12, we do not know whether the exponent of 5 on T is tight, and suspect that it isn't. We only know that the exponent needs to be at least 2, because of Grover's algorithm [Gro96].
We remark that Theorem 12 bears similarity to a well-known conjecture that involves simulation of quantum query algorithms by classical algorithms. A decade ago, motivated by the question of whether P = BQP relative to a random oracle with probability 1, Aaronson and Ambainis [AA14] proposed the following conjecture: Conjecture 13 ([AA14, Conjecture 1.5]; attributed to folklore). Consider a quantum algorithm Q that makes T queries to x ∈ {0, 1} N . Then for any ε, δ > 0, there exists a deterministic classical algorithm that makes poly T, 1 ε , 1 δ queries to x, and approximates Q's acceptance probability to within additive error ε on a 1 − δ fraction of uniformly randomly inputs x.
While Conjecture 13 has become influential in Fourier analysis of Boolean functions, 8 it remains open to this day. Theorem 12 could be seen as the analogue of Conjecture 13 for sparse oracles-an analogue that, because of the sparseness, turns out to be much easier to prove.
We conclude with the proof of Theorem 7, showing that PP is not contained in the QMA hierarchy relative to a random oracle. This is arguably the most technically involved part of this work. Recall that our key contribution, and the most important step of our proof, is a random restriction lemma for quantum query algorithms. In fact, we even prove a random restriction lemma for functions with low quantum Merlin-Arthur (QMA) query complexity: that is, functions f where a verifier, given an arbitrarily long "witness state," can become convinced that f (x) = 1 by making few queries to x. Notably, our definition of QMA query complexity does not care about the length of the witness, but only the number of queries made by the verifier. This property allows us to extend our results to complexity classes beyond QMA, such as QMIP.
An informal statement of our random restriction lemma is given below: Theorem 14 (Theorem 64, informal). Consider a partial function f : {0, 1} N → {0, 1, ⊥} with QMA query complexity at most polylog(N ). For some p = 1 √ N polylog(N ) , let ρ be a random restriction that leaves each variable unrestricted with probability p. Then f ρ is 1 quasipoly(N ) -close, in expectation over ρ, to a polylog(N )-width DNF formula. 9 An unusual feature of Theorem 14 is that we can only show that f ρ is close to a simple function in expectation. By contrast, Håstad's switching lemma for DNF formulas [Hås87] shows that the restricted function reduces to a simple function with high probability, so in some sense our result is weaker. Additionally, unlike the switching lemma, our result has a quantitative dependence on the number of inputs N . Whether this dependence can be removed (so that the bound depends only on the number of queries) remains an interesting problem for future work.
With Theorem 14 in hand, proving that PP ⊂ QMA QMA QMA ··· relative to a random oracle is conceptually analogous to the proof that PP ⊂ PH relative to a random oracle [Hås87]. We first view a QMA QMA QMA ··· machine as a small constant-depth circuit in which the gates are functions of low QMA query complexity. Then we want to argue that the probability that such a circuit agrees with the Parity function on a random input is small. We accomplish this via repeated application of Theorem 14, interleaved with Håstad's switching lemma for DNF formulas [Hås87].
To elaborate further, we first take a random restriction that, by Theorem 14, turns all of the bottom-layer QMA gates into DNF formulas. Next, we apply another random restriction and appeal to the switching lemma to argue that these DNFs reduce to functions of low decision tree complexity, which can be absorbed into the next layer of QMA gates. Finally, we repeat as many times as needed until the entire circuit collapses to a low-depth decision tree. Since the Parity function reduces to another Parity function under any random restriction, we conclude that this decision tree will disagree with the reduced Parity function on a large fraction of inputs, and hence the original circuit must have disagreed with the Parity function on a large fraction of inputs as well.
Of course, the actual proof of Theorem 7 is more complicated because of the accounting needed to bound the error introduced from Theorem 14, but all of the important concepts are captured above.
We end with a few remarks on the proof ideas needed for Theorem 14. Essentially, the first step involves proving that if we take a function f computed by a quantum query algorithm Q, a random restriction ρ, and a uniformly random input x to f ρ , then x likely contains a small set K of "influential" variables. These influential variables have the property that for any string y that agrees with x on K, |Pr[Q(x) = 1] − Pr[Q(y) = 1]| is bounded by a small constant. Hence, K serves as a certificate for f ρ 's behavior on x.
Proving that such a K usually exists amounts to a careful application of the BBBV Theorem [BBBV97]; the reader may find the details in Theorem 59. Finally, we generalize from quantum query algorithms to arbitrary QMA query algorithms by observing that we only need to keep track of the certificates for inputs x such that f ρ (x) = 1. The DNF we obtain in Theorem 14 is then simply the OR of all of these small 1-certificates.

Notation and Basic Tools
We denote by [N ] the set {1, 2, . . . , N }. For a finite set S, |S| denotes the size of S. If D is a probability distribution, then x ∼ D means that x is a random variable sampled from D. If v is a real or complex vector, then ||v|| denotes the Euclidean norm of v.
We use poly(n) to denote an arbitrary polynomially-bounded function of n, i.e. a function f for which there is a constant c such that f (n) ≤ n c for all sufficiently large n. Likewise, we use polylog(n) for an arbitrary f satisfying f (n) ≤ log(n) c for all sufficiently large n, and quasipoly(n) for an arbitrary f satisfying f (n) ≤ 2 log(n) c for all sufficiently large n.
For a string x ∈ {0, 1} N , |x| denotes the length of x. Additionally, if i ∈ [N ], then x ⊕i denotes the string obtained from x by flipping the ith bit. Similarly, if S ⊆ [N ], then x ⊕S denotes the string obtained from x by flipping the bits corresponding to all indices in S. For sets S ⊆ [N ], we sometimes use {0, 1} S to denote mappings from S to {0, 1}; these may equivalently be identified with strings in {0, 1} |S| obtained by concatenating the bits of the mapping in order. We denote by x| S the string in {0, 1} S obtained by restricting x to the bits indexed by S.
We view partial Boolean functions as functions of the form f : We use ⊥ (instead of * ) to refer to the evaluation of f on inputs outside the domain so as to avoid conflicting with our notation for random restrictions; see Section 2.4 below.
We use the following forms of the Chernoff bound: Fact 15 (Chernoff bound). Suppose X 1 , . . . , X n are independent identically distributed random variables where X i = 1 with probability p and X i = 0 with probability 1 − p. Let X = n i=1 X i and let µ = E [X] = pn. Then for all δ ≥ 0 it holds that: Additionally, if δ ≤ 1, then we may use the weaker bound: We also require Hoeffding's inequality, which generalizes Fact 15 to sums of arbitrary independent bounded random variables: Fact 16 (Hoeffding's inequality). Suppose X 1 , . . . , X n are independent random variables subject to . Then for all δ ≥ 0 it holds that:

Complexity Classes and Oracles
We assume familiarity with basic complexity classes, including: P, NP, PH = ∞ k=0 Σ P k , PP, P #P , BQP, QCMA, and QMA; see e.g. the Complexity Zoo 10 for definitions. For one of these complexity classes C, PromiseC denotes the corresponding class of promise problems. Recall that a promise problem can be viewed as a partial function Π : In this work, we follow the convention that an algorithm refers to a (possibly probabilistic) abstract procedure, while a machine refers to a computational problem (either a language or promise problem) that is decided by an algorithm. For example, if A is a polynomial-time quantum algorithm, and M is the PromiseBQP machine corresponding to A, then this means that M : Note that, while A defines a probabilistic procedure, M has no further randomness in its definition after rounding the acceptance probabilities of A.
We frequently make use of complexity classes augmented with oracles, where we use the standard notation that C O denotes a complexity class C augmented with oracle O. We also consider oracles for promise problems in the standard way: if C is a complexity class and Π a promise problem, then a language (or promise problem) L is in C Π if there exists a C oracle machine M such that, for every language A that extends Π, M A decides L. We also take this as a definition of M Π : We remark that it is not clear to us if this is the "right" way to define queries to a promise problem for quantum complexity classes, such as BQP Π or QMA Π . If we have query access to some quantum algorithm that "solves" a promise problem, that algorithm could conceivably behave arbitrarily (even non-unitarily) on the inputs outside of the promise: there is no guarantee that it decides some language, as we assume above. However, since we are chiefly interested in proving lower bounds on QMA complexity, this distinction makes little difference to us: our choice of definition could only possibly make the class QMA Π more powerful than if the oracle could have worse behavior on non-promise inputs. Whether complexity classes such as BQP Π and QMA Π are robust with respect to the notion of promise problem queries remains an interesting question for future work. 11 If C and D are both complexity classes, then C D := L∈D C L . A tower of relativized complexity classes such as C D O should be understood as C (D O ) , which is to say that notation for relativization, like exponentiation, is right associative. Nevertheless, in such cases, we can always view a language (or promise problem) in a complexity class such as C D O as being specified by a C D oracle machine. For example, a language in P NP O is uniquely specified by (1) a P oracle machine A (a polynomial-time deterministic oracle Turing machine), (2) an NP oracle machine B (a polynomial-time nondeterministic oracle Turing machine), and (3) the oracle O. In such cases, we may refer to the pair A, B as a P NP oracle machine. We define a quantum analogue of the polynomial hierarchy that we call QMAH, and denote by PromiseQMAH the promise version of this class. Let PromiseQMAH 1 = PromiseQMA, and for k > 1 we recursively define: Then, analogous to PH, we take: PromiseQMAH k QMAH denotes the set of languages in PromiseQMAH.
We note that there are many other possible ways to define a quantum analogue of the polynomial hierarchy (see [GSS + 18]), and that our definition appears to differ from all others that we are aware of. The definition we give is closest in spirit to a class called BQPH by Vinkhuijzen [Vin18], except that we allow recursive queries to PromiseQMA instead of just QMA.
We next specify some terminology and notation that we will use for constructing oracles. We will often find it convenient to specify oracles as a union of disjoint regions. Formally, this means the following. Suppose we have an increasing sequence n 1 < n 2 < ... and an associated sequence of functions A 1 , A 2 , . . ., where A i : {0, 1} n i → {0, 1}. We call each A i a region, and define the oracle O : {0, 1} * → {0, 1} constructed from these regions via: We may also construct oracles by joining other oracles together. For example, if we have a pair of oracles A, B : A random oracle O is a uniformly random language where for each x ∈ {0, 1} * , O(x) = 0 or 1 with probability 1 2 (independently for each x).

Query Complexity and Related Measures
We assume some familiarity with quantum and classical query complexity. We recommend a survey by Ambainis [Amb18] for additional background and definitions. A quantum query to a string x ∈ {0, 1} N is implemented via the unitary transformation U x that acts on basis states of the form |i |w as U and w is an index over a workspace register. We start with some standard definitions for classical and quantum query complexity.
Definition 17 (Decision tree complexity). The decision tree complexity of a function f : {0, 1} N → {0, 1, ⊥}, also called the deterministic query complexity of f and denoted D(f ), is the fewest number of queries made by any deterministic algorithm A(x) that satisfies, for all Definition 18 (Quantum query complexity). The (bounded-error) quantum query complexity of a function f : is the fewest number of queries made by any quantum query algorithm A(x) that satisfies, for all x ∈ Dom(f ): We define a notion of QMA (Quantum Merlin-Arthur) query complexity as follows.
Definition 19 (QMA query complexity). The (bounded-error) QMA query complexity of a function is the fewest number of queries made by any quantum query algorithm V(|ψ , x) that takes an auxiliary input state |ψ and satisfies, for all x ∈ Dom(f ): The algorithm V is sometimes called the verifier, and the state |ψ a witness.
Note that, in contrast to most previous works (c.f. [RS04, AKKT20, ST19]), our definition of QMA query complexity completely ignores the number of qubits in the witness state |ψ . Our definition is more closely related to the quantum certificate complexity QC(f ) that was introduced by Aaronson [Aar08]. The key difference between QMA(f ) and QC(f ) is that QMA(f ) only requires the ability to query-efficiently verify 1-inputs to the function, whereas QC(f ) assumes the existence of a query-efficient verifier on both 0-and 1-inputs. Thus, one can view QMA(f ) as a one-sided version of QC(f ). 12 It is important to emphasize that QMA query complexity is not completely trivial: even though the witness can have unbounded length, the power of the verifier is still limited by the number of queries it makes. Indeed, in some cases, the proof does not help at all. For example, for the function AND N on N bits that outputs 1 if all of the inputs are 1, we have Q(AND N ) = QMA(AND N ) = Θ √ N , as observed by Raz and Shpilka [RS04]. We next define sensitivity, and the related B-block sensitivity.
Definition 20 (Sensitivity). The sensitivity of a function f : The sensitivity of f is defined as: The block sensitivity of f with respect to B is defined as: Note that sensitivity is the special case of B-block sensitivity in which B is the partition into singletons.
We require a somewhat unusual definition of certificate complexity. Our definition agrees with the standard definition for total functions, but may differ for partial functions.
The certificate complexity of f on x, denoted C x (f ), is the minimum size of any certificate for f on x. The certificate complexity of f is defined as: Intuitively, in this definition of certificate complexity, a b-certificate for b ∈ {0, 1} witnesses that f (x) = 1 − b, in contrast to the standard definition where a b-certificate witnesses that f (x) = b.

Random Restrictions
A restriction is a function ρ : [N ] → {0, 1, * }. A random restriction with Pr[ * ] = p is a distribution over restrictions in which, for each i ∈ [N ], we independently sample: we denote by f ρ : {0, 1} S → {0, 1, ⊥} the function obtained from f by fixing the inputs where ρ(i) ∈ {0, 1}. We call the remaining variables the unrestricted variables. We sometimes apply restrictions to functions f i that have a subscript in the name, in which case we denote the restricted function by f i|ρ for notational clarity.
In this work, we also make use of projections, which are a generalization of restrictions that were introduced in [HRST17]. The exact definition of projections is unimportant for us, but intuitively, they are restrictions where certain unrestricted variables may be mapped to each other; see [HRST17] for a more precise definition. We use the same notation f ρ for applying a projection ρ to a function f as we do for restrictions.

Circuit Complexity
In this work, we consider Boolean circuits where the gates can be arbitrary partial Boolean functions We always specify the basis of gates allowed in Boolean circuits. Most commonly, we will consider Boolean circuits with AND, OR, and NOT gates where the AND and OR gates can have unbounded fan-in, but we will also consider e.g. circuits where the gates can be arbitrary functions of low QMA query complexity.
The size of a circuit is the number of gates of fan-in larger than 1 (i.e. excluding NOT gates). The depth of circuit is the length of the longest path from an input variable to the output gate, ignoring gates of fan-in 1.
An AND/OR/NOT circuit is alternating if all NOT gates are directly above the input, and all paths from the inputs to the output gate alternate between AND and OR gates. A circuit is layered if for each gate g in the circuit, the distance from g to the output gate is the same along all paths. We denote by AC 0 [s, d] the set of alternating, layered AND/OR/NOT circuits of size at most s and depth at most d. By a folklore result, any AND/OR/NOT circuit can be turned into an alternating, layered circuit of the same depth at the cost of a small (constant multiplicative) increase in size.
A DNF formula, also just called a DNF, is a depth-2 AC 0 circuit where the top gate is an OR gate (i.e. the circuit is an OR of ANDs). The width of a DNF is the maximum fan-in of any of the AND gates.
We require the following results in circuit complexity.
Theorem 23 ([Hås87, Lemma 7.8]). For every constant d, there exists a constant c such that for all sufficiently large N , for all C ∈ AC 0 2 N c , d , one has: where Parity N is the parity function on N bits.
Theorem 24 ([HRST17, Proof of Theorem 10.1]). For all constant d ≥ 2 and all sufficiently large m ∈ N, there exists a function Sipser d ∈ AC 0 2 Θ(m) , d with N = 2 Θ(m) inputs, and a class R of random projections such that the following hold: where D is the distribution over bit strings in which each coordinate is 0 with probability b and 1 with probability 1 − b.
Additionally, let C ∈ AC 0 [s, d − 1]. If we sample ρ ∼ R, then: (c) Except with probability at most O 2 −m/2 , Sipser d|ρ is reduced to an AND gate of fan-in An exact definition of the Sipser d function is not important for us, but to help give some intuition, we mention a few of its other important properties. Sipser d can be constructed as a depth-regular read-once monotone formula in which the gates at odd distance from the input are AND gates and the gates at even distance are OR gates. Additionally, for each i ∈ [d], the gates at distance i from the inputs all have the same fan-in f i . These f i s satisfy f 1 = 2m and f i = 2 Θ(m) for i > 1. This regularity allows for an appropriately scaled version of the Sipser d function (or its negation) to be computed in Σ P d−1 . Specifically, given an oracle O : {0, 1} log N → {0, 1}, and viewing the first N bits of the truth table of O as an input HRST17] for further details.
[HRST17] roughly explains the intuitive meaning of the above theorem as follows. Property (a) guarantees that the distribution R of random projections completes to the uniform distribution. Property (b) shows that the circuit C simplifies with high probability under a random projection, while property (c) shows that Sipser d retains structure under this distribution of projections with high probability. A simple corollary of these properties is the following: Then, for all sufficiently large m, we have: Circuit complexity lower bounds are an indispensable tool for proving separations of relativized complexity classes, as was first observed by Furst, Saxe, and Sipser [FSS84]. This connection can be formalized via the following lemma, which shows that the behavior of any PH oracle machine can be computed by an AC 0 circuit whose inputs are the bits of the oracle string.
Lemma 26 (Implicit in [FSS84, Lemma 2.3]). Let M be a Σ P k oracle machine, and let p(n) be a polynomial upper bound on the running time of M on inputs of length n. Then for any x ∈ {0, 1} n , there exists a circuit C ∈ AC 0 2 poly(n) , k + 1 such that for any oracle O : {0, 1} * → {0, 1}, we have: where O [p(n)] denotes the concatenation of the bits of O on all strings of length at most p(n).
Thus, lower bounds on AC 0 circuit complexity give rise to oracle separations involving PH. In particular, average-case lower bounds on the size of AC 0 circuits can be used to construct separations relative to random oracles. For example, Theorem 23 implies that P #P ⊂ PH relative to a random oracle [Hås87], while Corollary 25 implies that Σ P k+1 ⊂ Σ P k relative to a random oracle [HRST17,RST15].
In most cases, when applying Lemma 26 to jump between PH oracle machines and AC 0 circuits, we follow the convention of using n to denote the length of an input to the PH machine, and N to denote the (exponentially larger) size of the input to the corresponding AC 0 circuit. For example, we might consider a PH machine that queries a function f : The truth table of f can be interpreted as a string of length N = 2 p(n) . The corresponding AC 0 circuit will have N inputs and size s ≤ 2 poly(n) . Thus, when we view s as a function of the input size N of the circuit, we have the bound s ≤ quasipoly(N ).

Other Background
The form of the Raz-Tal Theorem stated below forms the basis for several of our results. It states that there exists a distribution that looks pseudorandom to small constant-depth AC 0 circuits, but that is easily distinguishable from random by an efficient quantum algorithm.
Theorem 27 ([RT19, Theorem 1.2]). For all sufficiently large N , there exists an explicit distribution F N that we call the Forrelation distribution over {0, 1} N such that: 1. There exists a quantum algorithm A that makes polylog(N ) queries and runs in time polylog (N ) such that: Note that, by standard amplification techniques, the 1 N 2 in the above theorem can be replaced by any δ ≤ 2 −polylog(N ) at a cost of polylog(N ) in the other parameters. For our purposes, the above theorem suffices as written. In some cases where N is clear from context, we omit the subscript and write the distribution as F. Additionally, in a slight abuse of notation, we sometimes informally call the decision problem of distinguishing a sample from F N from a sample from the uniform distribution the Forrelation problem.
The next lemma was essentially shown in [BBBV97]. We provide a proof for completeness.
Lemma 28. Consider a quantum algorithm Q that makes T queries to x ∈ {0, 1} N . Write the state of the quantum algorithm immediately after t queries to x as: where w are indices over a workspace register. Define the query magnitude q i of an input i ∈ [N ] by: Then for any y ∈ {0, 1} N , we have: Proof. Denote by |ψ t the state of the quantum algorithm after t queries, where the first t − 1 queries are to x and the tth query is to y. For t > 0, we have: Hence, if we denote by |ϕ t the state of the quantum algorithm after t queries, where all t queries are to y, then:

Consequences of the Raz-Tal Theorem
In this section, we prove several oracle separations that build on the Raz- Tal Theorem (Theorem 27) and other known circuit lower bounds.

Relativizing (Non-)Implications of NP ⊆ BQP
Our first result proves the following: Theorem 29. There exists an oracle relative to which BQP = P #P and PH is infinite.
The proof idea is as follows. First, we take a random oracle, which makes PH infinite [HRST17,RST15]. Then, we encode the answers to all possible P #P queries in instances of the Forrelation problem, allowing a BQP machine to efficiently decide any P #P language. We then leverage Theorem 27 to argue that adding these Forrelation instances does not collapse PH, because the Forrelation instances look random to PH algorithms. The formal proof is given below.
Proof of Theorem 29. We will inductively construct this oracle O, which will consist of two parts, A and B. Denote the first part of the oracle A, and let this be a random oracle. For each t ∈ N, we will add a region of B called B t that will depend on the previously constructed parts of the oracle. For convenience, we let A t denote the region of A corresponding to inputs of length t, and we write Let S t be the set of all ordered pairs of the form M, x such that: 1. M is a P #P oracle machine and x is an input to M , 2. M, x takes less than t bits to specify, and Note that there are at most 2 t elements in S t . Let M 1 , M 2 , . . . , M 2 t be an enumeration of S t . For each M i in S t , we add a function f i : . The function f i is chosen subject to the following rules: 1. If M i accepts, then f i is drawn from the Forrelation distribution F 2 t 2 (given in Theorem 27).
2. If M i rejects, then f i is uniformly random.
Let D be the resulting distribution over oracles O = (A, B). In more detail, by Theorem 27 we know that: where the probability in the above expression is also taken over the randomness of A. By Markov's inequality, we may conclude: Hence, the BQP promise problem defined by A agrees with the P #P language on M, x , except with probability at most 3 · 2 −2t 2 . We now appeal to the Borel-Cantelli Lemma to argue that, with probability 1 over O ∼ D, A correctly decides M O (x) for all but finitely many x ∈ {0, 1} * . Since there are at most 2 t inputs M, x that take less than t bits to specify, we have: Therefore, the probability that A fails on infinitely many inputs M, x is 0. Hence, A can be modified into a BQP algorithm that decides M O (x) for all x ∈ {0, 1} * , with probability 1 over O ∼ D. Now, we must show that PH O is infinite. We will accomplish this by proving, for all k ∈ N, Σ P O k = Σ P O k−1 with probability 1 over the choice of O. Let L O be the unary language used for the same purpose as in [RST15,HRST17]. That is, L O consists of strings 0 n such that, if we treat n as an index into a portion of the random oracle A n that encodes a size-2 n instance of the Sipser k+1 function, then that instance evaluates to 1. By construction, HRST17]. Furthermore, [RST15,HRST17] show that L O is not in Σ P A k−1 with probability 1 over the random oracle A. We need to argue that adding B has probability 0 of changing this situation. Fix any Σ P O k−1 oracle machine M . By the union bound, it suffices to show that Let n 1 < n 2 < · · · be an infinite sequence of input lengths, spaced far enough apart (e.g. n i+1 = 2 n i ) such that M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. Then we have that Thus it suffices to show that, for every fixed M , we have p(M, i) ≤ 0.7 for all but finitely many i. To do this, we will consider a new quantity q(M, i), which is defined exactly the same way as p(M, i), except that now the oracle is chosen from a different distribution, which we call D i . This D i is defined identically to D on A and B 1 , . . . , B n i , but is uniformly random on B m for all m > n i . It suffices to prove the following: for any fixed M , Hence, M is forced to evaluate the size-2 n i Sipser k+1 function using only auxilliary and uncorrelated random bits. By the well-known connection between Σ P k−1 oracle machines and constant-depth circuits (Lemma 26), M 's behavior on this size-2 n i string can be computed by an AC 0 2 poly(n i ) , k circuit. Corollary 25 shows that such a circuit correctly evaluates this Sipser k+1 function with probability greater than (say) 0.6 for at most finitely many i. This even holds conditioned on M O correctly deciding 0 n 1 , . . . , 0 n i−1 , because the size-2 n i Sipser k+1 instance is chosen independently from the smaller instances, and because M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i.
For statement (b), we will prove this claim using a hybrid argument. We consider an infinite sequence of hybrids {D i,j : j ∈ N} between D i = D i,0 and D, where in the jth hybrid D i,j we sample A and B 1 , . . . , B n i +j according to D and B n i +j+1 , B n i +j+2 , . . . uniformly at random. The change between each D i,j−1 and D i,j may be further decomposed into a sequence of smaller changes: from the uniform distribution U to the Forrelated F, for each function f : {0, 1} (n i +j) 2 → {0, 1} corresponding to a P #P oracle machine that happens to accept.
Suppose we fix the values of O on everything except for f . Theorem 27 implies that: This is because, again using Lemma 26, there exists an AC 0 2 poly(n i ) , k circuit that takes the oracle string as input and evaluates to M O (0 n i ). In fact, (1) also holds even if the parts of O other than f are not necessarily fixed, but are drawn from some distribution, by convexity (so long as the distribution is the same in both of the probabilities in (1)). In particular, using the fact that the n i s are far enough apart for sufficiently large i, (1) also holds (for all sufficiently large i) when the parts of O other than f are drawn from the distribution conditioned on M O correctly deciding 0 n 1 , . . . , 0 n i−1 . Now, recall that there are at most 2 t Forrelation instances in the B t part of the oracle. By the triangle inequality, bounding over each of these instances yields: where we implicitly condition on M O correctly deciding 0 n 1 , . . . , 0 n i−1 in both of the probabilities above, omitting it as written purely for notational simplicity. Hence, when we change all of the hybrids, we obtain: for all but at most finitely many i.
We conclude this section with a simple corollary.
Corollary 31. There exists an oracle relative to which BQP ⊂ NP/poly.

Weak NP, Strong BQP
In this section, we prove the following: Theorem 32. There exists an oracle relative to which P = NP = BQP = P #P .
Note that, relative to any oracle, P = NP implies P = PH. So, the Raz-Tal oracle separation of BQP and PH [RT19] is necessary to prove Theorem 32, in the sense that Theorem 32 is strictly stronger: any oracle O that satisfies Theorem 32 must also have We follow a similar proof strategy to Theorem 29, with some additional steps. First, we take a random oracle, which separates PH from P #P (morally, because Parity is not approximable by AC 0 circuits [Hås87]). We encode the answers to all possible P #P queries in instances of the Forrelation problem, allowing a BQP machine to efficiently decide any P #P language. Then, we add a region of the oracle that answers all NP queries, which collapses PH to P. Finally, we leverage Theorem 27 to argue that the Forrelation instances have no effect on the separation between PH and P #P , because the Forrelation instances look random to PH algorithms. The formal proof is given below.
Proof of Theorem 32. This oracle O will consist of three parts: a random oracle A, and oracles B and C that we will construct inductively. For each t ∈ N, we will add regions B t and C t that will depend on the previously constructed parts of the oracle. For convenience, we let A t denote the region of A corresponding to inputs of length t, and we write O t = (A t , B t , C t ).
We first describe B, which will effectively collapse P #P to BQP. For t ∈ N, let S t be the set of all ordered pairs of the form M, x such that: 1. M is a P #P oracle machine and x is an input to M , 2. M, x takes less than t bits to specify, and 3. M is syntactically restricted to run in less than t steps, and to query only the O 1 , O 2 , . . . , O √ t regions of the oracle.
Note that there are at most 2 t elements in S t . Let M 1 , M 2 , . . . , M 2 t be an enumeration of S t . For each . The function f i is chosen subject to the following rules: 1. If M i accepts, then f i is drawn from the Forrelation distribution F 2 t 2 (given in Theorem 27).
2. If M i rejects, then f i is uniformly random.
We next describe C, which will effectively collapse NP to P. For t ∈ N, define T t similarly to S t , except that we take NP oracle machines instead of P #P oracle machines. For each M i in T t , we add a bit into C t that returns Let D be the resulting distribution over oracles O = (A, B, C). We will show that the statement of the theorem holds with probability 1 over O sampled from D. To complete the proof, we will show that NP O = P #P O with probability 1 over O. Let L O be the following unary language: L O consists of strings 0 n such that, if we treat n as an index into a portion of the random oracle A n of size 2 n , then the parity of that length-2 n string is 1. By construction, L O ∈ P #P O . We will show that L O ∈ NP O with probability 1 over O.
Fix any NP O oracle machine M . By the union bound, it suffices to show that Let n 1 < n 2 < · · · be an infinite sequence of input lengths, spaced far enough apart (e.g. n i+1 = 2 n i ) such that M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. Then we have that Thus it suffices to show that, for every fixed M , we have p(M, i) ≤ 0.7 for all but finitely many i. To do this, we will consider a new quantity q(M, i), which is defined exactly the same way as p(M, i), except that now the oracle is chosen from a different distribution, which we call D i . This D i is defined identically to D on A, C, and B 1 , . . . , B n i , but is uniformly random on B m for all m > n i . It suffices to prove the following: for any fixed M , To prove these, we first need the following lemma, which essentially states that for any t ≤ poly(t), any bit in C t can be computed by a small (i.e. quasipolynomial in the input length) constant-depth AC 0 circuit whose inputs do not depend on C i for any i > t.
Lemma 35. Fix t, d ∈ N, and let t ≤ t 2 d . For each M, x ∈ T t , there exists an AND/OR/NOT circuit of size at most 2 1+t 2 d and depth 2d that takes as input A 1 , A 2 , . . . , A t 2 d−1 ; B 1 , B 2 , . . . , B t 2 d−1 ; and C 1 , C 2 , . . . , C t , and outputs M (x).
Proof of Lemma. Assume t ≥ 2 (otherwise the theorem is trivial). We proceed by induction on d. This function may thus be expressed as a DNF formula of width at most t , which is in turn an AND/OR/NOT circuit of depth 2 and size at most 2 t + 1 ≤ 2 t 2 + 1 ≤ 2 1+t 2 .
For the inductive step, let d ≥ 2. Similar to the base case, we use the definition of T t to obtain a circuit of depth 2 and size at most 2 t + 1 that takes as input O 1 , O 2 , . . . , O t 2 d−1 and outputs M (x). To complete the theorem, we use the inductive hypothesis to replace each of the inputs to this DNF formula from the regions C t+1 , C t+2 , . . . , C t 2 d−1 with the respective circuits that compute them. This yields a circuit of depth 2d, and by the inductive hypothesis, the total number of gates in this circuit is at most: because for each t + 1 ≤ i ≤ t 2 d−1 , there are at most 2 i bits in C i . The above quantity is upper bounded by: Above, the first inequality holds because t ≤ t 2 d ; the second inequality simply expands the range of the sum (which certainly increases the sum by at least 1); the third inequality applies j i=1 2 i ≤ 2 j+1 ; and the remaining inequalities hold because t ≥ 2 and d ≥ 2.
Note that Lemma 35 does not depend on the distribution of A and B, but only on the way C is defined recursively in terms of A and B. Hence, it holds for both O drawn from D or drawn from any D i . We also note that the circuit given in Lemma 35 is not in AC 0 normal form (i.e. it is not necessarily alternating and layered), but can be made so at the cost of a small increase in size.
Choosing specific parameters in Lemma 35 gives the following simple corollary: With Corollary 36 in hand, the remainder of the proof closely follows the proof of Theorem 29. Statement (a) essentially follows from the work of [Hås87]. In more detail, consider the circuit produced by Corollary 36 that computes M (0 n i ). The key observation is that the only portion of the input to this circuit that can depend on whether 0 n i is in L O is the input to the size-2 n i parity function that is encoded in A. All other portions of the input are sampled independently from this region under D i : 1. The rest of A is sampled uniformly at random, 2. B 1 , . . . , B n i and C 1 , . . . , C n i are drawn from a distribution that cannot depend on any queries to A on inputs of length √ n i or greater (so in particular, they cannot depend on A n i ), and 3. B n i +1 , B n i +2 , . . . are sampled uniformly at random.
Hence, M is forced to evaluate the size-2 n i parity function using only auxiliary and uncorrelated random bits. By Theorem 23, M can do this with probability greater than 0.6 for at most finitely many i. This even holds conditioned on M O correctly deciding 0 n 1 , . . . , 0 n i−1 , because the size-2 n i parity instance is chosen independently from the smaller instances, and because M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. For statement (b), we will prove this claim using a hybrid argument. We consider an infinite sequence of hybrids {D i,j : j ∈ N} between D i = D i,0 and D, where in the jth hybrid D i,j we sample A, C, and B 1 , . . . , B n i +j according to D and B n i +j+1 , B n i +j+2 , . . . uniformly at random. The change between each D i,j−1 and D i,j may be further decomposed into a sequence of smaller changes: from the uniform distribution U to the Forrelated F, for each function f : {0, 1} (n i +j) 2 → {0, 1} corresponding to a P #P oracle machine that happens to accept.
Suppose we "fix" the values of O on everything except for f , in the following sense. We fix A and B, except for some particular f in B that is allowed to vary. Then, we define C recursively in terms of A and B in the usual, deterministic way (so that changing f can affect C, but not the rest of A and B). Theorem 27 implies that: This is because, by Corollary 36, there exists an AC 0 2 poly(n i ) , O(1) circuit that takes A, B, and C 1 , . . . , C n i as input and evaluates to M O (0 n i ). In fact, (2) also holds even if the parts of A, B, and C 1 , . . . , C n i other than f are not necessarily fixed, but are drawn from some distribution, by convexity (so long as the distribution is the same in both of the probabilities in (2)). In particular, using the fact that the n i s are far enough apart for sufficiently large i, (2) also holds (for all sufficiently large i) when the parts of A, B, and C 1 , . . . , C n i other than f are drawn from the distribution conditioned on M O correctly deciding 0 n 1 , . . . , 0 n i−1 . Now, recall that there are at most 2 t Forrelation instances in the B t part of the oracle. By the triangle inequality, bounding over each of these instances yields: where we implicitly condition on M O correctly deciding 0 n 1 , . . . , 0 n i−1 in both of the probabilities above, omitting it as written purely for notational simplicity. Hence, when we change all of the hybrids, we obtain: for all but at most finitely many i.

BQP PH Lower Bounds for Sipser Functions
In this section, we prove that BQP Σ P k does not contain Σ P k+1 relative to a random oracle, generalizing the known result that PH is infinite relative to a random oracle [HRST17,RST15].
We first require the following form of the BBBV Theorem [BBBV97]. It essentially states that a quantum algorithm that makes few queries to its input is unlikely to detect small random changes to the input. Viewed another way, Lemma 37 is just a probabilistic version of Lemma 28.
Lemma 37. Consider a quantum algorithm Q that makes T queries to x ∈ {0, 1} N . Let y ∈ {0, 1} N be drawn from some distribution such that, for all i ∈ [N ], Pr y [x i = y i ] ≤ p. Then for any r > 0: Proof. Let Q be the quantum query algorithm corresponding to f . By Lemma 28, we have that for any fixed y: where we recall the definition of the query magnitudes q i which depend on the algorithm's behavior on input x, and which satisfy n i=1 q i = T . This implies that: where the third line applies Markov's inequality (the q i s are nonnegative), and the last two lines use linearity of expectation along with the fact that the q i s sum to T .
The proof of this theorem largely follows Theorem 10.1 of [HRST17], the relevant parts of which are quoted in Theorem 24. We take a distribution ρ ∼ R of random projections with the property that (a) R completes to the uniform distribution, (b) f ρ simplifies with high probability over ρ, and (c) Sipser d|ρ retains structure with high probability over ρ. Essentially the only difference compared to [HRST17] is that we must incorporate the BBBV Theorem (in the form of Corollary 38) in order to argue (b).
Proof of Theorem 39. By Theorem 24(a), Theorem 24(b) and a union bound over all of the sub-circuits of the top gate imply that, except with probability at most s2 −2 m/2−4 over ρ ∼ R, f ρ can be computed by a depth-2 circuit where the top gate has bounded-error quantum query complexity T , and all of the gates below the top gate have deterministic query complexity at most 2 m/2−4 . In this case, we say for brevity that f ρ "simplifies". By Theorem 24(c) and a union bound, except with probability at most O 2 −m/2 + s2 −2 m/4−2 over ρ ∼ R, f ρ simplifies and Sipser d|ρ is an AND of fan-in (ln 2) · 2 m · 1 ± O 2 −m/4 . An AND of fan-in (ln 2) · 2 m · 1 ± O 2 −m/4 evaluates to 1 with probability 1 2 1 ± O 2 −m/4 on an input sampled from D. On the other hand, if f ρ simplifies, then for each sub-circuit C of the top gate, Pr x∼D C(x) = C 1 |x| ≤ b2 m/2−4 , just because D(C) ≤ 2 m/2−4 and each bit of x is 0 with probability at most b. Hence, by Corollary 38 with p = b2 m/2−4 , if f ρ simplifies, then for some i ∈ {0, 1}, Pr x∼D [f ρ (x) = i] ≤ 2304bT 2 2 m/2−4 . Since b ≤ 2 −m , putting these together gives us that: To complete this section, we require the following extension of Furst-Saxe-Siper [FSS84] (Lemma 26) to BQP Σ P k machines.
Proposition 40. Let M be a BQP Σ P k oracle machine (i.e. a pair A, B of a BQP oracle machine A and a Σ P k oracle machine B). Let p(n) be a polynomial upper bound on the runtime of A and B on inputs of length n. Then for any x ∈ {0, 1} n , there is a depth-(k + 2) circuit C of size at most 2 poly(n) in which the top gate has bounded-error quantum query complexity at most p(n), and all of the sub-circuits of the top gate are AC 0 2 poly(n) , k + 1 circuits, such that for any oracle O : {0, 1} * → {0, 1} we have: where O [p(p(n))] denotes the concatenation of the bits of O on all strings of length at most p(p(n)).
Proof. For convenience, denote by L the language decided by B O . M O (x) = A L (x) is a function of bounded-error quantum query complexity at most p(n) in the bits of L. We take this function to be the top gate of our circuit, and use Lemma 26 to replace the inputs to this gate, the bits of L, with AC 0 circuits. Since A L (x) runs in time at most p(n), it can only query the evaluation of B O on inputs up to length at most p(n). By Lemma 26, for each y ∈ {0, 1} m with m ≤ p(n), B O (y) is computed by an AC 0 [s, k + 1] circuit for some s ≤ 2 poly(p(n)) ≤ 2 poly(n) , where the inputs to this circuit are the bits of O on inputs of length at most p(p(n)). The resulting circuit obtained by composing the quantum gate with these AC 0 circuits has total number of gates bounded above by: 2 m · 2 poly(m) ≤ 2 poly(n) , and thus it satisfies the statement of the proposition.
By standard techniques, we obtain the main result of this section, stated in terms of oracles instead of query complexity.
with probability 1 over a random oracle O.
Proof. Let d = k + 2. Let L O be the unary language used for the same purpose as in [RST15,HRST17]. That is, L O consists of strings 0 n such that, if we treat n as an index into a portion of the random oracle O that encodes a size-2 n instance of the Sipser d function, then that instance evaluates to 1. By construction, Let n 1 < n 2 < · · · be an infinite sequence of input lengths, spaced far enough apart (e.g. n i+1 = 2 n i ) such that M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. Then we have that Thus it suffices to show that, for every fixed M , we have p(M, i) ≤ 0.7 for all but finitely many i. Proposition 40 shows that M 's behavior on 0 n i can be computed by a circuit of size s ≤ 2 poly(n i ) in which the top gate has bounded-error quantum query complexity T ≤ poly(n i ), and all of the sub-circuits of the top gate are depth-(d − 1) AC 0 circuits. Theorem 39 with N = 2 n i and m = Θ(n i ) shows that such a circuit correctly evaluates the Sipser d function with probability greater than (say) 0.7 for at most finitely many i. This even holds conditioned on M O correctly deciding 0 n 1 , . . . , 0 n i−1 , because the size-2 n i Sipser d instance is chosen independently of the smaller instances, and because M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i.

BQP PH Lower Bounds for OR • Forrelation
In this section, we use tail bounds on the sensitivity of AC 0 circuits to construct an oracle relative to which NP BQP ⊂ BQP PH . Such bounds are given implicitly in Section 3 of [GSTW16]. For completeness, we derive our own bound on the sensitivity tails of AC 0 circuits, though our bound is probably quantitatively suboptimal.
To prove that the sensitivity of AC 0 circuits concentrates well, the first ingredient we need is a random restriction lemma for AC 0 circuits. We use the following form, due to Rossman [Ros17].
Theorem 42 ( [Ros17]). Let f ∈ AC 0 [s, d], and let ρ be a random restriction with Pr[ * ] = p. Then for any t > 0: With this in hand, it is straightforward to derive our sensitivity tail bound.
Then for any t > 0, Proof. Let ρ be a random restriction with Pr[ * ] = p, for some p to be chosen later. It will be convenient to view the choice of ρ as follows: we choose a string x ∈ {0, 1} N uniformly at random, and then we choose a set S ⊆ [N ] wherein each i ∈ [N ] is included in S independently with probability p. Then, we take ρ to be: Thus, by definition, it holds that f ρ (x| S ) = f (x).
Observe that for any fixed x ∈ {0, 1} N and j > 0, we have: where the first line holds because each sensitive bit of f on x is kept unrestricted with probability p; the second line holds by the definition of sensitivity; the third line holds by known relations between query measures; and the last line holds because D(f ρ ) ≤ N always holds. With this in hand, we derive: Above, the first line applies (3); the third line holds by Markov's inequality; and the last line applies Theorem 42. Choose p = O (log s) 1−d so that the above expression simplifies to 2 −j · N pt−j . Then, set j = pt − 1 and the corollary follows.
The sensitivity tail bound above immediately implies a tail bound on the block sensitivity of AC 0 circuits. We thank Avishay Tal for providing us with a proof of this fact.
Proof. Consider the function g : {0, 1} N +k defined by where z i · B i denotes the all zeros string if z i = 0, and otherwise is the indicator string of B i . We claim that g Notice that each bit of x is either a bit in y, or else the XOR of a bit of y with a bit of z. Hence, we can compute g by feeding in at most N XOR gates and their negations into f . The XOR function can be written as either an OR of ANDs or an AND of ORs: Hence, we can absorb one layer of AND or OR gates into the bottom layer of the circuit that computes f , thus obtaining a circuit of depth d + 1.
The rough idea of the proof going forward is as follows: an NP BQP machine can easily distinguish (1) a uniformly random M × N array of bits, and (2) an M × N array which contains a single row drawn from the Forrelation distribution, and is otherwise random. We want to show that a BQP PH machine cannot distinguish (1) and (2). To prove this, we first use our block sensitivity tail bound to argue in Lemma 45 below that for most uniformly random strings x, an AC 0 circuit is unlikely to detect a change to x made by uniformly randomly resampling a single row of x. Then, we use the Raz-Tal Theorem to argue in Lemma 46 that the same holds if we instead resample a single row of x from the Forrelation distribution, rather than the uniform distribution. Finally, in Theorem 47 we apply the BBBV Theorem to argue that a BQP PH oracle machine cannot distinguish cases (1) and (2).
Putting these together, we obtain: where the first line substitutes (5); the second line holds by (6)  • If b = 0, then z is uniformly random.
• If b = 1, then a single uniformly chosen row of z is sampled from the Forrelation distribution F N , and the remaining M − 1 rows of z are uniformly random. Then: Proof. We can think of sampling z as follows. First, we choose a string x 0 ∼ {0, 1} M N . Then, we sample x 1 by uniformly at random replacing one of the rows of x 0 with a sample from F N . Finally, we sample b ∼ {0, 1} and set z = x b . Call a fixed x 0 "bad" if, for one of the sub-circuits C of the top gate, we have Pr is the parameter given in Lemma 46. Lemma 46, combined with a union bound over the quasipoly(N )-many such sub-circuits, implies that: Clearly, it holds that: b is uniformly random, even conditioned on x 0 being good. On the other hand, Corollary 38 implies that for some i ∈ {0, 1} (depending on x 0 ), Pr Thus, it holds that: Putting these bounds together implies the statement of the theorem.
Via standard complexity-theoretic techinques, Theorem 47 implies the following oracle separation, which resolves the question of Fortnow [For05].
Corollary 48. There exists an oracle relative to which NP BQP ⊂ BQP PH .
Proof. We construct an oracle A as follows. Let L A be a uniformly random unary language. For each n ∈ N, we add into A a region consisting of a function f n : {0, 1} 2n 2 → {0, 1}. Choose f n as follows: • If L A (0 n ) = 0, then f n is uniformly random.
• If L A (0 n ) = 1, then viewing the truth table of f n as consisting of 2 n 2 rows of length 2 n 2 , we pick a single row at random and sample it from the Forrelation distribution F 2 n 2 , and sample the remaining 2 n 2 − 1 rows from the uniform distribution.
Let D be the resulting distribution over oracles A. We first show that L A ∈ NP BQP A with probability 1 over A ∼ D. To do so, we define a language P A as follows: for a string x ∈ {0, 1} * , P A (x) = 1 if |x| = n 2 and the xth row of f n was drawn from the Forrelation distribution; otherwise P A (x) = 0. Clearly, L A ∈ NP P A : to determine if 0 n ∈ L A , nondeterministically guess a string x ∈ {0, 1} n 2 and check if x ∈ P A . Thus, it suffices to show that P A ∈ BQP A , which we do below. (Note that this proof shares large parts with the proof of Claim 30, only modifying a few parameters.) Claim 49. P A ∈ BQP A with probability 1 over A.
Proof of Claim. Given an input x of length n 2 , a quantum algorithm can decide whether x ∈ P A in poly(n) time by looking up xth row of f n , and then deciding whether it is Forrelated or random by using the distinguishing algorithm A from Theorem 27.
In more detail, let g x : {0, 1} n 2 → {0, 1} denote the xth row of f n (i.e. g x (y) := f n (x, y)). By Theorem 27 we know that: Pr where the probability in the above expression is also taken over the randomness of A. By Markov's inequality, we may conclude: Hence, the BQP promise problem defined by A agrees with P A on x, except with probability at most 3 · 2 −2n 2 . We now appeal to the Borel-Cantelli Lemma to argue that, with probability 1 over A, A correctly decides P A (x) for all but finitely many x ∈ {0, 1} * . Since there are exactly 2 n 2 inputs x of length {0, 1} n 2 , we have: Therefore, the probability that A fails on infinitely many inputs x is 0. Hence, A can be modified into a BQP algorithm that decides P A (x) for all x ∈ {0, 1} * , with probability 1 over A ∼ D.
It remains to show that L A ∈ BQP PH A with probability 1 over A. As we will show, this follows from Theorem 47 in the much same way that Corollary 41 follows from Theorem 39. Fix a BQP Σ P k oracle machine M . By the union bound, it suffices to show that Let n 1 < n 2 < · · · be an infinite sequence of input lengths, spaced far enough apart (e.g. n i+1 = 2 n i ) such that M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. Then we have that Thus it suffices to show that, for every fixed M , we have p(M, i) ≤ 0.7 for all but finitely many i. Proposition 40 shows that M 's behavior on 0 n i can be computed by a circuit of size 2 poly(n i ) in which the top gate has bounded-error quantum query complexity T ≤ poly(n i ), and all of the sub-circuits of the top gate are AC 0 2 poly(n i ) , k + 1 circuits. Theorem 47 with M = N = 2 n 2 i shows that such a circuit correctly evaluates the OR • Forrelation function with probability greater than (say) 0.7 for at most finitely many i. This even holds conditioned on M A correctly deciding 0 n 1 , . . . , 0 n i−1 , because the size-2 2n 2 i OR • Forrelation instance is chosen independently of the smaller instances, and because M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i.
Using techniques analogous to Theorem 32, we obtain the following stronger oracle separation.
Corollary 50. There exists an oracle relative to which P = NP but BQP = QCMA.
Proof sketch. This oracle O will consist of two parts: an oracle A drawn from the same distribution as the oracle A in Corollary 48, and an oracle B that we will construct inductively. For each t ∈ N, we add a region B t that will depend on the previously constructed parts of the oracle. For convenience, we denote by A t the region of A corresponding to inputs of length t, and write Similarly to Theorem 32, we define S t as the set of all NP machines that take less than t bits to specify, run in at most t steps, and query only the O 1 , . . . , O √ t regions of the oracle. Then, we encode into B t the answers to all machines in S t . This has the effect of making P O = NP O , as a polynomial-time algorithm can decide the behavior of any NP O machine M by looking up the relevant bit in B that encodes M 's behavior.
It remains to show that BQP O = QCMA O with probability 1 over O. We achieve this by taking the language L A defined in Corollary 48, which is clearly in QCMA O , and showing that L A ∈ BQP O with probability 1 over O.
Analogous to Lemma 35, one can show that for any t ≤ poly(t), any bit of B t can be computed by an AC 0 2 poly(t) , O(1) circuit whose inputs depend only on A and B 1 , B 2 , . . . , B t . Hence, any BQP O machine that runs in time poly(t) can be computed by a circuit of size 2 poly(t) in which the top gate has bounded-error quantum query complexity poly(t), all of the sub-circuits of the top gate are AC 0 2 poly(t) , O(1) circuits, and the inputs are A and B 1 , B 2 , . . . , B t . In particular, if t = n, then all of the inputs are uncorrelated with L A (0 n ), except for A 2n 2 , the region whose OR • Forrelation instance encodes L A (0 n ). But in that case, we can again appeal to Theorem 47 with M = N = 2 n 2 and T = poly(n) to argue that such a circuit correctly decides L A (0 n ) with probability at most 0.7 for infinitely many n.

PH BQP Lower Bounds for Forrelation • OR
In this section, we construct an oracle relative to which BQP NP ⊂ PH PromiseBQP .
Within this section, for a string z ∈ {0, 1} M and some choice of N , let D z,N denote the following distribution over {0, 1} M N . View x ∼ D z,N as an M × N array of bits sampled as follows: if z i = 0, then the ith row of x is all 0s, while if z i = 1, then the ith row of x has a single 1 chosen uniformly at random and 0s everywhere else.
Our first key lemma shows that, for a string x ∼ D z,N , a quantum algorithm that queries x can be efficiently simulated by a classical query algorithm, with high probability over x. We start with a version of this lemma in which the quantum algorithm makes only a single query.
Lemma 51. Consider a quantum algorithm Q that makes 1 query to x ∈ {0, 1} M N to produce a state |ψ . Then for any K ∈ N, there exists a deterministic classical algorithm that makes K queries to x, and outputs a description of a state |ϕ such that for any α ≥ 8 N and any z ∈ {0, 1} M : Proof. Analogous to Lemma 28, let q i,j be the query magnitude (i.e. probability) with which Q queries x i,j during its single query. That is, if the initial state |ψ 0 of Q has the form: where w are indices over a workspace register, then The classical algorithm is simply the following: query every x i,j such that q i,j ≥ 1 K . Clearly there are at most K such bits, so the algorithm makes at most K queries. Then, calculate Q's post-query state, assuming that all of the unqueried bits are 0. Call this state |ϕ .
We now argue that the classical algorithm achieves the desired approximation to |ψ with the correct probability. Fix some z ∈ {0, 1} M . For each row i with z i = 1, let j(i, x) be the unique column j such that x i,j = 1. Now define a random variable w(i, x) that measures the contribution of row i to the error of our classical simulation: Note that the w(i, x)'s are independent random variables, and also satisfy (7) and linearity of expectation. We also have w(i, x) ≤ 1 K for all i, but we will actually need a stronger upper bound: namely w(i, x) ≤ m i , where Note that m i ≤ 1 K for all i, and also that Recall that we wish to bound the distance between |ψ and |ϕ . (7) implies that and therefore We finally appeal to Hoeffding's inequality (Fact 16) to bound this quantity. Set µ := 1 N and δ := α 2 N 4 − 1. Then where the first line applies (9); the second line applies Fact 16; the third line substitutes (8); and the fourth line uses the assumption that α ≥ 8 N .
Next, by repeated application of Lemma 51, we generalize Lemma 51 to quantum algorithms that make multiple queries.
Lemma 52. Consider a quantum algorithm Q that makes T queries to x ∈ {0, 1} M N to produce a state |ψ T . Then for any K ∈ N, there exists a classical algorithm that makes KT queries to x, and outputs a description of a state |ϕ T such that for any α ≥ 8 N and any z ∈ {0, 1} M : Proof. View Q as a sequence of T 1-query algorithms Q 1 , Q 2 , . . . , Q T , where each Q t is a unitary transformation. For t ≤ T , define |ψ t as the state of Q after t queries. This is to say, if the initial state of Q is |ψ 0 , then for t > 0, |ψ t = Q t |ψ t−1 . Intuitively speaking, the classical simulation algorithm simply applies the algorithm from Lemma 51 T times consecutively. In slightly more detail, let |ϕ 0 := |ψ 0 . For t > 0, define |ϕ t inductively as the state obtained after applying the classical algorithm from Lemma 51 corresponding to Q t |ψ t−1 . Then clearly |ϕ T is computable by a classical algorithm that makes KT queries to x.
It remains to show that |ψ T and |ϕ T are close with high probability. For t ≤ T , define |γ t as the state obtained by applying the classical algorithm for the first t steps and the quantum algorithm for the remaining T − t steps, i.e.
Note that |γ 0 = |ψ T and |γ T = |ϕ T . From this, we may bound: where the second line holds by the triangle inequality, and the last line holds because the Q t 's are unitary transformations. Lemma 51 implies that all of the terms in this sum are bounded with high probability. In particular, we conclude: where the first line applies (10), the second line holds by a union bound, and the last line holds by Lemma 51.
The next theorem is essentially just a restatement of Lemma 52 with cleaner parameters. It can be understood as a version of the Aaronson-Ambainis conjecture [AA14, Conjecture 1.5] for sparse oracles.
Theorem 53. Consider a quantum algorithm Q that makes T queries to x ∈ {0, 1} M N . Then for any ε ≥ 4T 8 N and δ > 0, there exists a classical algorithm that makes O T 5 ε 4 log T δ queries to x, and that outputs an estimate p such that for any z ∈ {0, 1} M : Proof. Let Q be the quantum algorithm corresponding to f , and let |ψ be the output state of Q on input x immediately before measurement. For some K to be chosen later, consider the classical algorithm corresponding to Q from Lemma 52 that makes KT queries and produces a classical description of a quantum state |ϕ on input x. Let p be the probability that the first bit of |ϕ is measured to be 1 in the computational basis.
[BV97, Lemma 3.6] tells us that on any input x: Choose α = ε 4T , which, by the assumption of the theorem, must also satisfy α ≥ 8 N . By appealing to Lemma 52, we conclude that Thus, we just need to choose K such that T · e − α 4 K 32 ≤ δ, or equivalently: Choosing K = O T 4 ε 4 log T δ completes the theorem, as the classical algorithm makes KT queries.
As a straightforward corollary, we obtain the following functional version of Theorem 53. Proof. Let Q be the quantum query algorithm corresponding to f . Choose ε = 1 6 , and consider running the classical algorithm from Theorem 53 that produces an estimate p of Q's acceptance probability. (The condition of Theorem 53 is satisfied because 4T 8 N ≤ 1 6 ). Define g by: We want to show that g usually agrees with f on inputs drawn from D z,N . Because Q computes f with error at most 1 3 , we have: by Theorem 53. Additionally, D(g) ≤ O T 5 log T δ because g depends only on p.
The next theorem essentially shows that no PH PromiseBQP oracle machine can solve the Forrelation• OR problem (i.e. given an input divided into rows, decide if the ORs of the rows are Forrelated or uniformly random). Let b ∼ {0, 1} be a uniformly random bit. Suppose z ∈ {0, 1} M is sampled such that: • If b = 0, then z is uniformly random.
• If b = 1, then z is drawn from the Forrelation distribution F M . Then: Proof By a union bound over all of the bottom-level gates, observe that from the assumption of Corollary 54, just because g disagrees with f only if at least one of the decision trees disagrees with its corresponding quantum query algorithm. • If z j = 0, then the jth row ofx is all zeros.
• If z j = 1, then the jth row ofx contains a single 1 in the i j th position.
Putting these together, we find that: where the first two lines apply (11) and (12), the third line holds by Theorem 27, and the last line uses the fact that M ≤ quasipoly(N ).
To complete this section, we require the following proposition, which is the same as Proposition 40 but with the role of BQP and Σ P k reversed, and with the extra subtlety that we must also consider queries to promise problems. . We take this f to be the top gate of our circuit, and will replace the inputs of this gate by functions of low quantum query complexity. Recall from Section 2.5 that for b ∈ {0, 1}, a gate labeled by f evaluates to b on input P ∈ {0, 1, ⊥} N if, for every string Q ∈ {0, 1} N that extends P , we have f (Q) = b. Additionally, recall from Section 2.2 that we define queries to a promise problem Π such that: 0 A L (x) = 0 for every language L that extends Π, 1 A L (x) = 1 for every language L that extends Π, ⊥ otherwise.
It follows that, for any promise problem Π, A Π (x) = f Π [p(n)] (or, in plain words, the extension of f to allow inputs in {0, 1, ⊥} is consistent with the extension of A to allow queries to a promise problem).
Let Π be the promise problem decided by B O . Since A Π (x) runs in time at most p(n), it can only query the evaluation of B O on inputs up to length at most p(n). For each y ∈ {0, 1} m with m ≤ p(n), there exists a partial function g y with Q(g y ) ≤ p(m) ≤ p(p(n)) such that, for every oracle O, B O (y) is computed by g y O p(m) .
Consider the circuit C obtained by feeding these functions {g y : . Furthermore, C clearly satisfies the desired size, depth, and structure requirements.
By straightforward techniques, Theorem 55 can be extended to a proof of the following oracle result.
Corollary 57. There exists an oracle relative to which BQP NP ⊂ PH PromiseBQP .
Proof. We construct an oracle A as follows. Let L A be a uniformly random unary language. For each n ∈ N, we add into A a region consisting of a function f n : {0, 1} 2n → {0, 1}. Viewing the truth table of f n as a 2 n × 2 n array of bits, choose f n as follows: • If L A (0 n ) = 0, sample a uniformly random string z of length 2 n , and draw f ∼ D z,2 n .
• If L A (0 n ) = 1, sample z from the Forrelation distribution F 2 n , and draw f ∼ D z,2 n .
Let D be the resulting distribution over oracles A.
We first show that L A ∈ BQP NP A with probability 1 over A ∼ D. To do so, we define a language P A as follows: for a string x ∈ {0, 1} * , P A (x) = 1 if |x| = n and the xth row of f n contains a 1; otherwise P A (x) = 0. Clearly, P A ∈ NP A : to determine if x ∈ P A , nondeterministically guess a string y ∈ {0, 1} n and check if f n (x, y) = 1. Thus, it suffices to show that L A ∈ BQP P A , which we do below. (Note that this proof shares large parts with the proof of Claim 30, only modifying a few parameters.) Claim 58. L A ∈ BQP P A with probability 1 over A.
Proof of Claim. A quantum algorithm can decide whether 0 n ∈ L A in poly(n) time by using the Forrelation distinguishing algorithm A from Theorem 27 on the region of P A corresponding to inputs of length n.
In more detail, let z : {0, 1} n → {0, 1} denote the restriction of P A to inputs of length n. By Theorem 27 we know that: Pr where the probability in the above expression is also taken over the randomness of A. By Markov's inequality, we may conclude: Hence, the BQP promise problem defined by A agrees with L A on 0 n , except with probability at most 3 · 2 −2n . We now appeal to the Borel-Cantelli Lemma to argue that, with probability 1 over A, A correctly decides L A (0 n ) for all but finitely many n ∈ N. We have: Therefore, the probability that A fails on infinitely many inputs 0 n is 0. Hence, A can be modified into a BQP algorithm that decides L A (0 n ) for all n ∈ N, with probability 1 over A ∼ D.
It remains to show that L A ∈ PH PromiseBQP A with probability 1 over A. As we will show, this follows from Theorem 55 in the much same way that Corollary 41 follows from Theorem 39. Fix a Σ P k PromiseBQP oracle machine M . By the union bound, it suffices to show that Let n 1 < n 2 < · · · be an infinite sequence of input lengths, spaced far enough apart (e.g. n i+1 = 2 n i ) such that M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. Then we have that Thus it suffices to show that, for every fixed M , we have p(M, i) ≤ 0.7 for all but finitely many i. Proposition 56 shows that M 's behavior on 0 n i can be computed by a depth-2 circuit of size 2 poly(n i ) in which the top gate is a function in AC 0 2 poly(n i ) , k + 1 , and all of the bottom gates are functions with bounded-error quantum query complexity at most poly(n i ). Theorem 55 with M = N = 2 n i shows that such a circuit correctly evaluates the Forrelation • OR function with probability greater than (say) 0.7 for at most finitely many i. This even holds conditioned on M A correctly deciding 0 n 1 , . . . , 0 n i−1 , because the size-2 2n i Forrelation • OR instance is chosen independently of the smaller instances, and because M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i.

Limitations of the QMA Hierarchy (And Beyond)
In this section, we use random restriction arguments to prove that PP ⊂ QMAH relative to a random oracle.

The Basic Random Restriction Argument
The most basic form of our random restriction argument, though not necessarily its most easily applicable, is given below. The theorem can be understood as stating that if we choose a random subset S of the bits of some input x, then S usually contains a small set K such that the quantum algorithm's acceptance probability cannot change much when any bits of S \ K are flipped. In particular, K serves as a sort of "certificate" of the quantum algorithm's behavior when the bits of S \ K are unrestricted.
Theorem 59 (Random restriction for BQP). Consider a quantum algorithm Q that makes T queries to x ∈ {0, 1} N . Choose k ∈ N. If S ⊆ [N ] is sampled such that each i ∈ [N ] is in S with probability p, then with probability at least 1 − 2e −k/6 , there exists a set K ⊆ S of size at most k such that for every y ∈ {0, 1} N with {i ∈ [N ] : x i = y i } ⊆ S \ K, we have: Proof. We proceed in cases. Suppose k > 2pN . Then, we may simply take the set K = S, which satisfies the theorem whenever |S| ≤ k. By a Chernoff bound (Fact 15) with δ = k pN − 1, the probability that this condition is violated is upper bounded by: where we use the inequality δ 2 2+δ ≥ 1+δ 6 which holds for all δ ≥ 1. In the complementary case, suppose k ≤ 2pN . Recall the definition of the query magnitudes q i from Lemma 28, which are defined in terms of the behavior of Q on x.
Above, the first line applies Lemma 28; the second line holds by the assumption that {i ∈ [N ] : x i = y i } ⊆ S \ K; the third line applies the definition of K to conclude that q i ≤ τ for all i ∈ S \ K; and the last line substitutes |S| ≤ 2pN and τ = 2T p k .

Measuring Closeness of Functions
In order to better make sense of Theorem 59, we introduce some language that allows us to quantify how "close" a pair of partial functions are.
Definition 60. Let f, g : {0, 1} N → {0, 1, ⊥} be partial functions. We say that g disagrees with f on x if x ∈ Dom(f ) and g(x) = f (x). The disagreement of g with respect to f , denoted disagr f (g), is the fraction of inputs on which f and g disagree: If C is a class of partial functions, the disagreement of C with respect to f , denoted disagr f (C), is the minimum disagreement of any function in C with f : Note that the above definition is not symmetric in f and g. We typically think of f as some "target" function, and g as some machine that tries to compute f on the inputs where f is defined. The goal is for g to be consistent with f with good probability; thus we only penalize g if it reports an incorrect answer when f takes a value in {0, 1}. This next few propositions show that disagreement behaves intuitively in various ways. First, we show that disagreement satisfies a sort of "triangle inequality".
Proof. This follows from Definition 60 and a union bound: The next two propositions show that disagreement behaves intuitively with respect to random restrictions. First, we show that disagreement is preserved, in expectation, under random restrictions. = disagr f (g).
Finally, we show that if we perform a sequence of random restrictions, each of which incurs some cost in disagreement, then the disagreement accumulates additively.
Proof. Let g ∈ C be the function (depending on ρ) that minimizes disagr fρ (g), and let h ∈ D be the function (depending on ρ and σ) that minimizes disagr gσ (h). Then we have: where the first line holds by Proposition 61; the second line applies Proposition 62 and linearity of expectation; and the last line holds because of assumptions (a) and (b).

Random Restriction for QMA Queries
With the tools introduced in the previous section, we can state a more intuitive and useful form of our random restriction argument for QMA query algorithms. It states that a random restriction of a QMA query algorithm is close in expectation to a small-width DNF formula.
Theorem 64. Consider a partial function f : Let ρ be a random restriction with Pr[ * ] = p. Let DN F k denote the set of width-k DNFs. Then Eρ disagr fρ (DN F k ) ≤ 2e −k/6 .
Proof. It will be convenient to view the choice of ρ as follows: we choose a string z ∈ {0, 1} N uniformly at random, and then we choose a set S ⊆ [N ] wherein each i ∈ [N ] is included in S independently with probability p. Then, we take ρ to be: Thus, by definition, it holds that f ρ (z| S ) = f (z). Choose g ∈ DN F k as follows, depending on the choice of ρ. For each x ∈ Dom(f ρ ), choose a certificate K x for f ρ on x of minimal size. Define g by: This is to say that we take g to be the OR of all of the chosen 1-certificates of f ρ that have size at most k. Clearly, g is computable by a width-k DNF, so it remains to show that g has small disagreement with respect to f in expectation.
Call the pair (z, S) "good" if either f (z) = 1 or C z| S (f ρ ) ≤ k. Observe that g agrees with f ρ on the input z| S whenever (z, S) is good: • If f (z) = 0, then z| S cannot contain a 1-certificate for f ρ , and so g(z| S ) = f ρ (z| S ) = 0.
• If f (z) = ⊥ then g always agrees with f ρ on z| S .
• Lastly, if f (z) = 1 and C z| S (f ρ ) ≤ k, then z| S certainly contains the certificate K z| S and hence g(z| S ) = f ρ (z| S ) = 1.
Thus we can see that the expected disagreement of g with respect to f satisfies: It remains to prove that most (z, S) are good. Let V (|ψ , z) be the QMA verifier corresponding to f on input z, where |ψ is the witness. Fix z, and let |ψ z be the witness that maximizes Pr[V (|ψ z , z) = 1]. By Theorem 59, for any z ∈ {0, 1} N , with probability at least 1 − 2e −k/6 over S, there exists a set K ⊆ S of size at most k such that for every y ∈ {0, 1} N with {i ∈ [N ] : z i = y i } ∈ S \ K we have: In particular, if f (z) = 1 then Pr[V (|ψ z , y) = 1] ≥ 2 3 − 1 4 > 1 3 , and so f (y) = 0. This is to say that K is a certificate for f ρ on z| S , and therefore C z| S (f ρ ) ≤ k and (z, S) is good.

Application to QMAH
In order to generalize Theorem 64 to QMAH machines, we require the following form of Håstad's switching lemma for DNF formulas [Hås87]. The statement given below, and arguably its simplest proof, are given in an exposition by Thapen [Tha09]. Technically, this is just a weaker statement of Theorem 42, though we prefer the version given here because it makes the constant factor explicit.
Lemma 65 (Switching Lemma). Let f be a width-k DNF. If ρ is a random restriction with Pr[ * ] = q < 1 9 , then for any t > 0, Pr Corollary 66. Let f be a width-k DNF. Denote by D t the set of functions that have deterministic query complexity at most t. If ρ is a random restriction with Pr[ * ] = q < 1 9 , then for any t > 0, we have Eρ [disagr fρ (D t )] ≤ (9qk) t .
With all of these tools in hand, we prove in our next theorem that under an appropriately chosen random restriction, a circuit composed of QMA query gates simplifies to a function that is close (in expectation) to a function with low deterministic query complexity. The proof amounts to a recursive application of Theorem 64 combined with Corollary 66.
This recursive definition implies that: Additionally, a simple inductive calculation shows that N i takes the closed form: We view ρ as a sequence of restrictions ρ 1 , . . . , ρ d in which ρ i has Pr[ * ] = p i q, where q = e −1/6 9k (one can easily verify from (13) and (14) that d i=1 p i q equals the probability given in the statement in the theorem). We view each ρ i itself as the composition of two random restrictions, one with Pr[ * ] = p i and one with Pr[ * ] = q.
We proceed in cases. Suppose k > N d . Let S = {i ∈ [N ] : ρ(i) = * } denote the set of unrestricted variables. Notice that disagr fρ (D k ) = 0 whenever |S| ≤ k, just because D k contains all total functions on at most k bits. Let δ = k N ·Pr[ * ] − 1. By (13), which implies that δ ≥ 1. By a Chernoff bound (Fact 15), this implies that: where we use the inequality δ 2 2+δ ≥ 1+δ 6 which holds for all δ ≥ 1. Thus, the theorem is proved in this k > N d case.
In the complementary case, suppose k ≤ N d . Let C i be the class of functions such that for all g ∈ C i : (a) g is computable by a circuit with the same structure as f , except that the gates at distance 13 at most i from the input are eliminated and the gates at distance i + 1 make at most Rk queries (or, if i = d, D(g) ≤ k).
(b) g depends on at most N i inputs.
By convention, let C 0 = {f }. With this definition, the statement of the theorem follows from Proposition 63 and an inductive application of the following claim: Claim 68. For all g ∈ C i−1 , Eρ i disagr gρ i (C i ) ≤ 4e −k/6 · s i , where s i is the number of gates at distance exactly i from the inputs in the circuit that computes f . Proof of Claim. Consider applying ρ i to g. After the random restriction with Pr[ * ] = p i , by a Chernoff bound (Fact 15) and because g depends on at most N i−1 variables, the resulting function depends on at most N i = 2p i N i−1 variables, except with probability at most e −N i /6 ≤ e −N d /6 ≤ e −k/6 over this first restriction. 14 Additionally, by Theorem 64 with T = Rk and p = p i , because g is a function of at most N i−1 variables, there exist width-k DNFs that each have expected disagreement at most 2e −k/6 with respect to the corresponding bottom-layer QMA gates of the circuit that computes g ρ i .
After the next random restriction with Pr[ * ] = q, by Corollary 66, these width-k DNFs each have expected disagreement at most e −k/6 from functions of deterministic query complexity at most k. Hence, by Proposition 63, viewing ρ i as the composition of these two random restrictions, each bottom-layer QMA gate in the circuit that computes g ρ i has expected disagreement at most 3e −k/6 from a function of deterministic query complexity at most k.
Let h be a function depending on ρ i , chosen as follows. Take h to be the all zeros function if g ρ i depends on more than N i variables; otherwise let h be the function obtained from g by replacing the bottom-level gates of the circuit that computes g with the corresponding functions of deterministic query complexity k. We verify that h ∈ C i : (a) We can absorb the functions of query complexity k into the next layer of QMA gates, increasing the query complexity of each gate by a multiplicative factor of k. Alternatively, if i = d, then D(h) ≤ k just because g consists of a single gate.
(b) Either g ρ i depends on at most N i variables, or else h is trivial; in either case h depends on at most N i inputs.
We now demonstrate that Eρ i disagr gρ i (h) ≤ 4e −k/6 · s i . Notice that h never disagrees with g ρ i on input x, unless either (1) g ρ i depends on more than N i variables, or (2) one of the functions of deterministic query complexity k disagrees with its corresponding QMA gate on x. Hence, by a union bound, This completes the theorem in the k ≤ N d case.
As a corollary, we obtain the following result, which shows that small circuits composed of functions with low QMA query complexity cannot compute the Parity function. Proof. Choose k = 6 ln (5s/ε) ≤ polylog(N ). Let ρ be a random restriction where p = Pr[ * ] is the probability given in the statement of Theorem 67. A simple calculation shows that pN ≥ N Ω(1) polylog(N ) ; hence k ≤ pN 2 for sufficiently large N . Let g ∈ D k be the function (depending on ρ) that minimizes disagr fρ (g). With this, we have the following chain of inequalities: Above, the first line holds by Proposition 62; the second line holds by Proposition 61; the third line applies linearity of expectation along with the bound from Theorem 67; the fourth line uses the fact that any function of deterministic query complexity k disagrees with the (k + 1)-bit parity function It remains to show that L O ∈ QMAH O . (The remainder of this proof is largely the same as our other oracle separations that follow from circuit lower bounds.) Fix a QMAH oracle machine M . By the union bound, it suffices to show that Let n 1 < n 2 < · · · be an infinite sequence of input lengths, spaced far enough apart (e.g. n i+1 = 2 n i ) such that M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i. Thus it suffices to show that, for every fixed M , we have p(M, i) ≤ 0.7 for all but finitely many i. Proposition 70 shows that M 's behavior on 0 n i can be computed by a circuit of size at most 2 poly(n i ) and depth O(1) in which each gate has QMA query complexity at most poly(n i ). Corollary 69 with N = 2 n i , R = poly(n i ), and ε = 0.2 shows that such a circuit correctly evaluates the Parity N function with probability greater than 0.7 for at most finitely many i. This even holds conditioned on M O correctly deciding 0 n 1 , . . . , 0 n i−1 , because the size-2 n i Parity instance is chosen independently of the smaller instances, and because M (0 n i ) can query the oracle on strings of length n i+1 or greater for at most finitely many values of i.

Beyond QMAH
Our proof that PP ⊂ QMAH relative to a random oracle also extends to complexity classes that are potentially much stronger than QMAH. This is because our definition of QMA query complexity (Definition 19) only depends on the number of queries made by the verifier, and not on the length of the witness state. Hence, QMA query complexity actually upper bounds the relativized power of almost any complexity class that involves interactive proofs with a polynomial-time quantum verifier, including QMA(2) [KMY03], QSZK [Wat02], and QMIP [KM03]. To illustrate, we argue briefly that PP ⊂ QMIP PromiseQMIP PromiseQMIP ··· relative to a random oracle. Recall that PromiseQMIP is the set of promise problems Π for which there exists an efficient quantum multiprover interactive proof system: a communication protocol in which one or more provers communicate with a verifier, trying to convince the verifier that Π(x) = 1. The verifier is a polynomial time machine that can send and receive quantum messages. The provers are computationally unbounded, and may share an entangled state at the start of the protocol. Otherwise, the provers are not allowed to communicate with each other during the protocol. Then, Π(x) = 1 if there exists a prover strategy that causes the verifier to accept with probability at least 2 3 , while Π(x) = 0 if, for every prover strategy, the verifier accepts with probability at most 1 3 . The key observation is that a poly(n)-time QMIP oracle protocol can be simulated by a poly(n)query QMA protocol in which the verifier receives an arbitrarily long witness, and the verifier is computationally unbounded. In this QMA protocol, the witness is interpreted as a string that is purported to encode the answers to all oracle queries on at most poly(n) bits. The verifier then simulates the QMIP protocol, choosing the prover strategy that causes the QMIP verifier to accept with the greatest possible probability when the oracle is consistent with the given witness.
Finding this optimal strategy is merely a computational problem, and so the QMA verifier remains query-efficient.
Thus, we can extend Proposition 70 from QMAH oracle machines to QMIP PromiseQMIP PromiseQMIP ··· oracle machines. It follows, using the same proof as Corollary 71, that PP ⊂ QMIP PromiseQMIP PromiseQMIP ··· relative to a random oracle-despite the fact that QMIP = MIP * = RE in the unrelativized world [RUV13, JNV + 20]! 6 Open Problems 6.1 Oracles where BQP = EXP We construct oracles relative to which BQP = P #P and yet either PH is infinite (Theorem 29), or P = NP (Theorem 32). Can these be strengthened to oracles where we also have BQP = EXP?
The main challenge in generalizing our proofs is that P #P machines, unlike EXP machines, have a polynomial upper bound on the length of the queries they can make. This property allowed us to encode the behavior of a P #P machine M into a part of the oracle that M cannot query, but that a BQP machine with a larger polynomial running time can query. Alas, such a simple trick will not work when M is an EXP machine. Nevertheless, there exist alternative tools that can collapse EXP to such weaker complexity classes. For instance, Heller [Hel86] gives an oracle relative to which BPP = EXP. Beigel and Maciel [BM99] even construct an oracle relative to which P = NP and ⊕P = EXP, using AC 0 circuit lower bounds for the Parity problem that are analogous to the lower bounds we use for Forrelation.

Finer Control over BQP and PH
Recall Conjecture 5, which states that for every k, there exists an oracle relative to which Σ P k ⊆ BQP but Σ P k+1 ⊂ BQP. We conjecture more strongly that a small modification of the oracle O constructed in Theorem 29 achieves this. Recall that O consists of a random oracle A, and an oracle B that recursively hides the answers to all possible P #P O queries in instances of the Forrelation problem. The idea is simply to modify the definition of B so that it instead encodes the outputs of Σ P k machines instead of P #P machines.
Our intuition is that, because the Forrelation instances look random to Σ P k machines, a Σ P k machine should not be able to recursively reason about B. Thus, a BQP machine that queries O = (A, B) should be effectively no more powerful than a BQP Σ P k machine that queries only A. If this intuition can be made precise, then one could possibly appeal to our proof that Σ P k+1 ⊂ BQP Σ P k relative to a random oracle. Of course, we could not get this proof strategy to work-otherwise, we would not have needed the machinery surrounding sensitivity concentration of AC 0 circuits in order to get an oracle where NP BQP ⊂ BQP NP ! We now sketch what we consider a viable alternative approach towards showing that our conjectured oracle separation holds. Instead of the "top-down" view taken above, where one tries to argue that a Σ P k machine gains no benefit from making recursive queries to B, one might instead attempt a "bottom-up" approach, where one uses the structure of the target Σ P k+1 problem (the Sipser k+2 function) to argue that each bit of B has only minimal correlation with the answer, starting with the parts of B that are constructed first. Very roughly speaking, our idea would be to combine the random projection technique of [HRST17] with some generalization of the AC 0 sensitivity concentration bounds that we prove in Section 4.2.
In slightly more detail, we would first hit A with a random projection, one that with high probability turns the Sipser k+2 function into an AND of large fan-in, while turning any Σ P A k machine into a low-depth decision tree. Then, we would want to argue that if we fix the unrestricted variables of A to all 1s, and choose Forrelation instances in B consistent with this, then each bit of B is unlikely to flip if we instead randomly change a few bits of A to 0s, and resample the Forrelation instances of B corresponding to Σ P k machines that return different answers. If this could be shown, then as in Theorem 39, an appeal to Lemma 37 (which is a modification of the BBBV Theorem [BBBV97]) ought to be sufficient to argue that a BQP O machine could not compute the Sipser k+2 function.
For the bits of B corresponding to the bottom-level Σ P k machines that only query A directly, this is easy to show, as a low-depth decision tree is unlikely to query any 0s under a distribution of mostly 1s. However, for the higher levels of B corresponding to Σ P k machines that can query the earlier bits of B, this becomes more challenging: we have to argue that a Σ P k machine that queries a long list of Forrelation instances is unlikely to return a different answer when we randomly flip a few of the instances between the uniform and Forrelated distributions. This might require a generalization of Lemma 46 in which (1) the string x is not just uniformly random, but is an arbitrary sequence of Forrelated and uniformly random rows, and (2) instead of flipping a single random row of x from uniformly random to Forrelated, we flip an arbitrary subset of the rows between random and Forrelated, subject only to the constraint that the probability of any individual row being chosen is small.
If this problem is too difficult, it remains interesting, in our view, to give an oracle where NP ⊆ BQP but PH ⊂ BQP. This would merely require proving our proposed generalization of Lemma 46 for low-width DNF formulas, as opposed to arbitrary AC 0 circuits of quasipolynomial size.

Stronger Random Restriction Lemmas
Can one prove a sharper version of our random restriction lemma for QMA query algorithms (Theorem 64)? Unlike the switching lemma for DNF formulas (Lemma 65), our result has a quantitative dependence on the number of inputs N . Thus, whereas a polylog(N )-width DNF simplifies (to a low-depth decision tree, with high probability) under a random restriction with Pr[ * ] = 1 polylog(N ) , we can only show that a polylog(N )-query QMA algorithm simplifies under a random restriction with Pr[ * ] = 1 √ N polylog(N ) , which leaves much fewer unrestricted variables. We see no reason why such a dependence on N should be necessary, and we conjecture that a polylog(N )query QMA algorithm should simplify greatly under a random restriction with Pr[ * ] = 1 polylog(N ) . It would be interesting to see whether one could prove this even without a bound on the QMA witness length, as we do in our proofs.
It is also worth exploring whether our random restriction lemma could be generalized to other classes of functions. Our argument works for functions of low quantum query complexity, so it is natural to ask: is there a comparable random restriction lemma for bounded low-degree polynomials, and thus functions of low approximate degree? Kabanets, Kane, and Lu [KKL17] exhibit a random restriction lemma for polynomial threshold functions, an even stronger class of functions, though their bounds become very weak when the degree is much larger than √ log N . We conjecture that an analogue of Theorem 64 should hold if we replace low QMA query complexity by low approximate degree, perhaps even with better quantitative parameters. 16 6.4 Collapsing QMAH to P In Corollary 71, we gave an oracle relative to which PP ⊂ QMAH (indeed, we showed that this holds even for a random oracle). Can one generalize this to an oracle relative to which P = QMA = QMAH = PP? A priori, it might seem that one could use techniques similar to the ones we used in Theorem 32 to set P = NP while still keeping P = P #P . That is, the idea would be to start with a random oracle A, then inductively construct an oracle B, recursively encoding into B answers to all QMA machines that query earlier parts of A and B. One would then hope to prove an analogue of Lemma 35, showing that the bits of B can be computed by small low-depth circuits where the gates are functions of low QMA query complexity, and the inputs are in A. Finally, one could appeal to Corollary 69 to argue that such a circuit cannot compute Parity.
The main issue is that QMA is a semantic complexity class, in contrast to NP, which is a syntactic complexity class. This is to say that every NP machine defines a language, whereas a QMA machine only defines a promise problem. Hence, it is not clear how B should answer on machines that fail to satisfy the QMA promise without "leaking" information that would otherwise be difficult to compute. Even if we, say, assign those bits of B randomly, we can no longer argue that those bits are computable by a QMA query algorithm, which would break our idea for generalizing Lemma 35.
To illustrate the difficulty in constructing such an oracle, we describe an example of an oracle O = (A, B) that fails to put PP outside QMAH. We start by taking a random oracle A. Then, we inductively construct B, where each bit of B encodes the behavior of a QMA O verifier M, x , where M can query the previously constructed parts of the oracle, as follows. We let p := max |ψ Pr[M (x, |ψ )] = 1, and then we randomly choose the encoded bit to be 1 with probability p and 0 with probability 1 − p. This is to say that we set the bit to 1 with probability equaling the acceptance probability of the QMA verifier, maximized over all possible witness states |ψ .
Unfortunately, while one can easily show that BPP O = QMA O , O also allows an algorithm to "pull the randomness out" of a quantum algorithm, which makes O much more powerful than it seems! By padding M, x with extra bits, one can obtain from the oracle arbitrarily many independent bits sampled with bias p. Because PH O ⊆ BPP O , a BPP O machine can run Stockmeyer's algorithm [Sto83] on these samples to obtain a multiplicative approximation of any such p. In particular, this implies that the quantum approximate counting problem, defined in Section 1.3, is in BPP O . But the quantum approximate counting problem is PP O -hard [Kup15], so we also have BPP O = PP O . Hence, any oracle that makes P = QMA = PP would have to choose a more careful encoding of the answers to QMA problems than the one described here.