Authors Robert {\v S}palek, Mario Szegedy,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18
http://theoryofcomputing.org
All Quantum Adversary Methods are
Equivalent
Robert Špalek Mario Szegedy
Received: August 4, 2005; published: January 31, 2006.
Abstract: The quantum adversary method is one of the most versatile lower-bound meth-
ods for quantum algorithms. We show that all known variants of this method are equivalent:
spectral adversary (Barnum, Saks, and Szegedy, 2003), weighted adversary (Ambainis,
2003), strong weighted adversary (Zhang, 2005), and the Kolmogorov complexity adver-
sary (Laplante and Magniez, 2004). We also present a few new equivalent formulations of
the method. This shows that there is essentially one quantum adversary method. From our
approach, all known limitations of these versions of the quantum adversary method easily
follow.
ACM Classification: F.1.2, F.1.3
AMS Classification: 81P68, 68Q17
Key words and phrases: Quantum computing, query complexity, adversary lower bounds
1 Introduction
1.1 Lower-bound methods for quantum query complexity
In the query complexity model, the input is accessed using oracle queries and the query complexity of
the algorithm is the number of calls to the oracle. The query complexity model is helpful in obtaining
time complexity lower bounds, and often this is the only way to obtain time bounds in the random access
model.
The first lower-bound method on quantum computation was the hybrid method of Bennett, Bernstein,
√
Brassard, and Vazirani [9] to show an Ω( n) lower bound on the quantum database search. Their proof
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2006 Robert Špalek and Mario Szegedy DOI: 10.4086/toc.2006.v002a001
ROBERT Š PALEK , M ARIO S ZEGEDY
is based on the following simple observation: If the value of function f differs on two inputs x, y, then
the output quantum states of any bounded-error algorithm for f on x and y must be almost orthogonal.
On the other hand, the inner product is 1 at the beginning, because the computation starts in a fixed
state. By upper-bounding the change of the inner product after one query, we lower bound the number
of queries that need to be made.
The second lower-bound method is the polynomial method of Beals, Buhrman, Cleve, Mosca, and
de Wolf [8]. It is based on the observation that the measurement probabilities can be described by low-
degree polynomials in the input bits. If t queries have been made, then the degree is at most 2t. Since the
measurement probabilities are always inside [0, 1], one can apply degree lower bounds for polynomials
to obtain good lower bounds for quantum query complexity.
The third lower-bound method is the quantum adversary method of Ambainis [2]. It extends the
hybrid method. Instead of examining a fixed input pair, Ambainis takes an average over many pairs of
inputs. In this paper, we study different variants of the quantum adversary method.
The fourth lower-bound method is the semidefinite programming method of Barnum, Saks, and
Szegedy [7]. It exactly characterizes quantum query complexity by a semidefinite program. The dual of
this program gives a lower bound that encompasses the quantum adversary bound.
1.2 The variants of the quantum adversary method
The original version of the quantum adversary method, let us call it unweighted, was invented by Am-
√
bainis [2]. It was successfully used to obtain the following tight lower bounds: Ω( n) for Grover
√ √
search [12], Ω( n) for two-level And-Or trees (see [13] for a matching upper bound), and Ω( n) for
inverting a permutation. The method starts with choosing a set of pairs of inputs on which f takes dif-
ferent values. Then the lower bound is determined by some combinatorial properties of the graph of all
pairs chosen.
Some functions, such as sorting or ordered search, could not be satisfactorily lower-bounded by the
unweighted adversary method. Høyer, Neerbek, and Shi used a novel argument [14] to obtain tight
bounds for these problems. They weighted the input pairs and obtained the lower bound by evaluating
the spectral norm of the Hilbert matrix. Barnum, Saks, and Szegedy proposed a general method [7]
that gives necessary and sufficient conditions for the existence of a quantum query algorithm. They also
described a special case, the so-called spectral method, which gives a lower bound in terms of spectral
norms of an adversary matrix. Ambainis also published a weighted version of his adversary method [3].
He showed that it is stronger than the unweighted method and successfully applied it to get a lower
bound for several iterated functions. This method is slightly harder to apply, because it requires one
to design a so-called weight scheme, which can be seen as a quantum counterpart of the classical hard
distribution on the inputs. Zhang observed that Ambainis had generalized his oldest method [2] in two
independent ways, so he unified them, and published a strong weighted adversary method [27]. Finally,
Laplante and Magniez used Kolmogorov complexity in an unusual way and described a Kolmogorov
complexity method [17].
All adversary lower-bound methods above except the Kolmogorov complexity method were defined
and proved only for Boolean functions, that is for functions with Boolean input bits and a Boolean
output.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 2
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
A few relations between the methods are known. It is a trivial fact that the strong weighted adversary
is at least as good as the weighted adversary. Laplante and Magniez showed [17] that the Kolmogorov
complexity method is at least as strong as all the following methods: the Ambainis unweighted and
weighted method, the strong weighted method, and the spectral method. The method of Høyer et al. [14]
is a special case of the weighted adversary method. It seemed that there were several incompatible
variants of the quantum adversary method of different strength.
In addition it was known that there were some limitations for lower bounds obtained by the adversary
method. √Let f√be Boolean. Szegedy observed [26] that the weighted adversary method is limited
by min( C0 n, C1 n), where C0 is the zero-certificate complexity of f and C1 is the one-certificate
complexity of f . Laplante and Magniez proved the same limitation for the Kolmogorov complexity
method
√ [17], which implies that all other methods are also bounded. Finally, this bound was improved
to C0C1 for total f by Zhang [27] and independently by us.
1.3 Our results
In this paper, we clean up the forest of adversary methods. First, we extend all adversary lower bound
methods to general non-Boolean functions. Second, we show that there is essentially only one quantum
adversary method and that all the former methods [7, 3, 27, 17] are just different formulations of the
same method. Since one method can be defined in several seemingly unrelated ways and yet one always
obtains the same bound, it implies that the quantum adversary method is a very robust concept.
Third, we present a new simple proof of the limitation of the quantum adversary method. If we
order the letters in the output alphabet√by their certificate complexities
√ such that C0 ≥ C1 ≥ . . . , then all
adversary lower bounds are at most 2 C1 n for partial f and C0C1 for total f .
1.4 Separation between the polynomial and adversary method
The polynomial method and the adversary method are generally incomparable. There are examples
when the polynomial method gives better bounds and vice versa.
The polynomial method has been successfully applied to obtain tight lower bounds for the following
problems: Ω n1/3 for the collision problem and Ω n2/3 for the element distinctness problem [1]
(see [4] for a matching upper bound). The quantum adversary method is incapable of proving such
lower bounds due to the small certificate complexity of the function. Furthermore, the polynomial
method often gives tight lower bounds for the exact and zero-error quantum complexity, such as n for
the Or function [8]. The adversary method completely fails in this setting and the only lower bound it
can offer is the bounded-error lower bound.
On the other hand, Ambainis exhibited some iterated functions [3] for which the adversary method
gives better lower bounds than the polynomial method. The largest established gap between the two
methods is n1.321 . Furthermore, it is unknown how to apply the polynomial method to obtain several
lower bounds that are very simple to prove by the adversary method. A famous example is the two-
√
level And-Or tree. The adversary method givesa tight lower bound Ω( n) [2], whereas the best bound
obtained by the polynomial method is Ω n1/3 and it follows [5] from the element distinctness lower
bound [1].
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 3
ROBERT Š PALEK , M ARIO S ZEGEDY
There are functions for which none of the methods is known to give a tight bound. A long-standing
open problem is the binary And-Or tree. The best known quantum algorithm is just an implementation
of the classical zero-error algorithm by Snir [25] running in expected time O n0.753 , which is optimal
for both zero-error [23] and bounded-error [24] algorithms. The adversary lower bounds are limited by
√ √
C0C1 = n. In a recent development, Laplante, Lee, and Szegedy showed [16] that this limitation
√
n holds for every read-once {∧, ∨} formula. The best known lower bound obtained by the polynomial
√
method is also Ω( n) and it follows from embedding the parity function. It could be that the polynomial
method can prove a stronger lower bound. Two other examples are triangle finding and verification of
1.3
matrix products. For triangle finding, the best upper bound is O n [20] and the best lower bound is
Ω(n). For verification of matrix products, the best upper bound is O n5/3 [10] and the best lower bound
is Ω n3/2 . Again, the adversary method cannot give better bounds, but the polynomial method might.
The semidefinite programming method [7] gives an exact characterization of quantum query com-
plexity. However, it is too general to be applied directly. It is an interesting open problem to find a lower
bound that cannot be proved by the adversary or polynomial method.
2 Preliminaries
2.1 Quantum query algorithms
We assume familiarity with quantum computing [22] and sketch the model of quantum query complex-
ity, referring to [11] for more details, also on the relation between query complexity and certificate
complexity. Suppose we want to compute some function f : S → H, where S ⊆ GN and G, H are some
finite alphabets. For input x ∈ S, a query gives us access to the input variables. It corresponds to the
unitary transformation, which depends on input x in the following way:
Ox : |i, b, zi 7→ |i, (b + xi ) mod |G|, zi .
Here i ∈ [N] = {1, . . . , N} and b ∈ G; the z-part corresponds to the workspace, which is not affected by
the query. We assume the input can be accessed only via such queries. A T -query quantum algorithm
has the form A = UT OxUT −1 · · · OxU1 OxU0 , where the Uk are fixed unitary transformations, independent
of x. This A depends on x via the T applications of Ox . The algorithm starts in initial S-qubit state
|0i. The output of A is obtained by observing the first few qubits of the final superposition A|0i, and its
success probability on input x is the probability of outputting f (x).
2.2 Kolmogorov complexity
An excellent book about Kolmogorov complexity is the book [18] by Li and Vitányi. Deep knowledge of
Kolmogorov complexity is not necessary to understand this paper. Some results on the relation between
various classical forms of the quantum adversary method and the Kolmogorov complexity method are
taken from Laplante and Magniez [17], and the others just use basic techniques.
A set is called prefix-free if none of its members is a prefix of another member. Fix a universal
Turing machine M and a prefix-free set S. The prefix-free Kolmogorov complexity of x given y, denoted
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 4
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
by K(x|y), is the length of the shortest program from S that prints x if it gets y on the input. Formally,
K(x|y) = min{|P| : P ∈ S, M(P, y) = x} .
2.3 Semidefinite programming
In this paper, we use the duality theory of semidefinite programming [19]. There are various forms of
the duality principle in the literature. We use a semidefinite extension of Farkas’s lemma [19, Theorem
3.4].
2.4 Notation
Let [n] = {1, 2, . . . , n}. Let Σ∗ denote the set of all finite strings over alphabet Σ. All logarithms are
binary. Let I denote the identity matrix. Let AT denote the transpose of A. Let diag (A) denote the
column vector containing the main diagonal of A. Let tr (A) be the trace of A and let A · B be the scalar
product of A and B, formally A · B = ∑x,y A[x, y]B[x, y]. For a column vector x, let |x| denote the `2 -norm
√
of x, formally |x| = xT x. Let λ (A) denote the spectral norm of A, formally λ (A) = maxx:|x|6=0 |Ax|/|x|.
Let AB denote the usual matrix product and let A ◦ B denote the Hadamard (point-wise) product [21].
Formally, (AB)[x, y] = ∑i A[x, i]B[i, y] and (A ◦ B)[x, y] = A[x, y]B[x, y]. Let A ≥ B denote the point-wise
comparison and let C D denote that C − D is positive semidefinite. Formally, ∀x, y : A[x, y] ≥ B[x, y]
and ∀v : vT (C − D)v ≥ 0. Let rx (M) denote the `2 -norm of the x-th row of M and let cy (M) denote the
`2 -norm of the y-th column of M. Formally,
rx (M) = ∑ M[x, y]2 cy (M) = ∑ M[x, y]2 .
r r
and
y x
Let r(M) = maxx rx (M) and c(M) = maxy cy (M).
Let S ⊆ Gn be a set of inputs. We say that a function f : S → H is total if S = Gn . A general function
is called partial. Let f be a partial function. A certificate for an input x ∈ S is a subset I ⊆ [n] such that
fixing the input variables i ∈ I to xi determines the function value. Formally,
∀y ∈ S : y|I = x|I ⇒ f (y) = f (x) ,
where x|I denotes the substring of x indexed by I. A certificate I for x is called minimal if |I| ≤ |J| for
every certificate J for x. Let Cf (x) denote the lexicographically smallest minimal certificate for x. For
an h ∈ H, let Ch ( f ) = maxx: f (x)=h |Cf (x)| be the h-certificate complexity of f .
3 Main result
In this section, we present several equivalent quantum adversary methods and a new simple proof of
the limitations of these methods. We can categorize these methods into two groups. Some of them
solve conditions on the primal of the quantum system [7]: these are the spectral, weighted, strong
weighted, and generalized spectral adversary; and some of them solve conditions on the dual: these are
the Kolmogorov complexity bound, minimax, and the semidefinite version of minimax. Primal methods
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 5
ROBERT Š PALEK , M ARIO S ZEGEDY
are mostly used to give lower bounds on the query complexity, while we can use the duals to give
limitations of the method.
The primal methods, that is the spectral, weighted, and strong weighted adversary, have been stated
only for Boolean functions. The generalization to the more general non-Boolean case is straightforward
and hence we state them here in the generalized form.
Theorem 3.1. Let S ⊆ Gn and let f : S → H be a partial function. Let Qε ( f ) denote the ε-error quantum
query complexity of f . Then
Qε ( f )
√ ≥ SA( f ) = WA( f ) = SWA( f ) = MM( f ) = SMM( f ) = GSA( f ) = Θ(KA( f )) ,
1−2 ε(1−ε)
where SA, WA, SWA, MM, SMM, GSA, and KA are lower bounds given by the following methods.
• Spectral adversary [7]. Let Di , F be |S| × |S| zero-one valued matrices that satisfy Di [x, y] = 1 iff
xi 6= yi for i ∈ [n], and F[x, y] = 1 iff f (x) 6= f (y). Let Γ denote an |S| × |S| non-negative symmetric
matrix such that Γ ◦ F = Γ. Then
λ (Γ)
SA( f ) = max . (3.1)
Γ maxi λ (Γ ◦ Di )
• Weighted adversary [3].1 Let w, w0 denote a weight scheme as follows:
– Every pair (x, y) ∈ S2 is assigned a non-negative weight w(x, y) = w(y, x) that satisfies
w(x, y) = 0 whenever f (x) = f (y).
– Every triple (x, y, i) ∈ S2 × [n] is assigned a non-negative weight w0 (x, y, i) that satisfies
w0 (x, y, i) = 0 whenever xi = yi or f (x) = f (y), and w0 (x, y, i)w0 (y, x, i) ≥ w2 (x, y) for all
x, y, i such that xi 6= yi and f (x) 6= f (y).
For all x, i, let wt(x) = ∑y w(x, y) and v(x, i) = ∑y w0 (x, y, i). Then
s
wt(x)wt(y)
WA( f ) = max0 min . (3.2)
w,w x,y, i, j
f (x)6= f (y)
v(x, i)v(y, j)
v(x,i)v(y, j)>0
• Strong weighted adversary [27]. Let w, w0 denote a weight scheme as above. Then
s
wt(x)wt(y)
SWA( f ) = max0 min . (3.3)
w,w x,y,i
w(x,y)>0
v(x, i)v(y, i)
xi 6=yi
1 We use a different formulation [17] than in the original Ambainis papers [2, 3]. In particular, we omit the relation R ⊆ A×B
on which the weights are required to be nonzero, and instead allow zero weights. It is simple to prove that both formulations
are equivalent.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 6
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
• Kolmogorov complexity [17].2 Let σ ∈ {0, 1}∗ denote a finite string. Then
1
KA( f ) = min max √ . (3.4)
f (x)6= f (y) ∑i:xi 6=yi
x,y −K(i|x,σ )−K(i|y,σ )
σ 2
• Minimax over probability distributions [17]. Let p : S × [n] → R denote a set of probability
distributions, that is px (i) ≥ 0 and ∑i px (i) = 1 for every x. Then
1
MM( f ) = min max (3.5)
f (x)6= f (y) ∑i:xi 6=yi
x,y
p
p px (i) py (i)
∑ px (i) py (i) .
q
= 1 max min x,y
(3.6)
p
f (x)6= f (y) i:xi 6=yi
• Semidefinite version of minimax. Let Di , F be matrices as above. Then SMM( f ) = 1/µmax ,
where µmax is the maximal solution of the following semidefinite program:
maximize µ
subject to ∀i : Ri 0
(3.7)
∑i Ri ◦ I = I
∑i Ri ◦ Di ≥ µF .
• Generalized spectral adversary. Let Di , F be matrices as above. Then GSA( f ) = 1/µmin , where
µmin is the minimal solution of the following semidefinite program:
minimize µ = tr ∆
subject to ∆ is diagonal
Z ≥0 (3.8)
Z ·F = 1
∀i : ∆ − Z ◦ Di 0 .
Before we prove the main theorem in the next sections, let us draw some consequences. We show
that there are limits that none of these quantum adversary methods can go beyond.
Theorem 3.2. Let S ⊆ Gn and let f : S → H be a partial function. Let the output alphabet be H =
{0, 1, . . . , |H| − 1} and order the letters h ∈ H by their h-certificate complexities
p such that C0 ≥ C1 ≥
· · · ≥ C|H|−1 . Then the max-min bound (3.6) is upper-bounded by MM( f ) ≤ 2 C1 ( f ) · n. If f is total,
p
that is if S = Gn , then MM( f ) ≤ C0 ( f ) ·C1 ( f ).
2 We use a different formulation than Laplante and Magniez [17]. They minimize over all algorithms A computing f and
substitute σ = source code of A, whereas we minimize over all finite strings σ . Our way is equivalent. One can easily argue
that any finite string σ can be “embedded” into any algorithm B: Let C be the source code of B with appended comment σ that
is never executed. Now, the programs B and C are equivalent, and K(x|σ ) ≤ K(x|C) + O(1) for every x.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 7
ROBERT Š PALEK , M ARIO S ZEGEDY
Proof. The following simple argument is due to Ronald de Wolf. We exhibit two sets of probability
distributions p such that
1 1
∑ px (i) py (i) ≥ 2√C1 n , resp. √C0C1 .
q
m(p) = min x,y
f (x)6= f (y) i:xi 6=yi
The max-min bound (3.6) is MM( f ) = 1/ max p m(p) and the statement follows.
Let f be partial. For every x ∈ S, distribute one half of the probability uniformly over any minimal
certificate Cf (x), and one half of the probability uniformly over all input variables. Formally,
1 1 1
px (i) = + iff i ∈ Cf (x) , and px (i) = for i 6∈ Cf (x) .
2n 2|Cf (x)| 2n
Take any x, y such that f (x) 6= f (y). Assume that Cx ≤ Cy , and take the f (x)-certificate I = Cf (x). Since
y|I 6= x|I , there is a j ∈ I such that x j 6= y j . Now we lower-bound the sum of (3.6).
s
1 1 1 1
∑ px (i) py (i) ≥ px ( j) py ( j) ≥ |2Cf (x)| · 2n ≥ 2pC f (x) n ≥ 2√C1 n .
q q
i:xi 6=yi
√
Since this inequality holds for any x, √y such that f (x) 6= f (y), also m(p) ≥ 1/2 C1 n. Take the
reciprocal and conclude that MM( f ) ≤ 2 C1 n. √
For Boolean output alphabet H = {0, 1}, we can prove a slightly stronger bound MM( f ) ≤ C1 n
as follows. Define p as a uniform distribution over some minimal certificate for all one-inputs, and a
uniform distribution over all input bits for all zero-inputs. The same computation as above gives the
bound.
If f is total, then we can do even better. For every x ∈ Gn , distribute the probability uniformly
over any minimal certificate Cf (x). Formally, px (i) = 1/|Cf (x)| iff i ∈ Cf (x), and px (i) = 0 otherwise.
Take any x, y such that f (x) 6= f (y), and let I = Cf (x) ∩ Cf (y). There must exist a j ∈ I such that
x j 6= y j , otherwise we could find an input z that is consistent with both certificates. (That would be a
contradiction, because f is total and hence f (z) has to be defined pand be equal to both f (x) and f (y).)
After we have found a j, we lower-bound the sum of (3.6) by 1/ C f (x)C f (y) in the same way as above.
p √
Since C f (x)C f (y) ≤ C0C1 , the bound follows.
Some parts of the following statement have been observed for individual methods by Szegedy [26],
Laplante and Magniez [17], and Zhang [27]. This corollary rules out all adversary attempts to prove
good lower bounds for problems with small certificate complexity, such as element distinctness [1],
binary And-Or trees [6, 13], triangle finding [20], or verification of matrix products [10].
p p
p adversary lower bounds are at most min( C0 ( f )n, C1 ( f )n) for partial
Corollary 3.3. All quantum
Boolean functions and C0 ( f )C1 ( f ) for total Boolean functions.
4 Equivalence of spectral and strong weighted adversary
In this section, we give a linear-algebraic proof that the spectral bound [7] and the strong weighted
bound [27] are equal. The proof has three steps. First, we show that the weighted bound [3] is at least as
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 8
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
good as the spectral bound. Second, using a small combinatorial lemma, we show that the spectral bound
is at least as good as the strong weighted bound. The strong weighted bound is always at least as good
as the weighted bound, because every term in the minimization of (3.3) is included in the minimization
of (3.2): if w(x, y) > 0 and xi 6= yi , then f (x) 6= f (y) and both w0 (x, y, i) > 0 and w0 (y, x, i) > 0. The
generalization of the weighted adversary method thus does not make the bound stronger, however its
formulation is easier to use.
4.1 Reducing spectral adversary to weighted adversary
First, let us state two useful statements upper-bounding the spectral norm of a Hadamard product of two
non-negative matrices. The first one is due to Mathias [21]. The second one is our generalization and its
proof is postponed to Appendix A.
Lemma 4.1. [21] Let S be a non-negative symmetric matrix and let M and N be non-negative matrices
such that S ≤ M ◦ N. Then
λ (S) ≤ r(M)c(N) = max rx (M)cy (N) . (4.1)
x,y
Moreover,
p such that S = M ◦ M T and r(M) = c(M T ) =
for every symmetric S ≥ 0 there exists an M ≥ 0p
λ (S). This optimal matrix can be written as M[x, y] = S[x, y] · d[y]/d[x], where d is the principal
eigenvector of S.
Lemma 4.2. Let S be a non-negative symmetric matrix and let M and N be non-negative matrices such
that S ≤ M ◦ N. Then
λ (S) ≤ max
x,y
rx (M)cy (N) . (4.2)
S[x,y]>0
Now we use the first bound to reduce the spectral adversary to the weighted adversary.
Theorem 4.3. SA( f ) ≤ WA( f ).
Proof. Let Γ be a non-negative symmetric matrix with Γ ◦ F = Γ as in equation (3.1) that gives the opti-
mal spectral bound. Assume without loss of generality that λ (Γ) = 1. Let δ be the principal eigenvector
of Γ, that is Γδ = δ . Define the following weight scheme:
w(x, y) = w(y, x) = Γ[x, y] · δ [x]δ [y] .
p Γi = Γ ◦ Di into
Furthermore, for every i, using Lemma 4.1, decompose a Hadamard product of two
non-negative matrices Γi = Mi ◦ Mi such that r(Mi ) = λ (Γi ). Define w as follows:
T 0
w0 (x, y, i) = Mi [x, y]2 δ [x]2 .
Let us verify that w, w0 is a weight scheme. From the definition, w(x, y) = w0 (x, y, i) = 0 if f (x) =
f (y), and also w0 (x, y, i) = 0 if xi = yi . Furthermore, if f (x) 6= f (y) and xi 6= yi , then
w0 (x, y, i)w0 (y, x, i) = (Mi [x, y] δ [x])2 (Mi [y, x] δ [y])2 = (Γi [x, y] δ [x]δ [y])2 = w(x, y)2 .
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 9
ROBERT Š PALEK , M ARIO S ZEGEDY
Finally, let us compute the bound (3.2) given by the weight scheme.
wt(x) = ∑ w(x, y) = δ [x] ∑ Γ[x, y]δ [y] = δ [x] (Γδ )[x] = δ [x]2 ,
y y
v(x, i) ∑y w0 (x, y, i) ∑y Mi [x, y]2 δ [x]2
= = = rx (Mi )2 ≤ r(Mi )2 = λ (Γi ) .
wt(x) wt(x) δ [x]2
The weighted adversary lower bound (3.2) is thus at least
s
wt(x)wt(y) 1 λ (Γ)
WA( f ) ≥ min ≥ min p = = SA( f ) .
x,y, i, j
f (x)6= f (y)
v(x, i)v(y, j) i, j λ (Γi ) · λ (Γ j ) maxi λ (Γi )
v(x,i)v(y, j)>0
Hence the weighted adversary is at least as strong as the spectral adversary (3.1).
4.2 Reducing strong weighted adversary to spectral adversary
Theorem 4.4. SWA( f ) ≤ SA( f ).
Proof. Let w, w0 be a weight scheme as in Equation (3.2) that gives the optimal weighted bound. Define
the following symmetric matrix Γ on S × S:
w(x, y)
Γ[x, y] = p .
wt(x)wt(y)
wt(x). Let W = ∑x wt(x). Then
p
We also define column vector δ on S such that δ [x] =
λ (Γ) ≥ δ T Γδ /|δ |2 = W /W = 1 .
Define the following matrix on the index set S × S:
s
w0 (x, y, i)
Mi [x, y] = .
wt(x)
Every weight scheme satisfies w0 (x, y, i)w0 (y, x, i) ≥ w2 (x, y) for all x, y, i such that xi 6= yi . Hence
p
w0 (x, y, i)w0 (y, x, i) w(x, y) · Di [x, y]
Mi [x, y] · Mi [y, x] = p ≥ p = Γi [x, y] .
wt(x)wt(y) wt(x)wt(y)
This means that Γ ≤ M ◦ M T . By Lemma 4.2 and using cy (M T ) = ry (M),
s s
w0 (x, k, i) w0 (y, `, i) v(x, i)v(y, i)
λ (Γi ) ≤ max
x,y
rx (M)ry (M) = max
x,y ∑ wt(x) ∑ wt(y) = max x,y wt(x)wt(y)
.
Γi [x,y]>0 w(x,y)>0 k ` w(x,y)>0
xi 6=yi xi 6=yi
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 10
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
The spectral adversary lower bound (3.1) is thus at least
s
λ (Γ) wt(x)wt(y)
SA( f ) ≥ ≥ min min = SWA( f ) .
maxi λ (Γi ) i x,y
w(x,y)>0
v(x, i)v(y, i)
xi 6=yi
Hence the spectral adversary is at least as strong as the weighted adversary (3.3).
Remark 4.5. The strength of the obtained reduction depends on which statement is used for upper-
bounding the spectral norm of Γi .
• Lemma 4.2 has just given us SWA( f ) ≤ SA( f ).
• Lemma 4.1 would give a weaker bound WA( f ) ≤ SA( f ).
• Høyer, Neerbek, and Shi used an explicit expression for the norm of the Hilbert matrix to get
a lower bound for ordered search [14]. Their method is thus also a special case of the spectral
method.
• Both versions of the original unweighted adversary method [2] are obtained by using a spec-
tral matrix Γ corresponding to a zero-one valued weight scheme w, the lower bound λ (Γ) ≥
d T Γd/|d|2 , and Lemma 4.1, resp. Lemma 4.2.
5 Equivalence of minimax and generalized spectral adversary
In this section, we prove that the minimax bound is equal to the generalized spectral bound. We first
remove the reciprocal by taking the max-min bound. Second, we write this bound as a semidefinite
program. An application of duality theory of semidefinite programming finishes the proof.
Theorem 5.1. MM( f ) = SMM( f ).
p
Proof. Let p be a set of probability distributions as in Equation (3.6). Define Ri [x, y] = px (i) py (i).
Since px is a probability distribution, we get that ∑i Ri must have all ones on the diagonal. The condition
min x,y ∑i:xi 6=yi Ri [x, y] ≥ µ may be rewritten
f (x)6= f (y)
∀x, y : f (x) 6= f (y) =⇒ ∑ Ri [x, y] ≥ µ ,
i:xi 6=yi
which is to say ∑i Ri ◦ Di ≥ µF. Each matrix Ri should
p be an outer product of a non-negative vector
T
with itself: Ri = ri ri for a column vector ri [x] = px (i). We have, however, replaced that condition
by Ri 0 to get semidefinite program (3.7). Since ri riT 0, the program (3.7) is a relaxation of the
condition of (3.6) and SMM( f ) ≤ MM( f ).
Let us show that every solution Ri of the semidefinite program can be changed to an at least as
0 T
q rank-1 solution Ri . Take a Cholesky decomposition Ri = Xi Xi . Define a column-vector qi [x] =
good
∑ j Xi [x, j]2 and a rank-1 matrix R0i = qi qTi . It is not hard to show that all R0i satisfy the same constraints
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 11
ROBERT Š PALEK , M ARIO S ZEGEDY
as Ri . First, R0i is positive semidefinite. Second, R0i [x, x] = ∑ j Xi [x, j]2 = Ri [x, x], hence ∑i R0i ◦I = I. Third,
by a Cauchy-Schwarz inequality,
Ri [x, y] = ∑ Xi [x, j]Xi [y, j] ≤ ∑ Xi [x, k]2 ∑ Xi [y, `]2 = qi [x]qi [y] = R0i [x, y] ,
r r
j k `
hence ∑i R0i ◦ Di ≥ ∑i Ri ◦ Di ≥ µF. We conclude that MM( f ) ≤ SMM( f ).
The equivalence of the semidefinite version of minimax and the generalized spectral adversary is
proved using the duality theory of semidefinite programming. We use a semidefinite version of Farkas’s
lemma [19, Theorem 3.4].
Theorem 5.2. SMM( f ) = GSA( f ).
Proof. Let us compute the dual of a semidefinite program without converting it to/from the standard
form, but using Lagrange multipliers. Take the objective function µ of the semidefinite version of
minimax (3.7) and add negative penalty terms for violating the constraints.
µ + ∑ Yi · Ri + D · ∑ Ri ◦ I − I + Z · ∑ Ri ◦ Di − µF =
i i i
for Yi 0, unconstrained D, and Z ≥ 0
= ∑ Ri · Yi + D ◦ I + Z ◦ Di + µ 1 − Z · F − D · I .
i
Its dual system is formed by the constraints on Yi , D, and Z plus the requirements that both expression in
the parentheses are zero. The duality principle [19, Theorem 3.4] says that any primal solution is smaller
than or equal to any dual solution. Moreover, if any of the two systems has a strictly feasible solution,
then the maximal primal solution equals to the minimal dual solution.
Since Yi 0 only appears once, we get rid of it by requiring that D ◦ I + Z ◦ Di 0. We substitute
∆ = −D ◦ I and obtain ∆ − Z ◦ Di 0. The objective function is −D · I = tr ∆. We have obtained the
generalized spectral adversary (3.8). Let us prove its strong feasibility. Assume that the function f is not
constant, hence F 6= 0. Take Z a uniform probability distribution over nonzero entries of F and a large
enough constant ∆. This is a strictly feasible solution. We conclude that µmax = µmin .
6 Equivalence of generalized spectral and spectral adversary
In this section, we prove that the generalized spectral adversary bound is equal to the spectral adversary
bound. The main difference between them is that the generalized method uses an arbitrary positive
diagonal matrix ∆ as a new variable instead of the identity matrix I.
Theorem 6.1. GSA( f ) = SA( f ).
Proof. Let Z, ∆ be a solution of (3.8). First, let us prove that ∆ 0. Since both Z ≥ 0 and Di ≥ 0, it
holds that diag (−Z ◦ Di ) ≤ 0. We know that ∆ − Z ◦ Di 0, hence diag (∆ − Z ◦ Di ) ≥ 0, and diag (∆) ≥ 0
follows. Moreover, diag (∆) > 0 unless Z contains an empty row, in which case we delete it (together
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 12
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
with the corresponding column) and continue. Second, since positive semidefinite real matrices are
symmetric, ∆ − Z ◦ Di 0 implies that Z ◦ Di is symmetric (for every i). For every x 6= y there is a bit i
such that xi 6= yi , hence Z must be also symmetric.
Take a column vector a = diag (∆−1/2 ) and a rank-1 matrix A = aaT 0. It is simple to prove that
A ◦ X 0 for every matrix X 0. Since ∆ − Z ◦ Di 0, also A ◦ (∆ − Z ◦ Di ) = I − Z ◦ Di ◦ A 0 and
hence λ (Z ◦ Di ◦ A) ≤ 1. Now, define the spectral adversary matrix Γ = Z ◦ F ◦ A. Since 0 ≤ Z ◦ F ≤ Z,
it follows that
λ (Γ ◦ Di ) = λ (Z ◦ F ◦ A ◦ Di ) ≤ λ (Z ◦ Di ◦ A) ≤ 1 .
√
It remains to show that λ (Γ) ≥ 1/ tr ∆. Let b = diag ( ∆) and B = bbT . Then
1 = Z · F = Γ · B = bT Γb ≤ λ (Γ) · |b|2 = λ (Γ) · tr ∆ .
It is obvious that Γ is symmetric, Γ ≥ 0, and Γ ◦ F = Γ. The bound (3.1) given by Γ is bigger than or
equal to 1/ tr ∆, hence SA( f ) ≥ GSA( f ).
For the other direction, let Γ be a non-negative symmetric matrix satisfying Γ ◦ F = Γ. Let δ be
its principal eigenvector with |δ | = 1. Assume without loss of generality that λ (Γ) = 1 and let µ =
maxi λ (Γi ). Take A = δ δ T , Z = Γ ◦ A, and ∆ = µI ◦ A. Then Z · F = Γ · A = δ T Γδ = 1 and tr ∆ = µ.
For every i, λ (Γi ) ≤ µ, hence µI − Γ ◦ Di 0. It follows that 0 A ◦ (µI − Γ ◦ Di ) = ∆ − Z ◦ Di . The
semidefinite program (3.8) is satisfied and hence its optimum is µmin ≤ µ. We conclude that GSA( f ) ≥
SA( f ).
7 Proof of the main theorem
In this section, we close the circle of reductions. We use the results of Laplante and Magniez, who
recently proved [17] that the Kolmogorov complexity bound is asymptotically lower-bounded by the
weighted adversary bound and upper-bounded by the minimax bound. The upper bound is implicit in
their paper, because they did not state the minimax bound as a separate theorem.
Theorem 7.1. [17, Theorem 2] KA( f ) = Ω(WA( f )).
Theorem 7.2. KA( f ) = O(MM( f )).
Proof. Take a set of probability distributions p as in Equation (3.5). The query information lemma [17,
Lemma 3] says that K(i|x, p) ≤ log px1(i) +O(1) for every x, i such that px (i) > 0. This is true, because any
i of nonzero probability can be encoded in dlog px1(i) e bits using the Shannon-Fano code of distribution
px , and the Shannon-Fano code is a prefix-free code. Rewrite the inequality as px (i) = O 2−K(i|x,p) . The
statement follows, because the set of all strings σ in (3.4) includes among others also the descriptions
of all probability distributions p.
Remark 7.3. The constant in the equality KA( f ) = Θ(WA( f )) depends on the choice of the universal
Turing machine and the prefix-free set.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 13
ROBERT Š PALEK , M ARIO S ZEGEDY
Proof of Theorem 3.1. We have to prove that
Qε ( f )
p ≥ SA( f ) = WA( f ) = SWA( f ) = MM( f ) = SMM( f ) = GSA( f ) = Θ(KA( f )) .
1 − 2 ε(1 − ε)
Put together all known equalities and inequalities.
• SA( f ) = WA( f ) = SWA( f ) by Theorem 4.3 and Theorem 4.4,
• MM( f ) = SMM( f ) by Theorem 5.1,
• SMM( f ) = GSA( f ) by Theorem 5.2,
• GSA( f ) = SA( f ) by Theorem 6.1,
• KA( f ) = Θ(WA( f )) by Theorem 7.1 and Theorem 7.2.
Finally, one has to prove one of the lower bounds. For example, Ambainis proved [3] that Q2 ( f ) ≥ (1 −
2 ε(1 − ε)) WA( f ) for every Boolean f . Laplante and Magniez proved [17] that Q2 ( f ) = Ω(KA( f ))
p
for general f . Høyer and Špalek present in their survey [15] an alternative proof of the spectral adversary
bound that can easily be adapted to the non-Boolean case.
A Proof of the upper bound on the spectral norm
Proof of Lemma 4.2. Let S = M ◦ N. Define a shortcut
B(M, N) = max
x,y
rx (M)cy (N) .
S[x,y]>0
Without loss of generality, we assume that M[x, y] = 0 ⇔ N[x, y] = 0 ⇔ S[x, y] = 0. Let us prove the
existence of matrices M 0 , N 0 with B(M 0 , N 0 ) = r(M 0 )c(N 0 ) such that
M ◦ N = M 0 ◦ N 0 , and B(M, N) = B(M 0 , N 0 ) . (A.1)
We then apply Lemma 4.1 and obtain
λ (S) ≤ λ (M ◦ N) = λ (M 0 ◦ N 0 ) ≤ r(M 0 )c(N 0 ) = B(M 0 , N 0 ) = B(M, N) .
Take as M 0 , N 0 any pair of matrices that satisfies (A.1) and the following constraints:
• b = r(M 0 )c(N 0 ) is minimal, that is there is no pair M 00 , N 00 giving a smaller b,
• and, among those, the set R of maximum-norm rows of M 0 and the set C of maximum-norm
columns of N 0 are both minimal (in the same sense).
Let (r, c) be any “maximal” entry, that is S[r, c] > 0 and rr (M 0 )cc (N 0 ) = B(M 0 , N 0 ). Let R denote the
complement of R and let S[R,C] denote the sub-matrix of S indexed by R ×C. Then one of the following
cases happens:
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 14
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
1. (r, c) ∈ R ×C: Then B(M 0 , N 0 ) = r(M 0 )c(N 0 ) and we are done. If this is not the case, then we know
that S[R,C] = 0.
2. (r, c) ∈ R × C: Then S[R,C] = 0, otherwise we get a contradiction with one of the minimality
assumptions. If S[x, y] 6= 0 for some (x, y) ∈ R × C, multiply M 0 [x, y] by 1 + ε and divide N 0 [x, y]
by 1 + ε for some small ε > 0 such that the norm of the x-th row of M 0 is still smaller than r(M 0 ).
Now, we have either deleted the y-th column from C or, if |C| = 1, decreased c(N 0 ). Both cases
are a contradiction. Finally, if S[R,C] = 0, then c(N 0 ) = 0 due to S[R,C] = 0 and the fact that C
are the maximum-norm columns. Hence S is a zero matrix, and we are done.
3. (r, c) ∈ R ×C: This case is similar to the previous case.
4. (r, c) ∈ R × C: First, note that S[R, c] = 0, otherwise (r, c) would not be “maximal”. Now we
divide all entries in M 0 [R,C] by 1 + ε and multiply all entries in N 0 [R,C] by 1 + ε for some small
ε > 0 such that the “maximal” entries are unchanged. Since S[R,C] = 0, it follows that either
S[R,C] = 0 and S is a zero matrix, or there is a nonzero number in every row of M 0 [R,C]. Therefore,
unless S is a zero matrix, we have preserved B(M 0 , N 0 ) and c(N 0 ), and decreased r(M 0 ), which is a
contradiction.
We conclude that (r, c) ∈ R ×C, B(M 0 , N 0 ) = r(M 0 )c(N 0 ), and hence λ (S) ≤ B(M, N).
Acknowledgments
We thank Ronald de Wolf for many fruitful discussions, for his suggestions concerning Theorem 3.2,
and for proofreading, and Troy Lee for discussions. We thank anonymous referees for their helpful
comments.
Robert Špalek is supported in part by the EU fifth framework project RESQ, IST-2001-37559. Mario
Szegedy is supported by NSF grant 0105692, and in part by the National Security Agency (NSA) and
Advanced Research and Development Activity (ARDA) under Army Research Office (ARO), contract
number DAAD19-01-1-0506.
References
[1] * S. A ARONSON AND Y. S HI: Quantum lower bounds for the collision and the element distinctness
problem. Journal of the ACM, 51(4):595–605, 2004. [JACM:1008731.1008735, arXiv:quant-
ph/0111102]. 1.4, 3
[2] * A. A MBAINIS: Quantum lower bounds by quantum arguments. Journal of Computer and System
Sciences, 64(4):750–767, 2002. Earlier version in STOC ’00. [JCSS:10.1006/jcss.2002.1826,
STOC:335305.335394, arXiv:quant-ph/0002066]. 1.1, 1.2, 1.4, 1, 4.5
[3] * A. A MBAINIS: Polynomial degree vs. quantum query complexity. In Proc. of 44th IEEE FOCS,
pp. 230–239, 2003. [FOCS:10.1109/SFCS.2003.1238197, arXiv:quant-ph/0305028]. 1.2, 1.3,
1.4, 3.1, 1, 4, 7
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 15
ROBERT Š PALEK , M ARIO S ZEGEDY
[4] * A. A MBAINIS: Quantum walk algorithm for element distinctness. In Proc. of 45th IEEE FOCS,
pp. 22–31, 2004. [arXiv:quant-ph/0311001]. 1.4
[5] * A. A MBAINIS: Polynomial degree and lower bounds in quantum complexity: Collision and
element distinctness with small range. Theory of Computing, 1:37–46, 2005. [ToC:v001/a003,
arXiv:quant-ph/0305179]. 1.4
[6] * H. BARNUM AND M. S AKS: A lower bound on the quantum query complexity of
read-once functions. Journal of Computer and System Sciences, 69(2):244–258, 2004.
[JCSS:10.1016/j.jcss.2004.02.002, arXiv:quant-ph/0201007]. 3
[7] * H. BARNUM , M. S AKS , AND M. S ZEGEDY: Quantum decision trees and semidefinite program-
ming. In Proc. of 18th IEEE Complexity, pp. 179–193, 2003. [CCC:10.1109/CCC.2003.1214419].
1.1, 1.2, 1.3, 1.4, 3, 3.1, 4
[8] * R. B EALS , H. B UHRMAN , R. C LEVE , M. M OSCA , AND R. DE W OLF: Quantum lower
bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. Earlier version in FOCS
’98. [JACM:502090.502097, FOCS:10.1109/SFCS.1998.743485, arXiv:quant-ph/9802049]. 1.1,
1.4
[9] * H. B ENNETT, E. B ERNSTEIN , G. B RASSARD , AND U. VAZIRANI: Strengths and weaknesses
of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. [SICOMP:30093,
arXiv:quant-ph/9701001]. 1.1
[10] * H. B UHRMAN AND R. Š PALEK: Quantum verification of matrix products. In Proc. of 17th ACM-
SIAM SODA, pp. 880–889, 2006. [SODA:1109557.1109654, arXiv:quant-ph/0409035]. 1.4, 3
[11] * H. B UHRMAN AND R. DE W OLF: Complexity measures and decision tree complexity: A survey.
Theoretical Computer Science, 288(1):21–43, 2002. [TCS:10.1016/S0304-3975(01)00144-X]. 2.1
[12] * L. K. G ROVER: A fast quantum mechanical algorithm for database search. In Proc. of 28th ACM
STOC, pp. 212–219, 1996. [STOC:237814.237866, arXiv:quant-ph/9605043]. 1.2
[13] * P. H ØYER , M. M OSCA , AND R. DE W OLF: Quantum search on bounded-error inputs. In
Proc. of 30th ICALP, pp. 291–299, 2003. LNCS 2719. [ICALP:214dhep41d6vk3d2, arXiv:quant-
ph/0304052]. 1.2, 3
[14] * P. H ØYER , J. N EERBEK , AND Y. S HI: Quantum complexities of ordered searching, sorting, and
element distinctness. Algorithmica, 34(4):429–448, 2002. Special issue on Quantum Computation
and Cryptography. [Algorithmica:25gl9elr5rxr3q6a, arXiv:quant-ph/0102078]. 1.2, 4.5
[15] * P. H ØYER AND R. Š PALEK: Lower bounds on quantum query complexity. EATCS Bulletin,
87:78–103, October, 2005. [arXiv:quant-ph/0509153]. 7
[16] * S. L APLANTE , T. L EE , AND M. S ZEGEDY: The quantum adversary method and formula size
lower bounds. In Proc. of 20th IEEE Complexity, pp. 76–90, 2005. [CCC:10.1109/CCC.2005.29,
arXiv:quant-ph/0501057]. 1.4
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 16
A LL Q UANTUM A DVERSARY M ETHODS ARE E QUIVALENT
[17] * S. L APLANTE AND F. M AGNIEZ: Lower bounds for randomized and quantum query com-
plexity using Kolmogorov arguments. In Proc. of 19th IEEE Complexity, pp. 294–304, 2004.
[CCC:10.1109/CCC.2004.1313852, arXiv:quant-ph/0311189]. 1.2, 1.3, 2.2, 1, 3.1, 3.1, 2, 3, 7,
7.1, 7, 7
[18] * M. L I AND P. M. B. V IT ÁNYI: An Introduction to Kolmogorov Complexity and its Applications.
Springer, Berlin, second edition, 1997. 2.2
[19] * L. L OV ÁSZ: Semidefinite programs and combinatorial optimization. http://research.
microsoft.com/users/lovasz/semidef.ps, 2000. 2.3, 5, 5
[20] * F. M AGNIEZ , M. S ANTHA , AND M. S ZEGEDY: Quantum algorithms for the triangle problem.
In Proc. of 16th ACM-SIAM SODA, pp. 1109–1117, 2005. [SODA:1070432.1070591, arXiv:quant-
ph/0310134]. 1.4, 3
[21] * R. M ATHIAS: The spectral norm of a nonnegative matrix. Linear Algebra and its Applications,
139:269–284, 1990. [10.10160024-3795(90)90403-Y]. 2.4, 4.1, 4.1
[22] * M. A. N IELSEN AND I. L. C HUANG: Quantum Computation and Quantum Information. Cam-
bridge University Press, 2000. 2.1
[23] * M. S AKS AND A. W IGDERSON: Probabilistic Boolean decision trees and the complexity of
evaluating games trees. In Proc. of 27th IEEE FOCS, pp. 29–38, 1986. 1.4
[24] * M. S ANTHA: On the Monte Carlo decision tree complexity of read-once formulae. Random
Structures and Algorithms, 6(1):75–87, 1995. 1.4
[25] * M. S NIR: Lower bounds on probabilistic decision trees. Theoretical Computer Science, 38:69–
82, 1985. [TCS:10.1016/0304-3975(85)90210-5]. 1.4
[26] * M. S ZEGEDY: On the quantum query complexity of detecting triangles in graphs. quant-
ph/0310107, 2003. [arXiv:quant-ph/0310107]. 1.2, 3
[27] * S. Z HANG: On the power of Ambainis’s lower bounds. Theoretical Computer Science,
339(2–3):241–256, 2005. Earlier version in ICALP’04. [TCS:10.1016/j.tcs.2005.01.019,
ICALP:gm2ff6wpc0q39v3x, arXiv:quant-ph/0311060]. 1.2, 1.3, 3.1, 3, 4
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 17
ROBERT Š PALEK , M ARIO S ZEGEDY
AUTHORS
Robert Špalek
graduate student
Centrum voor Wiskunde en Informatica
Amsterdam, The Netherlands
sr cwi nl
http://www.ucw.cz/~robert/
Mario Szegedy
professor
Rutgers, the State University of New Jersey
Piscataway, New Jersey, USA
szegedy cs rutgers edu
http://athos.rutgers.edu/~szegedy/
ABOUT THE AUTHORS
ROBERT Š PALEK received his Masters Degrees in Computer Science from Charles Univer-
sity, Prague and Vrije Universiteit, Amsterdam. He is currently a graduate student at
CWI, advised by Harry Buhrman. His research interests include quantum computing,
computational complexity, algorithms, data structures, and search engines. He loves
dancing salsa, climbing, photography, travelling to distant countries, and playing guitar.
M ARIO S ZEGEDY received his Ph. D. in computer science at the University of Chicago un-
der the supervision of Laci Babai and Janos Simon. He held a Lady Davis Postdoctoral
Fellowship at the Hebrew University, Jerusalem (1989-90), a postdoc at the University
of Chicago, 1991-92, and a postdoc at Bell Laboratories (1992). He was a permanent
member of Bell Labs for 7 years and for two more years of AT&T Research. He left
AT&T in September 1999 to conduct research at the Institute for Advanced Study in
Princeton for a year. In 2000 he joined the faculty of Rutgers University.
He received the Gödel Prize twice, in 2001 for his part in the PCP Theorem and its con-
nection to inapproximability and in 2005 for the analysis of data streams using limited
memory.
His research interests include complexity theory, combinatorics, combinatorial geome-
try and quantum computing, but he also has an interest in algebra and in programming
languages.
With a group of students he has founded QCteam, a quantum computing laboratory at
Rutgers, which is his main project at the present time. The laboratory has received
substantial funding from the university and from the National Science Foundation. It
has a vigorous visitor program, and pursues collaboration with the local industry.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 1–18 18