Quantum lower bounds by polynomials.
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1}N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O(Ts6) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Introduction
The black-box model of computation arises when one is given a black-box containing
an N -tuple of Boolean variables The box is equipped
to output the bit x i on input i . We wish to determine some property of X , accessing
the x i only through the black-box. Such a black-box access is called a query.
A property of X is any Boolean function that depends on X , that is, a property
is a function f : {0, 1} N
# {0, 1}. We want to compute such properties using as
few queries as possible. For classical algorithms, this optimal number of queries is
known as the decision tree complexity of f .
Consider, for example, the case where the goal is to determine whether or not
X contains at least one 1, so we want to compute the property
# x N-1 . It is well known that the number of queries required to compute OR N
by any classical (deterministic or probabilistic) algorithm is #(N ). Grover [1996]
discovered a remarkable quantum algorithm that can be used to compute OR N with
small error probability using only O( # N ) queries. His algorithm makes essential
use of the fact that a quantum algorithm can apply a query to a superposition of
different i , thereby accessing different input bits x i at the same time, each with some
amplitude. This upper bound of O( # N ) queries was shown to be asymptotically
optimal [Bennett et al. 1997; Boyer et al. 1998; Zalka 1999] (the first version of
Bennett et al. [1997] in fact appeared before Grover's algorithm).
Most other existing quantum algorithms can be naturally expressed in the black-box
model. For example, in the case of Simon's problem [Simon 1997], one is given
a function -
X: {0, 1} n
satisfying the promise that there is an s # {0, 1} n
such that -
(addition
mod 2). The goal is to determine whether not. Simon's quantum algorithm
yields an exponential speed-up over classical algorithms: it requires an expected
number of O(n) applications of -
X , whereas every classical randomized algorithm
for the same problem must make #(
queries. Note that the function -
can
be viewed as a black-box bits, and that an -
application can be simulated by n queries to X . Thus, we see that Simon's problem
fits squarely in the black-box setting, and exhibits an exponential quantum-classical
separation for this promise-problem. The promise means that Simon's problem
# {0, 1} is partial; it is not defined on all X # {0, 1} N but only on X
that correspond to an -
X satisfying the promise. (In the previous example of OR N ,
the function is total; however, the quantum speed-up is only quadratic instead
of exponential.) Something similar holds for the order-finding problem, which is
the core of Shor's [1997] efficient quantum factoring algorithm. In this case, the
780 R. BEALS ET AL.
promise is the periodicity of a certain function derived from the number that we
want to factor (see Cleve [2000] for the exponential classical lower bound for order-
finding). Most other quantum algorithms are naturally expressed in the black-box
model as well. 1
Of course, upper bounds in the black-box model immediately yield upper bounds
for the circuit description model in which the function X is succinctly described as
a (log N ) O(1) -sized circuit computing x i from i . On the other hand, lower bounds
in the black-box model do not imply lower bounds in the circuit model, though
they can provide useful guidance, indicating what certain algorithmic approaches
are capable of accomplishing. It is noteworthy that, at present, there is no known
algorithm for computing OR N (i.e., satisfiability of a log N -variable propositional
formula) in the circuit model that is significantly more efficient than using the circuit
solely to make queries. Some better algorithms are known for k-SAT [Sch-oning
1999] but not for satisfiability in general (though proving that no better algorithm
exists is likely to be difficult, as it would imply P #= NP).
It should also be noted that the black-box complexity of a function only considers
the number of queries; it does not capture the complexity of the auxiliary
computational steps that have to be performed in addition to the queries. In cases
such as the computation of OR, PARITY, MAJORITY, this auxiliary work is not
significantly larger than the number of queries; however, in some cases it may be
much larger. For example, consider the case of factoring N -bit integers. The best
known algorithms for this involve #(N ) queries to determine the integer, followed
by 2 N #(1)
operations in the classical case but only N 2 (log N ) O(1) operations in the
quantum case [Shor 1997]. Thus, the number of queries seems not to be of primary
importance in the case of factoring. However, the problem that Shor's quantum
algorithm actually solves is the order-finding problem, which can be expressed in
the black-box model as mentioned above.
In this paper, we analyze the black-box complexity of several functions and
classes of functions in the quantum computation setting, establishing strong lower
bounds. In particular, we show that the kind of exponential quantum speed-up that
algorithms like Simon's achieve for partial functions cannot be obtained by any
quantum algorithm for any total function: at most a polynomial speed-up is possible.
We also tightly characterize the quantum black-box complexity of all symmetric
functions, and obtain exact bounds for functions such as AND, OR, PARITY, and
MAJORITY for various error models: exact, zero-error, bounded-error.
An important ingredient of our approach is a reduction that translates quantum
algorithms that make T queries into multilinear polynomials of degree at most
2T over the N variables. This is a quantum extension of the so-called polynomial
method, which has been successfully applied in classical complexity theory
(see e.g., Nisan and Szegedy [1994] and Beigel [1993]). Also, our polynomial
relationship between the quantum and the classical complexity is analogous to
earlier results by Nisan [1991], who proved a polynomial relationship between
randomized and deterministic decision tree complexity.
1 See, for example, Deutsch and Jozsa [1992], Boneh and Lipton [1995], Kitaev [1995], Boyer et al.
[1998], Brassard and H-yer [1997], Brassard et al. [1997], H-yer [1997], Mosca and Ekert [1998],
Cleve et al. [1998], Brassard et al. [2000], Grover [1998], Buhrman et al. [1998], van Dam [1998],
Farhi et al. [1999b], H-yer et al. [2001], Buhrman et al. [2001], and van Dam and Hallgren [2000].
Quantum Lower Bounds by Polynomials 781
The only quantum black-box lower bounds known prior to this work were Jozsa's
[1991] limitations on the power of 1-query algorithms, the search-type bounds of
Bennett et al. [1997], Boyer et al. [1998], and Zalka [1999], and some bounds
derived from communication complexity [Buhrman et al. 1998]. The tight lower
bound for PARITY of Farhi et al. [1998] appeared independently and around the
same time as a first version of this work [Beals et al. 1998], but their proof technique
does not seem to generalize easily beyond PARITY. After the first appearance of
this work, our polynomial approach has been used to derive many other quantum
lower bounds. 2 Recently, an alternative quantum lower-bound method appeared
[Ambainis 2000] that yields good bounds in cases where polynomial degrees are
hard to determine (for instance, for AND-OR trees), but it seems, on the other
hand, that some bounds obtainable using the polynomial method cannot easily be
obtained using this new method (see, e.g., Buhrman et al. [1999]).
2. Summary of Results
We consider three different settings for computing f on {0, 1} N in the black-box
model. In the exact setting, an algorithm is required to return f (X ) with certainty
for every X . In the zero-error setting, for every X , an algorithm may return "incon-
clusive" with probability at most 1/2, but if it returns an answer, this must be the
correct value of f (X ) (algorithms in this setting are sometimes called Las Vegas
algorithms). Finally, in the two-sided bounded-error setting, for every X , an algorithm
must correctly return the answer with probability at least 2/3 (algorithms in
this setting are sometimes called Monte Carlo algorithms; the 2/3 is arbitrary and
may be replaced by any 1/2 + # for fixed constant 0 < # < 1/2).
Our main results are: 3
(1) In the black-box model, the quantum speed-up for any total function cannot be
more than by a sixth-root. More specifically, if a quantum algorithm computes
f with bounded-error probability by making T queries, then there is a classical
deterministic algorithm that computes f exactly making at most O(T 6 ) queries.
If f is monotone, then the classical algorithm needs at most O(T 4 ) queries,
and if f is symmetric, then it needs at most O(T 2 ) queries. If the quantum
algorithm is exact, then the classical algorithm needs O(T 4 ) queries.
As a by-product, we also improve the polynomial relation between the decision
tree complexity D( f ) and the approximate degree
of Nisan and
Szegedy [1994] from D( f ) # O(
(2) We tightly characterize the black-box complexity of all nonconstant symmetric
functions as follows: In the exact or zero-error settings #(N ) queries are necessary
and sufficient, and in the bounded-error setting # N (N - #( f ))) queries
2 See, for example Nayak and Wu [1999], Buhrman et al. [1999], Farhi et al. [1999a], Ambainis
[1999], de Wolf [2000], and Servedio and Gortler [2000].
3 All our results remain valid if we consider a controlled black-box, where the first bit of the state
indicates whether the black-box is to be applied or not. (Thus, such a black-box would map |0, i, b, z#
to |0, i, b, z# and |1, i, b, z# to |1, i, b # x i , z#.) Also, our results remain valid if we consider mixed
rather than only pure states. In particular, allowing intermediate measurements in a quantum query
algorithm does not give more power since all measurements can be delayed until the end of the
computation at the cost of some additional memory.


I. SOME QUANTUM COMPLEXITIES
Exact Zero-error Bounded-error
are necessary and sufficient, where #( f
if the Hamming weight of the input changes from k to k + 1} (this #( f ) is a
number that is low if f flips for inputs with Hamming weight close to N/2
[Paturi 1992]). This should be compared with the classical bounded-error query
complexity of such functions, which is #(N ). Thus, #( f ) characterizes the
speed-up that quantum algorithms give for all total functions.
An interesting example is the THRESHOLDM function, which is 1 iff its input
X contains at least M 1s. This has query complexity # M(N
(3) For OR, AND, PARITY, MAJORITY, we obtain the bounds shown in Table I.
(all given numbers are both necessary and sufficient). These results are all new,
with the exception of the # N )-bounds for OR and AND in the bounded-error
setting, which appear in Bennett et al. [1997], Boyer et al. [1998] and
Zalka [1999]. The new bounds improve by polylog(N ) factors previous lower-bound
results from Buhrman et al. [1998], which were obtained through a
reduction from communication complexity. The new bounds for PARITY were
independently obtained by Farhi et al. [1998].
Note that lower bounds for OR imply lower bounds for the search problem,
where we want to find an i such that x if such an i exists. Thus, exact or
zero-error quantum search requires N queries, in contrast to # N ) queries
for the bounded-error case. (On the other hand, if we are promised in advance
that the number of solutions is t , then a solution can be found with probability
using O( # N/t) queries [Brassard et al. 2000].)
3. Some Definitions
Our main goal in this paper is to find the number of queries a quantum algorithm
needs to compute some Boolean function by relating such algorithms to polyno-
mials. In this section, we give some basic definitions and properties of multilinear
polynomials and Boolean functions, and describe our quantum setting.
3.1. Boolean Functions and Polynomials. We assume the following setting,
mainly adapted from Nisan and Szegedy [1994]. We have a vector of N Boolean
variables we want to compute a Boolean function f :
{0, 1} N
# {0, 1} of X . Unless explicitly stated otherwise, f will always be to-
tal. The Hamming weight (number of 1s) of X is denoted by |X |. For example,
odd, and MAJ N (X
We can represent Boolean functions using N -variate polynomials p: R N
# R.
1}, we can restrict attention to multilinear p. If
then we say that represents f . It is easy to see
that every f is represented by a unique multilinear polynomial p of degree # N . We
use deg(f) to denote the degree of this p. If | p(X )- f (X )| # 1/3 for all X # {0, 1} N ,
Quantum Lower Bounds by Polynomials 783
we say p approximates f , and
denotes the degree of a minimum-degree
p that approximates f . For example, x 0 x 1 - x N-1 is a multilinear polynomial of
degree N that represents AND N . Similarly, 1-(1-x 0
. The polynomial 1
but does not represent
Nisan and Szegedy [1994, Theorem 2.1] proved a general lower bound on the
degree of any Boolean function that depends on N variables:
THEOREM 3.1 [NISAN AND SZEGEDY 1994]. If f is a Boolean function that
depends on N variables, then deg( f ) # logN - O(log log N ).
Let p: R N
# R be a polynomial. If # is some permutation on {0, . , N - 1},
be the set of all
permutations. The symmetrization p sym of p averages over all permutations of
the input, and is defined as:
Note that p sym is a polynomial of degree at most the degree of p. Symmetrizing
may actually lower the degree: if
0. The following lemma,
originally due to Minsky and Papert [1968], allows us to reduce an N -variate
polynomial to a single-variate one.
LEMMA 3.2 [MINSKY AND PAPERT 1968]. If p: R n
# R is a multilinear poly-
nomial, then there exists a polynomial q: R # R, of degree at most the degree of
p, such that p sym (X
PROOF. Let d be the degree of p sym , which is at most the degree of p. Let V j
denote the sum of all ( N
products of j different variables, so
can be written
as
for some a i # R. Note that V j assumes value ( |X |
which is a polynomial of degree j of |X |. Therefore, the single-
variate polynomial q defined by
d
satisfies the lemma.
A Boolean function f is symmetric if permuting the input does not change the
function value (i.e., f (X ) only depends on |X |). Paturi has proved a powerful
theorem that characterizes
. For such f , let f
low if f k "jumps" near the middle (i.e., for some k # N/2). Now Paturi
[1992, Theorem 1] gives:
784 R. BEALS ET AL.
THEOREM 3.3 [PATURI 1992]. If f is a nonconstant symmetric Boolean function
on {0, 1} N , then
For functions like OR N and AND N , we have #( f
#(
# N ). For PARITY N (which is 1 iff |X | is odd) and MAJ N (which is 1 iff
|X | > N/2), we have #( f is even and #( f
3.2. THE FRAMEWORK OF QUANTUMNETWORKS. Our goal is to compute some
Boolean function f of given as a black-box: calling
the black-box on i returns the value of x i . Wewant to use as few queries as possible.
A classical algorithm that computes f by using (adaptive) black-box queries to
X is called a decision tree, since it can be pictured as a binary tree where each
node is a query, each node has the two outcomes of the query as children, and the
leaves give answer f (X 1. The cost of such an algorithm is the
number of queries made on the worst-case input X , that is, the depth of the tree.
The decision tree complexity D( f ) of f is the cost of the best decision tree that
computes f . Similarly, we can define R( f ) as the worst-case number of queries for
randomized algorithms that compute f (X ) with error probability # 1/3 for all X .
By a well-known result of Nisan [1991, Theorem 4], the best randomized algorithm
can be at most polynomially more efficient than the best deterministic algorithm:
For a general introduction to quantum computing, we refer to Nielsen and Chuang
[2000]. A quantum network (also called quantum algorithm) with T queries is the
quantum analogue to a classical decision tree with T queries, where queries and
other operations can now be made in quantum superposition. Such a network can
be represented as a sequence of unitary transformations:
where the U i are arbitrary unitary transformations, and the O j are unitary transformations
that correspond to queries to X . The computation ends with some measurement
or observation of the final state. We assume each transformation acts
on m qubits and each qubit has basis states |0# and |1#, so there are 2 m basis
states for each stage of the computation. It will be convenient to represent each
basis state as a binary string of length m or as the corresponding natural num-
ber, so we have basis states |0#, |1#, |2#, . , |2 m
- 1#. Let K be the index set
- 1}. With some abuse of notation, we sometimes identify a set
of numbers with the corresponding set of basis states. Every state |# of the net-work
can be uniquely written as |# k#K # k |k#, where the # k are complex
numbers such that # k#K |# k | 2
1. When |# is measured in the above basis,
the probability of observing |k# is |# k | 2 . Since we want to compute a function
of X , which is given as a black-box, the initial state of the network is not very
important and we disregard it hereafter; we may assume the initial state to be
|0# always.
The queries are implemented using the unitary transformations O j in the following
standard way. The transformation O j only affects the leftmost part of a basis
state: it maps basis state |i, b, z# to |i, b # x i , z# denotes XOR). Here, i has
length #log N# bits, b is one bit, and z is an arbitrary string of m - #log N# - 1
bits. Note that the O j are all equal.
Quantum Lower Bounds by Polynomials 785
How does a quantum network compute a Boolean function f of X? Let us
designate the rightmost qubit of the final state of the network as the output bit.
More precisely, the output of the computation is defined to be the value we observe
if we measure the rightmost qubit of the final state. If this output equals f (X )
with certainty, for every X , then the network computes f exactly. If the output
with probability at least 2/3, for every X , then the network computes
f with bounded error probability at most 1/3. To define the zero-error setting, the
output is obtained by observing the two rightmost qubits of the final state. If the
first of these qubits is 0, the network claims ignorance ("inconclusive"); otherwise,
the second qubit should contain f (X ) with certainty. For every X , the probability
of getting "inconclusive" should be less than 1/2. We use Q
to denote the minimum number of queries required by a quantum network
to compute f in the exact, zero-error and bounded-error settings, respectively.
It can be shown that the quantum setting generalizes the classical setting, hence
4. General Lower Bounds on the Number of Queries
In this section, wewill provide some general lower bounds on the number of queries
required to compute a Boolean function f on a quantum network, either exactly or
with zero- or bounded-error probability.
4.1. THE ACCEPTANCE PROBABILITY IS A POLYNOMIAL. Here, we prove that
the acceptance probability of a T -query quantum network can be written as a
multilinear N -variate polynomial P(X ) of degree at most 2T . The next lemmas
relate quantum networks to polynomials; they are the key to most of our
results.
LEMMA 4.1 Let N be a quantum network that makes T queries to a black-box
. Then there exist complex-valued N -variate multilinear polynomials
, each of degree at most T , such that the final state of the network is
the superposition
for any black-box X .
PROOF. Let |# i # be the state of the network (using some black-box X ) just
before the i th query. Note that |# i +1 # =U i O i |# i #. The amplitudes in |# 0 # depend
on the initial state and on U 0 but not on X , so they are polynomials of X of degree
query maps basis state |i, b, z# to |i, b # x i , z#. Hence, if the amplitude of
|i, 0, z# in |# 0 # is # and the amplitude of |i, 1, z# is #, then the amplitude of |i, 0, z#
after the query becomes (1 - x and the amplitude of |i, 1, z# becomes
are polynomials of degree 1. (In general, if the amplitudes
before a query are polynomials of degree # j , then the amplitudes after the query
will be polynomials of degree Between the first and the second query lies
the unitary transformation U 1 . However, the amplitudes after applying U 1 are just
linear combinations of the amplitudes before applying U 1 , so the amplitudes in |# 1 #
are polynomials of degree at most 1. Continuing in this manner, the amplitudes of
the final states are found to be polynomials of degree at most T . We can make these
786 R. BEALS ET AL.
polynomials multilinear without affecting their values on X # {0, 1} N , by replacing
i by x i .
Note that we have not used the assumption that the U j are unitary, but only their
linearity. The next lemma is also implicit in the combination of some proofs in
Fenner et al. [1993] and Fortnow and Rogers [1999].
LEMMA 4.2 Let Nbe a quantum network that makes T queries to a black-box
X, and B be a set of basis states. Then there exists a real-valued multilinear
polynomial P(X ) of degree at most 2T, which equals the probability that observing
the final state of the network with black-box X yields a state from B.
PROOF. By the previous lemma, we can write the final state of the network as
for any X , where the p k are complex-valued polynomials of degree # T . The probability
of observing a state in B is
If we split p k into its real and imaginary parts as
where pr k and pi k are real-valued polynomials of degree # T , then |
which is a real-valued polynomial of degree at most 2T .
Hence, P is also a real-valued polynomial of degree at most 2T , which we can
make multilinear without affecting its values on X # {0, 1} N .
Letting B be the set of states that have 1 as rightmost bit, it follows that we
can write the acceptance probability of a T -query network (i.e., the probability of
getting output 1) as a polynomial P(X ) of degree # 2T .
4.2. LOWER BOUNDS FOR EXACT AND ZERO-ERROR QUANTUM COMPUTATION.
Consider a quantum network that computes f exactly using queries.
Its acceptance probability P(X ) is a polynomial of degree # 2T that equals f (X )
for all X . But then P(X ) must have degree deg( f ), which implies the following
lower bound result for Q
THEOREM 4.3 If f is a Boolean function, then Q
Combining this with Theorem 3.1, we obtain a weak but general lower bound:
COROLLARY 4.4 If f depends on N variables, then Q
O(loglogN ).
For symmetric f , we can prove a much stronger bound. First, for the zero-error
setting:
THEOREM 4.5 If f is nonconstant and symmetric, then Q
PROOF. We assume f (X for at least (N different Hammingweights
of X ; the proof is similar if f (X for at least (N different Hamming
weights. Consider a network that uses queries to compute f with zero-
error. Let B be the set of basis states that have 11 as rightmost bits. These are
Quantum Lower Bounds by Polynomials 787
the basis states corresponding to output 1. By Lemma 4.2, there is a real-valued
multilinear polynomial P of degree # 2T , such that for all X , P(X ) equals the
probability that the output of the network is 11 (i.e., that the network answers 1).
Since the network computes f with zero-error and f is nonconstant, P(X ) is non-constant
and equals 0 on at least (N different Hamming weights (namely,
the Hamming weights for which f (X q be the single-variate polynomial
of degree #2T obtained from symmetrizing P (Lemma 3.2). This q is nonconstant
and has at least (N hence degree at least (N + 1)/2, and the
result follows.
Thus, functions like threshold functions, etc. all require
at least (N queries to be computed exactly or with zero-error on a quantum
network. Since N queries always suffice, even classically, we have
and
Secondly, for the exact setting we can prove slightly stronger lower bounds using
results by Von zur Gathen and Roche [1997, Theorems 2.6 and 2.8]:
THEOREM 4.6 [VON ZUR GATHEN AND ROCHE 1997]. If f is nonconstant and
symmetric, then deg( f
COROLLARY 4.7 If f is nonconstant and symmetric, then Q
O(N 0.548 ). If, in addition, N
In Section 6, we give more precise bounds for some particular functions. In
particular, this will show that the N/2 lower bound is tight, as it can be met for
PARITY N .
4.3. LOWER BOUNDS FOR BOUNDED-ERROR QUANTUM COMPUTATION. Here,
we use similar techniques to get bounds on the number of queries required for
bounded-error computation of some function. Consider the acceptance probability
of a T-query network that computes f with bounded-error, written as a polynomial
P(X ) of degree #2T . If f (X
then 2/3 # P(X ) # 1. Hence, P approximates f , and we obtain:
THEOREM 4.8 If f is a Boolean function, then Q
This result implies that a quantum algorithm that computes f with bounded
error probability can be at most polynomially more efficient (in terms of number
of queries) than a classical deterministic algorithm: Nisan and Szegedy [1994,
Theorem 3.9] proved that D( f ) # O(
together with the previous
theorem implies The fact that there is a polynomial relation
between the classical and the quantum complexity is also implicit in the generic
oracle-constructions of Fortnow and Rogers [1999]. In Section 5, we prove the
stronger result D( f
Combining Theorem 4.8 with Paturi's Theorem 3.3 gives a lower bound for
symmetric functions in the bounded-error setting: if f is nonconstant and sym-
metric, then Q ))). We can in fact prove a matching upper
bound, using the following result about quantum counting [Brassard et al. 2000,
Theorem 13]:
THEOREM 4.9 [BRASSARD ET AL. 2000]. There exists a quantum algorithm
with the following property. For every N -bit input X (with number T,
788 R. BEALS ET AL.
the algorithm uses T queries and outputs a number -
t such that
t | # 2#
with probability at least 8/# 2 .
THEOREM 4.10 If f is nonconstant and symmetric, then we have that
PROOF. We describe a strategy that computes f with small error probability.
First, note that since #( f
must be identically 0 or 1 for k #
In
order to be able to compute f (X ), it is sufficient to know t exactly if t < #(N -
or to know that #(N -#( f ))/2# t #
Run the quantum counting algorithm for # (N - #( f ))N ) steps to count
the number of 1s in X . If t is in one of the two tails (t < #(N -#( f ))/2# or
high probability, the algorithm gives us an
exact count of t . If #(N - #( f ))/2# t #(N +#( f ) - 2)/2#, then, with high
probability, the counting algorithm returns some - t that is in this interval as well.
Thus, with high probability, f - t equals f This shows that we can compute
f using only O( # N (N - #( f ))) queries.
Theorem 4.10 implies that the above-stated result about quantum counting
(Theorem 4.9) is optimal, since a better upper bound for counting would give a
better upper bound on Q know that
Theorem 4.10 is tight. In contrast to Theorem 4.10, it can be shown that a randomized
classical strategy needs #(N ) queries to compute any nonconstant symmetric
f with bounded-error.
Moreover, it can be shown that almost all functions f satisfy deg( f
Buhrman and de Wolf [2001], hence almost all f have reading
the preliminary version of this paper [Beals et al. 1998], Ambainis [1999] proved
a similar result for the approximate case: almost all f satisfy
O( # N log N ) and hence have On the other hand,
van Dam [1998] proved that, with good probability, we can learn all N variables in
the black-box using only N/2 queries. This implies the general upper bound
. This bound is almost tight, as we will show later
on that Q
4.4. LOWER BOUNDS IN TERMS OF BLOCK SENSITIVITY. Above, we gave lower
bounds on the number of queries used, in terms of degrees of polynomials that
represent or approximate the function f that is to be computed. Here we give
lower bounds in terms of the block sensitivity of f , a measure introduced in
Nisan [1991].
Definition 4.11. Let f : {0, 1} N
# {0, 1} be a function, X # {0, 1} N , and B #
{0, . , N - 1} a set of indices. Let X B denote the string obtained from X by
flipping the variables in B. We say that f is sensitive to B on X if f (X
The block sensitivity bs X ( f ) of f on X is the maximum number t for which there
Quantum Lower Bounds by Polynomials 789
exist t disjoint sets of indices B 1 , . , B t such that f is sensitive to each B i on X .
The block sensitivity bs( f ) of f is the maximum of bs X
For example, bs(OR N
flipping B i in X flips the value of OR N from 0 to 1.
We can adapt the proof of Nisan and Szegedy [1994, Lemma 3.8] on lower
bounds of polynomials to get lower bounds on the number of queries in a quantum
network in terms of block sensitivity. 4 The proof uses a theorem from Ehlich and
Zeller [1964] and Rivlin and Cheney [1966]:
THEOREM 4.12 [EHLICH AND ZELLER 1964; RIVLIN AND CHENEY 1966].
Let p: R#R be a polynomial such that b 1 # p(i) # b 2 for every integer
and the derivative p # satisfies | p # (x)| # c for some real 0 # x # N . Then
THEOREM 4.13. If f is a Boolean function, then
.
PROOF. We prove the lower bound on Q here, the bound on Q completely
analogous. Consider a network using queries that computes f
with error probability #1/3. Let p be the polynomial of degree #2T that approximates
f , obtained as for Theorem 4.8. Note that p(X ) # [0, 1] for all X # {0, 1} N ,
because p represents a probability.
be the input and sets that achieve the block
sensitivity. We assume without loss of generality that f (Z
replacing every x j in p as
follows:
occurs in none of the B i
Now it is easy to see that q has the following properties:
(1) q is a multilinear polynomial of degree # d # 2T
Let r be the single-variate polynomial of degree #d obtained from symmetrizing
q over {0, 1} b (Lemma 3.2). Note that 0 # r (i
and for some x # [0, 1] we have r # (x) # 1/3 (because r (0) # 1/3 and r (1) # 2/3).
Applying Theorem 4.12, we obtain d # (1/3)b/(1/3
We can generalize this result to the computation of partial Boolean functions,
which are only defined on a domain D# {0, 1} N of inputs that satisfy some
promise, by generalizing the definition of block sensitivity to partial functions in the
obvious way.
4 This theorem can also be proved by an argument similar to the lower-bound proof for quantum
searching in Bennett et al. [1997] (see, e.g., Vazirani [1998]).
790 R. BEALS ET AL.
5. Polynomial Relation for Classical and Quantum Complexity
Here we will compare the classical complexities D( f ) and R( f ) with the
quantum complexities. First some separations: in the next section, we show
. In the bounded-error setting
so we have a quadratic gap between Q on the one hand and
on the other. 5
Nisan proved that the randomized complexity is at most polynomially better than
the deterministic complexity: D( f As mentioned in
Section 4, we can prove that also the quantum complexity can be at most polynomially
better than the best deterministic algorithm: D( f Here we give
the stronger result that D( f In other words, if we can compute some
function quantumly with bounded-error using T queries, we can compute it classically
error-free using O(T 6 ) queries. We need the notion of certificate complexity:
Definition 5.1. Let C be an assignment C of values to some subset
S of the N variables. We say that C is consistent with X # {0, 1} N if x i =C(i) for
For b # {0, 1}, a b-certificate for f is an assignment C such that f (X
X is consistent with C . The size of C is |S|.
The certificate complexity C X ( f ) of f on X is the size of a smallest f (X )-
certificate that is consistent with X . The certificate complexity of f is C( f
The 1-certificate complexity of f is C (1) ( f
and similarly we define C
For example, if f is the OR-function, then the certificate complexity on the input
(1, 0, 0, . , 0) is 1, because the assignment x forces the OR to 1. The
same holds for the other X for which f (X On the other hand,
the certificate complexity on (0, 0, . , 0) is N , so C( f
The first inequality in the next lemma is obvious from the definitions, the second
inequality is Nisan [1991, Lemma 2.4]. We include the proof for completeness.
LEMMA 5.2 [NISAN 1991]. C (1)
PROOF. Consider an input X # {0, 1} N and let B 1 , . , B b be disjoint minimal
sets of variables that achieve the block sensitivity
show that that sets variables according to X , is a certificate for
X of size # bs( f ) 2 .
First, if C were not an f (X )-certificate, then let X # be an input that agrees
with C , such that f (X Now f is sensitive to B b+1 on X
and B b+1 is disjoint from B 1 , . , B b , which contradicts Hence, C is
an f (X )-certificate.
Second, note that, for must have
of the B i -variables in X B , then the function value must flip from f (X B ) to
5 In the case of randomized decision trees, no function is known for which there is a quadratic gap
between D( f ) and R( f ), the best-known separation is for complete binary AND/OR-trees, where
and it has been conjectured that this is the largest gap possible.
This applies to zero-error randomized trees [Saks and Wigderson 1986] as well as bounded-error trees
[Santha 1991].
Quantum Lower Bounds by Polynomials 791
would not be minimal), so every B i -variable forms a sensitive
set for f on input X B i . Hence, the size of C is |#
The crucial lemma is the following, which we prove along the lines of Nisan
PROOF. The following describes an algorithm to compute f (X ), querying at
most C (1) ( f )bs( f ) variables of X (in the algorithm, by a "consistent" certificate
C or input Y at some point we mean a C or Y that agrees with the values of all
variables queried up to that point).
(1) Repeat the following at most bs( f ) times:
Pick a consistent 1-certificate C and query those of its variables whose X -values
are still unknown (if there is no such C , then return 0 and stop); if the queried
values agree with C , then return 1 and stop.
(2) Pick a consistent Y # {0, 1} N and return f (Y ).
The nondeterministic "pick a C " and "pick a Y " can easily be made deterministic
by choosing the first C (respectively, Y ) in some fixed order. Call this algorithm
A. Since A runs for at most bs( f ) stages and each stage queries at most C (1)
variables, A queries at most C (1) ( f )bs( f ) variables.
It remains to show that A always returns the right answer. If it returns an answer
in step (1), this is either because there are no consistent 1-certificates left (and hence
must be 0) or because X is found to agree with a particular 1-certificate C ;
in both cases A gives the right answer.
Now consider the case where A returns an answer in step (2). We will show
that all consistent Y must have the same f -value. Suppose not. Then there are
consistent Y, Y # with f (Y
contains a consistent 1-certificate C b+1 . We will
derive from these C i disjoint sets B i such that f is sensitive to each B i on Y . For
every as the set of variables on which Y and C i disagree.
Clearly, each B i is non-empty. Note that Y B agrees with C i , so f (Y B
shows that f is sensitive to each B i on Y . Let v be a variable in some
then (v). Now for j > i , C j has been chosen consistent with all
variables queried up to that point (including v), so we cannot have X
. This shows that all B i and B j are disjoint. But then f is
sensitive to bs( f disjoint sets on Y , which is a contradiction. Accordingly, all
consistent Y in step (2) must have the same f -value, and A returns the right value
is one of those consistent Y .
The inequality of the previous lemma is tight, because if f =OR, then D( f
The previous two lemmas imply D( f . Combining this with
Theorem 4.13 (bs( f the main result:
THEOREM 5.4. If f is a Boolean function, then D( f
We do not know if the D( f )-relation is tight, and suspect that
it is not. The best separation we know is for OR and similar functions, where
792 R. BEALS ET AL.
However, for such symmetric Boolean function,
we can do no better than a quadratic separation: D( f ) # N always holds, and we
have Theorem 4.10, hence D( f
f . For monotone Boolean functions, where the function value either increases or
decreases monotonically if we set more input bits to 1, we can use [Nisan 1991,
Proposition 2.2] (bs( f . For the case of
exact computation, we can also give a better result: Nisan and Smolensky proved
f (they never published this, but allowed their proof
to be included in Buhrman and de Wolf [2001]). Together with our Theorem 4.3,
this yields
THEOREM 5.5. If f is a Boolean function, then D( f
As a by-product, we improve the polynomial relation between D( f ) and
Nisan and Szegedy [1994, Theorem 3.9] proved
Using our result D( f Nisan and Szegedy's bs( f
and Szegedy 1994, Lemma 3.8], we obtain
COROLLARY 5.6.
6. Some Particular Functions
In this section, we consider the precise complexity of various specific functions.
First, we consider the OR-function, which is related to search. By Grover's
well-known search algorithm [Grover 1996; Boyer et al. 1998], if at least one x i
equals 1, we can find an index i such that x high probability of success
in O( # N ) queries. This implies that we can also compute the OR-function with
high success probability in O( # N generate an index i ,
and return x i . Since bs(OR N Theorem 4.13 gives us a lower bound of # N/4
on computing OR N with bounded error probability (this #(
first
shown in Bennett et al. [1997] and is given in a tighter form in Boyer et al. [1998]
and Zalka [1999], but the way we obtained it here is rather different from those
proofs). Thus classically we require #(N ) queries.
Now suppose we want to get rid of the probability of error: can we compute OR N
exactly or with zero-error using O( # N ) queries? If not, can quantum computation
give us at least some advantage over the classical deterministic case? Both questions
have a negative answer:
PROPOSITION 6.1. Q 0 (OR N
PROOF. Consider a zero-error network for OR N that uses
queries. By Lemma 4.1, there are complex-valued polynomials p k of degree at
most T , such that the final state of the network on black-box X is
Let B be the set of all basis states having 10 as rightmost bits (i.e., where the output is
the answer 0). Then, for every k # B, wemust have
otherwise, the probability of getting the incorrect answer 0 on |# X
# would be
Quantum Lower Bounds by Polynomials 793
nonzero. On the other hand, there must be at least one
since the probability of getting the correct answer 0 on |# 0
# must be nonzero.
Let p(X ) be the real part of 1 - p k # (X )/p k ( # 0). This polynomial p has degree
at most T and represents OR N . But then p must have degree deg(OR N
so T # N .
COROLLARY 6.2. A quantum network for exact or zero-error search requires
queries.
In contrast, under the promise that the number of solutions is either 0 or t , for
some fixed known t , exact search can be done in O( # N/t) queries [Brassard et al.
2000]. A partial block sensitivity argument (see the comment following Theorem
shows that this is optimal up to a multiplicative constant.
Like the OR-function, PARITY has deg(PARITY N so by Theorem 4.3
exact computation requires at least #N/2# queries. This is also sufficient. It is
well known that the XOR of 2 variables can be computed using only one query
[Cleve et al. 1998]. Assuming N even, we can group the variables of X as N/2
pairs: compute the XOR of all pairs using
N/2 queries. The parity of X is the parity of these N/2 XOR values, which can
be computed without any further queries. If we allow bounded-error, then #N/2#
queries of course still suffice. It follows from Theorem 4.8 that this cannot be
improved, because
LEMMA 6.3 [MINSKY AND PAPERT 1968].
PROOF. Let f be PARITY on N variables. Let p be a polynomial of degree
f ) that approximates f . Since p approximates f , its symmetrization p sym
also approximates f . By Lemma 3.2, there is a polynomial q, of degree at most
inputs. Thus, we must have | f (X
(assuming N
even).
We see that the polynomial q(x) - 1/2 must have at least N zeroes, hence q has
degree at least N and
PROPOSITION 6.4. If f is PARITY on {0, 1} N , then Q
#N/2#. 6
Note that this result also implies that Theorems 4.3 and 4.8 are tight. For classical
algorithms, N queries are necessary in the exact, zero-error, and bounded-error
settings. Note that while computing PARITY on a quantum network is much harder
than OR in the bounded-error setting (#N/2# versus # N )), in the exact setting
PARITY is actually easier (#N/2# versus N ).
6 This has also been proved independently by Farhi et al. [1998], using a different technique. As noted
independently by Terhal [1997] and Farhi et al. [1998], this result immediately implies results by
Ozhigov [1998] to the effect that no quantum computer can significantly speed up the computation of
all functions (this follows because no quantum computer can significantly speed up the computation
of PARITY).
794 R. BEALS ET AL.
The upper bound on PARITY uses the fact that the XOR connective can be
computed with only one query. Using polynomial arguments, it turns out that XOR
and its negation are the only examples among all 16 connectives on 2 variables
where quantum gives an advantage over classical computation.
Since OR N can be reduced to MAJORITY on 2N -1 variables (if we set the first
variables to 1, then the MAJORITY of all variables equals the OR of the last
N variables) and OR requires N queries to be computed exactly or with zero-error,
it follows that MAJ N takes at least (N queries. Hayes et al. [1998] found
an exact quantum algorithm that uses at most N
is the number of 1s in the binary representation of N ; this can save up to log N
queries. This also follows from classical results [Saks and Werman 1991; Alonso
et al. 1993] that show that an item with the majority value canbe identified classically
deterministically with N -w(N ) comparisons between bits (a comparison between
two input bits is the parity of the two bits, which can be computed with 1 quantum
query). For the zero-error case, the same (N + 1)/2 lower bound applies; Hayes
et al. [1998] give a zero-error quantum algorithm that works in roughly 2
queries.
For the bounded-error case, we can apply Theorem 4.10: #(MAJ N so we need
queries. The best upper bound we have here is N/2
which follows from [van Dam 1998].
The #(N ) lower bound for MAJORITY also implies a lower bound for the
number of comparisons required to sort N totally ordered elements. It is well known
that N log N +#(N ) comparisons between elements are necessary and sufficient
for sorting on a classical computer. Note that if we can sort then we can compute
MAJORITY: if we sort the N -bit black-box, then the bit at the (N/2)th position
gives the MAJORITY-value (a comparison between 2 black-box bits can easily be
simulated by a few queries). Hence, our #(N )-bound for MAJORITY implies:
COROLLARY 6.5. Sorting N elements on a quantum computer takes at least
An #(N ) lower bound for sorting was also derived independently in Farhi et al.
[1999a], via a different application of our polynomial-based method. The bound
has recently been improved to the optimal #(N log N ) [H-yer et al. 2001].

ACKNOWLEDGMENTS

We thank Lance Fortnow for stimulating discussions on
many of the topics treated here; Alain Tapp for sending us a preliminary version
of Brassard et al. [1998] and subsequent discussions about quantum counting;
Andris Ambainis for sending us his proof that most functions cannot be computed
with bounded-error using significantly fewer than N queries; NoamNisan for
sending us his and Roman Smolensky's proof that D( f
Melkebeek, Tom Hayes, and Sandy Kutin for their algorithms for MAJORITY;
Hayes and Kutin for the reference to Gathen and Roche [1997]; and two anonymous
referees for some comments that improved the presentation of the paper.



--R

Determining the majority.
A note on quantum black-box complexity of almost all Boolean functions


Strengths and weaknesses of quantum computing.
Tight bounds on quantum searching.
Fortschritte der Physik

Quantum algorithm for the collision problem.

Quantum algorithms for element distinctness.
To appear.
The query complexity of order-finding
London A454

Schwankung von Polynomen zwischen Gitterpunkten.
A limit on the speed of quantum computation in determining parity.
How many functions can be distinguished with k quantum queries?
An oracle builder's toolkit.
Complexity limitations on quantum computation.

A fast quantum mechanical algorithm for database search.



Conjugated operators in quantum algorithms.
Quantum bounds for ordered searching and sorting.
Quantum measurements and the Abelian stabilizer problem.
Quantum searching
In MFCS'98 Workshop on Randomized Algorithms
The hidden subgroup problem and eigenvalue estimation on a quantum computer.
CREW PRAMs and decision trees.
On the degree of Boolean functions as real polynomials.
Quantum computer can not speed up iterated applications of a black box.
A comparison of uniform approximations on an interval and a finite subset thereof.
Probabilistic Boolean decision trees and the complexity of evaluating game trees.
On computing majority by comparisons.
On the Monte Carlo decision tree complexity of read-once formulae


On the power of quantum computation.
Characterization of non-deterministic quantum query and quantum communication complexity

--TR
Perceptrons: expanded edition
CREW PRAMs and decision trees
On the degree of polynomials that approximate symmetric Boolean functions (preliminary version)
Determining the majority
On the degree of Boolean functions as real polynomials
A fast quantum mechanical algorithm for database search
Quantum cryptanalysis of hash and claw-free functions
On the Power of Quantum Computation
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Strengths and Weaknesses of Quantum Computing
A framework for fast quantum mechanical algorithms
Quantum vs. classical communication and computation
The quantum query complexity of approximating the median and related statistics
A note on quantum black-box complexity of almost all Boolean functions
Complexity limitations on Quantum computation
Quantum lower bounds by quantum arguments
Complexity measures and decision tree complexity
The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer
Quantum Computer Can Not Speed Up Iterated Applications of a Black Box
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
Quantum Counting
Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract)
Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity
The Query Complexity of Order-Finding
Quantum Lower Bounds by Polynomials
Quantum Oracle Interrogation
Bounds for Small-Error and Zero-Error Quantum Algorithms
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems
An Exact Quantum Polynomial-Time Algorithm for Simon''s Problem
Quantum Algorithms for Element Distinctness
Quantum versus Classical Learnability
On the Quantum Complexity of Majority

--CTR
Yves F. Verhoeven, Enhanced algorithms for local search, Information Processing Letters, v.97 n.5, p.171-176, March 2006
Pascal Koiran , Vincent Nesme , Natacha Portier, The quantum query complexity of the abelian hidden subgroup problem, Theoretical Computer Science, v.380 n.1-2, p.115-126, June, 2007
Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Journal of Computer and System Sciences, v.69 n.3, p.395-420, November 2004
Harry Buhrman , Robert palek, Quantum verification of matrix products, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.880-889, January 22-26, 2006, Miami, Florida
Yaoyun Shi, Quantum and classical tradeoffs, Theoretical Computer Science, v.344 n.2-3, p.335-345, 17 November 2005
Peter Hoyer , Troy Lee , Robert Spalek, Negative weights make adversaries stronger, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Franois Le Gall, Exponential separation of quantum and classical online space complexity, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Scott Aaronson, Lower bounds for local search by quantum arguments, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.465-474, June 13-16, 2004, Chicago, IL, USA
Miklos Santha , Mario Szegedy, Quantum and classical query complexities of local search are polynomially related, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Igor E. Shparlinski, Bounds on the Fourier coefficients of the weighted sum function, Information Processing Letters, v.103 n.3, p.83-87, July, 2007
Holger Spakowski , Rahul Tripathi, LWPP and WPP are not uniformly gap-definable, Journal of Computer and System Sciences, v.72 n.4, p.660-689, June 2006
Andris Ambainis , Robert palek , Ronald de Wolf, A new quantum lower bound method,: with applications to direct product theorems and time-space tradeoffs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Andris Ambainis, Polynomial degree vs. quantum query complexity, Journal of Computer and System Sciences, v.72 n.2, p.220-238, March 2006
Shengyu Zhang, New upper and lower bounds for randomized and quantum local search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Frdric Magniez , Miklos Santha , Mario Szegedy, Quantum algorithms for the triangle problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
A. Ambainis, Quantum search algorithms, ACM SIGACT News, v.35 n.2, June 2004
Shengyu Zhang, On the power of Ambainis lower bounds, Theoretical Computer Science, v.339 n.2, p.241-256, 12 June 2005
Scott Aaronson, Guest Column: NP-complete problems and physical reality, ACM SIGACT News, v.36 n.1, March 2005
query complexity;quantum computing;lower bounds;black-box model;polynomial method