Esma Aïmeur
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.
- Aïmeur, E., Brassard, G. & Gambs, S. (2006). Machine learning in a quantum world. Proceedings of Canadian AI 2006 (pp. 433--444).Google Scholar
Digital Library
- Ambainis, A. (2003). Quantum walks and their algorithmic applications. International Journal of Quantum Information, 1, 507--518.Google ScholarCross Ref
- Angluin, D. (1988). Queries and concept learning. Machine Learning, 2, 319--342. Google ScholarDigital Library
- Bell, J. (1964). On the Einstein-Podolsky-Rosen paradox. Physics, 1(3), 195--200.Google ScholarCross Ref
- 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).Google Scholar
- Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509--517. Google ScholarDigital Library
- Bonner, R. & Freivalds, R. (2002). A survey of quantum learning. Proceedings of the Workshop on Quantum Computation and Learning (pp. 106--119).Google Scholar
- Borůvka, O. (1926). O jistém problému minimálním. Práce Moravské Přirodovědecké Společnosti, 3, 37--58.Google Scholar
- Boyer, M., Brassard, G., Høyer, P. & Tapp, A. (1998). Tight bounds on quantum searching. Fortschritte Der Physik, 46, 493--505.Google ScholarCross Ref
- Brassard, G., Høyer, P., Mosca, M. & Tapp, A. (2002). Quantum amplitude amplification and estimation. Contemporary Mathematics, 305, 53--74.Google ScholarCross Ref
- 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).Google ScholarCross Ref
- Dürr, C. & Høøyer, P. (1996). A quantum algorithm for finding the minimum. Available on http://arxiv.org/quant-ph/9607014.Google Scholar
- Einstein, A., Podolsky, B. & Rosen, N. (1935). Can quantum mechanical description of physical reality be considered complete? Physical Review, 47, 777--780.Google ScholarCross Ref
- Grover, L. K. (1997). Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2), 325--328.Google ScholarCross Ref
- Grover, L. K. (1998). A framework for fast quantum mechanical algorithms. Proceedings of the 30th ACM Symposium on Theory of Computing: STOC'98 (pp. 53--62). Google ScholarDigital Library
- Harel, D. & Koren, Y. (2001). On clustering using random walks. Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS'01 (pp. 18--41). Google ScholarDigital Library
- Horn, D. & Gottlieb, A. (2001). The method of quantum clustering. Proceedings of the Neural Information Processing Systems: NIPS'01 (pp. 769--776).Google Scholar
- Horn, D. & Gottlieb, A. (2002). Algorithm for data clustering in pattern recognition problems based on quantum mechanics. Physical Review Letters, 88(1).Google Scholar
- Kaufman, L. & Rousseeuw, P. (1987). Clustering by means of medoids. in Statistical Data Analysis Based on the L1--Norm and Related Methods, Y. Dodge (editor), North-Holland, Amsterdam (pp. 405--416).Google Scholar
- Mishra, N., Oblinger, D. & Pitt, L. (2001). Sublinear time approximate clustering. Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms: SODA'01 (pp. 439--447). Google ScholarDigital Library
- Nayak, A. & Wu, F. (1999). The quantum query complexity of approximating the median and related statistics. Proceedings of the 31st ACM Symposium on Theory of Computing: STOC'99 (pp. 384--393). Google ScholarDigital Library
- Nielsen, M. & Chuang, I. (Eds.). (2000). Quantum Computation and Quantum Information. Cambridge University Press.Google Scholar
- Servedio, R. (2001). Separating quantum and classical learning. Proceedings of the International Conference on Automata, Languages and Programming: ICALP'01 (pp. 1065--1080). Google ScholarDigital Library
- Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal of Computing, 26, 1484--1509. Google ScholarDigital Library
- Small, C. G. (1990). A survey of multidimensional medians. International Statistical Review, 58(3), 263--277.Google ScholarCross Ref
- Szegedy, M. (2004). Quantum speed-up of Markov chain based algorithms. Proceedings of 45th IEEE Symposium on Foundations of Computer Science: FOCS'04 (pp. 32--41). Google ScholarDigital Library
- Tenenbaum, J. B., de Silva, V. & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.Google ScholarCross Ref
- Quantum clustering algorithms
Recommendations
Photonic scheme of quantum phase estimation for quantum algorithms via quantum dots
AbstractVarious quantum algorithms depend on quantum phase estimation (QPE) as basic blocks or main subroutines to leverage superposition and entanglement during quantum computations. The QPE algorithm estimates the unknown phase of an eigenvalue ...
Quantum correlation swapping
Quantum correlations (QCs), including quantum entanglement and those different, are important quantum resources and have attracted much attention recently. Quantum entanglement swapping as a kernel technique has already been applied to quantum repeaters ...
Can quantum discord increase in a quantum communication task?
Quantum teleportation of an unknown quantum state is one of the few communication tasks which has no classical counterpart. Usually the aim of teleportation is to send an unknown quantum state to a receiver. But is it possible in some way that the ...
Comments