TR04-045 Authors: Hartmut Klauck, Robert Spalek, Ronald de Wolf

Publication: 3rd June 2004 18:16

Downloads: 1424

Keywords:

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^2*S=Omega(N^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.