- Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs
- Number of pages
- Unknown Publisher
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
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.