Recommendation systems with the quantum k-NN and Grover algorithms for data processing

Sawerwain, Marek ; Wróblewski, Marek

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 1, pp. 139-150.

Résumé

In this article, we discuss the implementation of a quantum recommendation system that uses a quantum variant of the k-nearest neighbours algorithm and the Grover algorithm to search for a specific element in an unstructured database. In addition to the presentation of the recommendation system as an algorithm, the article also shows the main steps in construction of a suitable quantum circuit for realisation of a given recommendation system. The computational complexity of individual calculation steps in the recommendation system is also indicated. The verification of the correctness of the proposed system is analysed as well, indicating an algebraic equation describing the probability of success of the recommendation. The article also shows numerical examples presenting the behaviour of the recommendation system for two selected cases.

Détail

Keywords: quantum k-NN algorithm, recommendation system, Grover algorithm, big data
Mots-clés : kwantowy algorytm k-NN, system rekomendujący, algorytm Grovera, duży zbiór danych

Bibliographie

[1] Aaronson, S. and Gottesman, D. (2004). Improved simulation of stabilizer circuits, Physical Review A 70(5): 052328, DOI: 10.1103/PhysRevA.70.052328.

[2] Alpaydin, E. (2004). Introduction to Machine Learning (Adaptive Computation and Machine Learning), Massachusetts Institute of Technology Press, Cambridge, MA.

[3] Arikan, E. (2003). An information-theoretic analysis of Grover’s algorithm, in A.S. Shumovsky and V.I. Rupasov (Eds.), Quantum Communication and Information Technologies, Springer Netherlands, Dordrecht, pp. 339–347.

[4] Armbrust, M., Fox, A., Griffith, R., Joseph, A.D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I. and Zaharia, M. (2010). A view of cloud computing, Communications of the Association for Computing Machinery 53(4): 50–58, DOI: 10.1145/1721654.1721672.

[5] Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A. and Weinfurter, H. (1995). Elementary gates for quantum computation, Physical Review A 52(5): 3457–3467, DOI: 10.1103/PhysRevA.52.3457.

[6] Biham, E., Biham, O., Biron, D., Grassl, M. and Lidar, D. (1999). Grover’s quantum search algorithm for an arbitrary initial amplitude distribution, Physical Review 60(4): 2742–2745, DOI: 10.1103/PhysRevA.60.2742.

[7] Brassard, G. and Hoyer, P. (1997). An exact quantum polynomial-time algorithm for Simon’s problem, Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, Ramat Gan, Israel, DOI: 10.1109/ISTCS.1997.595153.

[8] Busemeyer, J. and Bruza, P. (2012). Quantum Models of Cognition and Decision, Cambridge University Press, Cambridge.

[9] Chakrabarty, I., Khan, S. and Singh, V. (2017). Dynamic grover search: Applications in recommendation systems and optimization problems, Quantum Information Processing 16(6): 153, DOI: 10.1007/s11128-017-1600-4.

[10] D’Hondt, E. and Panangaden, P. (2006). Quantum weakest preconditions, Mathematical Structures in Computer Science 16(3): 429–451.

[11] Galindo, A. and Martin-Delgado, M. A. (2000). A family of Grover’s quantum searching algorithms, Physical Review A 62(6): 062303, DOI: 10.1103/PhysRevA.62.062303.

[12] Galindo, A. and Martin-Delgado, M.A. (2002). Information and computation: Classical and quantum aspects, Reviews of Modern Physics 74(2): 347–423, DOI: 10.1103/RevModPhys.74.347.

[13] Gielerak, R. and Sawerwain, M. (2010). Generalised quantum weakest preconditions, Quantum Information Processing 9(4): 441–449, DOI: 10.1007/s11128-009-0151-8.

[14] Grover, L.K. (1996). A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC’96, Philadelphia, PA, USA, pp. 212–219, DOI: 10.1145/237814.237866.

[15] Hechenbichler, K. and Schliep, K. (2004). Weighted k-nearest-neighbor techniques and ordinal classification, Technical report, Ludwig-Maximilians-Universität München, München, https://epub.ub.uni-muenchen.de/1769/1/paper_399.pdf.

[16] IBM (2018). Q Experience, https://quantumexperience.ng.bluemix.net/.

[17] Li, C.-K., Roberts, R. and Yin, X. (2013). Decomposition of unitary matrices and quantum gates, International Journal of Quantum Information 11(1): 1350015, DOI: 10.1142/S0219749913500159.

[18] Montanaro, A. (2017). Quantum pattern matching fast on average, Alghoritmica: An International Journal in Computer Science 77(1): 16–39, DOI: 10.1007/s00453-015-0060-4.

[19] Nielsen, M. and Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press, Cambridge.

[20] Nielsen, P. (2016). Big data analytics—a brief research synthesis, in L. Borzemski et al. (Eds.), Information Systems Architecture and Technology, Springer International Publishing, Cham, pp. 3–9.

[21] OMDb (2018). Homepage, http://www.omdbapi.com/.

[22] Pinkse, P., Goorden, S., Horstmann, M., Skoric, B. and Mosk, A. (2013). Quantum pattern recognition, Conference on Lasers and Electro-Optics Europe (CLEO EUROPE/IQEC) and International Quantum Electronics Conference, Munich, Germany, p. 1–1.

[23] Santucci, E. (2017). Quantum minimum distance classifier, Entropy 19(12): 659, DOI: 10.3390/e19120659.

[24] Sawerwain, M. and Wróblewski, M. (2019). Application of quantum k-nn and Grover’s algorithms for recommendation big-data system, in L. Borzemski et al. (Eds.), Information Systems Architecture and Technology, Springer International Publishing, Cham, pp. 235–244.

[25] Schuld, M., Sinayskiy, I. and Petruccione, F. (2014). Quantum computing for pattern classification, in D.-N. Pham and S.-B. Park (Eds.), PRICAI 2014: Trends in Artificial Intelligence, Springer International Publishing, Cham, pp. 208–220.

[26] Sergioli, G., Bosyk, G.M., Santucci, E. and Giuntini, R. (2017). A quantum-inspired version of the classification problem, International Journal of Theoretical Physics 56(12): 3880–3888, DOI: 10.1007/s10773-017-3371-1.

[27] Sergioli, G., Santucci, E., Didaci, L., Miszczak, J.A. and Giuntini, R. (2018). A quantum-inspired version of the nearest mean classifier, Soft Computing 22(3): 691–705, DOI: 10.1007/s00500-016-2478-2.

[28] Shende, V. and Markov, I.L. (2009). On the CNOT-cost of TOFFOLI gates, Quantum Information Computation 9(5): 461–486.

[29] Shor, P. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review 41(2): 303–332, DOI: 10.1137/S0036144598347011.

[30] Steane, A. (1998). Quantum computing, Reports on Progress in Physics 61(2): 117–173, DOI: 10.1088/0034-4885/61/2/002.

[31] Stefanowski, J., Krawiec, K. and Wrembel, R. (2017). Exploring complex and big data, International Journal of Applied Mathematics and Computer Science 27(4): 669–679, DOI: 10.1515/amcs-2017-0046.

[32] Trugenberger, C.A. (2002). Quantum pattern recognition, Quantum Information Processing 1(6): 471–493, DOI: 10.1023/A:1024022632303.

[33] Veloso, B., Malheiro, B. and Burguillo, J.C. (2015). A multi-agent brokerage platform for media content recommendation, International Journal of Applied Mathematics and Computer Science 25(3): 513–527, DOI: 10.1515/amcs-2015-0038.

[34] Walther, P., Resch, K.J., Rudolph, T., Schenck, E., Weinfurter, H., Vedral, V., Aspelmeyer, M. and Zeilinger, A. (2005). Experimental one-way quantum computing, Nature 434(0): 169–176, DOI: 10.1038/nature03347.

[35] Wiebe, N., Kapoor, A. and Svore, K. (2015). Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning, Quantum Information and Computation 15(3–4): 316–356.

[36] Wiśniewska, J. and Sawerwain, M. (2018). Recognizing the pattern of binary Hermitian matrices by quantum knn and SVM methods, Vietnam Journal of Computer Science 5(3): 197–204, DOI: 10.1007/s40595-018-0115-y.