194 citations · 1.9k across the 115 of their papers we have counts for
5 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…
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…
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…
Quantum search algorithms
Andris Ambainis
We review some of quantum algorithms for search problems: Grover's search algorithm, its generalization to amplitude amplification, the applications of amplitude amplification to v…
Probabilistic and Team PFIN-type Learning: General Properties
Andris Ambainis
We consider the probability hierarchy for Popperian FINite learning and study the general properties of this hierarchy. We prove that the probability hierarchy is decidable, i.e. t…