QUANTUM SPECTRAL CLUSTERING THROUGH A BIASED PHASE ESTIMATION ALGORITHM

Abstract

In this paper, we go through the theoretical steps of the spectral clustering on quantum computers by employing the phase estimation and the amplitude amplification algorithms. We discuss circuit designs for each step and show how to obtain the clustering solution from the output state. In addition, we introduce a biased version of the phase estimation algorithm which significantly speeds up the amplitude amplication process. The complexity of the whole process is analyzed: It is shown that when the circuit representation of a data matrix of order N is produced through an ancilla based circuit in which the matrix is written as a sum of L number of Householder matrices; the computational complexity is bounded by O 2mLN number of quantum gates. Here, m represents the number of qubits involved in the phase register of the phase estimation algorithm.

Keywords

• Spectral Clustering,Quantum Algorithms.

References

1. Kempe, J., (2003), Quantum random walks: An introductory overview, Contemporary Physics, 44(4), pp. 307–327.
2. Faccin, M., Migda l, P., Johnson, T. H., Bergholm, V. and Biamonte, J. D., (2014), Com- munity detection in quantum complex networks, Physical Review X, 4(4), p. 041012.
3. Wiebe, N., Kapoor, A. and Svore, K. M., (2015), Quantum algorithms for nearest- neighbor methods for supervised and unsupervised learning, Quantum Information & Computation, 15(3-4), pp. 316–356.
4. Wiebe, N., Kapoor, A. and Svore, K. M., (2016), Quantum deep learning, Quantum
5. Information & Computation, 16(7-8), pp. 541–587. A¨ımeur, E., Brassard, G. and Gambs, S., (2013), Quantum speed-up for unsupervised learning, Machine Learning, 90(2), pp. 261–287.
6. Lloyd, S., Garnerone, S. and Zanardi, P., (2016), Quantum algorithms for topological and geometric analysis of data, Nature communications, 7.
7. Lloyd, S., Mohseni, M. and Rebentrost, P., (2014), Quantum principal component analysis, Nature Physics, 10(9), pp. 631–633.
8. Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N. and Lloyd, S., (2017)

9. Quantum machine learning, Nature, 549(7671), p. 195.
10. Arunachalam, S. and de Wolf, R., (2017), A survey of quantum learning theory, arXiv preprint arXiv:1701.06806.
11. Schuld, M., Sinayskiy, I. and Petruccione, F., (2015), An introduction to quantum machine learning, Contemporary Physics, 56(2), pp. 172–185.
12. Kaufman, L. and Rousseeuw, P. J., (2009), Finding groups in data: an introduction to cluster analysis, volume 344, John Wiley & Sons.
13. Daskin, A., (2016), Obtaining a linear combination of the principal components of a matrix on quantum computers, Quantum Information Processing, 15(10), pp. 4013–
14. Daskin, A., (2018), A quantum implementation model for artificial neural networks, Quanta, 7, pp. 7–18.
15. MacQueen, J. et al., (1967), Some methods for classification and analysis of multivariate observations, in Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, Oakland, CA, USA., pp. 281–297.
16. Dhillon, I. S., Guan, Y. and Kulis, B., (2004), A unified view of kernel k-means, spec- tral clustering and graph cuts, Computer Science Department, University of Texas at Austin.
17. Lloyd, S., (1982), Least squares quantization in pcm, IEEE transactions on information theory, 28(2), pp. 129–137.
18. A¨ımeur, E., Brassard, G. and Gambs, S., (2007), Quantum clustering algorithms, in
19. Proceedings of the 24th international conference on machine learning, ACM, pp. 1–8. Grover, L. K., (1996), A fast quantum mechanical algorithm for database search, in
20. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM, pp. 212–219. Von Luxburg, U., (2007), A tutorial on spectral clustering, Statistics and computing, (4), pp. 395–416.
21. Shi, J. and Malik, J., (2000), Normalized cuts and image segmentation, IEEE Transac- tions on pattern analysis and machine intelligence, 22(8), pp. 888–905.
22. Ng, A. Y., Jordan, M. I., Weiss, Y. et al., (2002), On spectral clustering: Analysis and an algorithm, Advances in neural information processing systems, 2, pp. 849–856.
23. Zha, H., He, X., Ding, C., Gu, M. and Simon, H. D., (2001), Spectral relaxation for k-means clustering, in Advances in neural information processing systems, pp. 1057–
24. Ding, C. and He, X., (2004), K-means clustering via principal component analysis, in
25. Proceedings of the twenty-first international conference on Machine learning, ACM, p. 29. Jordan, F. and Bach, F., (2004), Learning spectral clustering, Adv. Neural Inf. Process. Syst, 16, pp. 305–312.
26. Kitaev, A., (1996), Quantum measurements and the abelian stabilizer problem, Elec- tronic Colloquium on Computational Complexity (ECCC), 3(3).
27. Nielsen, M. A. and Chuang, I. L., (2010), Quantum computation and quantum infor- mation, Cambridge university press.
28. Mosca, M. et al., (1998), Quantum searching, counting and amplitude amplification by eigenvector analysis, in MFCS98 workshop on Randomized Algorithms, pp. 90–100.
29. Brassard, G., Hoyer, P., Mosca, M. and Tapp, A., (2002), Quantum amplitude ampli- fication and estimation, Contemporary Mathematics, 305, pp. 53–74.
30. Berry, D., Ahokas, G., Cleve, R. and Sanders, B., (2007), Efficient quantum algorithms for simulating sparse hamiltonians, Communications in Mathematical Physics, 270(2), pp. 359–371.
31. Childs, A. M. and Kothari, R., (2011), Simulating sparse hamiltonians with star de- compositions, in Theory of Quantum Computation, Communication, and Cryptogra- phy, volume 6519 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, pp. 94–103.
32. Daskin, A. and Kais, S., (2018), Direct application of the phase estimation algorithm to find the eigenvalues of the hamiltonians, Chemical Physics, 514, pp. 87–94.
33. Farhi, E., Goldstone, J. and Gutmann, S., (2014), A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028.