{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T19:31:43Z","timestamp":1771270303724,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Disruptive Technologies Innovation Fund (DTIF), by Enterprise Ireland","award":["DTIF2019-090"],"award-info":[{"award-number":["DTIF2019-090"]}]},{"name":"IBM Quantum and Mastercard Ireland"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>We propose a novel variational method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies (1) on a new representation of the adjacency matrices of the underlying graphs, which requires a number of qubits that scales logarithmically with the number of vertices of the graphs; and (2) on a new ansatz that can efficiently probe the permutation space. Simulations are then presented to showcase the approach on graphs up to 16 vertices, whereas, given the logarithmic scaling, the approach could be applied to realistic sub-graph isomorphism problem instances in the medium term.<\/jats:p>","DOI":"10.1145\/3569095","type":"journal-article","created":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T14:14:12Z","timestamp":1666793652000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["A Quantum Algorithm\u00a0for the Sub-graph Isomorphism Problem"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7268-1149","authenticated-orcid":false,"given":"Nicola","family":"Mariella","sequence":"first","affiliation":[{"name":"IBM Research Europe - Ireland, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2923-3361","authenticated-orcid":false,"given":"Andrea","family":"Simonetto","sequence":"additional","affiliation":[{"name":"UMA, ENSTA Paris, Institut Polytechnique de Paris, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Gadi Aleksandrowicz Thomas Alexander Panagiotis Barkoutsos Luciano Bello Yael Ben-Haim David Bucher Francisco Jose Cabrera-Hern\u00e1ndez Jorge Carballo-Franquis Adrian Chen Chun-Fu Chen Jerry M. Chow Antonio D. C\u00f3rcoles-Gonzales Abigail J. Cross Andrew Cross Juan Cruz-Benito Chris Culver Salvador De La Puente Gonz\u00e1lez Enrique De La Torre Delton Ding Eugene Dumitrescu Ivan Duran Pieter Eendebak Mark Everitt Ismael Faro Sertage Albert Frisch Andreas Fuhrer Jay Gambetta Borja Godoy Gago Juan Gomez-Mosquera Donny Greenberg Ikko Hamamura Vojtech Havlicek Joe Hellmers \u0141ukasz Herok Hiroshi Horii Shaohan Hu Takashi Imamichi Toshinari Itoko Ali Javadi-Abhari Naoki Kanazawa Anton Karazeev Kevin Krsulich Peng Liu Yang Luh Yunho Maeng Manoel Marques Francisco Jose Mart\u00edn-Fern\u00e1ndez Douglas T. McClure David McKay Srujan Meesala Antonio Mezzacapo Nikolaj Moll Diego Moreda Rodr\u00edguez Giacomo Nannicini Paul Nation Pauline Ollitrault Lee James O\u2019Riordan Hanhee Paik Jes\u00fas P\u00e9rez Anna Phan Marco Pistoia Viktor Prutyanov Max Reuter Julia Rice Abd\u00f3n Rodr\u00edguez Davila Raymond Harry Putra Rudy Mingi Ryu Ninad Sathaye Chris Schnabel Eddie Schoute Kanav Setia Yunong Shi Adenilton Silva Yukio Siraichi Seyon Sivarajah John A. Smolin Mathias Soeken Hitomi Takahashi Ivano Tavernelli Charles Taylor Pete Taylour Kenso Trabing Matthew Treinish Wes Turner Desiree Vogt-Lee Christophe Vuillot Jonathan A. Wildstrom Jessica Wilson Erick Winston Christopher Wood Stephen Wood Stefan W\u00f6rner Ismail Yunus Akhalwaya and Christa Zoufal. 2019. Qiskit: An Open-source Framework for Quantum Computing Zenodo DOI:https:\/\/zenodo.org\/record\/2562111\/export\/hx#.Y3tNMi8w1qs"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1401651112"},{"key":"e_1_3_3_4_2","volume-title":"Number Theory","author":"Andrews G. E.","year":"1994","unstructured":"G. E. Andrews. 1994. Number Theory. Dover Publications."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46541-3_36"},{"key":"e_1_3_3_6_2","first-page":"583","volume-title":"International Conference on 3D Vision (3DV)","author":"Benkner Marcel Seelbach","year":"2020","unstructured":"Marcel Seelbach Benkner, Vladislav Golyanik, Christian Theobalt, and Michael Moeller. 2020. Adiabatic quantum graph matching with permutation matrix constraints. In International Conference on 3D Vision (3DV). 583\u2013592."},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"7566","DOI":"10.1109\/ICCV48922.2021.00749","volume-title":"IEEE\/CVF International Conference on Computer Vision (ICCV)","author":"Benkner Marcel Seelbach","year":"2021","unstructured":"Marcel Seelbach Benkner, Zorah L\u00e4hner, Vladislav Golyanik, Christof Wunderlich, Christian Theobalt, and Michael Moeller. 2021. Q-Match: Iterative shape matching via quantum annealing. In IEEE\/CVF International Conference on Computer Vision (ICCV). 7566\u20137576."},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory (1st ed.)","author":"Bollob\u00e1s B\u00e9la","year":"1998","unstructured":"B\u00e9la Bollob\u00e1s. 1998. Modern Graph Theory (1st ed.). Springer-Verlag New York."},{"issue":"7","key":"e_1_3_3_9_2","first-page":"1","article-title":"A subgraph isomorphism algorithm and its application to biochemical data","volume":"14","author":"Bonnici Vincenzo","year":"2013","unstructured":"Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinf. 14, 7 (2013), 1\u201313.","journal-title":"BMC Bioinf."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.04.016"},{"key":"e_1_3_3_11_2","article-title":"On the variational perspectives to the graph isomorphism problem","author":"Chatterjee Turbasu","year":"2021","unstructured":"Turbasu Chatterjee, Shah Ishmam Mohtashim, and Akash Kundu. 2021. On the variational perspectives to the graph isomorphism problem. arXiv preprint arXiv:2111.09821 (2021).","journal-title":"arXiv preprint arXiv:2111.09821"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_3_3_15_2","unstructured":"Gavin E. Crooks. 2019. Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition. arxiv:1905.13311 [quant-ph]."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.09.001"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2008.10.013"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_3_3_19_2","first-page":"925","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD\u201911)","author":"Fan Wenfei","year":"2011","unstructured":"Wenfei Fan, Jianzhong Li, Jizhou Luo, Zijing Tan, Xin Wang, and Yinghui Wu. 2011. Incremental graph pattern matching. In ACM SIGMOD International Conference on Management of Data (SIGMOD\u201911). 925\u2013936."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.89.022342"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.138"},{"issue":"6","key":"e_1_3_3_22_2","article-title":"Limitations of quantum coset states for graph isomorphism","volume":"57","author":"Hallgren Sean","year":"2010","unstructured":"Sean Hallgren, Cristopher Moore, Martin R\u00f6tteler, Alexander Russell, and Pranab Sen. 2010. Limitations of quantum coset states for graph isomorphism. J. ACM 57, 6 (Nov.2010).","journal-title":"J. ACM"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-05-13-140"},{"key":"e_1_3_3_24_2","volume-title":"33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","author":"Kulkarni Raghav","year":"2016","unstructured":"Raghav Kulkarni and Supartha Podder. 2016. Quantum query complexity of subgraph isomorphism and homomorphism. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"issue":"2","key":"e_1_3_3_25_2","article-title":"An in-depth comparison of subgraph isomorphism algorithms in graph databases","volume":"6","author":"Lee J.","year":"2013","unstructured":"J. Lee, W.-S. Han, R. Kasperovics, and J.-H. Lee. 2013. An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proc. VLDB Endow. 6, 2 (2013).","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_3_26_2","article-title":"The quantum algorithm for graph isomorphism problem","author":"Li Xi","year":"2019","unstructured":"Xi Li and Hanwu Chen. 2019. The quantum algorithm for graph isomorphism problem. arXiv preprint arXiv:1901.06530 (2019).","journal-title":"arXiv preprint arXiv:1901.06530"},{"key":"e_1_3_3_27_2","first-page":"1082","article-title":"Time constrained continuous subgraph search over streaming graphs","author":"Li Youhuan","year":"2019","unstructured":"Youhuan Li, Lei Zou, M. Tamer \u00d6zsu, and Dongyan Zhao. 2019. Time constrained continuous subgraph search over streaming graphs. In IEEE 35th International Conference on Data Engineering (ICDE). 1082\u20131093.","journal-title":"IEEE 35th International Conference on Data Engineering (ICDE)"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.936019"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3505181"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/3241691.3241707"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958045"},{"key":"e_1_3_3_33_2","volume-title":"Subgraph Isomorphism Search In Massive Graph Data","author":"Nabti Chems Eddine","year":"2018","unstructured":"Chems Eddine Nabti. 2018. Subgraph Isomorphism Search In Massive Graph Data. Ph.D. Dissertation. Universite de Lyon, Lyon, France."},{"key":"e_1_3_3_34_2","article-title":"An exponentially more efficient optimization algorithm for noisy quantum computers","author":"Rancic Marko J.","year":"2021","unstructured":"Marko J. Rancic. 2021. An exponentially more efficient optimization algorithm for noisy quantum computers. arXiv preprint arXiv:2110.10788 (2021).","journal-title":"arXiv preprint arXiv:2110.10788"},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2178-2","volume-title":"Advanced Linear Algebra","author":"Roman S.","year":"1992","unstructured":"S. Roman. 1992. Advanced Linear Algebra. Springer-Verlag. 95220619"},{"key":"e_1_3_3_36_2","volume-title":"Lie Groups: An Introduction through Linear Groups","author":"Rossmann W.","year":"2006","unstructured":"W. Rossmann. 2006. Lie Groups: An Introduction through Linear Groups. Oxford University Press. 2001050008"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6804-6","volume-title":"The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions","author":"Sagan Bruce E.","year":"2001","unstructured":"Bruce E. Sagan. 2001. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer New York, New York, NY."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.12.018"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/tcad.2005.855930"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.05.002"},{"key":"e_1_3_3_41_2","first-page":"1083","volume-title":"ACM SIGMOD International Conference on Management of Data (SIGMOD\u201920)","author":"Sun Shixuan","year":"2020","unstructured":"Shixuan Sun and Qiong Luo. 2020. In-memory subgraph matching: An in-depth study. In ACM SIGMOD International Conference on Management of Data (SIGMOD\u201920). 1083\u20131098."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-08-31-314"},{"key":"e_1_3_3_43_2","article-title":"QFAST: Conflating search and numerical optimization for scalable quantum circuit synthesis","author":"Younis Ed","year":"2021","unstructured":"Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. 2021. QFAST: Conflating search and numerical optimization for scalable quantum circuit synthesis. arXiv preprint arXiv:2103.07093 (2021).","journal-title":"arXiv preprint arXiv:2103.07093"},{"issue":"1","key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"11168","DOI":"10.1038\/srep11168","article-title":"Experimental quantum annealing: Case study involving the graph isomorphism problem","volume":"5","author":"Zick Kenneth M.","year":"2015","unstructured":"Kenneth M. Zick, Omar Shehab, and Matthew French. 2015. Experimental quantum annealing: Case study involving the graph isomorphism problem. Sci. Rep. 5, 1 (2015), 11168.","journal-title":"Sci. Rep."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569095","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:41Z","timestamp":1750182701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3569095"],"URL":"https:\/\/doi.org\/10.1145\/3569095","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,24]]},"assertion":[{"value":"2021-11-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}