Machine Learning · 2012 · 213 citations · 61 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningQuantum ComputingQuantum AlgorithmsQuantum BitsQuantum CommunicationQuantum ComputationQuantum Machine LearningUnsupervised LearningClusteringClustering AnalysisDivisive ClusteringInitializationMinimum Spanning Tree AlgorithmsQuantizationQuantum Machine Learning AlgorithmsUnsupervised Outlier Detection
We show how the quantum paradigm can be used to speed up unsupervised learning algorithms. More precisely, we explain how it is possible to accelerate learning algorithms by quantizing some of their subroutines. Quantization refers to the process that partially or totally converts a classical algorithm to its quantum counterpart in order to improve performance. In particular, we give quantized versions of clustering via minimum spanning tree, divisive clustering and k -medians that are faster than their classical analogues. We also describe a distributed version of k -medians that allows the participants to save on the global communication cost of the protocol compared to the classical version. Finally, we design quantum algorithms for the construction of a neighbourhood graph, outlier detection as well as smart initialization of the cluster centres.
61
<i>Quantum Computation and Quantum Information</i>
Michael A. Nielsen, Isaac L. Chuang, Lov K. Grover · American Journal of Physics · 2002 · 22.7K citations
Quantum computation and quantum information
Jim Law · ACM SIGSOFT Software Engineering Notes · 2001 · 19.2K citations
Computing, Computer Science, Physics +13
Least squares quantization in PCM
Sheelagh Lloyd · IEEE Transactions on Information Theory · 1982 · 15.6K citations · Full text
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Joshua B. Tenenbaum, Vin de Silva, John Langford · Science · 2000 · 13.7K citations
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text