Physics – Quantum Physics
Scientific paper
2005-11-21
Physics
Quantum Physics
16 pages LaTeX. Version 2: title changed, proofs significantly cleaned up and made selfcontained. This version to appear in th
Scientific paper
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
Ambainis Andris
Spalek Robert
Wolf Ronald de
No associations
LandOfFree
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-291499