Authors Xinyu Wu,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11
www.theoryofcomputing.org
NOTE
A Stochastic Calculus Approach to the
Oracle Separation of BQP and PH
Xinyu Wu
Received February 7, 2020; Revised June 17, 2022; Published June 23, 2022
Abstract. Recently, Ran Raz and Avishay Tal proved that in some relativized
world, BQP is not contained in the polynomial-time hierarchy (STOCโ19). It has been
suggested that some aspects of the proof may be simplified by stochastic calculus.
In this note, we describe such a simplification.
1 Introduction
A recent landmark result by Ran Raz and Avishay Tal [8] shows that there exists an oracle ๐ด
such that BQP๐ด * PH๐ด . It has been suggested by several people, including Ryan OโDonnell,
James Lee, and Avishay Tal, that some aspects of the proof may be simplified by stochastic
calculus. We describe such a simplification.
As Aaronson [1] points out, there is a classical correspondence between the relativized
complexity of PH and the size of bounded-depth, unbounded fan-in Boolean circuits (Furst,
Saxe, Sipser [6]). Using this correspondence, the oracle separation reduces to upper bounds on
the statistical difference between two distributions. Concretely, it suffices to show that there
exists a distribution ๐ over {โ1, 1}2๐ such that
ACM Classification: F.1.3, G.3
AMS Classification: 68Q15, 81P68
Key words and phrases: quantum complexity, stochastic calculus
ยฉ 2022 Xinyu Wu
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a017
X INYU W U
1. For any ๐ : {โ1, 1}2๐ โ {0, 1} computable by a quasipolynomial-size bounded-depth
circuit,
polylog (๐)
|E[ ๐ (๐)] โ E[ ๐ (๐ฐ2๐ )]| โค โ , (1)
๐
where ๐ฐ2๐ is the uniform distribution over {โ1, 1}2๐ . The notation E[ ๐ (๐)] means
Exโผ๐ [ ๐ (x)]. In fact, a weaker upper bound of 1/(log ๐)๐(1) would suffice for the oracle
separation.
2. There exists a quantum algorithm ๐ that queries the input once and runs in ๐(log ๐)
time, such that
1
|E[๐(๐)] โ E[๐(๐ฐ2๐ )]| โฅ ฮฉ . (2)
log ๐
For an explanation of why these two items suffice for the separation result, we refer to Raz
and Talโs paper [8]. In their paper, Raz and Tal use a truncated Gaussian for ๐. Moreover,
they take ๐ to be the Forrelation query algorithm (first introduced as โFourier checkingโ by
Aaronson [1], and further analyzed in [2]). In this note, we will describe a construction of a
related but different distribution ๐ based on Brownian motion, which simplifies certain details
of the analysis. The resulting analysis gives the same bounds as Raz and Tal, up to constant
factors.
2 Overview
2.1 Strategy to construct the distribution ๐
For convenience, we shall refer to the distribution called ๐ in the Introduction as ๐ 0. We shall
use ๐ to denote an auxiliary distribution we shall use to construct ๐ 0 (see step 2 below).
We will first give an overview of the strategy to construct the distribution ๐ 0. In this section
we will not formalize stochastic calculus concepts, deferring this to Section 3.
The construction has two main steps:
1. Use a stopped Brownian motion to define a distribution ๐ on [โ1/2, 1/2]2๐ .
2. Round ๐ to a distribution ๐ 0 on {โ1, 1}2๐ which has the same expectation on Boolean
functions. (This step is identical with [8].)
We will define the distribution ๐ by describing how to sample from it.
Let x๐ก be a standard ๐-dimensional Brownian motion, where โstandardโ means its covariance
matrix is ๐ผ ๐ , the ๐ ร ๐ identity matrix. Let y๐ก = ๐ป๐โx๐ก , where ๐ป๐ is the ๐ ร ๐ normalized
Walsh-Hadamard matrix (the W-H matrix divided by ๐). Finally, let B๐ก be the 2๐ ร 1 column
matrix formed by x๐ก on top of y๐ก ; for typographical convenience we write this as B๐ก = (x๐ก , y๐ก ).
Proposition 2.1. B๐ก is a 2๐-dimensional Brownian motion with covariance matrix
๐ผ ๐ป๐
ฮฆB ๐ .
๐ป๐ ๐ผ๐
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 2
A S TOCHASTIC C ALCULUS A PPROACH TO THE O RACLE S EPARATION OF BQP AND PH
We defer the proof to Proposition 3.3.
Let ๐ > 0 and consider the random variable ๐ defined by
๐ B min{๐, first exit time of B๐ก from [โ1/2, 1/2]2๐ } . (3)
Let B๐ denote the random variable obtained by stopping the Brownian motion B๐ก at the
random time ๐ก = ๐ (for appropriately chosen ๐, see the line before Equation (12)). Let ๐ be the
distribution of the random variable B๐ .
Finally, use the method of Raz and Tal to round ๐ to obtain a distribution ๐ 0 on {โ1, 1}2๐
such that the following holds for every Boolean function ๐ : {โ1, 1}2๐ โ {0, 1} :
E [ ๐ห(z)] = 0 E 0[ ๐ (z0)] , (4)
zโผ๐ z โผ๐
where ๐ห denotes the (unique) multilinear polynomial ๐ห : โ2๐ โฆโ โ that extends ๐ . We shall
describe the method and prove Equation (4) in Proposition 4.2.
Therefore, if ๐ satisfies Equations (1) and (2), then so does ๐ 0. Hence, it will suffice to
analyze ๐ instead of ๐ 0.
2.2 Sketch of the quantum algorithm
The quantum algorithm ๐ used in Equation (2) is very simple: since ๐ป๐ can be implemented
by a quantum circuit of depth ๐(log ๐), computing hx, ๐ป๐ yi will only take a single query.
This value will have a large positive expectation when (x, y) is drawn from ๐ but will have
expectation 0 when (x, y) is drawn from ๐ฐ2๐ . This will be proven in Section 6.
2.3 Comparison with the proof of Raz and Tal
The proof here essentially follows the structure of RT, and uses many of the same technical ideas.
The main differences are in the proof of the lower bound against bounded-depth circuits, while
the quantum algorithm stays the same and has only a minor difference in its analysis.
Our main contribution lies in simplifying some aspects of Sections 5 and 7 from [8]. Because
our ๐ is defined to be bounded within [โ1, 1]2๐ , there is no need to analyze a truncation
function applied to ๐, as in [8, Claims 5.2 and 5.3]. Theorem 4.4 reproves [8, Theorem 7.4], using
some ideas from [8, Claim 7.2]. [8, Claim 7.3] is replaced with Lemma 4.3, while the analysis of
the random walk in [8, Theorem 7.4] is replaced with an application of Dynkinโs lemma. Also
using Dynkinโs lemma, we directly prove Theorem 4.4 using bounds on the second derivatives
of the function ๐ , instead of relying on Isserlisโs theorem for moments of multivariate Gaussians.
3 Technical preliminaries
We briefly review some probability and stochastic calculus concepts. See for instance [7, Chapters
2.1 and 7] for more details. We shall use the common notation (ฮฉ, โฑ , P) to denote a probability
space, where ฮฉ is the sample space, โฑ is the ๐-algebra of measurable sets, and P is the probability
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 3
X INYU W U
measure. A random variable is an โฑ -measurable function X : ฮฉ โ โ ๐ . A random variable X
induces a distribution which is a probability measure on โ ๐ , defined by ๐X (๐ต) = P(Xโ1 (๐ต)).
Definition 3.1. A stochastic process is a parametrized collection of random variables {X๐ก } ๐กโ๐
defined on a probability space (ฮฉ, โฑ , P) and assuming values in โ ๐ .
Typically, the parameter space is ๐ = [0, โ). For each ๐ก, we have a random variable
๐ โฆโ X๐ก (๐). On the other hand, for a fixed ๐ we can consider the function ๐ก โฆโ X๐ก (๐), a trajectory
of the process.
Definition 3.2. Let ๐พ be a positive semidefinite symmetric ๐ ร ๐ real matrix. An ๐-dimensional
Brownian motion {B๐ก } ๐กโ[0,โ) with mean 0 and covariance ๐พ is a stochastic process characterized
by the following:
(i) B0 = 0 almost surely.
(ii) for ๐ข, ๐ก โฅ 0 the increment B๐ก+๐ข โ B๐ก is independent of the past, {B๐ } ๐ <๐ก .
(iii) for ๐ข, ๐ก โฅ 0 the increment B๐ก+๐ข โ B๐ก is distributed as an ๐-dimensional Gaussian with
mean 0 and covariance matrix ๐ข๐พ.
(iv) almost all trajectories are continuous.
We say that B is a standard Brownian motion if ๐พ is the identity matrix.
We refer to [7, Section 2.2] for a proof that such a stochastic process exists on some underlying
probability space (ฮฉ, โฑ , P).
We now make an observation.
Proposition 3.3 (Restatement of Proposition 2.1). Let x๐ก be a standard ๐-dimensional Brownian
motion, and y๐ก = ๐ป๐ x๐ก . Let B๐ก = (x๐ก , y๐ก ). Then B๐ก is a 2๐-dimensional Brownian motion with
covariance matrix
๐ผ ๐ ๐ป๐
ฮฆB .
๐ป๐ ๐ผ ๐
Proof. We will check items (i)โ(iv) in the definition of Brownian motion. First, we note that
B๐ก = (x๐ก , y๐ก ) = (๐ผ ๐ , ๐ป๐ )๐ x๐ก , and so (i), (ii), and (iv) hold for B since they hold for x.
Now we show (iii), that is, for fixed ๐ก, ๐ข, we want to show that the random variable
B๐ก+๐ข โ B๐ก = (x๐ก+๐ข , y๐ก+๐ข ) โ (x๐ก , y๐ก ) is distributed as a Gaussian with mean 0 and covariance
๐ขฮฆ. Using property (iii) of x, we see that x๐ก+๐ข โ x๐ก is โ a Gaussian with mean 0 and covariance
๐ข๐ผ ๐ , so (x๐ก+๐ข , y๐ก+๐ข ) โ (x๐ก , y๐ก ) = (๐ผ ๐ , ๐ป๐ )๐ (x๐ก+๐ข โ x๐ก ) = ๐ข(๐ผ ๐ , ๐ป๐ )๐ ๐บ ๐ , where ๐บ ๐ is a standard
๐-dimensional Gaussian. Using the fact that for an ๐ ร ๐ matrix ๐ด, the random variable ๐ด๐บ ๐
is an ๐-dimensional Gaussian with mean 0 and covariance ๐ด๐ด๐ , we obtain that B๐ก+๐ข โ B๐ก is a
Gaussian with mean 0 and covariance ๐ข(๐ผ ๐ , ๐ป๐ )๐ (๐ผ ๐ , ๐ป๐ ) = ๐ขฮฆ.
We now define stopping times.
Definition 3.4. Let X = {X๐ก } ๐กโ[0,โ) be a stochastic process on (ฮฉ, โฑ , P). A random variable
๐ : ฮฉ โ [0, โ) is a stopping time for X if for any ๐ก โ [0, โ), the event {๐ โค ๐ก} is independent of
{X๐ } ๐ >๐ก . The stopped stochastic process X๐ is a random variable defined via X๐ (๐) B X๐(๐) (๐).
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 4
A S TOCHASTIC C ALCULUS A PPROACH TO THE O RACLE S EPARATION OF BQP AND PH
In particular, stopping times may be applied to a Brownian motion to produce a stopped
Brownian motion. For example, any constant ๐0 B ๐ก0 is a stopping time; the stopped Brownian
motion has distribution B๐ก0 . The first time that B๐ก exits the cube [โ1, 1]๐ , ๐1 B inf {๐ก โฅ 0 | B๐ก โ
[โ1, 1]๐ } is also a stopping time. The minimum or maximum of any two stopping times is a
stopping time. In particular, ๐ in Equation (3) is a stopping time.
We will need to use the following fact about Brownian motion.
Proposition 3.5. Let B๐ก be an ๐-dimensional standard Brownian motion, and ๐ be a bounded stopping
time. Then, E[kB๐ k 2 ] = E[๐].
Proof. This follows from a few well-known facts about Brownian motion. First, kB๐ก k 2 โ ๐ก
is a martingale [9, Proposition II.1.2(ii)]. Given a bounded stopping time ๐, E[kB๐ k 2 โ ๐] =
E[kB0 k 2 ] = 0 [9, Proposition II.1.4], and so E[kB๐ k 2 ] = E[๐].
The main stochastic calculus tool we will use is Dynkinโs formula, which, for a function
๐ : โ ๐ โ โ ๐ , relates E[ ๐ (B๐ก )] to the second partial derivatives of ๐ .
Theorem 3.6 (Dynkinโs formula, [7, Theorem 7.4.1]). Let B be an ๐-dimensional Brownian motion
with mean 0 and covariance matrix ๐พ, let ๐ be a bounded stopping time, and let ๐ : โ ๐ โ โ be a twice
continuously differentiable function. The following holds:
๏ฃฎโซ ๐ ร ๏ฃน
E[ ๐ (B๐ )] = ๐ (0) + E ๏ฃฏ ๐พ ๐๐ (๐๐๐ ๐ )(B๐ ) ๐๐ ๏ฃบ๏ฃบ
๏ฃฏ ๏ฃบ
๏ฃฏ (5)
๏ฃฏ 0 ๐,๐โ[๐] ๏ฃบ
๏ฃฐ ๏ฃป
where ๐๐๐ = ๐๐ฅ๐๐๐ฅ .
2
๐ ๐
We will also require the following tail bound on Brownian motion.
Proposition 3.7 ([9, Proposition II.1.8]). Let B be a standard 1-dimensional Brownian motion. For
๐, ๐ก > 0,
Pr sup |B๐ | โฅ ๐๐ก โค eโ๐ ๐ก/2 .
2
0โค๐ โค๐ก
4 Reduction to a Fourier bound
The main technical part of Raz and Talโs proof [8] shows that, for a Boolean function ๐ :
{โ1, 1}2๐ โ {โ1, 1} computable by a bounded-depth, quasipolynomial-size circuit, and a
multivariate Gaussian distribution ๐ต over โ2๐ ,
| E[ ๐ (trnc(๐ต))] โ E[ ๐ (๐ฐ2๐ )]| โค ๐(๐พ ยท polylog(๐)), (6)
where ๐พ is a bound on the (pairwise) covariances of the coordinates of ๐ต, trnc truncates ๐ต
so that the resulting random variable is within [โ1, 1]๐ , and ๐ฐ๐ is the uniform distribution
over {โ1, 1} ๐ . This is based on the ๐ = 2 case of Talโs fundamental result [10] that gives a
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 5
X INYU W U
polylog(๐) upper bound on the the level-๐ Fourier coefficients of Boolean functions computable
by a Boolean circuit of bounded depth and size ๐. We state Talโs exact bound as Theorem 5.1
below.
Another natural way of viewing a multivariate Gaussian distribution is as the result of an
๐-dimensional Brownian motion stopped at a fixed time. We can also build the truncation into
the stopping time. This allows us to use tools from stochastic calculus to analyze the distribution.
We first recall the definition of restrictions of Boolean functions.
Definition 4.1 (restriction). Let ๐ : {โ1, 1} ๐ โ โ and let ๐ โ {โ1, 1, โ} ๐ . Let free(๐) be the set
of coordinates with โโs. We define the restriction of ๐ by ๐ as ๐๐ : {โ1, 1} ๐ โ โ, where ๐๐ (๐ฅ) is
๐ evaluated at ๐ with the coordinates of ๐ฅ replacing1 the โโs in ๐.
Henceforth, we also identify functions on a Boolean domain, ๐ : {โ1, 1} ๐ โ โ, with their
multilinear polynomial representations (or Fourier expansions)
ร ร
๐ (๐ฅ) = ๐ (๐)
b ๐ฅ๐ . (7)
๐โ[๐] ๐โ๐
The following result has been extracted from the proof of Equation (2) in [8, Sec. 5].
Proposition 4.2. Let ๐ be a distribution on [โ1, 1]๐ . Let z0 โผ ๐ 0 be sampled by first drawing z โผ ๐.
Then, independently for each ๐ โ [๐], we will set z0๐ = 1 with probability (1 + z๐ )/2 and z0๐ = โ1 with
probability (1 โ z๐ )/2. For any function ๐ : {โ1, 1} ๐ โ โ, after identifying ๐ with its multilinear
polynomial representation, we have
E [ ๐ (z)] = 0 E 0[ ๐ (z0)].
zโผ๐ z โผ๐
Proof. The proof follows from the Fourier expansion. First, fix ๐ง โ [โ1, 1]๐ , and then draw
z0 โ {โ1, 1} ๐ using the procedure above.
๏ฃฎร ร ๏ฃน ร ร
0 0
๐ ๐ง] ๐ ๐ง ๐ E[z0๐ | ๐ง] = ๐ (๐ง).
๏ฃฏ ๏ฃบ
E [ (z ) | = E ๏ฃฏ b (๐) z ๐
๏ฃบ= b (๐)
z0 โผz ๏ฃฏ ๏ฃบ
๏ฃฏ๐โ[๐] ๐โ๐ ๏ฃบ ๐โ[๐] ๐โ๐
๏ฃฐ ๏ฃป
Taking the expectation of ๐ง over ๐, we infer Ezโผ๐ [ ๐ (z)] = Ez0โผ๐ 0 [ ๐ (z0)].
We make some observations about Fourier coefficients. First, the Fourier coefficients of ๐๐
๐๐ (๐) = 0 for all ๐ * free(๐). We also have that
satisfy b
๐ (๐) = (๐๐ ๐ )(0),
b (8)
๐
where ๐๐ = ๐โ๐ ๐๐ and ๐๐ = ๐๐ฅ ๐ is the partial derivative.
ร
1Although the domain of ๐๐ is {โ1, 1} ๐ , it only depends on the coordinates in free(๐).
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 6
A S TOCHASTIC C ALCULUS A PPROACH TO THE O RACLE S EPARATION OF BQP AND PH
Further, because ๐ is multilinear, for any โ โ โ \ {0} and any standard basis vector ๐ ๐ we
have
๐ (๐ฅ + โ๐ ๐ ) โ ๐ (๐ฅ)
(๐๐ ๐ )(๐ฅ) = . (9)
โ
The following lemma is similar to [5, Claim A.5], which first appeared in [3] and [4, Claim
3.3].
Lemma 4.3. Let ๐ : โ ๐ โ โ be a multilinear polynomial. For any ๐ฅ โ [โ1/2, 1/2]๐ , there exists a
distribution โ ๐ฅ over restrictions ๐ โ {โ1, 1, โ} ๐ , such that for any ๐, ๐ โ [๐],
(๐๐๐ ๐ )(๐ฅ) = 4 E (๐๐๐ ๐๐ )(0) .
(10)
๐โผโ ๐ฅ
Proof. We define โ ๐ฅ as follows: for each coordinate ๐ โ [๐] we independently set ๐ ๐ to be 1 with
probability 14 + ๐ฅ2๐ , to be โ1 with probability 14 โ ๐ฅ2๐ , and to be โ with probability 12 .
Using that ๐ is a multilinear polynomial, and that the coordinates are independent, we
deduce that for any ๐ฆ โ โ ๐ , ๐ (๐ฅ + ๐ฆ) = E๐โผโ ๐ฅ ๐๐ (2๐ฆ) . Then, using Equation (9),
(๐๐๐ ๐ )(๐ฅ) = ๐ (๐ฅ + ๐ ๐ + ๐ ๐ ) โ ๐ (๐ฅ + ๐ ๐ ) โ ๐ (๐ฅ + ๐ ๐ ) + ๐ (๐ฅ)
๐๐ (2๐ ๐ + 2๐ ๐ ) โ ๐๐ (2๐ ๐ ) โ ๐๐ (2๐ ๐ ) + ๐๐ (0) = 4 E (๐๐๐ ๐๐ )(0) .
= E
๐โผโ ๐ฅ ๐โผโ ๐ฅ
We now show our main result, which is analogous to [5, Theorem A.7] and [8, Theorem 2.4].
Theorem 4.4. Let ๐ : {โ1, 1} ๐ โ {โ1, 1} be a Boolean function, and let ๐ฟ > 0 such that for any
restriction ๐, ร
|b๐๐ (๐)| โค ๐ฟ.
๐โ[๐]
|๐|=2
Let ๐พ > 0 and let B be an ๐-dimensional Brownian motion with mean 0 and covariance matrix ๐พ.
Further assume that |๐พ ๐๐ | โค ๐พ for ๐ โ ๐.
Let ๐ > 0 and define the stopping time
๐ B min {๐, first time that B๐ก exits [โ1/2, 1/2]๐ }.
Then, identifying ๐ with its multilinear representation, we have
|E[ ๐ (B๐ )] โ E[ ๐ (๐ฐ๐ )]| โค 2๐๐พ๐ฟ.
Proof. First, we note that E[ ๐ (๐ฐ๐ )] = ๐ (0). Note that B๐ is always within [โ1/2, 1/2]๐ . We can
apply Theorem 3.6
๏ฃฎโซ ๐ ๏ฃน
1 ร
E[ ๐ (B๐ )] โ ๐ (0) = E ๏ฃฏ ๐พ ๐๐ (๐๐๐ ๐ )(B๐ ) ๐๐ ๏ฃบ๏ฃบ .
๏ฃฏ ๏ฃบ
๏ฃฏ (11)
๏ฃฏ 0 2 ๐,๐โ[๐] ๏ฃบ
๏ฃฐ ๏ฃป
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 7
X INYU W U
Then, we use the upper bound ๐ โค ๐, and that (๐๐๐ ๐ ) = 0 for all ๐ โ [๐] because ๐ is multilinear,
to get
๏ฃฎ ๏ฃน
1 ร
| E[ ๐ (B๐ )] โ ๐ (0)| โค ๐ E ๏ฃฏ sup ๐พ ๐๐ (๐๐๐ ๐ )(B๐ ) ๏ฃบ๏ฃบ
๏ฃฏ ๏ฃบ
๏ฃฏ
๏ฃฏ๐ โ[0,๐] 2 ๐,๐โ[๐] ๏ฃบ
๐๐พ
๏ฃฐ ร ๏ฃป
โค sup (๐๐๐ ๐ )(๐ฅ)
2 ๐ฅโ[โ1/2,1/2]๐
๐โ ๐
ร
(๐๐๐ ๐๐ )(0)
= 2๐๐พ sup E (Lemma 4.3)
๐ฅโ[โ1/2,1/2]๐ ๐โ ๐ ๐โผโ ๐ฅ
๏ฃฎร ๏ฃน
(๐๐๐ ๐๐ )(0) ๏ฃบ๏ฃบ
๏ฃฏ ๏ฃบ
โค 2๐๐พ sup E ๏ฃฏ๏ฃฏ
๐ฅโ[โ1/2,1/2]๐ ๐โผโ ๐ฅ ๏ฃฏ ๐โ ๐ ๏ฃบ
๏ฃฐ ๏ฃป
๏ฃฎ ๏ฃน
๏ฃฏ ร ๏ฃบ
๐๐ (๐) ๏ฃบ๏ฃบ
๏ฃฏ ๏ฃบ
โค 2๐๐พ sup E ๏ฃฏ๏ฃฏ b (Equation (8))
๐ฅโ[โ1/2,1/2]๐ ๐โผโ ๐ฅ ๏ฃฏ๐โfree(๐) ๏ฃบ
๏ฃฏ ๏ฃบ
๏ฃฐ |๐|=2 ๏ฃป
โค 2๐๐พ๐ฟ.
5 Bound for classical circuits
We now construct the distribution ๐ as described in Section 2.1. Due to Proposition 2.1, we can
take ๐ to be the distribution defined by B๐ , where B is a 2๐-dimensional Brownian motion
with covariance matrix ฮฆ, ๐ is defined as in Theorem 4.4, and and ๐ will be chosen appropriately
before Equation (12) below.
Following RazโTal, we first use the following result of Tal [10] on the Fourier weight of
Boolean circuits.
Theorem 5.1 (Theorem 37(3) of [10]). There exists a constant ๐ถ > 0 such that the following holds.
Let ๐ : {โ1, 1}2๐ โ {โ1, 1} be a Boolean function computed by a Boolean circuit of depth ๐ and size
๐ > 1. Then for all ๐, ร
๐ (๐)| โค 2(๐ถ(log ๐)๐โ1 ) ๐ .
|b
๐:|๐|=๐
In particular, if ๐ is computed by a bounded-depth circuit of quasipoly(๐) size, then
ร
๐ (๐)| โค polylog(๐).
|b
๐:|๐|=2
Since restriction does not increase circuit size or depth, we can apply Theorem 4.4 with
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 8
A S TOCHASTIC C ALCULUS A PPROACH TO THE O RACLE S EPARATION OF BQP AND PH
๐ = 1/(8 ln 2๐) and ๐พ = โ1 , to deduce that
๐
polylog (๐)
| E[ ๐ (B๐ )] โ ๐ (0)| โค โ , (12)
๐
where B๐ is defined as in Theorem 4.4, justifying Equation (1).
6 Quantum algorithm
Finally, we show that a 1-query ๐(log ๐)-time quantum algorithm can distinguish ๐ from the
uniform distribution. This is virtually identical to the argument in [8, Section 6], but we can
again use some stochastic calculus tools on the stopping time built into our, slightly different,
distribution.
The Forrelation query algorithm [1, 2] is an ๐(log ๐)-time quantum algorithm with inputs
๐ฅ, ๐ฆ โ {โ1, 1} ๐ which accepts with probability (1 + ๐(๐ฅ, ๐ฆ))/2, where
1
๐(๐ฅ, ๐ฆ) B h๐ฅ, ๐ป๐ ๐ฆi. (13)
๐
When the pair (๐ฅ, ๐ฆ) is drawn from the uniform distribution, E[๐(๐ฅ, ๐ฆ)] = 0. The quantum
algorithm is to prepare the uniform superposition over the basis states |1i . . . |๐i, query ๐ฅ, apply
the WalshโHadamard transform, query ๐ฆ, apply the WalshโHadamard transform again, then
measure in the computational basis and accept if the outcome is |1i. The quantum algorithm is
described in more detail in [1, Section 3.2].
We show the following inequality [8, Claim 6.3], which shows that the quantum algorithm
distinguishes ๐ from the uniform distribution with sufficiently high probability, justifying
Equation (2).
Proposition 6.1. E(x๐ ,y๐ )โผ๐ [๐(x๐ , y๐ )] โฅ 4๐ .
Proof. We have
1
E [๐(x๐ , y๐ )] = E[hx๐ , ๐ป๐ y๐ i]
(x๐ ,y๐ )โผ๐ ๐
1
= E[hx๐ , ๐ป๐
2
x๐ i] = E[kx๐ k 2 ] .
๐
By Proposition 3.5, we have
E[kx๐ k 2 ] = E[๐] . (14)
By Markovโs inequality,
๐
Pr[๐ > 2๐ ].
E[๐] โฅ
2
If ๐ โค 2๐ , it must be the case that the path exits [โ1/2, 1/2]2๐ no later than 2๐ . Hence, by the
union bound, we have
Pr ๐ โค 2๐ โค 2๐ ยท Pr 1st coordinate of (x๐ , y๐ ) exits โ 12 , 12 not later than 2๐ .
(15)
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 9
X INYU W U
(1)
Each coordinate of (x๐ , y๐ ) is a standard 1D Brownian motion since ๐พ ๐๐ = 1 for all ๐. Let B๐ก
denote the first coordinate of x๐ก . Applying Proposition 3.7,
" #
(1) 1 1
Pr sup |B๐ก | โฅ โค 2eโ1/4๐ = 2eโ2 ln 2๐ โค for ๐ โฅ 4. (16)
0โค๐กโค๐/2 2 4๐
Therefore, Pr[๐ โค 2๐ ] โค 12 , so E[๐] โฅ 4๐ .
7 Acknowledgments
I would like to thank Ryan OโDonnell and Avishay Tal for helpful discussions and their
suggestions concerning an early draft. Thanks also to Gregory Rosenthal and anonymous
reviewers for helpful comments.
References
[1] Scott Aaronson: BQP and the Polynomial Hierarchy. In Proc. 42nd STOC, pp. 141โ150.
ACM Press, 2010. [doi:10.1145/1806689.1806711] 1, 2, 9
[2] Scott Aaronson and Andris Ambainis: Forrelation: a problem that optimally separates
quantum from classical computing. SIAM J. Comput., 47(3):982โ1038, 2018. Preliminary
version in STOCโ15. [doi:10.1137/15M1050902] 2, 9
[3] Boaz Barak and Jarosลaw Bลasiok: On the Raz-Tal oracle separation of BQP and PH, 2018.
windowsontheory.org. 7
[4] Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett: Pseudoran-
dom generators from polarizing random walks. Theory of Computing, 15(10):1โ26, 2019.
Preliminary version in CCCโ18. [doi:10.4086/toc.2019.v015a010] 7
[5] Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal: Pseudorandom
generators from the second Fourier level and applications to AC0 with parity gates. In
Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCSโ19), pp. 22:1โ22:15. Schloss Dagstuhlโ
Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.22, ECCC:TR18-155]
7
[6] Merrick Lee Furst, James B. Saxe, and Michael Sipser: Parity, circuits, and the polynomial-
time hierarchy. Math. Systems Theory, 17(1):13โ27, 1984. Preliminary version in FOCSโ81.
[doi:10.1007/BF01744431] 1
[7] Bernt รksendal: Stochastic Differential Equations. Universitext. Springer, 6th edition, 2003.
[doi:10.1007/978-3-642-14394-6] 3, 4, 5
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 10
A S TOCHASTIC C ALCULUS A PPROACH TO THE O RACLE S EPARATION OF BQP AND PH
[8] Ran Raz and Avishay Tal: Oracle separation of BQP and PH. In Proc. 51st STOC, pp. 13โ23.
ACM Press, 2019. [doi:10.1145/3313276.3316315, ECCC:TR18-107] 1, 2, 3, 5, 6, 7, 9
[9] Daniel Revuz and Marc Yor: Continuous Martingales and Brownian Motion. Volume 293 of
Grundlehren der Math. Wiss. Springer, 3rd edition, 1999. [doi:10.1007/978-3-662-06400-9] 5
[10] Avishay Tal: Tight bounds on the Fourier spectrum of AC0 . In Proc. 32nd Comput. Complexity
Conf. (CCCโ17), pp. 15:1โ15:31. Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2017.
[doi:10.4230/LIPIcs.CCC.2017.15, ECCC:TR14-174] 5, 8
AUTHOR
Xinyu Wu
Graduate student
Computer Science Department
Carnegie Mellon University
Pittsburgh, PA, USA
xinyuwu cmu edu
https://www.andrew.cmu.edu/user/xinyuw1/
ABOUT THE AUTHOR
Xinyu Wu is a Ph. D. student at Carnegie Mellon University, advised by Ryan
OโDonnell and Pravesh Kothari. Her research interests are in spectral graph
theory, free probability, and their applications in understanding average-case
problems and quantum computing. She grew up in Singapore, and did her
undergraduate degree in math and computer science also at Carnegie Mellon.
She also enjoys cooking, cycling, and cat videos.
T HEORY OF C OMPUTING, Volume 18 (17), 2022, pp. 1โ11 11