Journal
SIAM JOURNAL ON COMPUTING
Volume 36, Issue 5, Pages 1472-1493Publisher
SIAM PUBLICATIONS
DOI: 10.1137/05063235X
Keywords
complexity theory; quantum computing; lower bounds; decision trees; communication complexity
Funding
- Canada's NSERC
- MITACS
- DFG [KL 1470/1]
- European Commission [IST-2001-37559, IST-2005-015848]
- Netherlands Organization for Scientific Research (NWO)
Ask authors/readers for more resources
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 (TS)-S-2 = 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available