179 citations · 179 across the 2 of their papers we have counts for
2 papers
quant-ph2005
A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
Andris Ambainis, Robert Spalek, Ronald de Wolf
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…
quant-ph1998★ 179 cited
Quantum Lower Bounds by Polynomials
Robert Beals, Harry Buhrman, Richard Cleve +2
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the…