- Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs
- Book/source title
- Proceedings of 45th IEEE FOCS
- Pages (from-to)
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.