65 citations · 120 across the 10 of their papers we have counts for
24 papers
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…
Robust Quantum Algorithms for Oracle Identification
Andris Ambainis, Kazuo Iwama, Akinori Kawachi +2
The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set of oracles and a blackbox oracle . Our task is to figure…
An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
We provide an elementary proof of the quantum adiabatic theorem.
Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption
Andris Ambainis, Adam Smith
A quantum encryption scheme (also called private quantum channel, or state randomization protocol) is a one-time pad for quantum messages. If two parties share a classical random s…
Quantum Identification of Boolean Oracles
Andris Ambainis, Kazuo Iwama, Akinori Kawachi +3
The oracle identification problem (OIP) is, given a set of Boolean oracles out of ones, to determine which oracle in is the current black-box oracle. We can exp…