194 citations · 1.9k across the 115 of their papers we have counts for
6 papers · 2 filters
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…
Quantum walks and their algorithmic applications
Andris Ambainis
Quantum walks are quantum counterparts of Markov chains. In this article, we give a brief overview of quantum walks, with emphasis on their algorithmic applications.
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…