Robert Spalek

FOCS Conference 2011 Conference Paper

Quantum Query Complexity of State Conversion

• Troy Lee
• Rajat Mittal 0001
• Ben Reichardt
• Robert Spalek
• Mario Szegedy

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.

STOC Conference 2008 Conference Paper

Span-program-based quantum algorithm for evaluating formulas

• Ben Reichardt
• Robert Spalek

FOCS Conference 2007 Conference Paper

Any AND-OR Formula of Size N can be Evaluated in time N 1/2+o(1) on a Quantum Computer

• Andris Ambainis
• Andrew M. Childs
• Ben Reichardt
• Robert Spalek
• Shengyu Zhang 0002

For any AND-OR formula of size N, there exists a bounded-error N 1/2+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(radicN) 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.

STOC Conference 2007 Conference Paper

Negative weights make adversaries stronger

• Peter Høyer
• Troy Lee
• Robert Spalek

STOC Conference 2006 Conference Paper

A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs

• Andris Ambainis
• Robert Spalek
• Ronald de Wolf

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.

SODA Conference 2006 Conference Paper

Quantum verification of matrix products

• Harry Buhrman
• Robert Spalek

FOCS Conference 2004 Conference Paper

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

• Hartmut Klauck
• Robert Spalek
• Ronald de Wolf

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 is 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. These results imply a time-space tradeoff T/sup 2/S = /spl Omega/(N/sup 3/) 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.