  We present several quantum algorithms for performing nearest-neighbor
learning. At the core of our algorithms are fast and coherent quantum methods
for computing distance metrics such as the inner product and Euclidean
distance. We prove upper bounds on the number of queries to the input data
required to compute these metrics. In the worst case, our quantum algorithms
lead to polynomial reductions in query complexity relative to the corresponding
classical algorithm. In certain cases, we show exponential or even
super-exponential reductions over the classical analog. We study the
performance of our quantum nearest-neighbor algorithms on several real-world
binary classification tasks and find that the classification accuracy is
competitive with classical methods.
