ECCC-Report TR04-045https://eccc.weizmann.ac.il/report/2004/045Comments and Revisions published for TR04-045en-usThu, 03 Jun 2004 18:16:57 +0300
Paper TR04-045
| Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs |
Hartmut Klauck,
Robert Spalek,
Ronald de Wolf
https://eccc.weizmann.ac.il/report/2004/045A 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.
Thu, 03 Jun 2004 18:16:57 +0300https://eccc.weizmann.ac.il/report/2004/045