# The Acrobatics of $\mathsf{BQP}$

Scott Aaronson University of Texas at Austin. Email<EMAIL_ADDRESS>Supported by a Vannevar Bush Fellowship from the US Department of Defense, a
Simons Investigator Award, and the Simons “It from Qubit” collaboration. DeVon
Ingram University of Chicago. Email<EMAIL_ADDRESS>Supported by an NSF
Graduate Research Fellowship. William Kretschmer University of Texas at
Austin. Email<EMAIL_ADDRESS>Supported by an NDSEG Fellowship.

###### Abstract

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}^{\mathsf{BQP}}\not\subset\mathsf{BQP}^{\mathsf{PH}}$, resolving a
2005 problem of Fortnow. Interpreted another way, we show that
$\mathsf{AC^{0}}$ circuits cannot perform useful homomorphic encryption on
instances of the Forrelation problem. 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}^{\mathsf{NP}}\not\subset\mathsf{PH}^{\mathsf{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}}}$, and more generally
$\mathsf{PP}\not\subset(\mathsf{MIP}^{*})^{(\mathsf{MIP}^{*})^{(\mathsf{MIP}^{*})^{\cdots}}}$
(!), despite the fact that $\mathsf{MIP}^{\ast}=\mathsf{RE}$ in the
unrelativized world. This result shows that there is no black-box quantum
analogue of Stockmeyer’s approximate counting algorithm.

  * •

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. (By contrast, if
$\mathsf{NP}\subseteq\mathsf{BPP}$, then $\mathsf{PH}$ collapses relative to
all oracles.)

  * •

There exists an oracle relative to which
$\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P}^{\mathsf{\\#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.

###### Contents

  1. 1 Introduction
    1. 1.1 The Contrast with $\mathsf{BPP}$
    2. 1.2 Relativization
    3. 1.3 Our Results
    4. 1.4 Proof Techniques
  2. 2 Preliminaries
    1. 2.1 Notation and Basic Tools
    2. 2.2 Complexity Classes
    3. 2.3 Query Complexity and Related Measures
    4. 2.4 Random Restrictions
    5. 2.5 Circuit Complexity
    6. 2.6 Other Background
  3. 3 Consequences of the Raz-Tal Theorem
    1. 3.1 Relativizing (Non-)Implications of $\mathsf{NP}\subseteq\mathsf{BQP}$
    2. 3.2 Weak $\mathsf{NP}$, Strong $\mathsf{BQP}$
  4. 4 Fine Control over $\mathsf{BQP}$ and $\mathsf{PH}$
    1. 4.1 $\mathsf{BQP}^{\mathsf{PH}}$ Lower Bounds for Sipser Functions
    2. 4.2 $\mathsf{BQP}^{\mathsf{PH}}$ Lower Bounds for $\textsc{OR}\circ\textsc{Forrelation}$
    3. 4.3 $\mathsf{PH}^{\mathsf{BQP}}$ Lower Bounds for $\textsc{Forrelation}\circ\textsc{OR}$
  5. 5 Limitations of the $\mathsf{QMA}$ Hierarchy (And Beyond)
    1. 5.1 The Basic Random Restriction Argument
    2. 5.2 Measuring Closeness of Functions
    3. 5.3 Random Restriction for $\mathsf{QMA}$ Query Algorithms
    4. 5.4 Application to $\mathsf{QMAH}$
  6. 6 Open Problems
    1. 6.1 Oracles where $\mathsf{BQP}=\mathsf{EXP}$
    2. 6.2 Finer Control over $\mathsf{BQP}$ and $\mathsf{PH}$
    3. 6.3 Stronger Random Restriction Lemmas
    4. 6.4 Collapsing $\mathsf{QMAH}$ to $\mathsf{P}$
  7. 7 Acknowledgments

##  1 Introduction

The complexity-theoretic study of quantum computation is often dated from
1993, when Bernstein and Vazirani [BV97] defined $\mathsf{BQP}$, or Bounded-
Error Quantum Polynomial-Time: the class of languages that admit efficient
quantum algorithms. Then as now, a central concern was how $\mathsf{BQP}$
relates to classical complexity classes, such as $\mathsf{P}$, $\mathsf{NP}$,
and $\mathsf{PH}$. Among the countless questions that one could raise here,
let us single out three as especially fundamental:

  1. (1)

Can quantum computers efficiently solve any problems that classical computers
cannot? In other words, does $\mathsf{BPP}=\mathsf{BQP}$?

  2. (2)

Can quantum computers solve $\mathsf{NP}$-complete problems in polynomial
time? In other words, is $\mathsf{NP}\subseteq\mathsf{BQP}$?

  3. (3)

What is the best classical upper bound on the power of quantum computation? Is
$\mathsf{BQP}\subseteq\mathsf{NP}$? Is $\mathsf{BQP}\subseteq\mathsf{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 $\mathsf{BQP}\not\subset\mathsf{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
$\mathsf{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 $\mathsf{BQP}$. Bernstein and
Vazirani [BV97] showed that
$\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{P^{\\#P}}$, and Adleman,
DeMarrais, and Huang [ADH97] improved the upper bound to
$\mathsf{BQP}\subseteq\mathsf{PP}$, giving us the following chain of
inclusions:

$\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{P^{\\#P}}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}.$

Fortnow and Rogers [FR98] slightly strengthened the inclusion
$\mathsf{BQP}\subseteq\mathsf{PP}$, to show for example that
$\mathsf{PP^{BQP}}=\mathsf{PP}$. This complemented the result of Bennett,
Bernstein, Brassard, and Vazirani [BBBV97] that
$\mathsf{BQP^{BQP}}=\mathsf{BQP}$: that is, $\mathsf{BQP}$ is “self-low,” or
“the $\mathsf{BQP}$ hierarchy collapses to $\mathsf{BQP}$.”

###  1.1 The Contrast with $\mathsf{BPP}$

Meanwhile, though, the relationships between $\mathsf{BQP}$ and complexity
classes like $\mathsf{NP}$, $\mathsf{PH}$, and $\mathsf{P/poly}$ have remained
mysterious. Besides the fundamental questions mentioned above—is
$\mathsf{NP}\subseteq\mathsf{BQP}$? is $\mathsf{BQP}\subseteq\mathsf{NP}$? is
$\mathsf{BQP}\subseteq\mathsf{PH}$?—one could ask other questions:

  1. (i)

In a 2005 blog post, Fortnow [For05] raised the question of whether
$\mathsf{NP^{BQP}}\subseteq\mathsf{BQP^{NP}}$. Do we even have
$\mathsf{NP^{BQP}}\subseteq\mathsf{BQP^{PH}}$? I.e., when quantum computation
is combined with classical nondeterminism, how does the order of combination
matter?

  2. (ii)

What about the converse: is $\mathsf{BQP^{NP}}\subseteq\mathsf{PH^{BQP}}$?

  3. (iii)

Suppose $\mathsf{NP}\subseteq\mathsf{BQP}$. Does it follow that
$\mathsf{PH}\subseteq\mathsf{BQP}$ as well?

  4. (iv)

Suppose $\mathsf{NP}\subseteq\mathsf{BQP}$. Does it follow that $\mathsf{PH}$
collapses?

  5. (v)

Is $\mathsf{BQP}\subset\mathsf{P/poly}$?

  6. (vi)

Suppose $\mathsf{P}=\mathsf{NP}$. Does it follow that $\mathsf{BQP}$ is
“small” (say, not equal to $\mathsf{EXP}$)?

  7. (vii)

Suppose $\mathsf{P}=\mathsf{NP}$. Does it follow that
$\mathsf{BQP}=\mathsf{QCMA}$, where $\mathsf{QCMA}$ (Quantum Classical Merlin
Arthur) is the analogue of $\mathsf{NP}$ with a $\mathsf{BQP}$ verifier?

What is particularly noteworthy about the questions above is that, if we
replace $\mathsf{BQP}$ by $\mathsf{BPP}$, then positive answers are known to
all of them:

  1. (i)

$\mathsf{NP}^{\mathsf{BPP}}\subseteq\mathsf{AM}\subseteq\mathsf{BPP}^{\mathsf{NP}}$.

  2. (ii)

$\mathsf{BPP}^{\mathsf{NP}}\subseteq\mathsf{PH}=\mathsf{PH}^{\mathsf{BPP}}$.

  3. (iii)

If $\mathsf{NP}\subseteq\mathsf{BPP}$, then $\mathsf{PH}=\mathsf{BPP}$—this is
sometimes given as a homework exercise in complexity theory courses, and also
follows from (i).

  4. (iv)

If $\mathsf{NP}\subseteq\mathsf{BPP}$, then
$\mathsf{PH}=\mathsf{\Sigma}_{2}^{\mathsf{P}}$—this follows from (iii) and the
Sipser-Lautemann Theorem [Sip83, Lau83].

  5. (v)

$\mathsf{BPP}\subset\mathsf{P/poly}$ is Adleman’s Theorem [Adl78].

  6. (vi)

If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{P}=\mathsf{BPP}$ and hence
$\mathsf{BPP}\neq\mathsf{EXP}$, by the time hierarchy theorem.

  7. (vii)

If $\mathsf{P}=\mathsf{NP}$, then of course $\mathsf{BPP}=\mathsf{MA}$.

So what is it that distinguishes $\mathsf{BPP}$ from $\mathsf{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 $\mathcal{D}$ over $n$-bit
strings such that even estimating the probabilities of the outcomes is a
$\mathsf{\\#P}$-hard problem. Meanwhile, though, if there were a polynomial-
time classical randomized algorithm $M(x,r)$ to sample from the same
distribution $\mathcal{D}$, then one could use the “pulling out $r$” trick to
estimate the probabilities of $M$’s outcomes in $\mathsf{PH}$. But this would
put $\mathsf{P}^{\mathsf{\\#P}}$ into $\mathsf{PH}$, thereby collapsing
$\mathsf{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 $\mathsf{BQP}$ behave more like $\mathsf{BPP}$? For questions like
whether $\mathsf{NP}\subseteq\mathsf{BQP}$ or whether
$\mathsf{BQP}\subseteq\mathsf{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 $\mathsf{NP}\subseteq\mathsf{BQP}$ and
$\mathsf{BQP}\subseteq\mathsf{AM}$. Then since $\mathsf{BQP}$ is closed under
complement, we would also have $\mathsf{coNP}\subseteq\mathsf{BQP}$, and hence
$\mathsf{coNP}\subseteq\mathsf{AM}$, which is known to imply a collapse of
$\mathsf{PH}$ [BHZ87]. And thus, if $\mathsf{PH}$ is infinite, then either
$\mathsf{NP}\not\subset\mathsf{BQP}$ or $\mathsf{BQP}\not\subset\mathsf{AM}$.
How can we say anything more interesting and nontrivial?

###  1.2 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
specially-constructed 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 $\mathsf{IP}=\mathsf{PSPACE}$ [Sha92],
$\mathsf{MIP}=\mathsf{NEXP}$ [BFL91], and more recently,
$\mathsf{MIP}^{*}=\mathsf{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 $\mathsf{NP}\subseteq\mathsf{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 $\mathsf{BPP}^{A}\neq\mathsf{BQP}^{A}$.
Shortly afterward, Simon [Sim97] gave a quantitatively stronger oracle
separation between $\mathsf{BPP}$ and $\mathsf{BQP}$, and then Shor [Sho99]
gave a still stronger separation, along the way to his famous discovery that
Factoring is in $\mathsf{BQP}$.

On the negative side, Bennett, Bernstein, Brassard, and Vazirani [BBBV97]
showed that there exists an oracle relative to which
$\mathsf{NP}\not\subset\mathsf{BQP}$: indeed, relative to which there are
problems that take $n$ time for an $\mathsf{NP}$ machine but
$\Omega\left(2^{n/2}\right)$ time for a $\mathsf{BQP}$ machine. Following the
discovery of Grover’s algorithm [Gro96], which quantumly searches any list of
$N$ items in $O\left(\sqrt{N}\right)$ 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
$\mathsf{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 $\mathsf{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
$\mathsf{P}=\mathsf{BQP}$—for example, a $\mathsf{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
$\mathsf{P}=\mathsf{BQP}$ and yet $\mathsf{PH}$ is infinite. In other words,
if $\mathsf{P}=\mathsf{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 $\mathsf{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
$\mathsf{PH}$ collapses—then nonrelativizing techniques will be needed there
as well.

What about showing the power of $\mathsf{BQP}$, by giving oracle obstructions
to containments like $\mathsf{BQP}\subseteq\mathsf{NP}$, or
$\mathsf{BQP}\subseteq\mathsf{PH}$? There, until recently, the progress was
much more limited. Watrous [Wat00] showed that there exists an oracle relative
to which $\mathsf{BQP}\not\subset\mathsf{NP}$ and even
$\mathsf{BQP}\not\subset\mathsf{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 $\mathsf{BQP}\not\subset\mathsf{PH}$ or even
$\mathsf{BQP}\not\subset\mathsf{AM}$, remained an open problem for two
decades. Aaronson [Aar10] proposed a program for proving an oracle separation
between $\mathsf{BQP}$ and $\mathsf{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}\to\\{1,-1\\}$, and promised that either

  1. (i)

$f$ and $g$ are uniformly random and independent, or

  2. (ii)

$f$ and $g$ are uniformly random individually, but $g$ has $\Omega(1)$
correlation with $\hat{f}$, 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 $\Omega\left(2^{n/4}\right)$ queries—improved by Aaronson and Ambainis
[AA18] to $\Omega\left(\frac{2^{n/2}}{n}\right)$ queries, which is essentially
tight. The central conjecture, which Aaronson left open, said that
$\textsc{Forrelation}\not\in\mathsf{PH}$—or equivalently, that there are no
$\mathsf{AC^{0}}$ circuits for Forrelation of constant depth and
$2^{\mathrm{poly}(n)}$ size.

Finally, Raz and Tal [RT19] managed to prove Aaronson’s conjecture, and
thereby obtain the long-sought oracle separation between $\mathsf{BQP}$ and
$\mathsf{PH}$.111Strictly speaking, they did this for a variant of Forrelation
where the correlation between $g$ and $\hat{f}$ is only $\sim\frac{1}{n}$, and
thus a quantum algorithm needs $\sim n$ queries to solve the problem, but this
will not affect anything that follows. 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 $\mathsf{AC^{0}}$ functions. Relevantly for us, Raz and Tal actually proved
the following stronger result:

######  Theorem 2 ([RT19]).

A $\mathsf{PH}$ machine can guess whether $f$ and $g$ are uniform or
Forrelated with bias at most $2^{-\Omega(n)}$.

Recall that before Raz and Tal, we did not even have an oracle relative to
which $\mathsf{BQP}\not\subset\mathsf{AM}$. Notice that, if
$\mathsf{BQP}\subseteq\mathsf{AM}$, then many other conclusions would follow
in a relativizing way. For example, we would have:

  * •

$\mathsf{P}=\mathsf{NP}$ implies $\mathsf{P}=\mathsf{BQP}$,

  * •

$\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{NP}^{\mathsf{AM}\cap\mathsf{coAM}}\subseteq\mathsf{BPP}^{\mathsf{NP}}\subseteq\mathsf{BQP}^{\mathsf{NP}}$,

  * •

If $\mathsf{NP}\subseteq\mathsf{BQP}$, then
$\mathsf{NP}^{\mathsf{NP}}\subseteq\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{BQP}^{\mathsf{NP}}=\mathsf{BQP}^{\mathsf{BQP}}=\mathsf{BQP}$,
and

  * •

If $\mathsf{NP}\subseteq\mathsf{BQP}$, then
$\mathsf{NP}\subseteq\mathsf{coAM}$, which implies that $\mathsf{PH}$
collapses.

Looking at it a different way, our inability even to separate $\mathsf{BQP}$
from $\mathsf{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” $\mathsf{BQP}$ from
$\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{PH}$, by showing that there are no
relativizing obstructions to any possible answers to questions like the ones
we asked in Section 1.1?

###  1.3 Our Results

We achieve new oracle separations that show an astonishing range of possible
behaviors for $\mathsf{BQP}$ and related complexity classes—in at least one
case, resolving a longstanding open problem in this topic. Our title, “The
Acrobatics of $\mathsf{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.

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 $\mathsf{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
$\mathsf{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.

######  Theorem 3 (Corollary 43, restated).

There exists an oracle relative to which
$\mathsf{NP}^{\mathsf{BQP}}\not\subset\mathsf{BQP}^{\mathsf{NP}}$, and indeed
$\mathsf{NP}^{\mathsf{BQP}}\not\subset\mathsf{BQP}^{\mathsf{PH}}$.

As mentioned earlier, Theorem 3 resolves an open problem of Fortnow [For05],
and demonstrates another clear difference between $\mathsf{BPP}$ and
$\mathsf{BQP}$.

As a straightforward byproduct of Theorem 3, we are also able to prove the
following:

######  Theorem 4 (Corollary 45, restated).

There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but
$\mathsf{BQP}\neq\mathsf{QCMA}$.

Conversely, it will follow from one of our later results, Theorem 9, that
there exists an oracle relative to which $\mathsf{P}\neq\mathsf{NP}$ and yet
$\mathsf{BQP}=\mathsf{QCMA}=\mathsf{QMA}$. In other words, as far as
relativizing techniques are concerned, the classical and quantum versions of
the $\mathsf{P}$ vs. $\mathsf{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 $\mathsf{NP}\subseteq\mathsf{BQP}$
but $\mathsf{PH}\not\subset\mathsf{BQP}$. Indeed, for every $k\in\mathbb{N}$,
there exists an oracle relative to which
$\mathsf{\Sigma}_{k}^{\mathsf{P}}\subseteq\mathsf{BQP}$ but
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}\not\subset\mathsf{BQP}$.

5 would provide spectacularly fine control over the relationship between
$\mathsf{BQP}$ and $\mathsf{PH}$, going far beyond Raz-Tal to show how
$\mathsf{BQP}$ could, e.g., swallow the first $18$ levels of $\mathsf{PH}$
without swallowing the $19$th. To see the connection between Theorem 3 and 5,
suppose $\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{BQP}^{\mathsf{NP}}$, and
suppose also that $\mathsf{NP}\subseteq\mathsf{BQP}$. Then, as observed by
Fortnow [For05], this would imply

$\mathsf{NP}^{\mathsf{NP}}\subseteq\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{BQP}^{\mathsf{NP}}\subseteq\mathsf{BQP}^{\mathsf{BQP}}=\mathsf{BQP},$

(and so on, for all higher levels of $\mathsf{PH}$), so that
$\mathsf{PH}\subseteq\mathsf{BQP}$ as well. Hence, any oracle that witnesses 5
also witnesses Theorem 3, so our proof of Theorem 3 is indeed a prerequisite
to 5.

Our proof of Theorem 3 also reveals additional remarkable structure (or a lack
thereof) involving the relation between the Forrelation problem and
$\mathsf{AC^{0}}$ circuits. At a high level, we prove Theorem 3 by showing
that no $\mathsf{BQP}^{\mathsf{PH}}$ algorithm can solve the
$\textsc{OR}\circ\textsc{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 $\mathsf{PH}$ machines should gain no useful
information from the input, just because Forrelation “looks random” (by Raz-
Tal), and hence a $\mathsf{BQP}^{\mathsf{PH}}$ machine should have roughly the
same power as a $\mathsf{BQP}$ machine at deciding
$\textsc{OR}\circ\textsc{Forrelation}$. If one could show this, then
completing the theorem would amount to showing that
$\textsc{OR}\circ\textsc{Forrelation}$ is hard for $\mathsf{BQP}$ machines,
which easily follows from the BBBV Theorem [BBBV97].

Alas, initial attempts to formalize this intuition fail for a single, crucial
reason: homomorphic encryption exists! The Raz-Tal Theorem merely proves that
Forrelation is a strong form of encryption against $\mathsf{PH}$ algorithms.
But to rule out a $\mathsf{BQP}^{\mathsf{PH}}$ algorithm for
$\textsc{OR}\circ\textsc{Forrelation}$, we also have to show that a collection
of $\mathsf{PH}$ algorithms cannot take a collection of Forrelation instances,
and transform them into a single Forrelation instance whose solution is the OR
of the solutions to the input instances. Put another way, we must show that
$\mathsf{AC^{0}}$ circuits of constant depth and $2^{\mathrm{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 $\mathsf{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 $\mathsf{AC^{0}}$ circuits: our
concentration theorem for block sensitivity. Loosely speaking, the
concentration theorem implies that, with overwhelming probability, any small
$\mathsf{AC^{0}}$ circuit is insensitive to toggling between a yes-instance
and a neighboring no-instance of the $\textsc{OR}\circ\textsc{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 51, restated).

There exists an oracle relative to which
$\mathsf{BQP}^{\mathsf{NP}}\not\subset\mathsf{PH}^{\mathsf{BQP}}$, and even
$\mathsf{BQP}^{\mathsf{NP}}\not\subset\mathsf{PH}^{\mathsf{PromiseBQP}}$.

Note that an oracle relative to which
$\mathsf{BQP}^{\mathsf{NP}}\not\subset\mathsf{NP}^{\mathsf{BQP}}$ is almost
trivial to achieve, for example by considering any problem in $\mathsf{coNP}$.
However, $\mathsf{BQP}^{\mathsf{NP}}\not\subset\mathsf{PH}^{\mathsf{BQP}}$ is
much harder. At a high level, rather than considering the composed problem
$\textsc{OR}\circ\textsc{Forrelation}$, we now need to consider the reverse
composition: $\textsc{Forrelation}\circ\textsc{OR}$, a problem that’s clearly
in $\mathsf{BQP}^{\mathsf{NP}}$, but plausibly not in
$\mathsf{PH}^{\mathsf{BQP}}$. The key step is to show that, when solving
$\textsc{Forrelation}\circ\textsc{OR}$, any $\mathsf{PH}^{\mathsf{BQP}}$
machine can be simulated by a $\mathsf{PH}$ machine: the $\mathsf{BQP}$ oracle
is completely superfluous! Once we’ve shown that,
$\textsc{Forrelation}\circ\textsc{OR}\not\in\mathsf{PH}$ then follows
immediately from Raz-Tal.

For our next result, recall that $\mathsf{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 63, restated).

$\mathsf{PP}$ is not contained in the _“ $\mathsf{QMA}$ hierarchy”_,
consisting of constant-depth towers of the form
$\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$, with probability $1$
relative to a random oracle.222Actually, our formal definition of the
$\mathsf{QMA}$ hierarchy is more general than the version given here, in order
to accommodate recursive queries to $\mathsf{QMA}$ promise problems. This only
makes our separation stronger. See Section 2.2 for details.

Before this paper, to our knowledge, it was not even known how to construct an
oracle relative to which $\mathsf{PP}\not\subset\mathsf{BQP}^{\mathsf{NP}}$,
let alone classes like
$\mathsf{BQP}^{\mathsf{NP}^{\mathsf{BQP}^{\mathsf{NP}^{\cdots}}}}$ or
$\mathsf{QCMA}^{\mathsf{QCMA}^{\mathsf{QCMA}^{\cdots}}}$, which are contained
in the $\mathsf{QMA}$ hierarchy. The closest result we are aware of is due to
Kretschmer [Kre21], who gave a quantum oracle relative to which
$\mathsf{BQP}=\mathsf{QMA}\neq\mathsf{PostBQP}$.

Perhaps shockingly, our proof of Theorem 7 can be extended even to show that
$\mathsf{PP}$ is not in, say,
$(\mathsf{MIP}^{*})^{(\mathsf{MIP}^{*})^{(\mathsf{MIP}^{*})^{\cdots}}}$
relative to a random oracle, where $\mathsf{MIP}^{*}$ means multi-prover
interactive proofs with entangled provers. This is despite the recent
breakthrough of Ji, Natarajan, Vidick, Wright, and Yuen [JNV+20], which showed
that in the unrelativized world, $\mathsf{MIP}^{*}=\mathsf{RE}$ (where
$\mathsf{RE}$ means Recursively Enumerable), so in particular,
$\mathsf{MIP}^{*}$ contains the halting problem. This underscores the dramatic
extent to which results like $\mathsf{MIP}^{*}=\mathsf{RE}$ are
nonrelativizing!

We mention another interesting interpretation of Theorem 7: it can 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 machine $M$ that runs in $\mathrm{poly}(n)$ time and an error
bound $\varepsilon\geq\frac{1}{\mathrm{poly}(n)}$, the approximate counting
problem is to estimate the acceptance probability of $M$ up to a
multiplicative factor of $1+\varepsilon$. Stockmeyer’s algorithm [Sto83] gives
a $\mathrm{poly}(n)$-time reduction from the approximate counting problem to a
problem in the third level of the polynomial hierarchy, and moreover, this
reduction relativizes.

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?333We thank Patrick Rall
(personal communication) for bringing this question to our attention. By well-
known reductions involving Aaronson’s postselection theorem [Aar05], all
problems in $\mathsf{PP}=\mathsf{PostBQP}$ efficiently reduce to the quantum
approximate counting problem (see e.g. [Kup15, Proposition 2.14]). Hence,
Theorem 7 implies that the quantum approximate counting problem cannot reduce
efficiently to the $\mathsf{QMA}$ hierarchy in a black box manner, giving some
sense in which a quantum analogue of Stockmeyer’s algorithm is impossible.

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, $\textsc{Parity}\not\in\mathsf{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 36, restated).

For every $k\in\mathbb{N}$,
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}\not\subset\mathsf{BQP}^{\mathsf{\Sigma}_{k}^{\mathsf{P}}}$
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
$\mathsf{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 $\mathsf{PH}$, but that quantum computing fails to
bridge that gap.

Again, Theorem 8 represents a necessary step toward a proof of 5, because if
we had
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}\subseteq\mathsf{BQP}^{\mathsf{\Sigma}_{k}^{\mathsf{P}}}$,
then clearly $\mathsf{\Sigma}_{k}^{\mathsf{P}}\subseteq\mathsf{BQP}$ would
imply
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}\subseteq\mathsf{BQP}^{\mathsf{BQP}}=\mathsf{BQP}$.

Our last two theorems return to the theme of the autonomy of $\mathsf{BQP}$.

######  Theorem 9 (Theorem 26, restated).

There exists an oracle relative to which $\mathsf{NP}\subseteq\mathsf{BQP}$,
and indeed $\mathsf{BQP}=\mathsf{P^{\\#P}}$, and yet $\mathsf{PH}$ is
infinite.

As a simple corollary (Corollary 28), we also obtain an oracle relative to
which $\mathsf{BQP}\not\subset\mathsf{NP/poly}$.

For three decades, one of the great questions of quantum computation has been
whether it can solve $\mathsf{NP}$-complete problems in polynomial time. Many
experts guess that the answer is no, for similar reasons as they guess that
$\mathsf{P}\neq\mathsf{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 $\mathsf{NP}\not\subset\mathsf{BQP}$ conjecture to any “pre-
quantum” beliefs about complexity classes. No one has any idea how to show,
for example, that if $\mathsf{NP}\subseteq\mathsf{BQP}$ then
$\mathsf{P}=\mathsf{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 $\mathsf{NP}\subseteq\mathsf{BQP}$, then
$\mathsf{PH}$ collapses—analogous to the Karp-Lipton Theorem [KL80], that if
$\mathsf{NP}\subset\mathsf{P/poly}$ then $\mathsf{PH}$ collapses, or the
Boppana-Håstad-Zachos Theorem [BHZ87], that if
$\mathsf{NP}\subseteq\mathsf{coAM}$ then $\mathsf{PH}$ collapses. But again,
no such result is known for $\mathsf{NP}\subseteq\mathsf{BQP}$. 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
$\mathsf{BQP}\subseteq\mathsf{AM}$, then $\mathsf{NP}\subseteq\mathsf{BQP}$
really would imply a collapse of $\mathsf{PH}$.

######  Theorem 10 (Theorem 29, restated).

There exists an oracle relative to which
$\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\\#P}}$.

Theorem 10 says, in effect, that there is no relativizing obstruction to
$\mathsf{BQP}$ being inordinately powerful even while $\mathsf{NP}$ is
inordinately weak. It substantially extends the Raz-Tal Theorem, that there is
an oracle relative to which $\mathsf{BQP}\not\subset\mathsf{PH}$, to show that
in some oracle worlds, $\mathsf{BQP}$ doesn’t go just slightly beyond the
power of $\mathsf{PH}$ (which, if $\mathsf{P}=\mathsf{NP}$, is simply the
power of $\mathsf{P}$), but vastly beyond it. We conjecture that Theorem 10
could be extended yet further, to give an oracle relative to which
$\mathsf{P}=\mathsf{NP}$ and yet $\mathsf{BQP}=\mathsf{EXP}$, but we leave
that problem to future work.

###  1.4 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
$\mathsf{BQP}=\mathsf{P^{\\#P}}$ but $\mathsf{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 $\mathsf{PH}$ infinite. Then, we
recursively add into the oracle the answers to all possible
$\mathsf{P^{\\#P}}$ queries, hiding the answers in instances of the
Forrelation problem. This gives a $\mathsf{BQP}$ machine the power to decide
any $\mathsf{P^{\\#P}}$ language.

It remains to argue that adding these Forrelation instances does not collapse
$\mathsf{PH}$. We want to show that relative to our oracle, for every $k$,
there exists a language in $\mathsf{\Sigma}_{k+1}^{\mathsf{P}}$ that is not in
$\mathsf{\Sigma}_{k}^{\mathsf{P}}$. This is where we leverage the Raz-Tal
Theorem: because the Forrelation instances look random to $\mathsf{PH}$, we
can show, by a hybrid argument, that a $\mathsf{\Sigma}_{k}^{\mathsf{P}}$
algorithm’s probability of correctly deciding a target function in
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}$ 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 $\mathsf{\Sigma}_{k+1}^{\mathsf{P}}$
language remains hard for $\mathsf{\Sigma}_{k}^{\mathsf{P}}$.

The proof of Theorem 10, giving an oracle where
$\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\\#P}}$, follows a similar
recipe to the proof of Theorem 9. We start with a random oracle, which
separates $\mathsf{PH}$ from $\mathsf{P^{\\#P}}$, and then we add a second
region of the oracle that puts $\mathsf{P^{\\#P}}$ into $\mathsf{BQP}$ by
encoding all $\mathsf{P^{\\#P}}$ queries in instances of the Forrelation
problem. Next, we add a third region of the oracle that answers all
$\mathsf{NP}$ queries, which has the effect of collapsing $\mathsf{PH}$ to
$\mathsf{P}$. Finally, we again leverage the Raz-Tal Theorem to argue that the
Forrelation instances have no effect on the separation between $\mathsf{PH}$
and $\mathsf{P^{\\#P}}$, because the Forrelation instances look random to
$\mathsf{PH}$ algorithms.

We next prove Theorem 8, that
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}\not\subset\mathsf{BQP}^{\mathsf{\Sigma}_{k}^{\mathsf{P}}}$
relative to a random oracle. Our proof builds heavily on the proof by [HRST17]
that
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}\not\subset\mathsf{\Sigma}_{k}^{\mathsf{P}}$
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
$\textsc{Sipser}_{d}$ that is computable by a small $\mathsf{AC^{0}}$ circuit
of depth $d$ (which corresponds to a $\mathsf{\Sigma}_{d-1}^{\mathsf{P}}$
algorithm), but such that any small $\mathsf{AC^{0}}$ circuit of depth $d-1$
(which corresponds to a $\mathsf{\Sigma}_{d-2}^{\mathsf{P}}$ algorithm)
computes $\textsc{Sipser}_{d}$ on at most a $\frac{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 $\mathcal{R}$ over
random projections with the following properties:

  1. (i)

Any small $\mathsf{AC^{0}}$ circuit $C$ of depth $d-1$ “simplifies” with high
probability under a random projection drawn from $\mathcal{R}$, say, by
collapsing to a low-depth decision tree.

  2. (ii)

The target $\textsc{Sipser}_{d}$ function “retains structure” with high
probability under a random projection drawn from $\mathcal{R}$.

  3. (iii)

The structure retained in (ii) implies that the original unrestricted circuit
$C$ fails to compute the $\textsc{Sipser}_{d}$ function on a large fraction of
inputs.

To prove Theorem 8, we generalize step (i) above from
$\mathsf{\Sigma}_{d-2}^{\mathsf{P}}$ algorithms to
$\mathsf{BQP}^{\mathsf{\Sigma}_{d-2}^{\mathsf{P}}}$ algorithms. That is, if we
have a quantum algorithm that queries arbitrary depth-$(d-1)$
$\mathsf{AC^{0}}$ functions of the input, then we show that this algorithm’s
acceptance probability also “simplifies” under a random projection from
$\mathcal{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 $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$. Recall that
we prove Theorem 3 by showing that no $\mathsf{BQP}^{\mathsf{PH}}$ algorithm
can solve the $\textsc{OR}\circ\textsc{Forrelation}$ problem. To establish
this, imagine that we fix a “no” instance $x$ of the
$\textsc{OR}\circ\textsc{Forrelation}$ problem, meaning that $x$ consists of a
list of $\sim 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
$\mathsf{AC^{0}}$ circuit of size $2^{\mathrm{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 $\mathsf{BQP}^{\mathsf{PH}}$
algorithm is unlikely to distinguish $x$ from $y$, implying that it could not
have solved the $\textsc{OR}\circ\textsc{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 if 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 $\mathsf{AC^{0}}$ circuit of size $2^{\mathrm{poly}(n)}$, then
$\left|\Pr_{y}[f(x)\neq f(y)]-\Pr_{z}[f(x)\neq f(z)]\right|\leq
2^{-\Omega(n)}$.

Our key observation is that the quantity $\Pr_{z}[f(x)\neq 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:

######  Theorem 11 (Corollary 39, informal).

Let $f:\\{0,1\\}^{N}\to\\{0,1\\}$ be an $\mathsf{AC^{0}}$ circuit of size
$\mathrm{quasipoly}(N)$ and depth $O(1)$, and let
$B=\\{B_{1},B_{2},\ldots,B_{k}\\}$ be a collection of disjoint subsets of
$[N]$. Then for any $t$,

$\Pr_{x\sim\\{0,1\\}^{N}}\left[\operatorname{\mathsf{bs}}_{B}^{x}(f)\geq
t\right]\leq 4N\cdot 2^{-\Omega\left(\frac{t}{\mathrm{polylog}(N)}\right)},$

where $\operatorname{\mathsf{bs}}_{B}^{x}(f)$ denotes the block sensitivity of
$f$ on $x$ with respect to $B$.

Informally, Theorem 11 says that the probability that an $\mathsf{AC^{0}}$
circuit has $B$-block sensitivity $t\gg\mathrm{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 $\mathsf{AC^{0}}$
circuits is at most $\mathrm{polylog}(N)$. It also generalizes a concentration
theorem for the sensitivity of $\mathsf{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.444Interestingly, [GSTW16]’s
goal, in proving their concentration theorem for the sensitivity of
$\mathsf{AC^{0}}$, was to make progress toward a proof of the famous
Sensitivity Conjecture—a goal that Huang [Hua19] achieved shortly afterward
using completely different methods. One happy corollary of this work is that,
nevertheless, [GSTW16]’s attempt on the problem was not entirely in vain. In
fact, we derive Theorem 11 as a simple corollary of such a sensitivity tail
bound for $\mathsf{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 $\mathsf{AC^{0}}$ random restriction lemma due to
Rossman [Ros17].

To prove Theorem 4, which gives an oracle relative to which
$\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{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
$\textsc{OR}\circ\textsc{Forrelation}$ problem. Next, we add a second region
of the oracle that answers all $\mathsf{NP}$ queries. This collapses
$\mathsf{PH}$ to $\mathsf{P}$. Finally, we use Theorem 3 to argue that these
$\mathsf{NP}$ queries do not enable a $\mathsf{BQP}$ algorithm to solve the
$\textsc{OR}\circ\textsc{Forrelation}$ problem, which is in $\mathsf{QCMA}$.

We now move on to the proof of Theorem 6, that there exists an oracle relative
to which $\mathsf{BQP}^{\mathsf{NP}}\not\subset\mathsf{PH}^{\mathsf{BQP}}$.
Recall that our strategy is to show that no $\mathsf{PH}^{\mathsf{BQP}}$
algorithm can solve the $\textsc{Forrelation}\circ\textsc{OR}$ problem. We
prove this by showing that with high probability, a
$\mathsf{PH}^{\mathsf{BQP}}$ algorithm on a random instance of the
$\textsc{Forrelation}\circ\textsc{OR}$ problem can be simulated by a
$\mathsf{PH}$ algorithm, 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 48, informal).

Consider a quantum algorithm $Q$ that makes $T$ queries to an $M\times N$
array of bits $x$, where each length-$N$ row of $x$ contains a single
uniformly random $1$ and $0$s everywhere else. Then for any
$\varepsilon\gg\frac{T}{\sqrt{N}}$ and $\delta>0$, there exists a
deterministic classical algorithm that makes
$O\left(\frac{T^{5}}{\varepsilon^{4}}\log\frac{T}{\delta}\right)$ queries to
$x$, and approximates $Q$’s acceptance probability to within additive error
$\varepsilon$ on a $1-\delta$ 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 $\mathsf{P}=\mathsf{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\in\\{0,1\\}^{N}$. Then for any $\varepsilon,\delta>0$, there exists a
deterministic classical algorithm that makes
$\mathrm{poly}\left(T,\frac{1}{\varepsilon},\frac{1}{\delta}\right)$ queries
to $x$, and approximates $Q$’s acceptance probability to within additive error
$\varepsilon$ on a $1-\delta$ fraction of uniformly randomly inputs $x$.

While 13 has become influential in Fourier analysis of Boolean functions,555In
the context of Fourier analysis, the Aaronson-Ambainis Conjecture usually
refers to a closely-related conjecture about influences of bounded low-degree
polynomials; see e.g. [Mon12, OZ16]. Aaronson and Ambainis [AA14] showed that
this related conjecture implies 13. it remains open to this day. Theorem 12
could be seen as the analogue of 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 $\mathsf{PP}$ is not
contained in the $\mathsf{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
$(\mathsf{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 $\mathsf{QMA}$ query
complexity does not care about the length of the witness, but only on the
number of queries made by the verifier. This property allows us to extend our
results to complexity classes beyond $\mathsf{QMA}$, such as
$\mathsf{MIP}^{*}$.

An informal statement of our random restriction lemma is given below:

######  Theorem 14 (Theorem 57, informal).

Consider a partial function $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$ with
$\mathsf{QMA}$ query complexity at most $\mathrm{polylog}(N)$. For some
$p=\frac{1}{\sqrt{N}\mathrm{polylog}(N)}$, let $\rho$ be a random restriction
that leaves each variable unrestricted with probability $p$. Then $f_{\rho}$
is $\frac{1}{\mathrm{quasipoly}(N)}$-close, in expectation over $\rho$, to a
$\mathrm{polylog}(N)$-width DNF formula.666By saying that $f_{\rho}$ is
“close” to a DNF formula, we mean that there exists a DNF $g$ depending on
$\rho$ such that the fraction of inputs on which $f_{\rho}$ and $g$ agree is
$1-\frac{1}{\mathrm{quasipoly}(N)}$, in expectation over $\rho$. In Section
5.2, we introduce some additional notation and terminology that makes it
easier to manipulate such expressions, but we will not use them in this
exposition.

An unusual feature of Theorem 14 is that we can only show that $f_{\rho}$ 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
$\mathsf{PP}\not\subset\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$
relative to a random oracle is conceptually analogous to the proof that
$\mathsf{PP}\not\subset\mathsf{PH}$ relative to a random oracle [Hås87]. We
first view a $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$ algorithm
as a small constant-depth circuit in which the gates are functions of low
$\mathsf{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 $\mathsf{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 $\mathsf{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 $\rho$, and a
uniformly random input $x$ to $f_{\rho}$, 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$,
$\left|\Pr[Q(x)=1]-\Pr[Q(y)=1]\right|$ is bounded by a small constant. Hence,
$K$ serves as a certificate for $f_{\rho}$’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 52. Finally,
we generalize from quantum query algorithms to arbitrary $\mathsf{QMA}$ query
algorithms by observing that we only need to keep track of the certificates
for inputs $x$ such that $f_{\rho}(x)=1$. The DNF we obtain in Theorem 14 is
then simply the OR of all of these small $1$-certificates.

##  2 Preliminaries

###  2.1 Notation and Basic Tools

We denote by $[N]$ the set $\\{1,2,\ldots,N\\}$. For a finite set $S$, $|S|$
denotes the size of $S$. If $\mathcal{D}$ is a probability distribution, then
$x\sim\mathcal{D}$ means that $x$ is a random variable sampled from
$\mathcal{D}$. If $v$ is a real or complex vector, then $||v||$ denotes the
Euclidean norm of $v$.

We use $\mathrm{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)\leq n^{c}$ for all sufficiently large $n$. Likewise, we use
$\mathrm{polylog}(n)$ for an arbitrary $f$ satisfying $f(n)\leq\log(n)^{c}$
for all sufficiently large $n$, and $\mathrm{quasipoly}(n)$ for an arbitrary
$f$ satisfying $f(n)\leq 2^{\log(n)^{c}}$ for all sufficiently large $n$.

For a string $x\in\\{0,1\\}^{N}$, $|x|$ denotes the length of $x$.
Additionally, if $i\in[N]$, then $x^{\oplus i}$ denotes the string obtained
from $x$ by flipping the $i$th bit. Similarly, if $S\subseteq[N]$, then
$x^{\oplus S}$ denotes the string obtained from $x$ by flipping the bits
corresponding to all indices in $S$. For sets $S\subseteq[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:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$, where the domain of $f$ is
$f^{-1}(\\{0,1\\})$. We $\bot$ (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},\ldots,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=\sum_{i=1}^{n}X_{i}$ and let $\mu=\mathop{\mathbb{E}}[X]=pn$.
Then for all $\delta\geq 0$ it holds that:

$\displaystyle\Pr\left[X\geq(1+\delta)\mu\right]$ $\displaystyle\leq
e^{-\frac{\delta^{2}\mu}{2+\delta}},$
$\displaystyle\Pr\left[X\leq(1-\delta)\mu\right]$ $\displaystyle\leq
e^{-\frac{\delta^{2}\mu}{2}},$

Additionally, if $\delta\leq 1$, then we may use the weaker bound:

$\Pr\left[X\geq(1+\delta)\mu\right]\leq e^{-\frac{\delta^{2}\mu}{3}}.$

We also require Hoeffding’s inequality, which generalizes 15 to sums of
arbitrary independent bounded random variables:

######  Fact 16 (Hoeffding’s inequality).

Suppose $X_{1},\ldots,X_{n}$ are independent random variables subject to
$a_{i}\leq X_{i}\leq b_{i}$ for all $i$. Let $X=\sum_{i=1}^{n}X_{i}$ and let
$\mu=\mathop{\mathbb{E}}[X]$. Then for all $\delta\geq 0$ it holds that:

$\Pr\left[X\geq(1+\delta)\mu\right]\leq\exp\left(-\frac{2\delta^{2}\mu^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

###  2.2 Complexity Classes

We assume familiarity with basic complexity classes, including: $\mathsf{P}$,
$\mathsf{NP}$,
$\mathsf{PH}=\bigcup_{k=0}^{\infty}\mathsf{\Sigma}_{k}^{\mathsf{P}}$,
$\mathsf{PP}$, $\mathsf{P}^{\mathsf{\\#P}}$, $\mathsf{BQP}$, $\mathsf{QCMA}$,
and $\mathsf{QMA}$; see e.g. the Complexity
Zoo777https://complexityzoo.net/Complexity_Zoo for definitions. We also
consider the relativized versions of these complexity classes augmented with
oracles, where we use the standard notation that $\mathcal{C}^{\mathcal{O}}$
denotes a complexity class $\mathcal{C}$ augmented with oracle $\mathcal{O}$.
A random oracle $\mathcal{O}$ is a uniformly random language where for each
$x\in\\{0,1\\}^{*}$, $\mathcal{O}(x)=0$ or $1$ with probability $\frac{1}{2}$
(independently for each $x$).

We define a quantum analogue of the polynomial hierarchy that we call
$\mathsf{QMAH}$, and denote by $\mathsf{PromiseQMAH}$ the promise version of
this class. Let $\mathsf{PromiseQMAH}_{0}=\mathsf{PromiseP}$, and for
$k\in\mathbb{N}$ we recursively define:

$\displaystyle\mathsf{PromiseQMAH}_{k}$
$\displaystyle\coloneqq\mathsf{PromiseQMA}^{\mathsf{PromiseQMAH}_{k-1}},$

Then, analogous to $\mathsf{PH}$, we take:

$\displaystyle\mathsf{PromiseQMAH}$
$\displaystyle\coloneqq\bigcup_{k=1}^{\infty}\mathsf{PromiseQMAH}_{k}$

$\mathsf{QMAH}$ denotes the set of languages in $\mathsf{PromiseQMAH}$. In the
above definition, we define queries to a promise problem in the standard way,
as follows. Recall that a promise problem can be viewed as a partial function
$\Pi:\\{0,1\\}^{*}\to\\{0,1,\bot\\}$. We say that a language
$A:\\{0,1\\}^{*}\to\\{0,1\\}$ extends $\Pi$ if for all $x\in\\{0,1\\}^{*}$,
$\Pi(x)\neq\bot\implies\Pi(x)=A(x)$. Then, a promise problem $P$ is in
$\mathsf{PromiseQMA}^{\Pi}$ if there exists a single $\mathsf{QMA}$ verifier
$V$ such that, for every language $A$ that extends $\Pi$, $V^{A}$ decides $P$.
For a class $\mathcal{C}$ of promise problems, we let
$\mathsf{PromiseQMA}^{\mathcal{C}}\coloneqq\bigcup_{\Pi\in\mathcal{C}}\mathsf{PromiseQMA}^{\Pi}$.
This is essentially the same definition that was given by Aaronson and Drucker
[AD14].

We remark that it is not clear to us if this is the “right” way to define
quantum queries to a promise problem. 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
$\mathsf{QMAH}$ complexity, this distinction makes little difference to us:
our choice of definition could only possibly make the class
$\mathsf{PromiseQMA}^{\Pi}$ more powerful than if the oracle could have worse
behavior on non-promise inputs. Whether complexity classes such as
$\mathsf{BQP}^{\Pi}$ and $\mathsf{QMA}^{\Pi}$ are robust with respect to the
notion of promise problem queries remains an interesting question for future
work.

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 $\mathsf{BQPH}$ by Vinkhuijzen [Vin18], except
that we allow recursive queries to $\mathsf{PromiseQMA}$ instead of just
$\mathsf{QMA}$.

###  2.3 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\in\\{0,1\\}^{N}$ is implemented
via the unitary transformation $U_{x}$ that acts on basis states of the form
$\ket{i}\ket{w}$ as $U_{x}\ket{i}\ket{w}=(-1)^{x_{i}}\ket{i}\ket{w}$, where
$i\in[N]$ and $w$ is an index over a workspace register.

Following standard notation, for a (possibly partial) function
$f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$, we denote by
$\operatorname{\mathsf{Q}}(f)$ the bounded-error quantum query complexity of
$f$, which means the fewest number of queries made by a quantum algorithm that
computes $f$ with error probability at most $\frac{1}{3}$. We denote by
$\operatorname{\mathsf{D}}(f)$ the deterministic query complexity of $f$,
which is also sometimes called decision tree complexity.

We define a notion of $\mathsf{QMA}$ (Quantum Merlin-Arthur) query complexity
as follows.

######  Definition 17 ($\mathsf{QMA}$ query complexity).

The _(bounded-error) $\mathsf{QMA}$ query complexity_ of a function
$f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$, denoted $\operatorname{\mathsf{QMA}}(f)$,
is the fewest number of queries made by any quantum query algorithm
$\mathcal{V}(\ket{\psi},x)$ that takes an auxiliary input state $\ket{\psi}$
and satisfies, for all $x\in\\{0,1\\}^{N}$:

  * •

(Completeness) If $f(x)=1$, then there exists a state $\ket{\psi}$ such that
$\Pr\left[\mathcal{V}(\ket{\psi},x)=1\right]\geq\frac{2}{3}$, and

  * •

(Soundness) If $f(x)=0$, then for every state $\ket{\psi}$,
$\Pr\left[\mathcal{V}(\ket{\psi},x)=1\right]\leq\frac{1}{3}$.

The algorithm $\mathcal{V}$ is sometimes called the _verifier_ , and the state
$\ket{\psi}$ a _witness_.

Note that in contrast to most previous works (c.f. [RS04, AKKT20, ST19]), our
definition of $\mathsf{QMA}$ query complexity completely ignores the number of
qubits in the witness state $\ket{\psi}$.

We next define sensitivity, and the related $B$-block sensitivity.

######  Definition 18 (Sensitivity).

The _sensitivity_ of a function $f:\\{0,1\\}^{N}\to\\{0,1\\}$ on input $x$ is
defined as:

$\operatorname{\mathsf{s}}^{x}(f)\coloneqq\left|\left\\{i\in[n]:f(x)\neq
f\left(x^{\oplus i}\right)\right\\}\right|.$

The _sensitivity of $f$_ is defined as:

$\operatorname{\mathsf{s}}(f)\coloneqq\max_{x\in\\{0,1\\}^{N}}\operatorname{\mathsf{s}}^{x}(f).$

######  Definition 19 ($B$-block sensitivity).

Let $B=\\{S_{1},S_{2},\ldots,S_{k}\\}$ be collection of disjoint subsets of
$[N]$. The _block sensitivity_ of a function $f:\\{0,1\\}^{N}\to\\{0,1\\}$ on
input $x\in\\{0,1\\}^{N}$ with respect to $B$ is defined as:

$\operatorname{\mathsf{bs}}_{B}^{x}(f)\coloneqq\left|\left\\{i\in[k]:f(x)\neq
f\left(x^{\oplus S_{i}}\right)\right\\}\right|.$

The _block sensitivity of $f$_ with respect to $B$ is defined as:

$\operatorname{\mathsf{bs}}_{B}(f)\coloneqq\max_{x\in\\{0,1\\}^{N}}\operatorname{\mathsf{bs}}_{B}^{x}(f).$

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.

######  Definition 20 (Certificate complexity).

Let $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$, and suppose $x\in\\{0,1\\}^{N}$
satisfies $f(x)\in\\{0,1\\}$. A _certificate for $x$ on $f$_, also called an
_$f(x)$ -certificate_, is a set $K\subseteq[N]$ such that for any
$y\in\\{0,1\\}^{N}$ satisfying $y_{i}=x_{i}$ for all $i\in K$, either
$f(y)=f(x)$ or $f(y)=\bot$.

The _certificate complexity of $f$ on $x$_, denoted
$\operatorname{\mathsf{C}}^{x}(f)$, is the minimum size of any certificate for
$f$ on $x$. The _certificate complexity of $f$_ is defined as:

$\operatorname{\mathsf{C}}(f)\coloneqq\max_{x\in\\{0,1\\}^{N}}\operatorname{\mathsf{C}}^{x}(f).$

Intuitively, in this definition of certificate complexity, a $b$-certificate
for $b\in\\{0,1\\}$ witnesses that $f(x)\neq 1-b$, in contrast to the standard
definition where a $b$-certificate witnesses that $f(x)=b$.

###  2.4 Random Restrictions

A restriction is a function $\rho:[N]\to\\{0,1,*\\}$. A random restriction
with $\Pr[*]=p$ is a distribution over restrictions in which, for each
$i\in[N]$, we independently sample:

$\rho(i)=\begin{cases}0&\text{ with probability }\frac{1-p}{2}\\\ 1&\text{
with probability }\frac{1-p}{2}\\\ *&\text{ with probability }p.\end{cases}$

If $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$ is a function and $\rho$ is a
restriction where $S=\\{i\in[N]:\rho(i)=*\\}$, we denote by
$f_{\rho}:\\{0,1\\}^{S}\to\\{0,1,\bot\\}$ the function obtained from $f$ by
fixing the inputs where $\rho(i)\in\\{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|\rho}$ 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_{\rho}$ for
applying a projection $\rho$ to a function $f$ as we do for restrictions.

###  2.5 Circuit Complexity

In this work, we consider Boolean circuits where the gates can be arbitrary
partial Boolean functions $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$. On input
$x\in\\{0,1,\bot\\}^{N}$, a circuit gate labeled by $f$ evaluates to
$b\in\\{0,1\\}$ if, for all $y\in\\{0,1\\}^{N}$ that agree with $x$ (meaning,
for all $i\in[n]$, $x_{i}\in\\{0,1\\}$ implies $y_{i}=x_{i}$), we have
$f(y)=b$; otherwise, the gate evaluates to $\bot$.

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 $\mathsf{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
$\mathsf{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 $\mathsf{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 21 ([Hås87, Lemma 7.8]).

For every constant $d$, there exists a constant $c$ such that for all
sufficiently large $N$, for all $C\in\mathsf{AC^{0}}\left[2^{N^{c}},d\right]$,
one has:

$\Pr_{x\sim\\{0,1\\}^{N}}\left[C(x)=\textsc{Parity}_{N}(x)\right]\leq 0.6,$

where $\textsc{Parity}_{N}$ is the parity function on $N$ bits.

######  Theorem 22 ([HRST17, Proof of Theorem 10.1]).

For all constant $d\geq 2$ and all sufficiently large $m\in\mathbb{N}$, there
exists a function $\textsc{Sipser}_{d}$ with $N=2^{\Theta(m)}$ inputs, and a
class $\mathcal{R}$ of random projections such that the following hold:

  1. (a)

For some value $b=2^{-m}\left(1-O\left(2^{-m/2}\right)\right)$, for any
function $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$,

$\Pr_{x\sim\\{0,1\\}^{N}}\left[f(x)=\textsc{Sipser}_{d}(x)\right]=\Pr_{x\sim
D,\rho\sim\mathcal{R}}\left[f_{\rho}(x)=\textsc{Sipser}_{d|\rho}(x)\right],$

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\in\mathsf{AC^{0}}[s,d-1]$. If we sample
$\rho\sim\mathcal{R}$, then:

  1. (b)

Except with probability at most $s2^{-2^{m/2-4}}$,
$\operatorname{\mathsf{D}}\left(C_{\rho}\right)\leq 2^{m/2-4}$.

  2. (c)

Except with probability at most $O\left(2^{-m/2}\right)$,
$\textsc{Sipser}_{d|\rho}$ is reduced to an AND gate of fan-in $(\ln 2)\cdot
2^{m}\cdot\left(1\pm O\left(2^{-m/4}\right)\right)$.

[HRST17] roughly explains the intuitive meaning of the above theorem as
follows. Property (a) guarantees that the distribution $\mathcal{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 $\textsc{Sipser}_{d}$ retains structure under this
distribution of projections with high probability. A simple corollary of these
properties is the following:

######  Corollary 23 ([HRST17, Theorem 10.1]).

Let $\textsc{Sipser}_{d}$ be the function defined in Theorem 22 on
$N=2^{\Theta(m)}$ bits. Let $C\in\mathsf{AC^{0}}[s,d-1]$. Then, for all
sufficiently large $m$, we have:

$\Pr_{x\sim\\{0,1\\}^{N}}\left[C(x)=\textsc{Sipser}_{d}(x)\right]\leq\frac{1}{2}+O\left(2^{-m/4}\right)+s2^{-2^{m/2-4}}.$

###  2.6 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 $\mathsf{AC^{0}}$ circuits, but that is
easily distinguishable from random by an efficient quantum algorithm.

######  Theorem 24 ([RT19, Theorem 1.2]).

For all sufficiently large $N$, there exists an explicit distribution
$\mathcal{F}_{N}$ that we call the _Forrelation distribution_ over
$\\{0,1\\}^{N}$ such that:

  1. 1.

There exists a quantum algorithm $\mathcal{A}$ that makes
$\mathrm{polylog}(N)$ queries and runs in time $\mathrm{polylog}(N)$ such
that:

$\left|\Pr_{x\sim\mathcal{F}_{N}}[\mathcal{A}(x)=1]-\Pr_{y\sim\\{0,1\\}^{N}}[\mathcal{A}(y)=1]\right|\geq
1-\frac{1}{N^{2}}.$

  2. 2.

For any $C\in\mathsf{AC^{0}}[\mathrm{quasipoly}(N),O(1)]$:

$\left|\Pr_{x\sim\mathcal{F}_{N}}[C(x)=1]-\Pr_{y\sim\\{0,1\\}^{N}}[C(y)=1]\right|\leq\frac{\mathrm{polylog}(N)}{\sqrt{N}}.$

Note that, by standard amplification techniques, the $\frac{1}{N^{2}}$ in the
above theorem can be replaced by any $\delta\leq 2^{-\mathrm{polylog}(N)}$ at
a cost of $\mathrm{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 $\mathcal{F}$.
Additionally, in a slight abuse of notation, we sometimes informally call the
decision problem of distinguishing a sample from $\mathcal{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 25.

Consider a quantum algorithm $Q$ that makes $T$ queries to
$x\in\\{0,1\\}^{N}$. Write the state of the quantum algorithm immediately
after $t$ queries to $x$ as:

$\ket{\psi_{t}}=\sum_{i=1}^{N}\sum_{w}\alpha_{i,w,t}\ket{i,w},$

where $w$ are indices over a workspace register. Define the _query magnitude_
$q_{i}$ of an input $i\in[N]$ by:

$q_{i}\coloneqq\sum_{t=1}^{T}\sum_{w}\left|\alpha_{i,w,t}\right|^{2}.$

Then for any $y\in\\{0,1\\}^{N}$, we have:

$\left|\Pr\left[Q(x)=1\right]-\Pr\left[Q(y)=1\right]\right|\leq
8\sqrt{T}\cdot\sqrt{\sum_{i:x_{i}\neq y_{i}}q_{i}}.$

###### Proof.

Denote by $\ket{\psi^{\prime}_{t}}$ the state of the quantum algorithm after
$t$ queries, where the first $t-1$ queries are to $x$ and the $t$th query is
to $y$. For $t>0$, we have:

$\displaystyle||\ket{\psi_{t}}-\ket{\psi^{\prime}_{t}}||$
$\displaystyle=\left|\left|2\sum_{i:x_{i}\neq
y_{i}}\sum_{w}\alpha_{i,w,t}\ket{i,w}\right|\right|$
$\displaystyle=2\sqrt{\sum_{i:x_{i}\neq y_{i}}\sum_{w}|\alpha_{i,w,t}|^{2}}.$

Hence, if we denote by $\ket{\varphi_{t}}$ the state of the quantum algorithm
after $t$ queries, where all $t$ queries are to $y$, then:

$\displaystyle\left|\Pr\left[Q(x)=1\right]-\Pr\left[Q(y)=1\right]\right|$
$\displaystyle\leq 4||\ket{\psi_{T}}-\ket{\varphi_{T}}||$
$\displaystyle\leq\sum_{t=1}^{T}8\sqrt{\sum_{i:x_{i}\neq
y_{i}}\sum_{w}|\alpha_{i,w,t}|^{2}}$ $\displaystyle\leq
8\sqrt{T}\cdot\sqrt{\sum_{t=1}^{T}\sum_{i:x_{i}\neq
y_{i}}\sum_{w}|\alpha_{i,w,t}|^{2}}$
$\displaystyle=8\sqrt{T}\cdot\sqrt{\sum_{i:x_{i}\neq y_{i}}q_{i}}.$

Above, the first line holds by [BV97, Lemma 3.6]; the second line is valid by
the BBBV hybrid argument used in [BBBV97, Theorem 3.3]; the third line applies
the Cauchy-Schwarz inequality, viewing the summation as the inner product
between the all $1$s vector and the terms of the sum; and the last line
substitutes the definition of $q_{i}$. ∎

##  3 Consequences of the Raz-Tal Theorem

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

###  3.1 Relativizing (Non-)Implications of $\mathsf{NP}\subseteq\mathsf{BQP}$

Our first result proves the following:

######  Theorem 26.

There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\\#P}}$ and
$\mathsf{PH}$ is infinite.

The proof idea is as follows. First, we take a random oracle, which makes
$\mathsf{PH}$ infinite [HRST17, RST15]. Then, we encode the answers to all
possible $\mathsf{P^{\\#P}}$ queries in instances of the Forrelation problem,
allowing a $\mathsf{BQP}$ machine to efficiently decide any
$\mathsf{P^{\\#P}}$ language. We then leverage Theorem 24 to argue that adding
these Forrelation instances does not collapse $\mathsf{PH}$, because the
Forrelation instances look random to $\mathsf{PH}$ algorithms. The formal
proof is given below.

###### Proof of Theorem 26.

We will inductively construct this oracle $\mathcal{O}$, which will consist of
two parts, $A$ and $B$. Denote the first region of the oracle $A$, and let
this be a random oracle. For each $t\in\mathbb{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 $\mathcal{O}_{t}=(A_{t},B_{t})$.

Let $S_{t}$ be the set of all ordered pairs of the form $\langle M,x\rangle$
such that:

  1. 1.

$M$ is a $\mathsf{P^{\\#P}}$ oracle machine and $x$ is an input to $M$,

  2. 2.

$\langle M,x\rangle$ takes less than $t$ bits to specify, and

  3. 3.

$M$ is syntactically restricted to run in less than $t$ steps, and to query
only the
$\mathcal{O}_{1},\mathcal{O}_{2},\ldots,\mathcal{O}_{\lfloor\sqrt{t}\rfloor}$
regions of the oracle.

Note that there are at most $2^{t}$ elements in $S_{t}$. Let
$M_{1},M_{2},\ldots,M_{2^{t}}$ be an enumeration of $S_{t}$. For each $M_{i}$
in $S_{t}$, we add a function $f_{i}:\\{0,1\\}^{t^{2}}\to\\{0,1\\}$ into
$B_{t}$. The function $f_{i}$ is chosen subject to the following rules:

  1. 1.

If $M_{i}$ accepts, then $f_{i}$ is drawn from the Forrelation distribution
$\mathcal{F}_{2^{t^{2}}}$ (given in Theorem 24).

  2. 2.

If $M_{i}$ rejects, then $f_{i}$ is uniformly random.

Let $\mathcal{D}$ be the resulting distribution over oracles
$\mathcal{O}=(A,B)$.

######  Claim 27.

$\mathsf{BQP}^{\mathcal{O}}=\mathsf{P}^{\mathsf{\\#P}^{\mathcal{O}}}$ with
probability $1$ over $\mathcal{O}$.

###### Proof of Claim.

It suffices to show that
$\mathsf{P}^{\mathsf{\\#P}^{\mathcal{O}}}\subseteq\mathsf{BQP}^{\mathcal{O}}$,
as the reverse containment holds relative to all oracles. Let $M$ be any
$\mathsf{P}^{\mathsf{\\#P}}$ oracle machine. Then given an input $x$ of size
$n$, a quantum algorithm can decide whether $M^{\mathcal{O}}(x)$ accepts in
$\mathrm{poly}(n)$ time by looking up the appropriate $B_{t}$, the one that
contains a Forrelation instance $f_{i}:\\{0,1\\}^{t^{2}}\to\\{0,1\\}$ encoding
the behavior of $\left<M,x\right>$, and then deciding whether $f_{i}$ is
Forrelated or random by using the algorithm $\mathcal{A}$ from Theorem 24.

In more detail, by Theorem 24 we know that:

$\Pr_{\mathcal{O}\sim\mathcal{D}}\left[\mathcal{A}(f_{i})\neq
M^{\mathcal{O}}(x)\right]\leq 2^{-2t^{2}},$

where the probability in the above expression is also taken over the
randomness of $\mathcal{A}$. By Markov’s inequality, we may conclude:

$\Pr_{\mathcal{O}\sim\mathcal{D}}\left[\Pr\left[\mathcal{A}(f_{i})\neq
M^{\mathcal{O}}(x)\right]\geq 1/3\right]\leq 3\cdot 2^{-2t^{2}}.$

Hence, the $\mathsf{BQP}$ promise problem defined by $\mathcal{A}$ agrees with
the $\mathsf{P}^{\mathsf{\\#P}}$ language on $\left<M,x\right>$, except with
probability at most $3\cdot 2^{-2t^{2}}$.

We now appeal to the Borel-Cantelli Lemma to argue that, with probability $1$
over $\mathcal{O}\sim\mathcal{D}$, $\mathcal{A}$ correctly decides
$M^{\mathcal{O}}(x)$ for all but finitely many $x\in\\{0,1\\}^{*}$. Since
there are at most $2^{t}$ inputs $\left<M,x\right>$ that take less than $t$
bits to specify, we have:

$\sum_{\langle
x,M\rangle\in\\{0,1\\}^{*}}\Pr_{\mathcal{O}\sim\mathcal{D}}\left[\mathcal{A}^{\mathcal{O}}\text{
does not decide }M^{\mathcal{O}}(x)\right]\leq\sum_{t=1}^{\infty}2^{t}\cdot
3\cdot 2^{-2t^{2}}<\infty$

Therefore, the probability that $\mathcal{A}$ fails on infinitely many inputs
$\left<M,x\right>$ is $0$. Hence, $\mathcal{A}$ can be modified into a
$\mathsf{BQP}$ algorithm that decides $M^{\mathcal{O}}(x)$ for all
$x\in\\{0,1\\}^{*}$, with probability $1$ over $\mathcal{O}\sim\mathcal{D}$. ∎

Now, we must show that $\mathsf{PH}^{\mathcal{O}}$ is infinite. We will
accomplish this by proving, for all $k\in\mathbb{N}$,
$\mathsf{\Sigma}_{k}^{\mathsf{P}^{\mathcal{O}}}\neq\mathsf{\Sigma}_{k-1}^{\mathsf{P}^{\mathcal{O}}}$
with probability 1 over the choice of $\mathcal{O}$. Let $L^{\mathcal{O}}$ be
the unary language used for the same purpose as in [RST15, HRST17]. That is,
$L^{\mathcal{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 $\textsc{Sipser}_{k+1}$ function, then that instance evaluates
to $1$. By construction,
$L^{\mathcal{O}}\in\mathsf{\Sigma}_{k}^{\mathsf{P}^{\mathcal{O}}}$ [RST15,
HRST17]. Furthermore, [RST15, HRST17] show that $L^{\mathcal{O}}$ is not in
$\mathsf{\Sigma}_{k-1}^{\mathsf{P}^{A}}$ with probability $1$ over the random
oracle $A$. We need to argue that adding $B$ has probability $0$ of changing
this situation. Fix any $\mathsf{\Sigma}_{k-1}^{\mathsf{P}^{\mathcal{O}}}$
oracle machine $M$. By the union bound, it suffices to show that

$\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\text{ decides
}L^{\mathcal{O}}\right]=0.$

Let $n_{1}<n_{2}<\cdots$ be an infinite sequence of input lengths, spaced far
enough apart (e.g. $n_{i+1}=2^{n_{i}}$) such that $M\left(0^{n_{i}}\right)$
can query the oracle on strings of length $n_{i+1}$ or greater for at most
finitely many values of $i$. Next, let

$p(M,i)\coloneqq\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\text{
correctly decides }0^{n_{i}}|M^{\mathcal{O}}\text{ correctly decided
}0^{n_{1}},\dots,0^{n_{i-1}}\right]$

Then we have that

$\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\text{ decides
}L^{\mathcal{O}}\right]\leq\prod_{i=1}^{\infty}p(M,i)$

Thus it suffices to show that, for every fixed $M$, we have $p(M,i)\leq 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 $\mathcal{D}$ on $A$ and
$B_{1},\ldots,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$,

  1. (a)

$q(M,i)\leq 0.6$ for all but finitely many values of $i$, and

  2. (b)

$|q(M,i)-p(M,i)|\leq 0.1$ for all but finitely many values of $i$.

Statement (a) essentially follows from the work of [HRST17]. The key
observation is that the only portion of $\mathcal{O}$ that can depend on
whether $0^{n_{i}}$ is in $L^{\mathcal{O}}$ is the input to the
size-$2^{n_{i}}$ $\textsc{Sipser}_{k+1}$ function that is encoded in $A$. All
other portions of $\mathcal{O}$ are sampled independently from this region
under $D_{i}$:

  1. 1.

The rest of $A$ is sampled uniformly at random,

  2. 2.

$B_{1},\ldots,B_{n_{i}}$ are drawn from a distribution that cannot depend on
any queries to $A$ on inputs of length $\lfloor\sqrt{n_{i}}\rfloor$ or greater
(so in particular, they cannot depend on $A_{n_{i}}$), and

  3. 3.

$B_{n_{i}+1},B_{n_{i}+2},\ldots$ are sampled uniformly at random.

Hence, $M$ is forced to evaluate the size-$2^{n_{i}}$ $\textsc{Sipser}_{k+1}$
function using only auxilliary and uncorrelated random bits. By the well-known
connection between $\mathsf{\Sigma}_{k-1}^{\mathsf{P}}$ query algorithms and
constant-depth circuits [FSS84], $M$’s behavior on this size-$2^{n_{i}}$
string can be computed by an
$\mathsf{AC^{0}}\left[2^{\mathrm{poly}(n_{i})},k\right]$ circuit. Corollary 23
shows that such a circuit correctly evaluates this $\textsc{Sipser}_{k+1}$
function with probability greater than (say) 0.6 for at most finitely many
$i$. This even holds conditioned on $M^{\mathcal{O}}$ correctly deciding
$0^{n_{1}},\dots,0^{n_{i-1}}$, because the size-$2^{n_{i}}$
$\textsc{Sipser}_{k+1}$ instance is chosen independently from the smaller
instances, and because $M\left(0^{n_{i}}\right)$ 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\in\mathbb{N}\\}$
between $D_{i}=D_{i,0}$ and $\mathcal{D}$, where in the $j$th hybrid $D_{i,j}$
we sample $A$ and $B_{1},\ldots,B_{n_{i}+j}$ according to $\mathcal{D}$ and
$B_{n_{i}+j+1},B_{n_{i}+j+2},\ldots$ 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 $\mathcal{U}$ to the Forrelated
$\mathcal{F}$, for each function $f:\\{0,1\\}^{(n_{i}+j)^{2}}\to\\{0,1\\}$
corresponding to a $\mathsf{\Sigma}_{k}^{\mathsf{P}}$ oracle machine that
happens to accept.

Suppose we fix the values of $\mathcal{O}$ on everything except for $f$.
Theorem 24 implies that:

$\left|\Pr_{f\sim\mathcal{F}}\left[M^{\mathcal{O}}\left(0^{n_{i}}\right)=1\right]-\Pr_{f\sim\mathcal{U}}\left[M^{\mathcal{O}}\left(0^{n_{i}}\right)=1\right]\right|\leq\frac{\mathrm{poly}(n_{i})}{2^{(n_{i}+j)^{2}/2}}.$
(1)

This is because, again using [FSS84], there exists an
$\mathsf{AC^{0}}\left[2^{\mathrm{poly}(n_{i})},k\right]$ circuit that takes
the oracle string as input and evaluates to
$M^{\mathcal{O}}\left(0^{n_{i}}\right)$. In fact, (1) also holds even if the
parts of $\mathcal{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 $\mathcal{O}$ other than $f$ are
drawn from the distribution conditioned on $M^{\mathcal{O}}$ correctly
deciding $0^{n_{1}},\dots,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:

$\left|\Pr_{\mathcal{O}\sim
D_{i,j-1}}\left[M^{\mathcal{O}}\left(0^{n_{i}}\right)=1\right]-\Pr_{\mathcal{O}\sim
D_{i,j}}\left[M^{\mathcal{O}}\left(0^{n_{i}}\right)=1\right]\right|\leq
2^{n_{i}+j}\cdot\frac{\mathrm{poly}(n_{i})}{2^{(n_{i}+j)^{2}/2}},$

where we implicitly condition on $M^{\mathcal{O}}$ correctly deciding
$0^{n_{1}},\dots,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:

$\displaystyle|q(M,i)-p(M,i)|$ $\displaystyle=\left|\Pr_{\mathcal{O}\sim
D_{i}}\left[M^{\mathcal{O}}\left(0^{n_{i}}\right)=1\right]-\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\left(0^{n_{i}}\right)=1\right]\right|$
$\displaystyle\leq\sum_{j=1}^{\infty}2^{n_{i}+j}\cdot\frac{\mathrm{poly}(n_{i})}{2^{(n_{i}+j)^{2}/2}}$
$\displaystyle\leq\frac{\mathrm{poly}(n_{i})}{2^{\Omega\left(n_{i}^{2}\right)}}$
$\displaystyle\leq 0.1$

for all but at most finitely many $i$. ∎

We conclude this section with a simple corollary.

######  Corollary 28.

There exists an oracle relative to which
$\mathsf{BQP}\not\subset\mathsf{NP/poly}$.

###### Proof.

It is known that for all oracles $\mathcal{O}$,
$\mathsf{coNP}^{\mathcal{O}}\subset\mathsf{NP}^{\mathcal{O}}/\mathsf{poly}$
implies that $\mathsf{PH}^{\mathcal{O}}$ collapses to the third level [Yap83].
Let $\mathcal{O}$ be the oracle used in Theorem 26. Since
$\mathsf{PH}^{\mathcal{O}}$ is infinite,
$\mathsf{coNP}^{\mathcal{O}}\not\subset\mathsf{NP}^{\mathcal{O}}/\mathsf{poly}$.
On the other hand,
$\mathsf{coNP}^{\mathcal{O}}\subseteq\mathsf{BQP}^{\mathcal{O}}$, and hence
$\mathsf{BQP}^{\mathcal{O}}\not\subset\mathsf{NP}^{\mathcal{O}}/\mathsf{poly}$.
∎

###  3.2 Weak $\mathsf{NP}$, Strong $\mathsf{BQP}$

In this section, we prove the following:

######  Theorem 29.

There exists an oracle relative to which
$\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP=P}^{\mathsf{\\#P}}$.

We follow a similar proof strategy to Theorem 26, with some additional steps.
First, we take a random oracle, which separates $\mathsf{PH}$ from
$\mathsf{P}^{\mathsf{\\#P}}$ [Hås87]. We encode the answers to all possible
$\mathsf{P}^{\mathsf{\\#P}}$ queries in instances of the Forrelation problem,
allowing a $\mathsf{BQP}$ machine to efficiently decide any
$\mathsf{P}^{\mathsf{\\#P}}$ language. Then, we add a region of the oracle
that answers all $\mathsf{NP}$ queries, which collapses $\mathsf{PH}$ to
$\mathsf{P}$. Finally, we leverage Theorem 24 to argue that the Forrelation
instances have no effect on the separation between $\mathsf{PH}$ and
$\mathsf{P}^{\mathsf{\\#P}}$, because the Forrelation instances look random to
$\mathsf{PH}$ algorithms. The formal proof is given below.

###### Proof of Theorem 29.

This oracle $\mathcal{O}$ will consist of three parts: a random oracle $A$,
and oracles $B$ and $C$ that we will construct inductively. For each
$t\in\mathbb{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 $\mathcal{O}_{t}=(A_{t},B_{t},C_{t})$.

We first describe $B$, which will effectively collapse
$\mathsf{P}^{\mathsf{\\#P}}$ to $\mathsf{BQP}$. For $t\in\mathbb{N}$, let
$S_{t}$ be the set of all ordered pairs of the form $\langle M,x\rangle$ such
that:

  1. 1.

$M$ is a $\mathsf{P}^{\mathsf{\\#P}}$ oracle machine and $x$ is an input to
$M$,

  2. 2.

$\langle M,x\rangle$ takes less than $t$ bits to specify, and

  3. 3.

$M$ is syntactically restricted to run in less than $t$ steps, and to query
only the
$\mathcal{O}_{1},\mathcal{O}_{2},\ldots,\mathcal{O}_{\lfloor\sqrt{t}\rfloor}$
regions of the oracle.

Note that there are at most $2^{t}$ elements in $S_{t}$. Let
$M_{1},M_{2},\ldots,M_{2^{t}}$ be an enumeration of $S_{t}$. For each $M_{i}$
in $S_{t}$, we add a function $f_{i}:\\{0,1\\}^{t^{2}}\to\\{0,1\\}$ into
$B_{t}$. The function $f_{i}$ is chosen subject to the following rules:

  1. 1.

If $M_{i}$ accepts, then $f_{i}$ is drawn from the Forrelation distribution
$\mathcal{F}_{2^{t^{2}}}$ (given in Theorem 24).

  2. 2.

If $M_{i}$ rejects, then $f_{i}$ is uniformly random.

We next describe $C$, which will effectively collapse $\mathsf{NP}$ to
$\mathsf{P}$. For $t\in\mathbb{N}$, define $T_{t}$ similarly to $S_{t}$,
except that we take $\mathsf{NP}$ oracle machines instead of
$\mathsf{P}^{\mathsf{\\#P}}$ oracle machines. For each $M_{i}$ in $T_{t}$, we
add a bit into $C_{t}$ that returns $M(x)$.

Let $\mathcal{D}$ be the resulting distribution over oracles
$\mathcal{O}=(A,B,C)$. We will show that the statement of the theorem holds
with probability $1$ over $\mathcal{O}$ sampled from $\mathcal{D}$.

######  Claim 30.

$\mathsf{P}^{\mathcal{O}}=\mathsf{NP}^{\mathcal{O}}$ with probability $1$ over
$\mathcal{O}$.

######  Claim 31.

$\mathsf{BQP}^{\mathcal{O}}=\mathsf{P}^{\mathsf{\\#P}^{\mathcal{O}}}$ with
probability $1$ over $\mathcal{O}$.

The proof of 30 is trivial: given an $\mathsf{NP}^{\mathcal{O}}$ machine $M$
and input $x$, a polynomial time algorithm can decide $M(x)$ by simply looking
up the bit in $C$ that encodes $M(x)$. The proof of 31 is completely analogous
to the proof of 27 in Theorem 26, so we omit it.

To complete the proof, we will show that
$\mathsf{NP}^{\mathcal{O}}\neq\mathsf{P}^{\mathsf{\\#P}^{\mathcal{O}}}$ with
probability $1$ over $\mathcal{O}$. Let $L^{\mathcal{O}}$ be the following
unary language: $L^{\mathcal{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^{\mathcal{O}}\in\mathsf{P}^{\mathsf{\\#P}^{\mathcal{O}}}$. We
will show that $L^{\mathcal{O}}\not\in\mathsf{NP}^{\mathcal{O}}$ with
probability $1$ over $\mathcal{O}$.

Fix any $\mathsf{NP}^{\mathcal{O}}$ oracle machine $M$. By the union bound, it
suffices to show that

$\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\text{ decides
}L^{\mathcal{O}}\right]=0.$

Let $n_{1}<n_{2}<\cdots$ be an infinite sequence of input lengths, spaced far
enough apart (e.g. $n_{i+1}=2^{n_{i}}$) such that $M\left(0^{n_{i}}\right)$
can query the oracle on strings of length $n_{i+1}$ or greater for at most
finitely many values of $i$. Next, let

$p(M,i)\coloneqq\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\text{
correctly decides }0^{n_{i}}|M^{\mathcal{O}}\text{ correctly decided
}0^{n_{1}},\dots,0^{n_{i-1}}\right]$

Then we have that

$\Pr_{\mathcal{O}\sim\mathcal{D}}\left[M^{\mathcal{O}}\text{ decides
}L^{\mathcal{O}}\right]\leq\prod_{i=1}^{\infty}p(M,i)$

Thus it suffices to show that, for every fixed $M$, we have $p(M,i)\leq 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 $\mathcal{D}$ on $A$, $C$, and
$B_{1},\ldots,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$,

  1. (a)

$q(M,i)\leq 0.6$ for all but finitely many values of $i$, and

  2. (b)

$|q(M,i)-p(M,i)|\leq 0.1$ for all but finitely many values of $i$.

To prove these, we first need the following lemma, which essentially states
that for any $t^{\prime}\leq\mathrm{poly}(t)$, any bit in $C_{t^{\prime}}$ can
be computed by a small (i.e. quasipolynomial in the input length) constant-
depth $\mathsf{AC^{0}}$ circuit whose inputs do not depend on $C_{i}$ for any
$i>t$.

######  Lemma 32.

Fix $t,d\in\mathbb{N}$, and let $t^{\prime}\leq t^{2^{d}}$. For each $\langle
M,x\rangle\in S_{t^{\prime}}$, 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},\ldots,A_{t^{2^{d-1}}}$; $B_{1},B_{2},\ldots,B_{t^{2^{d-1}}}$;
and $C_{1},C_{2},\ldots,C_{t}$, and outputs $M(x)$.

###### Proof of Lemma.

Assume $t\geq 2$ (otherwise the theorem is trivial). We proceed by induction
on $d$. Consider the base case $d=1$. By definition of $S_{t^{\prime}}$,
$\langle M,x\rangle$ is an $\mathsf{NP}$ oracle machine that runs in less than
$t^{\prime}$ steps and queries only the
$\mathcal{O}_{1},\mathcal{O}_{2},\ldots,\mathcal{O}_{t}$ regions of the
oracle. Hence, $M(x)$ computes a function of certificate complexity
(Definition 20) at most $t^{\prime}$ in the bits of
$\mathcal{O}_{1},\mathcal{O}_{2},\ldots,\mathcal{O}_{t}$. This function may
thus be expressed as a DNF formula of width at most $t^{\prime}$, which is in
turn an AND/OR/NOT circuit of depth $2$ and size at most $2^{t^{\prime}}+1\leq
2^{t^{2}}+1\leq 2^{1+t^{2}}$.

For the inductive step, let $d\geq 2$. Similar to the base case, we use the
definition of $S_{t^{\prime}}$ to obtain a circuit of depth $2$ and size at
most $2^{t^{\prime}}+1$ that takes as input
$\mathcal{O}_{1},\mathcal{O}_{2},\ldots,\mathcal{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},\ldots,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 upper bounded by:

$\displaystyle\left(2^{t^{\prime}}+1\right)+\sum_{i=t+1}^{t^{2^{d-1}}}2^{i}\cdot
2^{1+t^{2^{d-1}}}$
$\displaystyle\leq\left(2^{t^{2^{d}}}+1\right)+\sum_{i=t+1}^{t^{2^{d-1}}}2^{i}\cdot
2^{1+t^{2^{d-1}}}$ $\displaystyle\leq
2^{t^{2^{d}}}+\sum_{i=1}^{t^{2^{d-1}}}2^{i}\cdot 2^{1+t^{2^{d-1}}}$
$\displaystyle\leq 2^{t^{2^{d}}}+2^{1+t^{2^{d-1}}}\cdot 2^{1+t^{2^{d-1}}}$
$\displaystyle=2^{t^{2^{d}}}+2^{2+2t^{2^{d-1}}}$ $\displaystyle\leq
2^{t^{2^{d}}}+2^{4t^{2^{d-1}}}$ $\displaystyle\leq
2^{t^{2^{d}}}+2^{t^{2+2^{d-1}}}$ $\displaystyle\leq
2^{t^{2^{d}}}+2^{t^{2^{d}}}$ $\displaystyle=2^{1+t^{2^{d}}}.$

Above, the first inequality holds because $t^{\prime}\leq 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
$\sum_{i=1}^{j}2^{i}\leq 2^{j+1}$; and the remaining inequalities hold because
$t\geq 2$ and $d\geq 2$. ∎

Note that Lemma 32 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 $\mathcal{O}$ drawn from $\mathcal{D}$ or drawn from any
$D_{i}$. We also note that the circuit given in Lemma 32 is not in
$\mathsf{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.

With Lemma 32 in hand, the remainder of the proof is largely analogous to the
proof of Theorem 26. Statement (a) essentially follows from the work of
[Hås87]. Let $p(n)$ be a polynomial upper bound on the running time of $M$ on
inputs of length $n$, and also on the number of bits needed to specify
$\langle M,0^{n}\rangle$. This also means that $M$ is restricted to query only
$\mathcal{O}_{1},\ldots,\mathcal{O}_{p(n)}$. Let $t=n_{i}$ and
$t^{\prime}=p(n_{i})^{2}$. Then, by Lemma 32, for all sufficiently large $i$,
there exists an $\mathsf{AC^{0}}\left[2^{p(n_{i})^{O(1)}},O(1)\right]$ circuit
that takes as input $A$, $B$, and $C_{1},\ldots,C_{n_{i}}$ and computes
$M\left(0^{n_{i}}\right)$.

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^{\mathcal{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. 1.

The rest of $A$ is sampled uniformly at random,

  2. 2.

$B_{1},\ldots,B_{n_{i}}$ and $C_{1},\ldots,C_{n_{i}}$ are drawn from a
distribution that cannot depend on any queries to $A$ on inputs of length
$\lfloor\sqrt{n_{i}}\rfloor$ or greater (so in particular, they cannot depend
on $A_{n_{i}}$), and

  3. 3.

$B_{n_{i}+1},B_{n_{i}+2},\ldots$ 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 21, $M$ can do this
with probability greater than 0.6 for at most finitely many $i$. This even
holds conditioned on $M^{\mathcal{O}}$ correctly deciding
$0^{n_{1}},\dots,0^{n_{i-1}}$, because the size-$2^{n_{i}}$ parity instance is
chosen independently from the smaller instances, and because
$M\left(0^{n_{i}}\right)$ can query the oracle on strings of length $n_{i+1}$
or greater for at most finitely many values of $i$.

The proof of statement (b) is essentially the same as the proof of the
analogous statement in Theorem 26: we use Lemma 32 to argue that there exists
an $\mathsf{AC^{0}}\left[2^{\mathrm{poly}(n_{i})},O(1)\right]$ circuit that
takes the truth table of a Forrelation instance as input and evaluates to
$M^{\mathcal{O}}\left(0^{n_{i}}\right)$, and then we invoke Theorem 24 and a
hybrid argument to argue that this circuit cannot detect the changes to
$B_{m}$ for $m>n_{i}$ when switching between $\mathcal{D}$ and $D_{i}$. ∎

##  4 Fine Control over $\mathsf{BQP}$ and $\mathsf{PH}$

###  4.1 $\mathsf{BQP}^{\mathsf{PH}}$ Lower Bounds for Sipser Functions

In this section, we prove that
$\mathsf{BQP}^{\mathsf{\Sigma}_{k}^{\mathsf{P}}}$ does not contain
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}}$ relative to a random oracle, generalizing
the known result that $\mathsf{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 33 is just a probabilistic version of Lemma 25.

######  Lemma 33.

Consider a quantum algorithm $Q$ that makes $T$ queries to
$x\in\\{0,1\\}^{N}$. Let $y\in\\{0,1\\}^{N}$ be drawn from some distribution
such that, for all $i\in[N]$, $\Pr_{y}\left[x_{i}\neq y_{i}\right]\leq p$.
Then for any $r>0$:

$\Pr_{y}\left[\left|\Pr\left[Q(y)=1\right]-\Pr\left[Q(x)=1\right]\right|\geq
r\right]\leq\frac{64pT^{2}}{r^{2}}$

###### Proof.

Let $Q$ be the quantum query algorithm corresponding to $f$. By Lemma 25, we
have that for any fixed $y$:

$\left|\Pr\left[Q(x)=1\right]-\Pr\left[Q(y)=1\right]\right|\leq
8\sqrt{T}\cdot\sqrt{\sum_{i:x_{i}\neq y_{i}}q_{i}},$

where we recall the definition of the query magnitudes $q_{i}$ which depend on
the algorithm’s behavior on input $x$, and which satisfy
$\sum_{i=1}^{n}q_{i}=T$. This implies that:

$\displaystyle\Pr_{y}\left[\left|\Pr\left[Q(y)=1\right]-\Pr\left[Q(x)=1\right]\right|\geq
r\right]$ $\displaystyle\leq\Pr_{y}\left[8\sqrt{T}\cdot\sqrt{\sum_{i:x_{i}\neq
y_{i}}q_{i}}\geq r\right]$ $\displaystyle=\Pr_{y}\left[\sum_{i:x_{i}\neq
y_{i}}q_{i}\geq\frac{r^{2}}{64T}\right]$
$\displaystyle\leq\frac{64T}{r^{2}}\cdot\mathop{\mathbb{E}}_{y}\left[\sum_{i:x_{i}\neq
y_{i}}q_{i}\right]$
$\displaystyle=\frac{64T}{r^{2}}\cdot\sum_{i=1}^{n}q_{i}\cdot\Pr_{y}[y_{i}\neq
x_{i}]$ $\displaystyle\leq\frac{64pT^{2}}{r^{2}},$

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

######  Corollary 34.

Let $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$ be a partial function with
$\operatorname{\mathsf{Q}}(f)\leq T$. Fix $x\in\\{0,1\\}^{N}$, and let
$y\in\\{0,1\\}^{N}$ be drawn from some distribution such that, for all
$i\in[N]$, $\Pr_{y}\left[x_{i}\neq y_{i}\right]\leq p$. Then for some
$i\in\\{0,1\\}$, $\Pr_{y}[f(y)=i]\leq 2304pT^{2}$.

###### Proof.

Let $Q$ be the quantum query algorithm corresponding to $f$. We choose $i=1$
if $\Pr\left[Q(x)=1\right]\leq\frac{1}{2}$, and $i=0$ otherwise. Then the
claim follows from Lemma 33 with $r=\frac{1}{6}$, just because $Q$ computes
$f$ with error at most $\frac{1}{3}$. ∎

We now prove a query complexity version of the main result of this section.

######  Theorem 35.

Let $\textsc{Sipser}_{d}$ be the function defined in Theorem 22 for some
choice of $d$, $m$, and $N$. Let $f:\\{0,1\\}^{N}\to\\{0,1,\bot\\}$ be
computable by a depth-$d$ circuit of size $s$ in which the top gate has
bounded-error quantum query complexity $T$, and all of the sub-circuits of the
top gate are depth-$(d-1)$ $\mathsf{AC^{0}}$ circuits. Then:

$\Pr_{x\sim\\{0,1\\}^{N}}\left[f(x)=\textsc{Sipser}_{d}(x)\right]\leq\frac{1}{2}+O\left(2^{-m/4}\right)+s2^{-2^{m/2-4}}+2304T^{2}2^{-m/2-4}.$

The proof of this theorem largely follows Theorem 10.1 of [HRST17], the
relevant parts of which are quoted in Theorem 22. We take a distribution
$\rho\sim\mathcal{R}$ of random projections with the property that (a)
$\mathcal{R}$ completes to the uniform distribution, (b) $f_{\rho}$ simplifies
with high probability over $\rho$, and (c) $\textsc{Sipser}_{d|\rho}$ retains
structure with high probability over $\rho$. Essentially the only difference
compared to [HRST17] is that we must incorporate the BBBV Theorem (in the form
of Corollary 34) in order to argue (b).

###### Proof of Theorem 35.

By Theorem 22(a),

$\Pr_{x\sim\\{0,1\\}^{N}}\left[f(x)=\textsc{Sipser}_{d}(x)\right]=\Pr_{x\sim
D,\rho\sim\mathcal{R}}\left[f_{\rho}(x)=\textsc{Sipser}_{d|\rho}(x)\right].$

Theorem 22(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
$\rho\sim\mathcal{R}$, $f_{\rho}$ 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_{\rho}$ “simplifies”. By
Theorem 22(c) and a union bound, except with probability at most
$O\left(2^{-m/2}\right)+s2^{-2^{m/4-2}}$ over $\rho\sim\mathcal{R}$,
$f_{\rho}$ simplifies and $\textsc{Sipser}_{d|\rho}$ is an AND of fan-in $(\ln
2)\cdot 2^{m}\cdot\left(1\pm O\left(2^{-m/4}\right)\right)$.

An AND of fan-in $(\ln 2)\cdot 2^{m}\cdot\left(1\pm
O\left(2^{-m/4}\right)\right)$ evaluates to $1$ with probability
$\frac{1}{2}\left(1\pm O\left(2^{-m/4}\right)\right)$ on an input sampled from
$D$. On the other hand, if $f_{\rho}$ simplifies, then for each sub-circuit
$C$ of the top gate, $\Pr_{x\sim D}\left[C(x)\neq
C\left(1^{|x|}\right)\right]\leq b2^{m/2-4}$, just because
$\operatorname{\mathsf{D}}(C)\leq 2^{m/2-4}$ and each bit of $x$ is $0$ with
probability at most $b$. Hence, by Corollary 34 with $p=b2^{m/2-4}$, if
$f_{\rho}$ simplifies, then for some $i\in\\{0,1\\}$, $\Pr_{x\sim
D}\left[f_{\rho}(x)=i\right]\leq 2304bT^{2}2^{m/2-4}$. Since $b\leq 2^{-m}$,
putting these together gives us that:

$\Pr_{x\sim\mathcal{D},\rho\sim\mathcal{R}}\left[f_{\rho}(x)=\textsc{Sipser}_{d|\rho}(x)\right]\leq\frac{1}{2}+O\left(2^{-m/4}\right)+s2^{-2^{m/2-4}}+2304T^{2}2^{-m/2-4}.\qed$

By standard techniques, we obtain the main result of this section, stated in
terms of oracles instead of query complexity.

######  Corollary 36.

For all $k$,
$\mathsf{\Sigma}_{k+1}^{\mathsf{P}^{\mathcal{O}}}\not\subset\mathsf{BQP}^{\mathsf{\Sigma}_{k}^{\mathsf{P}^{\mathcal{O}}}}$
with probability $1$ over a random oracle $\mathcal{O}$.

###### Proof sketch.

Let $d=k+2$. Then this follows from Theorem 35 and the well-known connection
between constant-depth circuits and the polynomial hierarchy [FSS84].
Analogous to [RST15], we take the unary language:

$L^{\mathcal{O}}\coloneqq\left\\{0^{n}:\textsc{Sipser}_{d}\left(\mathcal{O}(y^{1,n}),\mathcal{O}(y^{2,n}),\cdots,\mathcal{O}(y^{N,n}\right)=1\right\\},$

where $\textsc{Sipser}_{d}$ has $N$ inputs, $n=\lceil\log_{2}N\rceil$, and
$y^{i,n}$ denotes the lexicographically $i$th string of length $n$. Then
$L^{\mathcal{O}}$ is computable in
$\mathsf{\Sigma}_{d-1}^{\mathsf{P}^{\mathcal{O}}}$ [RST15, HRST17]. On the
other hand, Theorem 35 with $m=\Theta(n)$, $T=\mathrm{poly}(n)$, and
$s=2^{\mathrm{poly}(n)}$ implies that any
$\mathsf{BQP}^{\mathsf{\Sigma}_{d-2}^{\mathsf{P}^{\mathcal{O}}}}$ machine
decides $L^{\mathcal{O}}(0^{n})$ with probability at most $\frac{1}{2}+o(1)$
over $\mathcal{O}$, for infinitely many $n$, even conditioned on correctly
deciding $L^{\mathcal{O}}(0^{\ell})$ for all $\ell<n$. In particular, for
every $\mathsf{BQP}^{\mathsf{\Sigma}_{d-2}^{\mathsf{P}^{\mathcal{O}}}}$
machine, with probability $1$ there exists some $n$ on which it fails. As
there are only countably many
$\mathsf{BQP}^{\mathsf{\Sigma}_{d-2}^{\mathsf{P}^{\mathcal{O}}}}$ machines, we
conclude that
$L^{\mathcal{O}}\not\in\mathsf{BQP}^{\mathsf{\Sigma}_{d-2}^{\mathsf{P}^{\mathcal{O}}}}$
with probability $1$ over $\mathcal{O}$. ∎

###  4.2 $\mathsf{BQP}^{\mathsf{PH}}$ Lower Bounds for
$\textsc{OR}\circ\textsc{Forrelation}$

In this section, we use tail bounds on the sensitivity of $\mathsf{AC^{0}}$
circuits to construct an oracle relative to which
$\mathsf{NP}^{\mathsf{BQP}}\not\subset\mathsf{BQP}^{\mathsf{PH}}$. Such bounds
are given implicitly in Section 3 of [GSTW16]. For completeness, we derive our
own bound on the sensitivity tails of $\mathsf{AC^{0}}$ circuits, though our
bound is probably quantitatively suboptimal.

To prove that the sensitivity of $\mathsf{AC^{0}}$ circuits concentrates well,
the first ingredient we need is a random restriction lemma for
$\mathsf{AC^{0}}$ circuits. We use the following form, due to Rossman [Ros17].

######  Theorem 37 ([Ros17]).

Let $f\in\mathsf{AC^{0}}[s,d]$, and let $\rho$ be a random restriction with
$\Pr[*]=p$. Then for any $t>0$:

$\Pr_{\rho}\left[\operatorname{\mathsf{D}}(f_{\rho})\geq
t\right]\leq\left(p\cdot O\left(\log s\right)^{d-1}\right)^{t}.$

With this in hand, it is straightforward to derive our sensitivity tail bound.

######  Lemma 38.

Let $f:\\{0,1\\}^{N}\to\\{0,1\\}$ be a circuit in $\mathsf{AC^{0}}[s,d]$. Then
for any $t>0$,

$\Pr_{x\sim\\{0,1\\}^{N}}\left[\operatorname{\mathsf{s}}^{x}(f)\geq
t\right]\leq 2N\cdot 2^{-\Omega\left(\frac{t}{(\log s)^{d-1}}\right)}.$

###### Proof.

Let $\rho$ be a random restriction with $\Pr[*]=p$, for some $p$ to be chosen
later. It will be convenient to view the choice of $\rho$ as follows: we
choose a string $x\in\\{0,1\\}^{N}$ uniformly at random, and then we choose a
set $S\subseteq[N]$ wherein each $i\in[N]$ is included in $S$ independently
with probability $p$. Then, we take $\rho$ to be:

$\rho(i)=\begin{cases}*&i\in S\\\ x_{i}&i\not\in S.\end{cases}$

Thus, by definition, it holds that $f_{\rho}(x|_{S})=f(x)$.

Observe that for any fixed $x\in\\{0,1\\}^{N}$ and $j>0$, we have:

$\displaystyle\operatorname{\mathsf{s}}^{x}(f)$
$\displaystyle=\frac{1}{p}\mathop{\mathbb{E}}_{S}\left[\operatorname{\mathsf{s}}^{x|_{S}}(f_{\rho})\right]$
$\displaystyle\leq\frac{1}{p}\mathop{\mathbb{E}}_{S}\left[\operatorname{\mathsf{s}}(f_{\rho})\right]$
$\displaystyle\leq\frac{1}{p}\mathop{\mathbb{E}}_{S}\left[\operatorname{\mathsf{D}}(f_{\rho})\right]$
$\displaystyle\leq\frac{1}{p}\cdot\left(j+N\cdot\Pr_{S}\left[\operatorname{\mathsf{D}}(f_{\rho})\geq
j\right]\right),$ (2)

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 $\operatorname{\mathsf{D}}(f_{\rho})\leq N$
always holds.

With this in hand, we derive:

$\displaystyle\Pr_{x}\left[\operatorname{\mathsf{s}}^{x}(f)\geq t\right]$
$\displaystyle\leq\Pr_{x}\left[\frac{1}{p}\cdot\left(j+N\cdot\Pr_{S}\left[\operatorname{\mathsf{D}}(f_{\rho})\geq
j\right]\right)\geq t\right]$
$\displaystyle=\Pr_{x}\left[\Pr_{S}\left[\operatorname{\mathsf{D}}(f_{\rho})\geq
j\right]\geq\frac{pt-j}{N}\right]$
$\displaystyle\leq\Pr_{x,S}\left[\operatorname{\mathsf{D}}(f_{\rho})\geq
j\right]\cdot\frac{N}{pt-j}$ $\displaystyle\leq\left(p\cdot O\left(\log
s\right)^{d-1}\right)^{j}\cdot\frac{N}{pt-j}.$

Above, the first line applies (2); the third line holds by Markov’s
inequality; and the last line applies Theorem 37.

Choose $p=O\left(\log s\right)^{1-d}$ so that the above expression simplifies
to $2^{-j}\cdot\frac{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 $\mathsf{AC^{0}}$ circuits. We thank Avishay Tal for providing
us with a proof of this fact.

######  Corollary 39.

Let $f:\\{0,1\\}^{N}\to\\{0,1\\}$ be a circuit in $\mathsf{AC^{0}}[s,d]$, and
let $B=\\{B_{1},B_{2},\ldots,B_{k}\\}$ be a collection of disjoint subsets of
$[N]$. Then for any $t$,

$\Pr_{x\sim\\{0,1\\}^{N}}\left[\operatorname{\mathsf{bs}}_{B}^{x}(f)\geq
t\right]\leq 4N\cdot 2^{-\Omega\left(\frac{t}{(\log(s+N))^{d}}\right)}.$

###### Proof.

Consider the function $g:\\{0,1\\}^{N+k}$ defined by

$g(y,z)\coloneqq f\left(y\oplus z_{1}\cdot B_{1}\oplus z_{2}\cdot
B_{2}\oplus\ldots\oplus z_{k}\cdot B_{k}\right),$

where $z_{i}\cdot B_{i}$ denotes the all zeros string if $z_{i}=0$, and
otherwise is the indicator string of $B_{i}$.

We claim that $g\in\mathsf{AC^{0}}[s+O(N),d+1]$. Let $x=y\oplus z_{1}\cdot
B_{1}\oplus z_{2}\cdot B_{2}\oplus\ldots\oplus z_{k}\cdot B_{k}$. 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: $a\oplus b=(a\lor b)\land(\lnot a\lor\lnot
b)=(a\land\lnot b)\lor(\lnot a\land b)$. 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$.

Notice that for any $x\in\\{0,1\\}^{N}$, there are exactly $2^{k}$ strings
$(y,z)\in\\{0,1\\}^{N+k}$ such that $x=y\oplus z_{1}\cdot B_{1}\oplus
z_{2}\cdot B_{2}\oplus\ldots\oplus z_{k}\cdot B_{k}$. Moreover, for any such
$(y,z)$ we have that
$\operatorname{\mathsf{bs}}_{B}^{x}(f)\leq\operatorname{\mathsf{s}}^{(y,z)}(g)$.
Thus, Lemma 38 implies that:

$\Pr_{x\sim\\{0,1\\}^{N}}\left[\operatorname{\mathsf{bs}}_{B}^{x}(f)\geq
t\right]\leq\Pr_{(y,z)\sim\\{0,1\\}^{N+k}}\left[\operatorname{\mathsf{s}}^{(y,z)}(g)\geq
t\right]\leq 2(N+k)\cdot 2^{-\Omega\left(\frac{t}{(\log(s+N))^{d}}\right)},$

and the corollary follows because $k\leq N$. ∎

The rough idea of the proof going forward is as follows: an
$\mathsf{NP}^{\mathsf{BQP}}$ algorithm can easily distinguish (1) a uniformly
random $M\times N$ array of bits, and (2) an $M\times N$ array which contains
a single row drawn from the Forrelation distribution, and is otherwise random.
We want to show that a $\mathsf{BQP}^{\mathsf{PH}}$ algorithm cannot
distinguish (1) and (2). To prove this, we first use our block sensitivity
tail bound to argue in Lemma 40 below that for most uniformly random strings
$x$, an $\mathsf{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 41 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 42 we apply the BBBV Theorem to argue that a
$\mathsf{BQP}^{\mathsf{PH}}$ query algorithm cannot distinguish cases (1) and
(2).

######  Lemma 40.

Let $f:\\{0,1\\}^{MN}\to\\{0,1\\}$ be a circuit in $\mathsf{AC^{0}}[s,d]$. Let
$x\in\\{0,1\\}^{MN}$ be an input, viewed as an $M\times N$ array with $M$ rows
and $N$ columns. Let $y$ be sampled depending on $x$ as follows: uniformly
select one of the rows of $x$, randomly reassign all of the bits of that row,
and leave the other rows of $x$ unchanged. Then for any $\varepsilon>0$:

$\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{y}\left[f(x)\neq
f(y)\right]\geq\varepsilon\right]\leq 8M^{2}N\cdot
2^{-\Omega\left(\frac{\varepsilon M}{(\log(s+MN))^{d}}\right)}.$

###### Proof.

Let $\mathcal{B}$ be the distribution over collections
$B=\\{S_{1},\ldots,S_{M}\\}$ of subsets of $[MN]$ wherein each $S_{i}$ is a
uniformly random subset of the $i$th row. Notice that for any fixed
$x\in\\{0,1\\}^{MN}$ and $j>0$, we have:

$\displaystyle\Pr_{y}\left[f(x)\neq f(y)\right]$
$\displaystyle=\frac{1}{M}\cdot\mathop{\mathbb{E}}_{B\sim\mathcal{B}}\left[\operatorname{\mathsf{bs}}^{x}_{B}(f)\right]$
$\displaystyle\leq\frac{1}{M}\cdot\left(j+M\cdot\Pr_{B\sim\mathcal{B}}\left[\operatorname{\mathsf{bs}}^{x}_{B}(f)\geq
j\right]\right)$
$\displaystyle=\frac{j}{M}+\Pr_{B\sim\mathcal{B}}\left[\operatorname{\mathsf{bs}}^{x}_{B}(f)\geq
j\right],$ (3)

just because one can sample $y$ by drawing $B\sim\mathcal{B}$, $i\sim[M]$, and
taking $y=x^{\oplus S_{i}}$. The inequality in the second line holds because
$\operatorname{\mathsf{bs}}^{x}_{B}(f)\leq|B|=M$.

With this in hand, we derive:

$\displaystyle\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{y}\left[f(x)\neq
f(y)\right]\geq\varepsilon\right]$
$\displaystyle\leq\Pr_{x}\left[\frac{j}{M}+\Pr_{B\sim\mathcal{B}}\left[\operatorname{\mathsf{bs}}^{x}_{B}(f)\geq
j\right]\geq\varepsilon\right]$
$\displaystyle=\Pr_{x}\left[\Pr_{B\sim\mathcal{B}}\left[\operatorname{\mathsf{bs}}^{x}_{B}(f)\geq
j\right]\geq\varepsilon-\frac{j}{M}\right]$
$\displaystyle\leq\Pr_{x,B}\left[\operatorname{\mathsf{bs}}^{x}_{B}(f)\geq
j\right]\cdot\frac{M}{\varepsilon M-j}$ $\displaystyle\leq 4MN\cdot
2^{-\Omega\left(\frac{j}{(\log(s+MN))^{d}}\right)}\cdot\frac{M}{\varepsilon
M-j}$ $\displaystyle\leq\frac{4M^{2}N}{\varepsilon M-j}\cdot
2^{-\Omega\left(\frac{j}{(\log(s+MN))^{d}}\right)}.$

Above, the first line applies (3); the third line holds by Markov’s
inequality; and the fourth line applies Corollary 39. Choosing $j=\varepsilon
M-1$ completes the proof. ∎

######  Lemma 41.

Let $M\leq\mathrm{quasipoly}(N)$, and suppose that
$f:\\{0,1\\}^{MN}\to\\{0,1\\}$ is a circuit in
$\mathsf{AC^{0}}[\mathrm{quasipoly}(N),O(1)]$. Let $x\in\\{0,1\\}^{MN}$ be an
input, viewed as an $M\times N$ array with $M$ rows and $N$ columns. Let $y$
be sampled depending on $x$ as follows: uniformly select one of the rows of
$x$, randomly sample that row from the Forrelation distribution
$\mathcal{F}_{N}$, and leave the other rows of $x$ unchanged. Then for some
$\varepsilon=\frac{\mathrm{polylog}(N)}{\sqrt{N}}$, we have:

$\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{y}\left[f(x)\neq
f(y)\right]\geq\varepsilon\right]\leq 8M^{2}N\cdot
2^{-\Omega\left(\frac{M}{\sqrt{N}\mathrm{polylog}(N)}\right)}.$

###### Proof.

Consider a Boolean function $C(x,z,i)$ that takes inputs $x\in\\{0,1\\}^{MN}$,
$z\in\\{0,1\\}^{N}$, and $i\in[M]$. Let $\tilde{y}$ be the string obtained
from $x$ by replacing the $i$th row with $z$. Let $C$ output $1$ if $f(x)\neq
f(\tilde{y})$, and $0$ otherwise. Clearly,
$C\in\mathsf{AC^{0}}[\mathrm{quasipoly}(N),O(1)]$. Observe that for any fixed
$x$:

$\Pr_{i\sim[M],z\sim\mathcal{F}_{N}}\left[C(x,z,i)=1\right]=\Pr_{y}[f(x)\neq
f(y)].$ (4)

By Theorem 24, for some $\varepsilon=\frac{\mathrm{polylog}(N)}{\sqrt{N}}$ we
have:

$\left|\Pr_{i\sim[M],z\sim\mathcal{F}_{N}}\left[C(x,z,i)=1\right]-\Pr_{i\sim[M],z\sim\\{0,1\\}^{N}}\left[C(x,z,i)=1\right]\right|\leq\frac{\varepsilon}{2}.$
(5)

Putting these together, we obtain:

$\displaystyle\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{y}\left[f(x)\neq
f(y)\right]\geq\varepsilon\right]$
$\displaystyle=\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{i\sim[M],z\sim\mathcal{F}_{N}}\left[C(x,z,i)=1\right]\geq\varepsilon\right]$
$\displaystyle\leq\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{i\sim[M],z\\{0,1\\}^{N}}\left[C(x,z,i)=1\right]\geq\frac{\varepsilon}{2}\right]$
$\displaystyle=\Pr_{x\sim\\{0,1\\}^{MN}}\left[\Pr_{i\sim[M],z\sim\\{0,1\\}^{N}}\left[f(x)\neq
f(\tilde{y})\right]\geq\frac{\varepsilon}{2}\right]$ $\displaystyle\leq
8M^{2}N\cdot 2^{-\Omega\left(\frac{\varepsilon M}{(\log(s+MN))^{d}}\right)}$
$\displaystyle\leq 8M^{2}N\cdot
2^{-\Omega\left(\frac{M}{\sqrt{N}\mathrm{polylog}(N)}\right)},$

where the first line substitutes (4); the second line holds by (5) and the
triangle inequality; the third line holds by the definition of $C$ and
$\tilde{y}$ in terms if $i$ and $z$; the fourth line invokes Lemma 40 for some
$s=\mathrm{quasipoly}(N)$ and $d=O(1)$; and the last line uses these bounds on
$s$ and $d$ along with the assumption that $M\leq\mathrm{quasipoly}(N)$. ∎

The next theorem essentially shows that no $\mathsf{BQP}^{\mathsf{PH}}$ query
algorithm can solve the $\textsc{OR}\circ\textsc{Forrelation}$ problem (i.e.
given a list of Forrelation instances, decide if one of them is Forrelated, or
if they are all uniform).

######  Theorem 42.

Let $M\leq\mathrm{quasipoly}(N)$, and let $f:\\{0,1\\}^{MN}\to\\{0,1,\bot\\}$
be computable by a circuit of size $\mathrm{quasipoly}(N)$ in which the top
gate has bounded-error quantum query complexity $T$, and all of the sub-
circuits of the top gate are $\mathsf{AC^{0}}[\mathrm{quasipoly}(N),O(1)]$
circuits.

Let $b\sim\\{0,1\\}$ be a uniformly random bit. Suppose $z\in\\{0,1\\}^{MN}$
is sampled such that:

  * •

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 $\mathcal{F}_{N}$, and the remaining $M-1$ rows of
$z$ are uniformly random.

Then:

$\Pr_{b,z}[f(z)=b]\leq\frac{1}{2}+\mathrm{quasipoly}(N)\cdot
2^{-\Omega\left(\frac{M}{\sqrt{N}\mathrm{polylog}(N)}\right)}+\frac{T^{2}\mathrm{polylog}(N)}{\sqrt{N}}.$

###### Proof.

We can think of sampling $z$ as follows. First, we choose a string
$x_{0}\sim\\{0,1\\}^{MN}$. Then, we sample $x_{1}$ by uniformly at random
replacing one of the rows of $x_{0}$ with a sample from $\mathcal{F}_{N}$.
Finally, we sample $b\sim\\{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_{x_{1}}[C(x_{0})\neq C(x_{1})]\geq\varepsilon$, where
$\varepsilon\leq\frac{\mathrm{polylog}(N)}{\sqrt{N}}$ is the parameter given
in Lemma 41. Lemma 41, combined with a union bound over the
$\mathrm{quasipoly}(N)$-many such sub-circuits, implies that:

$\Pr_{x_{0}\sim\\{0,1\\}^{MN}}\left[x_{0}\text{ is
bad}\right]\leq\mathrm{quasipoly}(N)\cdot
2^{-\Omega\left(\frac{M}{\sqrt{N}\mathrm{polylog}(N)}\right)}.$

Clearly, it holds that:

$\Pr_{b,z}[f(z)=b]\leq\Pr_{x_{0}\sim\\{0,1\\}^{MN}}\left[x_{0}\text{ is
bad}\right]+\Pr_{x_{1},b}\left[f(x_{b})=b|x_{0}\text{ is good}\right].$

$b$ is uniformly random, even conditioned on $x_{0}$ being good. On the other
hand, Corollary 34 implies that for some $i\in\\{0,1\\}$ (depending on
$x_{0}$), $\Pr_{x_{1},b}\left[f(x_{b})=i|x_{0}\text{ is good}\right]\leq
2304\varepsilon T^{2}$. Thus, it holds that:

$\Pr_{x_{1},b}\left[f(x_{b})=b|x_{0}\text{ is
good}\right]\leq\frac{1}{2}+\frac{T^{2}\mathrm{polylog}(N)}{\sqrt{N}}.$

Putting these bounds together implies the statement of the theorem. ∎

Via standard complexity-theoretic techinques, Theorem 42 implies the following
oracle separation, which resolves the question of Fortnow [For05].

######  Corollary 43.

There exists an oracle relative to which
$\mathsf{NP}^{\mathsf{BQP}}\not\subset\mathsf{BQP}^{\mathsf{PH}}$.

###### Proof sketch.

We construct an oracle $A$ as follows. Let $L^{A}$ be a uniformly random unary
language. For each $n\in\mathbb{N}$, add into $A$ a function
$f_{n}:\\{0,1\\}^{2n^{2}}\to\\{0,1\\}$ as follows:

  * •

If $L^{A}\left(0^{n}\right)=0$, then $f_{n}$ is uniformly random.

  * •

If $L^{A}\left(0^{n}\right)=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
$\mathcal{F}_{2^{t^{2}}}$, and sample the remaining $2^{n^{2}}-1$ rows from
the uniform distribution.

We first show that $L^{A}\in\mathsf{NP}^{\mathsf{BQP}^{A}}$ with probability
$1$ over $A$. To do so, we define a language $M^{A}$ as follows: for a string
$x\in\\{0,1\\}^{*}$, $M^{A}(x)=1$ if $|x|=n^{2}$ and the $x$th row of $f_{n}$
was drawn from the Forrelation distribution; otherwise $M^{A}(x)=0$. Clearly,
$L^{A}\in\mathsf{NP}^{M^{A}}$: to determine if $0^{n}\in L^{A}$,
nondeterministically guess a string $x\in\\{0,1\\}^{n^{2}}$ and check if $x\in
M^{A}$. Thus, it suffices to show that $M^{A}\in\mathsf{BQP}^{A}$, which we do
below:

######  Claim 44.

$M^{A}\in\mathsf{BQP}^{A}$ with probability $1$ over $A$.

###### Proof of Claim.

The proof is essentially the same as 27, just with slightly different
parameters. We use the algorithm $\mathcal{A}$ from Theorem 24 for
distinguishing the Forrelated and uniform distributions to decide $M^{A}$. For
the last step in which we apply the Borel-Cantelli Lemma to argue that, with
probability $1$ over $A$, $\mathcal{A}$ correctly decides $M^{A}(x)$ for all
but finitely many $x\in\\{0,1\\}^{*}$, we have:

$\sum_{x\in\\{0,1\\}^{*}}\Pr_{A}\left[\mathcal{A}^{A}\text{ does not decide
}M^{A}(x)\right]\leq\sum_{n=1}^{\infty}\sum_{x\in\\{0,1\\}^{n^{2}}}3\cdot
2^{-2n^{2}}\leq\sum_{n=1}^{\infty}2^{n^{2}}\cdot 3\cdot
2^{-2n^{2}}<\infty.\qed$

It remains to show that $L^{A}\not\in\mathsf{BQP}^{\mathsf{PH}^{A}}$ with
probability $1$ over $A$. By analogy with Corollary 36, this follows from
Theorem 42 with $M=N=2^{n^{2}}$ and $T=\mathrm{poly}(n)$, which shows that any
$\mathsf{BQP}^{\mathsf{PH}^{A}}$ machine will correctly decide $L^{A}(0^{n})$
with probability at most $\frac{1}{2}+o(1)$ for infinitely many $n$. ∎

Using techniques analogous to Theorem 29, we obtain the following stronger
oracle separation.

######  Corollary 45.

There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but
$\mathsf{BQP}\neq\mathsf{QCMA}$.

###### Proof sketch.

This oracle $\mathcal{O}$ will consist of two parts: an oracle $A$ drawn from
the same distribution as the oracle $A$ in Corollary 43, and an oracle $B$
that we will construct inductively. For each $t\in\mathbb{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 $\mathcal{O}_{t}=(A_{t},B_{t})$.

Similarly to Theorem 29, we define $S_{t}$ as the set of all $\mathsf{NP}$
machines that take less than $t$ bits to specify, run in at most $t$ steps,
and query only the
$\mathcal{O}_{1},\ldots,\mathcal{O}_{\lfloor\sqrt{t}\rfloor}$ regions of the
oracle. Then, we encode into $B_{t}$ the answers to all machines in $S_{t}$.
This has the effect of making
$\mathsf{P}^{\mathcal{O}}=\mathsf{NP}^{\mathcal{O}}$, as a polynomial-time
algorithm can decide the behavior of any $\mathsf{NP}^{\mathcal{O}}$ machine
$M$ by looking up the relevant bit in $B$ that encodes $M$’s behavior.

It remains to show that
$\mathsf{BQP}^{\mathcal{O}}\neq\mathsf{QCMA}^{\mathcal{O}}$ with probability
$1$ over $\mathcal{O}$. We achieve this by taking the language $L^{A}$ defined
in Corollary 43, which is clearly in $\mathsf{QCMA}^{\mathcal{O}}$, and
showing that $L^{A}\not\in\mathsf{BQP}$ with probability $1$ over
$\mathcal{O}$.

Analogous to Lemma 32, one can show that for any
$t^{\prime}\leq\mathrm{poly}(t)$, any bit of $B_{t^{\prime}}$ can be computed
by an $\mathsf{AC^{0}}\left[2^{\mathrm{poly}(t)},O(1)\right]$ circuit whose
inputs depend only on $A$ and $B_{1},B_{2},\ldots,B_{t}$. Hence, any
$\mathsf{BQP}^{\mathcal{O}}$ machine that runs in time $\mathrm{poly}(t)$ can
be computed by a circuit of size $2^{\mathrm{poly}(t)}$ in which the top gate
has bounded-error quantum query complexity $\mathrm{poly}(t)$, all of the sub-
circuits of the top gate are
$\mathsf{AC^{0}}\left[2^{\mathrm{poly}(t)},O(1)\right]$ circuits, and the
inputs are $A$ and $B_{1},B_{2},\ldots,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 $\textsc{OR}\circ\textsc{Forrelation}$ instance
encodes $L^{A}(0^{n})$. But in that case, we can again appeal to Theorem 42
with $M=N=2^{n^{2}}$ and $T=\mathrm{poly}(n)$ to argue that such an algorithm
correctly decides $L^{A}(0^{n})$ with probability at most $\frac{1}{2}+o(1)$
for infinitely many $n$. ∎

###  4.3 $\mathsf{PH}^{\mathsf{BQP}}$ Lower Bounds for
$\textsc{Forrelation}\circ\textsc{OR}$

In this section, we construct an oracle relative to which
$\mathsf{BQP}^{\mathsf{NP}}\not\subset\mathsf{PH}^{\mathsf{PromiseBQP}}$.

Within this section, for a string $z\in\\{0,1\\}^{M}$ and some choice of $N$,
let $\mathcal{D}_{z,N}$ denote the following distribution over
$\\{0,1\\}^{MN}$. View $x\sim\mathcal{D}_{z,N}$ as an $M\times N$ array of
bits sampled as follows: if $z_{i}=0$, then the $i$th row of $x$ is all $0$s,
while if $z_{i}=1$, then the $i$th row of $x$ has a single $1$ chosen
uniformly at random and $0$s everywhere else.

Our first key lemma shows that, for a string $x\sim\mathcal{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 46.

Consider a quantum algorithm $Q$ that makes $1$ query to $x\in\\{0,1\\}^{MN}$
to produce a state $\ket{\psi}$. Then for any $K\in\mathbb{N}$, there exists a
deterministic classical algorithm that makes $K$ queries to $x$, and outputs a
description of a state $\ket{\varphi}$ such that for any
$\alpha\geq\sqrt{\frac{8}{N}}$ and any $z\in\\{0,1\\}^{M}$:

$\Pr_{x\sim\mathcal{D}_{z,N}}\left[||\ket{\psi}-\ket{\varphi}||\geq\alpha\right]\leq
e^{-\frac{\alpha^{4}K}{32}}.$

###### Proof.

Analogous to Lemma 25, 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 $\ket{\psi_{0}}$ of $Q$ has the form:

$\ket{\psi_{0}}=\sum_{i=1}^{M}\sum_{j=1}^{N}\alpha_{i,j,w}\ket{i,j,w},$

where $w$ are indices over a workspace register, then

$q_{i,j}\coloneqq\sum_{w}|\alpha_{i,j,w}|^{2},$

so that $\sum_{i=1}^{M}\sum_{j=1}^{N}q_{i,j}=1$.

The classical algorithm is simply the following: query every $x_{i,j}$ such
that $q_{i,j}\geq\frac{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
$\ket{\varphi}$.

We now argue that the classical algorithm achieves the desired approximation
to $\ket{\psi}$ with the correct probability. Fix some $z\in\\{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:

$w(i,x)\coloneqq\begin{cases}q_{i,j(i,x)}&z_{i}=1\text{ and
}q_{i,j(i,x)}<\frac{1}{K},\\\ 0&\text{otherwise}.\end{cases}$ (6)