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 d=k-1.
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 Problem (ITCS'13)

We prove a tight quantum query lower bound Ω(n^k/(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 conversion (FOCS'11)

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 bound.

A direct product theorem for discrepancy (CCC'08)

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, disc_U^k(f ^(k)) = O(disc_U(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, SICOMP'10)

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 (STOC'07)

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 function composition. 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, Algorithmica'09)

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 (STACS'06)

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( n^7/6 √m U^1/3, √(n U) m) log n), where n is the number of vertices, m is the number of edges, and U ≤ n^1/4 is an upper bound on the capacity of an edge.

Quantum Verification of Matrix Products (SODA'06)

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(n^5/3) and expected time O(n^5/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(n^7/4). We also present a quantum matrix multiplication algorithm that is efficient when the result has few nonzero entries.

Lower Bounds on Quantum Query Complexity (Survey, BEATCS'05)

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 methods.

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 (STACS'03, ToC'05)

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 QNC^f₀) 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.