Physics – Quantum Physics
Scientific paper
2004-02-18
Physics
Quantum Physics
22 pages LaTeX. 2nd version: some parts rewritten, results are essentially the same. A shorter version will appear in IEEE FOC
Scientific paper
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.
Klauck Hartmut
Spalek Robert
Wolf Ronald de
No associations
LandOfFree
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-181256