We give a new version of the adversary method for proving lower bounds onquantum query algorithms. The new method is based on analyzing the eigenspacestructure of the problem at hand. We use it to prove a new and optimal strongdirect product theorem for 2-sided error quantum algorithms computing kindependent instances of a symmetric Boolean function: if the algorithm usessignificantly less than k times the number of queries needed for one instanceof the function, then its success probability is exponentially small in k. Wealso use the polynomial method to prove a direct product theorem for 1-sidederror algorithms for k threshold functions with a stronger bound on the successprobability. Finally, we present a quantum algorithm for evaluating solutionsto systems of linear inequalities, and use our direct product theorems to showthat the time-space tradeoff of this algorithm is close to optimal.
展开▼
