{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T23:32:06Z","timestamp":1769729526890,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s42484-024-00185-w","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T10:18:04Z","timestamp":1728382684000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Boost clustering with Gaussian Boson Sampling: a quantum-classical hybrid approach"],"prefix":"10.1007","volume":"6","author":[{"given":"Nicol\u00f2","family":"Bonaldi","sequence":"first","affiliation":[]},{"given":"Martina","family":"Rossi","sequence":"additional","affiliation":[]},{"given":"Daniele","family":"Mattioli","sequence":"additional","affiliation":[]},{"given":"Michele","family":"Grapulin","sequence":"additional","affiliation":[]},{"given":"Blanca Silva","family":"Fern\u00e1ndez","sequence":"additional","affiliation":[]},{"given":"Davide","family":"Caputo","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Magagnini","sequence":"additional","affiliation":[]},{"given":"Arianna","family":"Osti","sequence":"additional","affiliation":[]},{"given":"Fabio","family":"Veronese","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"185_CR1","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.ejc.2014.11.001","volume":"45","author":"M Aaghabali","year":"2015","unstructured":"Aaghabali M, Akbari S, Friedland S, Markstr\u00f6m K, Tajfirouz Z (2015) Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges. Eur J Comb (Print) 45:132\u2013144. https:\/\/doi.org\/10.1016\/j.ejc.2014.11.001","journal-title":"Eur J Comb (Print)"},{"key":"185_CR2","doi-asserted-by":"publisher","unstructured":"Aaronson S, Arkhipov A (2011) The computational complexity of linear optics. In: Proceedings of the forty-third annual ACM Symposium on theory of computing. STOC \u201911, pp 333\u2013342. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/1993636.1993682","DOI":"10.1145\/1993636.1993682"},{"key":"185_CR3","doi-asserted-by":"publisher","unstructured":"Albash T, Lidar DA (2018) Adiabatic quantum computation. Rev Mod Phys 90(1):015002. https:\/\/doi.org\/10.1103\/RevModPhys.90.015002. Publisher: American Physical Society","DOI":"10.1103\/RevModPhys.90.015002"},{"issue":"3","key":"185_CR4","doi-asserted-by":"publisher","first-page":"030503","DOI":"10.1103\/PhysRevLett.121.030503","volume":"121","author":"JM Arrazola","year":"2018","unstructured":"Arrazola JM, Bromley TR (2018) Using Gaussian Boson sampling to find dense subgraphs. Phys Rev Lett 121(3):030503. https:\/\/doi.org\/10.1103\/PhysRevLett.121.030503","journal-title":"Phys Rev Lett"},{"key":"185_CR5","doi-asserted-by":"publisher","unstructured":"Barvinok A (2016) Combinatorics and complexity of partition functions. Algorithms and combinatorics, vol 30. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-51829-9","DOI":"10.1007\/978-3-319-51829-9"},{"issue":"3","key":"185_CR6","doi-asserted-by":"publisher","first-page":"032310","DOI":"10.1103\/PhysRevA.98.032310","volume":"98","author":"K Br\u00e1dler","year":"2018","unstructured":"Br\u00e1dler K, Dallaire-Demers P-L, Rebentrost P, Su D, Weedbrook C (2018) Gaussian Boson Sampling for perfect matchings of arbitrary graphs. Phys Rev A 98(3):032310. https:\/\/doi.org\/10.1103\/PhysRevA.98.032310","journal-title":"Phys Rev A"},{"issue":"3","key":"185_CR7","doi-asserted-by":"publisher","first-page":"034010","DOI":"10.1088\/2058-9565\/ab8504","volume":"5","author":"TR Bromley","year":"2020","unstructured":"Bromley TR, Arrazola JM, Jahangiri S, Izaac J, Quesada N, Gran AD, Schuld M, Swinarton J, Zabaneh Z, Killoran N (2020) Applications of near-term photonic quantum computers: software and algorithms. Quantum Sci Technol 5(3):034010. https:\/\/doi.org\/10.1088\/2058-9565\/ab8504","journal-title":"Quantum Sci Technol"},{"key":"185_CR8","doi-asserted-by":"publisher","unstructured":"Broome MA, Fedrizzi A, Rahimi-Keshari S, Dove J, Aaronson S, Ralph TC, White AG (2013) Photonic Boson Sampling in a tunable circuit. Science 339(6121):794\u2013798. https:\/\/doi.org\/10.1126\/science.1231440. Publisher: American Association for the Advancement of Science","DOI":"10.1126\/science.1231440"},{"issue":"12","key":"185_CR9","doi-asserted-by":"publisher","first-page":"1634","DOI":"10.1007\/BF02781659","volume":"10","author":"ER Caianiello","year":"1953","unstructured":"Caianiello ER (1953) On quantum field theory - I: explicit solution of Dyson\u2019s equation in electrodynamics without use of Feynman graphs. Il Nuovo Cimento (1943-1954) 10(12):1634\u20131652. https:\/\/doi.org\/10.1007\/BF02781659","journal-title":"Il Nuovo Cimento (1943-1954)"},{"issue":"7","key":"185_CR10","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1038\/nphoton.2013.112","volume":"7","author":"A Crespi","year":"2013","unstructured":"Crespi A, Osellame R, Ramponi R, Brod DJ, Galvao EF, Spagnolo N, Vitelli C, Maiorino E, Mataloni P, Sciarrino F (2013) Experimental boson sampling in arbitrary integrated photonic circuits. Nat Photonics 7(7):545\u2013549. https:\/\/doi.org\/10.1038\/nphoton.2013.112","journal-title":"Nat Photonics"},{"key":"185_CR11","doi-asserted-by":"publisher","unstructured":"Deng Y-H, Gong S-Q, Gu Y-C, Zhang Z-J, Liu H-L, Su H, Tang H-Y, Xu J-M, Jia M-H, Chen M-C, Zhong H-S, Wang H, Yan J, Hu Y, Huang J, Zhang W-J, Li H, Jiang X, You L, Wang Z, Li L, Liu N-L, Lu C-Y, Pan J-W (2023) Solving graph problems using gaussian boson sampling. Phys Rev Lett 130:190601. https:\/\/doi.org\/10.1103\/PhysRevLett.130.190601","DOI":"10.1103\/PhysRevLett.130.190601"},{"key":"185_CR12","doi-asserted-by":"publisher","unstructured":"Deutsch D, Penrose R (1985) Quantum theory, the Church-Turing principle and the universal quantum computer. Proc R Soc London. A Math Phys Sci 400(1818):97\u2013117. https:\/\/doi.org\/10.1098\/rspa.1985.0070. Publisher: Royal Society","DOI":"10.1098\/rspa.1985.0070"},{"key":"185_CR13","unstructured":"Ester M, Kriegel H-P, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the second international conference on knowledge discovery and data mining. KDD\u201996, pp 226\u2013231. AAAI Press, Portland, Oregon"},{"issue":"17","key":"185_CR14","doi-asserted-by":"publisher","first-page":"170501","DOI":"10.1103\/PhysRevLett.119.170501","volume":"119","author":"CS Hamilton","year":"2017","unstructured":"Hamilton CS, Kruse R, Sansoni L, Barkhofen S, Silberhorn C, Jex I (2017) Gaussian Boson Sampling. Phys Rev Lett 119(17):170501. https:\/\/doi.org\/10.1103\/PhysRevLett.119.170501","journal-title":"Phys Rev Lett"},{"key":"185_CR15","doi-asserted-by":"publisher","unstructured":"Hastie T, Tibshirani R, Friedman J (2009) The elements of statistical learning. Springer series in statistics. Springer, New York, NY. https:\/\/doi.org\/10.1007\/978-0-387-84858-7","DOI":"10.1007\/978-0-387-84858-7"},{"key":"185_CR16","doi-asserted-by":"publisher","unstructured":"Horn RA, Johnson CR (1985) Matrix analysis. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511810817","DOI":"10.1017\/CBO9780511810817"},{"key":"185_CR17","volume-title":"Algorithms for clustering data","author":"AK Jain","year":"1988","unstructured":"Jain AK, Dubes RC (1988) Algorithms for clustering data. Prentice-Hall Inc, USA"},{"issue":"5","key":"185_CR18","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model. Phys Rev E 58(5):5355\u20135363. https:\/\/doi.org\/10.1103\/PhysRevE.58.5355","journal-title":"Phys Rev E"},{"issue":"3","key":"185_CR19","doi-asserted-by":"publisher","first-page":"032326","DOI":"10.1103\/PhysRevA.100.032326","volume":"100","author":"R Kruse","year":"2019","unstructured":"Kruse R, Hamilton CS, Sansoni L, Barkhofen S, Silberhorn C, Jex I (2019) A detailed study of Gaussian Boson Sampling. Phys Rev A 100(3):032326. https:\/\/doi.org\/10.1103\/PhysRevA.100.032326","journal-title":"Phys Rev A"},{"issue":"1","key":"185_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/srep15384","volume":"5","author":"H-T Lim","year":"2015","unstructured":"Lim H-T, Hong K-H, Kim Y-H (2015) Experimental demonstration of high fidelity entanglement distribution over decoherence channels via qubit transduction. Sci Rep 5(1):1\u20136. https:\/\/doi.org\/10.1038\/srep15384","journal-title":"Sci Rep"},{"key":"185_CR21","doi-asserted-by":"publisher","unstructured":"Lucas A (2014) Ising formulations of many NP problems. Front Phys 2. https:\/\/doi.org\/10.3389\/fphy.2014.00005","DOI":"10.3389\/fphy.2014.00005"},{"issue":"2","key":"185_CR22","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02289146","volume":"14","author":"RD Luce","year":"1949","unstructured":"Luce RD, Perry AD (1949) A method of matrix analysis of group structure. Psychometrika 14(2):95\u2013116. https:\/\/doi.org\/10.1007\/BF02289146","journal-title":"Psychometrika"},{"key":"185_CR23","doi-asserted-by":"publisher","unstructured":"Lund AP, Laing A, Rahimi-Keshari S, Rudolph T, O\u2019Brien JL, Ralph TC (2014) Boson sampling from a Gaussian state. Phys Rev Lett 113(10):100502. https:\/\/doi.org\/10.1103\/PhysRevLett.113.100502. Publisher: American Physical Society","DOI":"10.1103\/PhysRevLett.113.100502"},{"key":"185_CR24","unstructured":"MacQueen J (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley symposium on mathematical statistics and probability, vol 1, pp 281\u2013297"},{"key":"185_CR25","doi-asserted-by":"publisher","unstructured":"Madsen LS, Laudenbach F, Askarani MF, Rortais F, Vincent T, Bulmer JFF, Miatto FM, Neuhaus L, Helt LG, Collins MJ, Lita AE, Gerrits T, Nam SW, Vaidya VD, Menotti M, Dhand I, Vernon Z, Quesada N, Lavoie J (2022) Quantum computational advantage with a programmable photonic processor. Nature 606(7912):75\u201381. https:\/\/doi.org\/10.1038\/s41586-022-04725-x. Number: 7912 Publisher: Nature Publishing Group","DOI":"10.1038\/s41586-022-04725-x"},{"key":"185_CR26","volume-title":"Machine learning: a probabilistic perspective","author":"KP Murphy","year":"2012","unstructured":"Murphy KP (2012) Machine learning: a probabilistic perspective. The MIT Press, Cambridge, MA"},{"key":"185_CR27","volume-title":"Quantum computation and quantum information: 10th anniversary edition, Anniversary","author":"MA Nielsen","year":"2011","unstructured":"Nielsen MA, Chuang IL (2011) Quantum computation and quantum information: 10th anniversary edition, Anniversary, edition. Cambridge University Press, Cambridge; New York","edition":"edition"},{"key":"185_CR28","doi-asserted-by":"crossref","unstructured":"Oh C, Jiang L, Quesada N (2023) Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling. arXiv:2302.00536","DOI":"10.1103\/PRXQuantum.5.020341"},{"issue":"6","key":"185_CR29","doi-asserted-by":"publisher","first-page":"062322","DOI":"10.1103\/PhysRevA.98.062322","volume":"98","author":"N Quesada","year":"2018","unstructured":"Quesada N, Arrazola JM, Killoran N (2018) Gaussian boson sampling using threshold detectors. Phys Rev A 98(6):062322. https:\/\/doi.org\/10.1103\/PhysRevA.98.062322","journal-title":"Phys Rev A"},{"key":"185_CR30","doi-asserted-by":"publisher","unstructured":"Rousseeuw PJ (1987) Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. J Comput Appl Math 20:53\u201365. https:\/\/doi.org\/10.1016\/0377-0427(87)90125-7","DOI":"10.1016\/0377-0427(87)90125-7"},{"key":"185_CR31","volume-title":"Artificial intelligence: a modern approach, $$4^{th}$$ edn","author":"SJ Russell","year":"2020","unstructured":"Russell SJ, Norvig P, Chang M-W, Devlin J, Dragan A (2020) Artificial intelligence: a modern approach, $$4^{th}$$ edn. Pearson College Div, Hoboken"},{"key":"185_CR32","unstructured":"sf.apps.sample.sample (n.d.) sf.apps.sample.sample \u2013 Strawberry Fields 0.23.0 documentation. https:\/\/strawberryfields.readthedocs.io\/en\/stable\/code\/api\/strawberryfields.apps.sample.sample.html"},{"key":"185_CR33","unstructured":"Solomons NR, Thomas OF, McCutcheon DPS (2023) Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms. arXiv:2301.13217"},{"key":"185_CR34","doi-asserted-by":"publisher","unstructured":"Terhal B (2018) Quantum supremacy, here we come. Nat Phys 14:530\u2013531. https:\/\/doi.org\/10.1038\/s41567-018-0131-y","DOI":"10.1038\/s41567-018-0131-y"},{"issue":"2","key":"185_CR35","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979) The complexity of computing the permanent. Theor Comput Sci 8(2):189\u2013201. https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theor Comput Sci"},{"issue":"2","key":"185_CR36","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1103\/RevModPhys.84.621","volume":"84","author":"C Weedbrook","year":"2012","unstructured":"Weedbrook C, Pirandola S, Garcia-Patron R, Cerf NJ, Ralph TC, Shapiro JH, Lloyd S (2012) Gaussian quantum information. Rev Mod Phys 84(2):621\u2013669. https:\/\/doi.org\/10.1103\/RevModPhys.84.621","journal-title":"Rev Mod Phys"},{"key":"185_CR37","unstructured":"Xanadu (n.d.) Beating classical computers with Borealis. https:\/\/www.xanadu.ai\/blog\/beating-classical-computers-with-Borealis"},{"key":"185_CR38","unstructured":"Xanadu (n.d.) Welcome to Xanadu. https:\/\/www.xanadu.ai\/"},{"issue":"2","key":"185_CR39","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s40745-015-0040-1","volume":"2","author":"D Xu","year":"2015","unstructured":"Xu D, Tian Y (2015) A comprehensive survey of clustering algorithms. Ann Data Sci 2(2):165\u2013193. https:\/\/doi.org\/10.1007\/s40745-015-0040-1","journal-title":"Ann Data Sci"},{"key":"185_CR40","doi-asserted-by":"publisher","unstructured":"Zhong H-S, Wang H, Deng Y-H, Chen M-C, Peng L-C, Luo Y-H, Qin J, Wu D, Ding X, Hu Y, Hu P, Yang X-Y, Zhang W-J, Li H, Li Y, Jiang X, Gan L, Yang G, You L, Wang Z, Li L, Liu N-L, Lu C-Y, Pan J-W (2020) Quantum computational advantage using photons. Science 370(6523):1460\u20131463. https:\/\/doi.org\/10.1126\/science.abe8770. Publisher: American Association for the Advancement of Science","DOI":"10.1126\/science.abe8770"}],"updated-by":[{"DOI":"10.1007\/s42484-024-00212-w","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2024,11,29]],"date-time":"2024-11-29T00:00:00Z","timestamp":1732838400000}}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00185-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-024-00185-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00185-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T16:10:25Z","timestamp":1734970225000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-024-00185-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["185"],"URL":"https:\/\/doi.org\/10.1007\/s42484-024-00185-w","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s42484-024-00212-w","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,10,8]]},"assertion":[{"value":"27 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2024","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised: In this article the wrong figure appeared as Fig. 3d. The figure has been corrected.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2024","order":7,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":8,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":9,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s42484-024-00212-w","URL":"https:\/\/doi.org\/10.1007\/s42484-024-00212-w","order":10,"name":"change_details","label":"Change Details","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":"65"}}