{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:33:40Z","timestamp":1773246820192,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,9,17]],"date-time":"2024-09-17T00:00:00Z","timestamp":1726531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,17]],"date-time":"2024-09-17T00:00:00Z","timestamp":1726531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Union Next-GenerationEU - National Recovery and Resilience Plan","award":["I53C22000690001"],"award-info":[{"award-number":["I53C22000690001"]}]},{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"publisher","award":["E53C22001930001"],"award-info":[{"award-number":["E53C22001930001"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Over the past few years, we observed a rethinking of classical artificial intelligence algorithms from a quantum computing perspective. This trend is driven by the peculiar properties of quantum mechanics, which offer the potential to enhance artificial intelligence capabilities, enabling it to surpass the constraints of classical computing. However, redesigning classical algorithms into their quantum equivalents is not straightforward and poses numerous challenges. In this study, we analyze in-depth two orthogonal designs of the quantum\n                    <jats:italic>K<\/jats:italic>\n                    -nearest neighbor classifier. In particular, we show two solutions based on amplitude encoding and basis encoding of data, respectively. These two types of encoding impact the overall structure of the respective algorithms, which employ different distance metrics and show different performances. By breaking down each quantum algorithm, we clarify and compare implementation aspects ranging from data preparation to classification. Eventually, we discuss the difficulties associated with data preparation, the theoretical advantage of quantum algorithms, and their impact on performance with respect to the classical counterpart.\n                  <\/jats:p>","DOI":"10.1007\/s42484-024-00197-6","type":"journal-article","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T09:22:04Z","timestamp":1726651324000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The role of encodings and distance metrics for the quantum nearest neighbor"],"prefix":"10.1007","volume":"6","author":[{"given":"Alessandro","family":"Berti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Bernasconi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianna M.","family":"Del Corso","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Guidotti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,17]]},"reference":[{"key":"197_CR1","unstructured":"Afham A, Basheer A, Goyal SK et\u00a0al (2020) Quantum k-nearest neighbor machine learning algorithm. arXiv preprint arXiv:2003.09187"},{"key":"197_CR2","doi-asserted-by":"publisher","first-page":"6329","DOI":"10.1038\/s41598-021-85474-1","volume":"11","author":"IF Araujo","year":"2021","unstructured":"Araujo IF, Park KD, Petruccione F, Silva AJ (2021) A divide-and-conquer algorithm for quantum state preparation. Sci Rep 11:6329","journal-title":"Sci Rep"},{"key":"197_CR3","doi-asserted-by":"publisher","unstructured":"Berti A (2023) Logarithmic quantum forking. In: Proceedings of ESANN, pp 251\u2013256. https:\/\/doi.org\/10.14428\/esann\/2023.ES2023-93","DOI":"10.14428\/esann\/2023.ES2023-93"},{"key":"197_CR4","doi-asserted-by":"crossref","unstructured":"Berti A, Bernasconi A, Del Corso GM, Guidotti R (2022) Effect of different encodings and distance functions on quantum instance-based classifiers. In: Gama J, Li T, Yu Y, Chen E, Zheng Y, Teng F (eds) Advances in knowledge discovery and data mining - 26th Pacific-Asia conference, PAKDD 2022, Chengdu, China, May 16-19, 2022, Proceedings, Part II. Lecture Notes in Computer Science, vol 13281, pp 96\u2013108. Springer, s.l","DOI":"10.1007\/978-3-031-05936-0_8"},{"key":"197_CR5","doi-asserted-by":"crossref","unstructured":"Brassard G, H\u00f8yer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. Quantum Comput Inf 53\u201374","DOI":"10.1090\/conm\/305\/05215"},{"issue":"9","key":"197_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s11128-018-2004-9","volume":"17","author":"Y Dang","year":"2018","unstructured":"Dang Y, Jiang N, Hu H, Ji Z, Zhang W (2018) Image classification based on quantum k-nearest-neighbor algorithm. Quantum Inf Proc 17(9):239","journal-title":"Quantum Inf Proc"},{"key":"197_CR7","doi-asserted-by":"crossref","unstructured":"Dougherty J, Kohavi R, Sahami M (1995) Supervised and unsupervised discretization of continuous features. In: ICML, pp 194\u2013202","DOI":"10.1016\/B978-1-55860-377-6.50032-3"},{"key":"197_CR8","unstructured":"Durr C, Hoyer P (1999) A quantum algorithm for finding the minimum. arXiv preprint arXiv:quant-ph\/9607014v2"},{"key":"197_CR9","doi-asserted-by":"crossref","unstructured":"Fan C, Li P (2020) Classification acceleration via merging decision trees. FODS \u201920: ACM-IMS Foundations of Data Science Conference, Virtual Event, USA, October 19\u201320, 2020. ACM, s.l, pp 13\u201322","DOI":"10.1145\/3412815.3416886"},{"issue":"4","key":"197_CR10","first-page":"917","volume":"33","author":"HI Fawaz","year":"2019","unstructured":"Fawaz HI, Forestier G, Weber J, Idoumghar L, Muller P-A (2019) Deep learning for time series classification: a review. DAMI 33(4):917\u2013963","journal-title":"DAMI"},{"issue":"16","key":"197_CR11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti V, Lloyd S, Maccone L (2008) Quantum random access memory. Phys Rev Lett 100(16):160501","journal-title":"Phys Rev Lett"},{"key":"197_CR12","unstructured":"Kaye P (2004) Reversible addition circuit using one ancillary bit with application to quantum computing. arXiv, 0408173"},{"key":"197_CR13","unstructured":"Kerenidis I, Prakash A (2016) Quantum recommendation systems. arXiv preprint arXiv:1603.08675"},{"key":"197_CR14","unstructured":"Kerenidis I, Prakash A (2017) Quantum recommendation systems. In: Papadimitriou CH (ed.) 8th Innovations in theoretical computer science conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA. LIPIcs, vol 67, pp 49\u201314921. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, s.l"},{"key":"197_CR15","doi-asserted-by":"crossref","unstructured":"Leskovec J, Rajaraman A, Ullman JD (2014) Mining of massive datasets, 2nd edn. Cambridge University Press, s.l","DOI":"10.1017\/CBO9781139924801"},{"key":"197_CR16","doi-asserted-by":"crossref","unstructured":"Li J, Lin S, Kai Y, Guo G (2021) Quantum k-nearest neighbor classification algorithm based on Hamming distance. arXiv preprint arXiv:2103.04253","DOI":"10.1007\/s11128-021-03361-0"},{"key":"197_CR17","unstructured":"Lloyd S, Mohseni M, Rebentrost P (2013) Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411"},{"key":"197_CR18","doi-asserted-by":"crossref","unstructured":"Long GL, Sun Y (2001) Efficient scheme for initializing a quantum register with an arbitrary superposed state. Phys Rev A 64:014303","DOI":"10.1103\/PhysRevA.64.014303"},{"key":"197_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to information retrieval","author":"CD Manning","year":"2008","unstructured":"Manning CD, Raghavan P, Sch\u00fctze H (2008) Introduction to information retrieval. Cambridge University Press, s.l"},{"key":"197_CR20","first-page":"467","volume":"5","author":"M M\u00f6tt\u00f6nen","year":"2005","unstructured":"M\u00f6tt\u00f6nen M, Vartiainen JJ, Bergholm V, Salomaa MM (2005) Transformation of quantum states using uniformly controlled rotations. Quantum Inf. Com. 5:467\u2013473","journal-title":"Quantum Inf. Com."},{"key":"197_CR21","volume-title":"Quantum computation and quantum information (10th","author":"MA Nielsen","year":"2016","unstructured":"Nielsen MA, Chuang IL (2016) Quantum computation and quantum information (10th. Cambridge University Press, s.l, Anniversary"},{"issue":"6","key":"197_CR22","doi-asserted-by":"publisher","first-page":"2412","DOI":"10.1021\/ci060149f","volume":"46","author":"F Nigsch","year":"2006","unstructured":"Nigsch F, Bender A, Buuren B, Tissen J, Nigsch E, Mitchell JBO (2006) Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization. J Chem Inf Model 46(6):2412\u20132422","journal-title":"J Chem Inf Model"},{"issue":"1","key":"197_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41598-018-37186-2","volume":"9","author":"DK Park","year":"2019","unstructured":"Park DK, Petruccione F, Rhee J-KK (2019) Circuit-based quantum random access memory for classical data. Sci Rep 9(1):1\u20138","journal-title":"Sci Rep"},{"key":"197_CR24","doi-asserted-by":"crossref","unstructured":"Phalak K, Chatterjee A, Ghosh S (2023) Quantum random access memory for dummies","DOI":"10.3390\/s23177462"},{"key":"197_CR25","doi-asserted-by":"crossref","unstructured":"Ramaswamy S, Rastogi R, Shim K (2000) Efficient algorithms for mining outliers from large data sets. SIGMOD Conference. ACM, s.l, pp 427\u2013438","DOI":"10.1145\/335191.335437"},{"issue":"11","key":"197_CR26","doi-asserted-by":"publisher","first-page":"3496","DOI":"10.1007\/s10773-017-3514-4","volume":"56","author":"Y Ruan","year":"2017","unstructured":"Ruan Y, Xue X, Liu H, Tan J, Li X (2017) Quantum algorithm for k-nearest neighbors classification based on the metric of Hamming distance. Int J Theor Phys 56(11):3496\u20133507","journal-title":"Int J Theor Phys"},{"key":"197_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96424-9","volume-title":"Supervised learning with quantum computers","author":"M Schuld","year":"2018","unstructured":"Schuld M, Petruccione F (2018) Supervised learning with quantum computers. Springer, s.l"},{"issue":"6","key":"197_CR28","doi-asserted-by":"publisher","first-page":"60002","DOI":"10.1209\/0295-5075\/119\/60002","volume":"119","author":"M Schuld","year":"2017","unstructured":"Schuld M, Fingerhuth M, Petruccione F (2017) Implementing a distance-based classifier with a quantum interference circuit. EPL (Europhysics Let.) 119(6):60002","journal-title":"EPL (Europhysics Let.)"},{"key":"197_CR29","doi-asserted-by":"crossref","unstructured":"Schuld M, Sinayskiy I, Petruccione F (2014) Quantum computing for pattern classification. In: PRICAI. LNCS, vol 8862, pp 208\u2013220. Springer, s.l","DOI":"10.1007\/978-3-319-13560-1_17"},{"key":"197_CR30","doi-asserted-by":"crossref","unstructured":"Shende VV, Markov IL, Bullock SS (2004) Minimal universal two-qubit controlled not-based circuits. Phys Rev A 69","DOI":"10.1103\/PhysRevA.69.062321"},{"key":"197_CR31","doi-asserted-by":"crossref","unstructured":"Shende VV, Bullock SS, Markov IL (2006) Synthesis of quantum-logic circuits. IEEE Trans Com Aided Des Int Cir Syst 25(6):1000\u20131010","DOI":"10.1109\/TCAD.2005.855930"},{"key":"197_CR32","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.012307","volume":"73","author":"AN Soklakov","year":"2006","unstructured":"Soklakov AN, Schack R (2006) Efficient state preparation for a register of quantum bits. Phys Rev A 73:012307","journal-title":"Phys Rev A"},{"key":"197_CR33","volume-title":"Introduction to data mining","author":"P Tan","year":"2005","unstructured":"Tan P, Steinbach MS, Kumar V (2005) Introduction to data mining. Addison-Wesley, s.l"},{"issue":"1\u20134","key":"197_CR34","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/S0020-0255(99)00101-2","volume":"124","author":"D Ventura","year":"2000","unstructured":"Ventura D, Martinez TR (2000) Quantum associative memory. Inf Sci 124(1\u20134):273\u2013296","journal-title":"Inf Sci"},{"key":"197_CR35","unstructured":"Wiebe N, Kapoor A, Svore KM (2018) Quantum nearest-neighbor algorithms for machine learning. Quantum Inf Comput 15"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00197-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-024-00197-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00197-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T11:10:06Z","timestamp":1734952206000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-024-00197-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,17]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["197"],"URL":"https:\/\/doi.org\/10.1007\/s42484-024-00197-6","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3687812\/v1","asserted-by":"object"}]},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,17]]},"assertion":[{"value":"30 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"62"}}