Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs
Andris Ambainis, Robert Špalek, Ruben Wolf · 2005
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.