218 citations · 643 across the 16 of their papers we have counts for
4 papers · 1 filter
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…
Lower Bounds on Quantum Query Complexity
Peter Hoyer, Robert Spalek
Shor's and Grover's famous quantum algorithms for factoring and searching show that quantum computers can solve certain computational problems significantly faster than any classic…
Quantum Algorithms for Matching and Network Flows
Andris Ambainis, Robert Spalek
We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time…
Tight adversary bounds for composite functions
Peter Hoyer, Troy Lee, Robert Spalek
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many…