1.2k citations · 3.7k across the 62 of their papers we have counts for
3 papers · 2 filters
Lower Bounds for Quantum Search and Derandomization
Harry Buhrman, Ronald de Wolf
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In part…
Quantum vs. Classical Communication and Computation
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol f…
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…