{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:28:48Z","timestamp":1769729328763,"version":"3.49.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T00:00:00Z","timestamp":1675209600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T00:00:00Z","timestamp":1675209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005765","name":"Universidade de Lisboa","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005765","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Clustering algorithms are of fundamental importance when dealing with large unstructured datasets and discovering new patterns and correlations therein, with applications ranging from scientific research to medical imaging and marketing analysis. In this work, we introduce a quantum version of the density peak clustering algorithm, built upon a quantum routine for minimum finding. We prove a quantum speedup for a decision version of density peak clustering depending on the structure of the dataset. Specifically, the speedup is dependent on the heights of the trees of the induced graph of nearest-highers, i.e. the graph of connections to the nearest elements with higher density. We discuss this condition, showing that our algorithm is particularly suitable for high-dimensional datasets. Finally, we benchmark our proposal with a toy problem on a real quantum device.<\/jats:p>","DOI":"10.1007\/s42484-022-00090-0","type":"journal-article","created":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T21:40:20Z","timestamp":1675287620000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Quantum density peak clustering"],"prefix":"10.1007","volume":"5","author":[{"given":"Duarte","family":"Magano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorenzo","family":"Buffoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasser","family":"Omar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,2,1]]},"reference":[{"key":"90_CR1","unstructured":"Adcock J., Allen E., Day M., Frick S., Hinchliff J., Johnson M., Morley-Short S., Pallister S., Price A., Stanisic S. (2015) Advances in quantum machine learning. arXiv:1512.02900, [quant-ph]"},{"key":"90_CR2","doi-asserted-by":"publisher","unstructured":"A\u00efmeur E., Brassard G., Gambs S. (2007). In: ACM International Conference Proceeding Series, vol 227, (1). https:\/\/doi.org\/10.1145\/1273496.1273497https:\/\/doi.org\/10.1145\/1273496.1273497","DOI":"10.1145\/1273496.1273497 10.1145\/1273496.1273497"},{"key":"90_CR3","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10994-012-5316-5","volume":"90","author":"E A\u00efmeur","year":"2013","unstructured":"A\u00efmeur E., Brassard G., Gambs S. (2013) . Mach Learn 90:261. https:\/\/doi.org\/10.1007\/s10994-012-5316-5","journal-title":"Mach Learn"},{"key":"90_CR4","unstructured":"Ambainis A. (2017) Understanding quantum algorithms via query complexity. arXiv:1712.06349 [quant-ph]"},{"key":"90_CR5","unstructured":"Arunachalam S., de Wolf R. (2017) . arXiv:1701.06806, [quant-ph]"},{"key":"90_CR6","unstructured":"Bauckhage C., Brito E., Cvejoski K., Ojeda C., Sifa R., Wrobel S. (2017) Adiabatic quantum computing for binary clustering. arXiv:1706.05528 [quant-ph]"},{"key":"90_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1038\/nature23474","volume":"549","author":"J Biamonte","year":"2017","unstructured":"Biamonte J., Wittek P., Pancotti N., Rebentrost P., Wiebe N., Lloyd S. (2017) . Nature 549:195. https:\/\/doi.org\/10.1038\/nature23474","journal-title":"Nature"},{"key":"90_CR8","volume-title":"Pattern recognition and machine learning","author":"CM Bishop","year":"2011","unstructured":"Bishop CM (2011) Pattern recognition and machine learning, 1st ed. Springer, New York","edition":"1st ed."},{"key":"90_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0168-1699(99)00046-0","volume":"24","author":"J Blackard","year":"1999","unstructured":"Blackard J., Dean D. (1999) . Comput Electron Agric 24:131. https:\/\/doi.org\/10.1016\/S0168-1699(99)00046-0","journal-title":"Comput Electron Agric"},{"key":"90_CR10","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M Boyer","year":"1998","unstructured":"Boyer M., Brassard G., H\u00d8yer P., Tapp A. (1998) . Fortschr Phys 46:493","journal-title":"Fortschr Phys"},{"key":"90_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/CCDC.2019.8833427","volume":"17","author":"S Cheng","year":"2016","unstructured":"Cheng S., Quan T., Liu X., Zeng S. (2016) . BMC bioinformatics 17:1. https:\/\/doi.org\/10.1109\/CCDC.2019.8833427","journal-title":"BMC bioinformatics"},{"key":"90_CR12","unstructured":"Daskin A. (2017) Quantum spectral clustering through a biased phase estimation algorithm. arXiv:1703.05568 [quant-ph]"},{"key":"90_CR13","unstructured":"Durr C., Hoyer P. (1996) A quantum algorithm for finding the minimum. arXiv:quant-ph\/9607014"},{"key":"90_CR14","doi-asserted-by":"publisher","first-page":"107452","DOI":"10.1016\/j.patcog.2020.107452","volume":"107","author":"F Fang","year":"2020","unstructured":"Fang F., Qiu L., Yuan S. (2020) . Pattern Recogn. 107:107452","journal-title":"Pattern Recogn."},{"key":"90_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-017-01904-7","volume":"8","author":"C Figgatt","year":"2017","unstructured":"Figgatt C., Maslov D., Landsman K.A., Linke N.M., Debnath S., Monroe C. (2017) . Nature communications 8:1. https:\/\/doi.org\/10.1038\/s41467-017-01904-7https:\/\/doi.org\/10.1038\/s41467-017-01904-7","journal-title":"Nature communications"},{"key":"90_CR16","doi-asserted-by":"publisher","first-page":"160501","DOI":"10.1103\/PhysRevLett.100.160501","volume":"100","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti V., Lloyd S., Maccone L. (2008) . Phys Rev Lett 100:160501. https:\/\/doi.org\/10.1103\/PhysRevLett.100.160501","journal-title":"Phys Rev Lett"},{"key":"90_CR17","doi-asserted-by":"publisher","first-page":"052310","DOI":"10.1103\/PhysRevA.78.052310","volume":"78","author":"V Giovannetti","year":"2008","unstructured":"Giovannetti V., Lloyd S., Maccone L. (2008) . Phys Rev A 78:052310. https:\/\/doi.org\/10.1103\/PhysRevA.78.052310","journal-title":"Phys Rev A"},{"key":"90_CR18","volume-title":"Deep learning","author":"I Goodfellow","year":"2016","unstructured":"Goodfellow I., Bengio Y., Courville A. (2016) Deep learning. MIT Press, Cambridge. http:\/\/www.deeplearningbook.org"},{"key":"90_CR19","doi-asserted-by":"publisher","unstructured":"Graves A., Mohamed A.R., Hinton G. (2013) .. In: 2013 IEEE international conference on acoustics, speech and signal processing pp. 6645. https:\/\/doi.org\/10.1109\/ICASSP.2013.6638947","DOI":"10.1109\/ICASSP.2013.6638947"},{"key":"90_CR20","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"L Grover","year":"1997","unstructured":"Grover L. (1997) . Phys. Rev. Lett. 79:325. https:\/\/doi.org\/10.1103\/PhysRevLett.79.325https:\/\/doi.org\/10.1103\/PhysRevLett.79.325","journal-title":"Phys. Rev. Lett."},{"key":"90_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7","volume-title":"The elements of statistical learning","author":"T Hastie","year":"2009","unstructured":"Hastie T., Tibshirani R., Friedman J. (2009) The elements of statistical learning. Data Mining, Inference, and Prediction, Springer Science & Business Media"},{"key":"90_CR22","doi-asserted-by":"publisher","unstructured":"Hinton G.E., Dayan P., Frey B.J., Neal R.M. (1995) . https:\/\/doi.org\/10.1126\/science.7761831","DOI":"10.1126\/science.7761831"},{"key":"90_CR23","doi-asserted-by":"publisher","first-page":"042415","DOI":"10.1103\/PhysRevA.103.042415","volume":"103","author":"I Kerenidis","year":"2021","unstructured":"Kerenidis I., Landman J. (2021) . Phys. Rev. A 103:042415. https:\/\/doi.org\/10.1103\/PhysRevA.103.042415https:\/\/doi.org\/10.1103\/PhysRevA.103.042415","journal-title":"Phys. Rev. A"},{"key":"90_CR24","doi-asserted-by":"publisher","unstructured":"Kerenidis I., Landman J., Luongo A., Prakash A. (2019). In: Proceedings of the 33rd international conference on neural information processing systems vol 372 https:\/\/doi.org\/10.5555\/3454287.3454659https:\/\/doi.org\/10.5555\/3454287.3454659","DOI":"10.5555\/3454287.3454659 10.5555\/3454287.3454659"},{"key":"90_CR25","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s11128-010-0169-y","volume":"10","author":"Q Li","year":"2011","unstructured":"Li Q., He Y., Jiang J.P. (2011) . Quantum Inf Process 10:13. https:\/\/doi.org\/10.1007\/s11128-010-0169-y","journal-title":"Quantum Inf Process"},{"key":"90_CR26","doi-asserted-by":"crossref","unstructured":"Li J., Kais S. (2021) Quantum cluster algorithm for data classification, arXiv:2106.07078 [quant-ph]","DOI":"10.1186\/s41313-021-00029-1"},{"key":"90_CR27","unstructured":"Lloyd S., Mohseni M., Rebentrost P. (2013) Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411v2 [quant-ph]"},{"key":"90_CR28","doi-asserted-by":"publisher","unstructured":"Lloyd S., Mohseni M., Rebentrost P. (2014) Nature Physics. https:\/\/doi.org\/10.1038\/nphys3029","DOI":"10.1038\/nphys3029"},{"key":"90_CR29","unstructured":"Lloyd S., Schuld M., Ijaz A., Izaac J., Killoran N. (2020) . arXiv:2001.03622, [quanth-ph]"},{"key":"90_CR30","doi-asserted-by":"publisher","unstructured":"M.S.A.et al (2021) Qiskit: an open-source framework for quantum computing. https:\/\/doi.org\/10.5281\/zenodo.2573505","DOI":"10.5281\/zenodo.2573505"},{"key":"90_CR31","unstructured":"MacQueen J., et.al (1967) .. In: Proceedings of the fifth berkeley symposium on mathematical statistics and probability Vol 1 organization Oakland, CA, USA, pp 281-297"},{"key":"90_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TQE.2020.2965803","volume":"1","author":"OD Matteo","year":"2020","unstructured":"Matteo O.D., Gheorghiu V., Mosca M. (2020) . IEEE Transactions on Quantum Engineering 1:1\u201313. https:\/\/doi.org\/10.1109\/TQE.2020.2965803https:\/\/doi.org\/10.1109\/TQE.2020.2965803","journal-title":"IEEE Transactions on Quantum Engineering"},{"key":"90_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667 10.1017\/CBO9780511976667","volume-title":".","author":"M Nielsen","year":"2010","unstructured":"Nielsen M., Chuang I. (2010) . Quantum computation and quantum information, Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511976667https:\/\/doi.org\/10.1017\/CBO9780511976667"},{"key":"90_CR34","unstructured":"Otterbach J., Manenti R., Alidoust N., Bestwick A., Block M., Bloom B., Caldwell S., Didier N., Fried E. S., Hong S., et.al (2017) Unsupervised machine learning on a hybrid quantum computer. arXiv:1712.05771 [quant-ph]"},{"key":"90_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-019-40439-3","volume":"9","author":"DK Park","year":"2019","unstructured":"Park D.K., Petruccione F., Rhee J.K.K. (2019) . Sci Rep 9:1\u20138. https:\/\/doi.org\/10.1038\/s41598-019-40439-3","journal-title":"Sci Rep"},{"key":"90_CR36","unstructured":"Pires D., Bargassa P., Omar Y., Seixas J. (2021) A digital quantum algorithm for jet clustering in high-energy physics, arXiv:2101.05618 [quant-ph]"},{"key":"90_CR37","doi-asserted-by":"publisher","first-page":"1492","DOI":"10.1126\/science.1242072","volume":"344","author":"A Rodriguez","year":"2014","unstructured":"Rodriguez A., Laio A. (2014) . Science 344:1492. https:\/\/doi.org\/10.1126\/science.1242072https:\/\/doi.org\/10.1126\/science.1242072","journal-title":"Science"},{"key":"90_CR38","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s11128-014-0809-8","volume":"56","author":"M Schuld","year":"2015","unstructured":"Schuld M., Sinayskiy I., Petruccione F. (2015) . Contemp Phys 56:172. https:\/\/doi.org\/10.1007\/s11128-014-0809-8","journal-title":"Contemp Phys"},{"key":"90_CR39","volume-title":".","author":"N Sebe","year":"2005","unstructured":"Sebe N., Cohen I., Garg A., Huang T. S. (2005) . Machine learning in computer vision Vol 29, Springer Science & Business Media"},{"key":"90_CR40","unstructured":"Shi W., Lu N., Jiang B., Zhi Y., Xu Z. (2019). In: 2019 Chinese control and decision conference (CCDC) organization IEEE. pp 1954\u20131959"},{"key":"90_CR41","volume-title":"Reinforcement learning","author":"RS Sutton","year":"2018","unstructured":"Sutton R.S., Barto A.G. (2018) Reinforcement learning. An introduction MIT Press, Cambridge"},{"key":"90_CR42","doi-asserted-by":"publisher","unstructured":"Tieleman T. (2008) .. In: Inproceedings of the 25th international conference on machine learning organization ACM pp. 1064\u20131071. https:\/\/doi.org\/10.1145\/1390156.1390290","DOI":"10.1145\/1390156.1390290"},{"key":"90_CR43","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.patrec.2019.11.022","volume":"129","author":"B Tu","year":"2020","unstructured":"Tu B., Yang X., Li N., Zhou C., He D. (2020) . Pattern Recogn Lett 129:144. https:\/\/doi.org\/10.1016\/j.patrec.2019.11.022","journal-title":"Pattern Recogn Lett"},{"key":"90_CR44","doi-asserted-by":"publisher","first-page":"5085","DOI":"10.1109\/TGRS.2019.2896471","volume":"57","author":"B Tu","year":"2019","unstructured":"Tu B., Zhang X., Kang X., Wang J., Benediktsson J.A. (2019) . IEEE Trans Geosci Remote Sens 57:5085. https:\/\/doi.org\/10.1109\/TGRS.2019.2896471https:\/\/doi.org\/10.1109\/TGRS.2019.2896471","journal-title":"IEEE Trans Geosci Remote Sens"},{"key":"90_CR45","doi-asserted-by":"publisher","unstructured":"Vincent P., Larochelle H., Bengio Y., Manzagol P.A. (2008) Proceedings of the 25th international conference on Machine learning organization ACM pp. 1096\u20131103. https:\/\/doi.org\/10.1145\/1390156.1390294https:\/\/doi.org\/10.1145\/1390156.1390294","DOI":"10.1145\/1390156.1390294 10.1145\/1390156.1390294"},{"key":"90_CR46","doi-asserted-by":"publisher","unstructured":"Vinci W., Buffoni L., Sadeghi H., Khoshaman A., Andriyash E., Amin M. (2020) Machine learning: science and technology. https:\/\/doi.org\/10.1088\/2632-2153\/aba220","DOI":"10.1088\/2632-2153\/aba220"},{"key":"90_CR47","doi-asserted-by":"publisher","first-page":"050505","DOI":"10.1103\/PhysRevLett.109.050505","volume":"109","author":"N Wiebe","year":"2012","unstructured":"Wiebe N., Braun D., Lloyd S. (2012) . Physical review letters 109:050505. https:\/\/doi.org\/10.1103\/PhysRevLett.109.050505","journal-title":"Physical review letters"},{"key":"90_CR48","volume-title":"Quantum machine learning: what quantum computing means to data mining","author":"P Wittek","year":"2014","unstructured":"Wittek P. (2014) Quantum machine learning: what quantum computing means to data mining. Academic Press, New York"},{"key":"90_CR49","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1007\/s00500-009-0478-1","volume":"14","author":"Y Yu","year":"2010","unstructured":"Yu Y., Qian F., Liu H. (2010) . Soft. Comput. 14:921","journal-title":"Soft. Comput."},{"key":"90_CR50","first-page":"2579","volume":"9","author":"L van der Maaten","year":"2008","unstructured":"van der Maaten L., Hinton G. (2008) . J. Mach. Learn. Res. 9:2579","journal-title":"J. Mach. Learn. Res."}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-022-00090-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-022-00090-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-022-00090-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,19]],"date-time":"2023-06-19T07:28:49Z","timestamp":1687159729000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-022-00090-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,1]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["90"],"URL":"https:\/\/doi.org\/10.1007\/s42484-022-00090-0","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,1]]},"assertion":[{"value":"22 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This work does not involve human participants and presents no ethical concerns.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Consent for publication"}},{"value":"The authors declare no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Competing interests"}}],"article-number":"9"}}