Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs
| Authors |
|
| Publication date |
2005
|
| Number of pages |
26
|
| Publisher |
Unknown Publisher
|
| Organisations |
-
Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
|
| Abstract |
A direct product theorem upper-bounds the overall success probability of algorithms for computing many independent instances of a computational problem. We prove a direct product theorem for 2-sided error algorithms for symmetric functions in the setting of quantum query complexity, and a stronger direct product theorem for 1-sided error algorithms for threshold functions. We also present a quantum algorithm for deciding systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
|
| Document type |
Report
|
| Note |
quant-ph/0511200
|
|
Permalink to this page
|
Back