194 citations · 1.9k across the 115 of their papers we have counts for
7 papers · 1 filter
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.
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
Andris Ambainis, William Gasarch, Aravind Srinavasan +1
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic prot…
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…