Quantum clustering algorithms

ABSTRACT

By the term "quantization", we refer to the process of using quantum mechanics in order to improve a classical algorithm, usually by making it go faster. In this paper, we initiate the idea of quantizing clustering algorithms by using variations on a celebrated quantum algorithm due to Grover. After having introduced this novel approach to unsupervised learning, we illustrate it with a quantized version of three standard algorithms: divisive clustering, k-medians and an algorithm for the construction of a neighbourhood graph. We obtain a significant speedup compared to the classical approach.

REFERENCES

• 1: Aïmeur, E., Brassard, G. & Gambs, S. (2006). Machine learning in a quantum world. Proceedings of Canadian AI 2006 (pp. 433--444).
• 2: Ambainis, A. (2003). Quantum walks and their algorithmic applications. International Journal of Quantum Information, 1, 507--518.
• 3: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 4: Bell, J. (1964). On the Einstein-Podolsky-Rosen paradox. Physics, 1(3), 195--200.
• 5: Bennett, C. H. & Brassard, G. (1984). Quantum cryptography: Public key distribution and coin tossing. Proceedings of the IEEE Conference on Computers, Systems and Signal Processing, Bangalore, India (pp. 175--179).
• 6: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 7: Bonner, R. & Freivalds, R. (2002). A survey of quantum learning. Proceedings of the Workshop on Quantum Computation and Learning (pp. 106--119).
• 8: Borůvka, O. (1926). O jistém problému minimálním. Práce Moravské Přirodovědecké Společnosti, 3, 37--58.
• 9: Boyer, M., Brassard, G., Høyer, P. & Tapp, A. (1998). Tight bounds on quantum searching. Fortschritte Der Physik, 46, 493--505.
• 10: Brassard, G., Høyer, P., Mosca, M. & Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 53--74.
• 11: Dürr, C., Heiligman, M., Høyer, P. & Mhalla, M. (2004). Quantum query complexity of some graph problems. Proceedings of the International Conference on Automata, Languages and Programming: ICALP'04 (pp. 481--493).
• 12: Dürr, C. & Høøyer, P. (1996). A quantum algorithm for finding the minimum. Available on http://arxiv.org/quant-ph/9607014.
• 13: Einstein, A., Podolsky, B. & Rosen, N. (1935). Can quantum mechanical description of physical reality be considered complete? Physical Review, 47, 777--780.
• 14: Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2), 325--328.
• 15: Lov K. Grover, A framework for fast quantum mechanical algorithms, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.53-62, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276712]
• 16: David Harel , Yehuda Koren, On Clustering Using Random Walks, Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, p.18-41, December 13-15, 2001
• 17: Horn, D. & Gottlieb, A. (2001). The method of quantum clustering. Proceedings of the Neural Information Processing Systems: NIPS'01 (pp. 769--776).
• 18: Horn, D. & Gottlieb, A. (2002). Algorithm for data clustering in pattern recognition problems based on quantum mechanics. Physical Review Letters, 88(1).
• 19: Kaufman, L. & Rousseeuw, P. (1987). Clustering by means of medoids. in Statistical Data Analysis Based on the L<inf>1</inf>--Norm and Related Methods, Y. Dodge (editor), North-Holland, Amsterdam (pp. 405--416).
• 20: Nina Mishra , Dan Oblinger , Leonard Pitt, Sublinear time approximate clustering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.439-447, January 07-09, 2001, Washington, D.C., United States
• 21: Ashwin Nayak , Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.384-393, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301349]
• 22: Nielsen, M. & Chuang, I. (Eds.). (2000). Quantum Computation and Quantum Information. Cambridge University Press.
• 23: Rocco A. Servedio, Separating Quantum and Classical Learning, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.1065-1080, July 08-12, 2001
• 24: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 25: Small, C. G. (1990). A survey of multidimensional medians. International Statistical Review, 58(3), 263--277.
• 26: Mario Szegedy, Quantum Speed-Up of Markov Chain Based Algorithms, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.32-41, October 17-19, 2004 [doi>10.1109/FOCS.2004.53]
• 27: Tenenbaum, J. B., de Silva, V. & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.