1.2k citations · 3.7k across the 62 of their papers we have counts for
6 papers · 1 filter
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…
New Applications of the Incompressibility Method: Part I
Tao Jiang, Ming Li, Paul Vitanyi
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…
New Applications of the Incompressibility Method: Part II
Harry Buhrman, Tao Jiang, Ming Li +1
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas. To further demonstrate its power and elegance we exhibit ne…
Separating complexity classes using autoreducibility
Harry Buhrman, Lance Fortnow, Leen Torenvliet +1
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hie…
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…