65 citations · 120 across the 10 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
quant-ph2005★ 18 cited
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…
quant-ph2005★ 13 cited
A new quantum lower bound method, with an application to strong direct product theorem for quantum search
Andris Ambainis
We present a new method for proving lower bounds on quantum query algorithms. The new method is an extension of adversary method, by analyzing the eigenspace structure of the probl…