18 citations · 31 across the 2 of their papers we have counts for
6 papers · 1 filter
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…
Coins Make Quantum Walks Faster
Andris Ambainis, Julia Kempe, Alexander Rivosh
We show how to search N items arranged on a grid in time , using a discrete time quantum walk. This result for the first time exhibits a…