Abstracts of my scientific papers
- Adversary Lower Bound for the Orthogonal Array Problem
We prove a quantum query lower bound Ω(n(d+1)/(d+2))
for the problem of deciding whether an input string of size n contains
a k-tuple which belongs to a fixed orthogonal array on k
factors of strength d≤k-1 and index 1, provided that the
alphabet size is sufficiently large. Our lower bound is tight when
The orthogonal array problem includes the following problems as special cases:
- k-sum problem with d=k-1,
- k-distinctness problem with d=1,
- k-pattern problem with d=0,
- (d-1)-degree problem with 1≤d≤k-1,
- unordered search with d=0 and k=1, and
- graph collision with d=0 and k=2.
- Adversary Lower Bound for the k-sum
We prove a tight quantum query lower bound Ω(nk/(k+1))
for the problem of deciding whether there exist k numbers among
n that sum up to a prescribed number, provided that the alphabet size
is sufficiently large.
- Quantum query complexity of state
State conversion generalizes query complexity to the problem of converting
between two input-dependent quantum states by making queries to the input.
We characterize the complexity of this problem by introducing a natural
information-theoretic norm that extends the Schur product operator norm. The
complexity of converting between two systems of states is given by the
distance between them, as measured by this norm.
In the special case of function evaluation, the norm is closely related to
the general adversary bound, a semi-definite program that lower-bounds the
number of input queries needed by a quantum algorithm to evaluate a
function. We thus obtain that the general adversary bound characterizes the
quantum query complexity of any function whatsoever. This generalizes and
simplifies the proof of the same result in the case of boolean input and
output. Also in the case of function evaluation, we show that our norm
satisfies a remarkable composition property, implying that the quantum query
complexity of the composition of two functions is at most the product of the
query complexities of the functions, up to a constant. Finally, our result
implies that discrete and continuous-time query models are equivalent in the
bounded-error setting, even for the general state-conversion problem.
- A Dual Polynomial for OR
We reprove that the approximate degree of the OR function on n bits is
Ω(√n). We consider a linear program which is feasible if and
only if there is an approximate polynomial for a given function, and apply
the duality theory. The duality theory says that the primal program has no
solution if and only if its dual has a solution. Therefore one can prove
the nonexistence of an approximate polynomial by exhibiting a dual solution,
coined the dual polynomial. We construct such a polynomial.
- The Multiplicative Quantum Adversary (CCC'08)
We present a new variant of the quantum adversary method. All adversary
methods give lower bounds on the quantum query complexity of a function by
bounding the change of a progress function caused by one query. All previous
variants upper-bound the difference of the progress function, whereas
our new variant upper-bounds the ratio and that is why we coin it the
multiplicative adversary. The new method generalizes to all functions the
new quantum lower-bound method by Ambainis [Amb05, ASW06] based on
the analysis of eigenspaces of the density matrix. We prove a strong direct
product theorem for all functions that have a multiplicative adversary lower
- A direct product theorem for discrepancy
Discrepancy is a versatile bound in communication complexity which can be
used to show lower bounds in the distributional, randomized, quantum, and
even unbounded error models of communication. We show an optimal product
theorem for discrepancy, namely that for any two Boolean functions f,
g, disc(f ⊕ g) = Θ(disc(f) disc(g)). As a consequence
we obtain a strong direct product theorem for distributional complexity, and
direct sum theorems for worst-case complexity, for bounds shown by the
discrepancy method. Our results resolve an open problem of Shaltiel (2003)
who showed a weaker product theorem for discrepancy with respect to the
uniform distribution, discUk(f (k)) =
O(discU(f)) k/3. The
main tool for our results is semidefinite programming, in particular a
recent characterization of discrepancy in terms of a semidefinite
programming quantity by Linial and Shraibman (2006).
- Span-program-based quantum algorithm for
evaluating formulas (STOC'08, ToC'12)
We give a quantum algorithm for evaluating formulas over an extended gate
set, including all two- and three-bit binary gates (e.g., NAND, 3-majority).
The algorithm is optimal on read-once formulas for which each gate's inputs
are balanced in a certain sense.
The main new tool is a correspondence between a classical linear-algebraic
model of computation, "span programs," and weighted bipartite graphs. A span
program's evaluation corresponds to an eigenvalue-zero eigenvector of the
associated graph. A quantum computer can therefore evaluate the span program
by applying spectral estimation to the graph.
For example, the classical complexity of evaluating the balanced ternary
majority formula is unknown, and the natural generalization of randomized
alpha-beta pruning is known to be suboptimal. In contrast, our algorithm
generalizes the optimal quantum AND-OR formula evaluation algorithm and is
optimal for evaluating the balanced ternary majority formula.
- Any AND-OR formula of size N can be evaluated in time
N½+o(1) on a quantum computer (FOCS'07,
For any AND-OR formula of size N, there exists a bounded-error
N½+o(1)-time quantum algorithm, based on a discrete-time
quantum walk, that evaluates this formula on a black-box input. Balanced,
or "approximately balanced," formulas can be evaluated in O(√N)
queries, which is optimal. It follows that the (2-o(1))th power of the
quantum query complexity is a lower bound on the formula size, almost
solving in the positive an open problem posed by Laplante, Lee and Szegedy.
- Negative weights make adversaries stronger
The quantum adversary method is one of the most successful techniques for
proving lower bounds on quantum query complexity. It gives optimal lower
bounds for many problems, has application to classical complexity in
formula size lower bounds, and is versatile with equivalent formulations in
terms of weight schemes, eigenvalues, and Kolmogorov complexity.
All these formulations are information-theoretic and rely on the principle
that if an algorithm successfully computes a function then, in particular, it
is able to distinguish between inputs which map to different values.
We present a stronger version of the adversary method which goes beyond this
principle to make explicit use of the stronger condition that the algorithm
actually computes the function.
This new method, which we call ADV±, has all the advantages of
the old: it is a lower bound on bounded-error quantum query complexity, its
square is a lower bound on formula size, and it behaves well with respect to
Moreover ADV± is always at least as large as the adversary method ADV,
and we show an example of a monotone function for which
ADV±(f)=Ω(ADV(f)1.098). We also give examples showing
that ADV± does not face limitations of ADV such as the certificate
complexity barrier and the property testing barrier.
- A New Quantum Lower Bound Method, with Applications
to Direct Product Theorems and Time-Space Tradeoffs (STOC'06,
We give a new version of the adversary method for proving lower bounds on
quantum query algorithms. The new method is based on analyzing the eigenspace
structure of the problem at hand. We use it to prove a new and optimal strong
direct product theorem for 2-sided error quantum algorithms computing k
independent instances of a symmetric Boolean function: if the algorithm uses
significantly less than k times the number of queries needed for one
instance of the function, then its success probability is exponentially small
in k. We also use the polynomial method to prove a direct product
theorem for 1-sided error algorithms for k threshold functions with a
stronger bound on the success probability. Finally, we present a quantum
algorithm for evaluating solutions to systems of linear inequalities, and use
our direct product theorems to show that the time-space tradeoff of this
algorithm is close to optimal.
- Tight adversary bounds for composite functions
(superseded by Negative adversaries)
The quantum adversary method is a versatile method for proving
lower bounds on quantum algorithms. It yields tight bounds for many
computational problems, is robust in having many equivalent
formulations, and has natural connections to classical lower bounds.
A further nice property of the adversary method is that it behaves very
well with respect to composition of functions. We generalize the adversary
method to include costs---each bit of the input can be given an
arbitrary positive cost representing the difficulty of querying that bit.
We use this generalization to exactly capture the adversary
bound of a composite function in terms of the adversary bounds of its
component functions. Our results generalize and unify previously known
composition properties of adversary methods, and yield as a simple corollary
the Ω(√n) bound of Barnum and Saks on the quantum query complexity
of read-once functions.
- Quantum Algorithms for Matching and Network Flows
We present quantum algorithms for the following graph problems: finding a
maximal bipartite matching in time O(n √(m+n) log n), finding a maximal
non-bipartite matching in time O(n² (√(m/n) + log n) log n), and
finding a maximal flow in an integer network in time O(min( n7/6 √m
U1/3, √(n U) m) log n), where n is the number of vertices,
m is the number of
edges, and U ≤ n1/4 is an upper bound on the capacity of an edge.
- Quantum Verification of Matrix Products
We present a quantum algorithm that verifies a product of two n×n
matrices over any integral domain with bounded error in worst-case time
O(n5/3) and expected time O(n5/3 / min(w, √n)1/3),
where w is the number of wrong entries. This improves the previous
best algorithm that runs in time O(n7/4). We also present a quantum
matrix multiplication algorithm that is efficient when the result has few
- Lower Bounds on Quantum Query Complexity
Shor's and Grover's famous quantum algorithms for factoring and
searching show that quantum computers can solve certain computational
problems significantly faster than any classical computer. We discuss
here what quantum computers cannot do, and specifically how to
prove limits on their computational power. We cover the main known
techniques for proving lower bounds, and exemplify and compare the
- All Quantum Adversary Methods are
Equivalent (ICALP'05, ToC'06)
The quantum adversary method is one of the most versatile lower-bound methods
for quantum algorithms. We show that all known variants of this method are
equal: spectral adversary [Barnum, Saks, and Szegedy, 2003], weighted
adversary [Ambainis, 2003], strong weighted adversary [Zhang,
2004], and the Kolmogorov complexity adversary [Laplante and
Magniez, 2003]. 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 all versions of
the quantum adversary method easily follow.
- Quantum and Classical Strong Direct Product Theorems
and Optimal Time-Space Tradeoffs (FOCS'04, SICOMP'07)
A strong direct product theorem says that if we want to compute
k independent instances of a function, using less than k times
the resources needed for one instance, then our overall success
probability will be exponentially small in k.
We establish such theorems for the classical as well as quantum
query complexity of the OR function. This implies slightly
weaker direct product results for all total functions.
We prove a similar result for quantum communication
protocols computing k instances of the Disjointness function.
Our direct product theorems imply a time-space tradeoff
T² S = Ω(N³) for sorting N items on a quantum computer, which
is optimal up to polylog factors. They also give several tight
time-space and communication-space tradeoffs for the problems of
Boolean matrix-vector multiplication and matrix multiplication.
- Quantum Fan-out is Powerful
We demonstrate that the unbounded fan-out gate is very powerful.
Constant-depth polynomial-size quantum circuits with bounded fan-in and
unbounded fan-out over a fixed basis (denoted by
QNCf0) can approximate
with polynomially small error the following gates: parity, mod[q], And,
Or, majority, threshold[t], exact[q], and counting. Classically, we need
logarithmic depth even if we can use unbounded fan-in gates. If we allow
arbitrary one-qubit gates instead of a fixed basis, then these circuits can
also be made exact in log-star depth. Sorting, arithmetical operations, phase
estimation, and the quantum Fourier transform with arbitrary moduli can also
be approximated in constant depth.