Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning
Quantum Information and Computation · 2015-03 · 15 (3&4) · 316-356
DOI: 10.26421/qic15.3-4-7 ↗Kurz gefasst
Fachartikel in der Zeitschrift Quantum Information and Computation, 2015-03. Verfasst von Nathan Wiebe und 2 weiteren Autor:innen. Die Arbeit wurde bisher 95-mal zitiert (Crossref).
Abstract (Originalsprache)
We present quantum algorithms for performing nearest-neighbor learning and $k$--means clustering. At the core of our algorithms are fast and coherent quantum methods for computing the Euclidean distance both directly and via the inner product which we couple with methods for performing amplitude estimation that do not require measurement. We prove upper bounds on the number of queries to the input data required to compute such distances and find the nearest vector to a given test example. In the worst case, our quantum algorithms lead to polynomial reductions in query complexity relative to Monte Carlo algorithms. We also 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.
Zitieren
APA
Wiebe, N., Kapoor, A., & Svore, K. M. (2015). Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information and Computation, 15(3&4), 316-356. https://doi.org/10.26421/qic15.3-4-7
Vancouver
Wiebe N, Kapoor A, Svore KM. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information and Computation. 2015;15(3&4):316-356. doi:10.26421/qic15.3-4-7
BibTeX
@article{Wiebe2015,
author = {Wiebe, Nathan and Kapoor, Ashish and Svore, Krysta M.},
title = {Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning},
journal = {Quantum Information and Computation},
year = {2015},
volume = {15},
number = {3&4},
pages = {316--356},
doi = {10.26421/qic15.3-4-7}
}
EUVIMED