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

Sawerwain, Marek; Wróblewski, Marek

doi:10.2478/amcs-2019-0011

Abstract

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.

References

Aaronson, S. and Gottesman, D. (2004). Improved simulation of stabilizer circuits, Physical Review A70(5): 052328, DOI: 10.1103/PhysRevA.70.052328.10.1103/PhysRevA.70.052328
Search in Google Scholar Back to article
Alpaydin, E. (2004). Introduction to Machine Learning (Adaptive Computation and Machine Learning), Massachusetts Institute of Technology Press, Cambridge, MA.
Search in Google Scholar Back to article
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.10.1109/ISIT.2003.1228418
Search in Google Scholar Back to article
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 Machinery53(4): 50–58, DOI: 10.1145/1721654.1721672.10.1145/1721654.1721672
Open DOI Search in Google Scholar Back to article
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 A52(5): 3457–3467, DOI: 10.1103/PhysRevA.52.3457.10.1103/PhysRevA.52.34579912645
Open DOI Search in Google Scholar Back to article
Biham, E., Biham, O., Biron, D., Grassl, M. and Lidar, D. (1999). Grover’s quantum search algorithm for an arbitrary initial amplitude distribution, Physical Review60(4): 2742–2745, DOI: 10.1103/PhysRevA.60.2742.10.1103/PhysRevA.60.2742
Open DOI Search in Google Scholar Back to article
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.10.1109/ISTCS.1997.595153
Open DOI Search in Google Scholar Back to article
Busemeyer, J. and Bruza, P. (2012). Quantum Models of Cognition and Decision, Cambridge University Press, Cambridge.10.1017/CBO9780511997716
Search in Google Scholar Back to article
Chakrabarty, I., Khan, S. and Singh, V. (2017). Dynamic grover search: Applications in recommendation systems and optimization problems, Quantum Information Processing16(6): 153, DOI: 10.1007/s11128-017-1600-4.10.1007/s11128-017-1600-4
Open DOI Search in Google Scholar Back to article
D’Hondt, E. and Panangaden, P. (2006). Quantum weakest preconditions, Mathematical Structures in Computer Science16(3): 429–451.10.1017/S0960129506005251
Search in Google Scholar Back to article
Galindo, A. and Martin-Delgado, M. A. (2000). A family of Grover’s quantum searching algorithms, Physical Review A62(6): 062303, DOI: 10.1103/PhysRevA.62.062303.10.1103/PhysRevA.62.062303
Search in Google Scholar Back to article
Galindo, A. and Martin-Delgado, M.A. (2002). Information and computation: Classical and quantum aspects, Reviews of Modern Physics74(2): 347–423, DOI: 10.1103/RevModPhys.74.347.10.1103/RevModPhys.74.347
Open DOI Search in Google Scholar Back to article
Gielerak, R. and Sawerwain, M. (2010). Generalised quantum weakest preconditions, Quantum Information Processing9(4): 441–449, DOI: 10.1007/s11128-009-0151-8.10.1007/s11128-009-0151-8
Open DOI Search in Google Scholar Back to article
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.10.1145/237814.237866
Open DOI Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
IBM (2018). Q Experience, https://quantumexperience.ng.bluemix.net/.
Search in Google Scholar Back to article
Li, C.-K., Roberts, R. and Yin, X. (2013). Decomposition of unitary matrices and quantum gates, International Journal of Quantum Information11(1): 1350015, DOI: 10.1142/S0219749913500159.10.1142/S0219749913500159
Search in Google Scholar Back to article
Montanaro, A. (2017). Quantum pattern matching fast on average, Alghoritmica: An International Journal in Computer Science77(1): 16–39, DOI: 10.1007/s00453-015-0060-4.10.1007/s00453-015-0060-4
Open DOI Search in Google Scholar Back to article
Nielsen, M. and Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press, Cambridge.10.1017/CBO9780511976667
Search in Google Scholar Back to article
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.10.1007/978-3-319-28555-9_1
Search in Google Scholar Back to article
OMDb (2018). Homepage, http://www.omdbapi.com/.
Search in Google Scholar Back to article
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.10.1109/CLEOE-IQEC.2013.6801621
Search in Google Scholar Back to article
Santucci, E. (2017). Quantum minimum distance classifier, Entropy19(12): 659, DOI: 10.3390/e19120659.10.3390/e19120659
Open DOI Search in Google Scholar Back to article
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.10.1007/978-3-319-99981-4_22
Search in Google Scholar Back to article
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.10.1007/978-3-319-13560-1_17
Search in Google Scholar Back to article
Sergioli, G., Bosyk, G.M., Santucci, E. and Giuntini, R. (2017). A quantum-inspired version of the classification problem, International Journal of Theoretical Physics56(12): 3880–3888, DOI: 10.1007/s10773-017-3371-1.10.1007/s10773-017-3371-1
Open DOI Search in Google Scholar Back to article
Sergioli, G., Santucci, E., Didaci, L., Miszczak, J.A. and Giuntini, R. (2018). A quantum-inspired version of the nearest mean classifier, Soft Computing22(3): 691–705, DOI: 10.1007/s00500-016-2478-2.10.1007/s00500-016-2478-2
Open DOI Search in Google Scholar Back to article
Shende, V. and Markov, I.L. (2009). On the CNOT-cost of TOFFOLI gates, Quantum Information & Computation9(5): 461–486.10.26421/QIC8.5-6-8
Search in Google Scholar Back to article
Shor, P. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review41(2): 303–332, DOI: 10.1137/S0036144598347011.10.1137/S0036144598347011
Open DOI Search in Google Scholar Back to article
Steane, A. (1998). Quantum computing, Reports on Progress in Physics61(2): 117–173, DOI: 10.1088/0034-4885/61/2/002.10.1088/0034-4885/61/2/002
Open DOI Search in Google Scholar Back to article
Stefanowski, J., Krawiec, K. and Wrembel, R. (2017). Exploring complex and big data, International Journal of Applied Mathematics and Computer Science27(4): 669–679, DOI: 10.1515/amcs-2017-0046.10.1515/amcs-2017-0046
Open DOI Search in Google Scholar Back to article
Trugenberger, C.A. (2002). Quantum pattern recognition, Quantum Information Processing1(6): 471–493, DOI: 10.1023/A:1024022632303.10.1023/A:1024022632303
Open DOI Search in Google Scholar Back to article
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 Science25(3): 513–527, DOI: 10.1515/amcs-2015-0038.10.1515/amcs-2015-0038
Open DOI Search in Google Scholar Back to article
Walther, P., Resch, K.J., Rudolph, T., Schenck, E., Weinfurter, H., Vedral, V., Aspelmeyer, M. and Zeilinger, A. (2005). Experimental one-way quantum computing, Nature434(0): 169–176, DOI: 10.1038/nature03347.10.1038/nature0334715758991
Search in Google Scholar Back to article
Wiebe, N., Kapoor, A. and Svore, K. (2015). Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning, Quantum Information and Computation15(3–4): 316–356.10.26421/QIC15.3-4-7
Search in Google Scholar Back to article
Wiśniewska, J. and Sawerwain, M. (2018). Recognizing the pattern of binary Hermitian matrices by quantum knn and SVM methods, Vietnam Journal of Computer Science5(3): 197–204, DOI: 10.1007/s40595-018-0115-y.10.1007/s40595-018-0115-y
Open DOI Search in Google Scholar Back to article

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

Abstract

Paradigm

My account