{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,4]],"date-time":"2025-10-04T08:19:36Z","timestamp":1759565976914,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T00:00:00Z","timestamp":1674518400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T00:00:00Z","timestamp":1674518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"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>We investigate quantum circuits for graph representation learning, and propose <jats:italic>equivariant quantum graph circuits (EQGCs)<\/jats:italic>, as a class of parameterized quantum circuits with strong relational inductive bias for learning over graph-structured data. Conceptually, EQGCs serve as a unifying framework for quantum graph representation learning, allowing us to define several interesting subclasses subsuming existing proposals. In terms of the representation power, we prove that the subclasses of interest are universal approximators for functions over the bounded graph domain. This theoretical perspective on quantum graph machine learning methods opens many directions for further work, and could lead to models with capabilities beyond those of classical approaches. We also provide experimental evidence, and observe that the performance of EQGCs scales well with the depth of the model.<\/jats:p>","DOI":"10.1007\/s42484-022-00086-w","type":"journal-article","created":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T11:51:13Z","timestamp":1674561073000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Equivariant quantum graph circuits: constructions for universal approximation over graphs"],"prefix":"10.1007","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2098-6669","authenticated-orcid":false,"given":"P\u00e9ter","family":"Mernyei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Meichanetzidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0130smail \u0130lkan","family":"Ceylan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,24]]},"reference":[{"issue":"4","key":"86_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1038\/nphys3272","volume":"11","author":"S Aaronson","year":"2015","unstructured":"Aaronson S (2015) Read the fine print. Nat Phys 11(4):291\u2013293","journal-title":"Nat Phys"},{"key":"86_CR2","doi-asserted-by":"crossref","unstructured":"Abboud R, Ceylan \u0130\u0130, Grohe M et al (2021) The surprising power of graph neural networks with random node initialization. In: IJCAI","DOI":"10.24963\/ijcai.2021\/291"},{"key":"86_CR3","doi-asserted-by":"crossref","unstructured":"Ai X, Zhang Z, Sun L et al (2022) Decompositional quantum graph neural network. arXiv:220105158","DOI":"10.1109\/TNNLS.2022.3144343"},{"issue":"7779","key":"86_CR4","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1038\/s41586-019-1666-5","volume":"574","author":"F Arute","year":"2019","unstructured":"Arute F, Arya K, Babbush R et al (2019) Quantum supremacy using a programmable superconducting processor. Nature 574(7779):505\u2013510","journal-title":"Nature"},{"key":"86_CR5","unstructured":"Barcel\u00f3 P, Kostylev EV, Monet M et al (2020) The logical expressiveness of graph neural networks. In: ICLR"},{"key":"86_CR6","unstructured":"Battaglia PW, Hamrick JB, Bapst V et al (2018) Relational inductive biases, deep learning, and graph networks. arXiv:180601261"},{"key":"86_CR7","unstructured":"Beer K, Khosla M, K\u00f6hler J et al (2021) Quantum machine learning of graph-structured data. arXiv:210310837"},{"issue":"4","key":"86_CR8","doi-asserted-by":"publisher","first-page":"043,001","DOI":"10.1088\/2058-9565\/ab4eb5","volume":"4","author":"M Benedetti","year":"2019","unstructured":"Benedetti M, Lloyd E, Sack S, et al. (2019) Parameterized quantum circuits as machine learning models. Quant Sci Technol 4(4):043,001","journal-title":"Quant Sci Technol"},{"key":"86_CR9","doi-asserted-by":"crossref","unstructured":"Bordes A, Weston J, Collobert R et al (2011) Learning structured embeddings of knowledge bases. In: AAAI","DOI":"10.1609\/aaai.v25i1.7917"},{"issue":"8","key":"86_CR10","doi-asserted-by":"publisher","first-page":"080,501","DOI":"10.1103\/PhysRevLett.117.080501","volume":"117","author":"MJ Bremner","year":"2016","unstructured":"Bremner MJ, Montanaro A, Shepherd DJ (2016) Average-case complexity versus approximate simulation of commuting quantum computations. Phys Rev Lett 117(8):080,501","journal-title":"Phys Rev Lett"},{"key":"86_CR11","unstructured":"Chen SYC, Wei TC, Zhang C et al (2021) Hybrid quantum-classical graph convolutional network. arXiv:210106189"},{"issue":"2209","key":"86_CR12","doi-asserted-by":"publisher","first-page":"20170,551","DOI":"10.1098\/rspa.2017.0551","volume":"474","author":"C Ciliberto","year":"2018","unstructured":"Ciliberto C, Herbster M, Ialongo AD, et al. (2018) Quantum machine learning: a classical perspective. Proc R Soc A: Math Phys Eng Sci 474(2209):20170,551","journal-title":"Proc R Soc A: Math Phys Eng Sci"},{"key":"86_CR13","doi-asserted-by":"crossref","unstructured":"Coecke B, Kissinger A (2018) Picturing quantum processes. In: International conference on theory and application of diagrams. Springer, pp 28\u201331","DOI":"10.1007\/978-3-319-91376-6_6"},{"issue":"12","key":"86_CR14","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1038\/s41567-019-0648-8","volume":"15","author":"I Cong","year":"2019","unstructured":"Cong I, Choi S, Lukin M D (2019) Quantum convolutional neural networks. Nat Phys 15 (12):1273\u20131278","journal-title":"Nat Phys"},{"key":"86_CR15","doi-asserted-by":"crossref","unstructured":"Dasoulas G, Santos LD, Scaman K et al (2020) Coloring graph neural networks for node disambiguation. In: IJCAI","DOI":"10.24963\/ijcai.2020\/294"},{"key":"86_CR16","unstructured":"Gilmer J, Schoenholz SS, Riley PF et al (2017) Neural message passing for quantum chemistry. In: ICML. PMLR, pp 1263\u20131272"},{"key":"86_CR17","unstructured":"Gori M, Monfardini G, Scarselli F (2005) A new model for learning in graph domains. In: IJCNN"},{"issue":"9","key":"86_CR18","doi-asserted-by":"publisher","first-page":"090,506","DOI":"10.1103\/PhysRevLett.127.090506","volume":"127","author":"T Goto","year":"2021","unstructured":"Goto T, Tran QH, Nakajima K (2021) Universal approximation property of quantum machine learning models in quantum-enhanced feature spaces. Phys Rev Lett 127(9):090,506","journal-title":"Phys Rev Lett"},{"issue":"3","key":"86_CR19","first-page":"1","volume":"14","author":"WL Hamilton","year":"2020","unstructured":"Hamilton WL (2020) Graph representation learning. Synth Lect Artif Intell Mach Learn 14 (3):1\u2013159","journal-title":"Synth Lect Artif Intell Mach Learn"},{"issue":"15","key":"86_CR20","doi-asserted-by":"publisher","first-page":"150,502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Lett 103(15):150,502","journal-title":"Phys Lett"},{"issue":"3","key":"86_CR21","doi-asserted-by":"publisher","first-page":"032,416","DOI":"10.1103\/PhysRevA.104.032416","volume":"104","author":"LP Henry","year":"2021","unstructured":"Henry LP, Thabet S, Dalyac C et al (2021) Quantum evolution kernel: Machine learning on graphs with programmable arrays of qubits. Phys Rev A 104(3):032,416","journal-title":"Phys Rev A"},{"key":"86_CR22","unstructured":"Hinsche M, Ioannou M, Nietner A et al (2021) Learnability of the output distributions of local quantum circuits. arXiv:2110.05517"},{"issue":"5","key":"86_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0893-6080(89)90020-8","volume":"2","author":"K Hornik","year":"1989","unstructured":"Hornik K, Stinchcombe M, White H (1989) Multilayer feedforward networks are universal approximators. Neural Netw 2(5):359\u2013366","journal-title":"Neural Netw"},{"key":"86_CR24","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: ICLR"},{"key":"86_CR25","unstructured":"K\u00fcbler JM, Buchholz S, Sch\u00f6lkopf B (2021) The inductive bias of quantum kernels. arXiv:210603747"},{"key":"86_CR26","doi-asserted-by":"crossref","unstructured":"Li Q, Han Z, Wu XM (2018) Deeper insights into graph convolutional networks for semi-supervised learning. In: AAAI. AAAI Press","DOI":"10.1609\/aaai.v32i1.11604"},{"key":"86_CR27","unstructured":"Li Y, Tarlow D, Brockschmidt M et al (2016) Gated graph sequence neural networks. In: ICLR"},{"issue":"9","key":"86_CR28","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1038\/s41567-021-01287-z","volume":"17","author":"Y Liu","year":"2021","unstructured":"Liu Y, Arunachalam S, Temme K (2021) A rigorous and robust quantum speed-up in supervised machine learning. Nat Phys 17(9):1013\u20131017","journal-title":"Nat Phys"},{"key":"86_CR29","unstructured":"Loukas A (2020) What graph neural networks cannot learn: depth vs width. In: ICLR"},{"key":"86_CR30","unstructured":"Maron H, Ben-Hamu H, Serviansky H et al (2019a) Provably powerful graph networks. In: NeurIPS"},{"key":"86_CR31","unstructured":"Maron H, Ben-Hamu H, Shamir N et al (2019b) Invariant and equivariant graph networks. In: ICLR"},{"issue":"1","key":"86_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-018-07090-4","volume":"9","author":"JR McClean","year":"2018","unstructured":"McClean JR, Boixo S, Smelyanskiy VN et al (2018) Barren plateaus in quantum neural network training landscapes. Nat Commun 9(1):1\u20136","journal-title":"Nat Commun"},{"key":"86_CR33","doi-asserted-by":"crossref","unstructured":"Morris C, Ritzert M, Fey M et al (2019) Weisfeiler and leman go neural: Higher-order graph neural networks. In: AAAI","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"86_CR34","doi-asserted-by":"publisher","first-page":"391","DOI":"10.22331\/q-2021-01-28-391","volume":"5","author":"M Ostaszewski","year":"2021","unstructured":"Ostaszewski M, Grant E, Benedetti M (2021) Structure optimization for parameterized quantum circuits. Quantum 5:391","journal-title":"Quantum"},{"issue":"3","key":"86_CR35","doi-asserted-by":"publisher","first-page":"030,502","DOI":"10.1088\/2058-9565\/aab859","volume":"3","author":"A Perdomo-Ortiz","year":"2018","unstructured":"Perdomo-Ortiz A, Benedetti M, Realpe-G\u00f3mez J et al (2018) Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers. Quant Sci Technol 3(3):030,502","journal-title":"Quant Sci Technol"},{"key":"86_CR36","doi-asserted-by":"crossref","unstructured":"Sato R, Yamada M, Kashima H (2021) Random features strengthen graph neural networks. In: SDM, SIAM, pp 333\u2013341","DOI":"10.1137\/1.9781611976700.38"},{"issue":"1","key":"86_CR37","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","volume":"20","author":"F Scarselli","year":"2009","unstructured":"Scarselli F, Gori M, Tsoi AC et al (2009) The graph neural network model. Trans Neur Netw 20(1):61\u201380","journal-title":"Trans Neur Netw"},{"issue":"4","key":"86_CR38","doi-asserted-by":"publisher","first-page":"040,504","DOI":"10.1103\/PhysRevLett.122.040504","volume":"122","author":"M Schuld","year":"2019","unstructured":"Schuld M, Killoran N (2019) Quantum machine learning in feature Hilbert spaces. Phys Rev Lett 122(4):040,504","journal-title":"Phys Rev Lett"},{"issue":"3","key":"86_CR39","doi-asserted-by":"publisher","first-page":"032,331","DOI":"10.1103\/PhysRevA.99.032331","volume":"99","author":"M Schuld","year":"2019","unstructured":"Schuld M, Bergholm V, Gogolin C et al (2019) Evaluating analytic gradients on quantum hardware. Phys Rev A 99(3):032,331","journal-title":"Phys Rev A"},{"issue":"3","key":"86_CR40","doi-asserted-by":"publisher","first-page":"032430","DOI":"10.1103\/PhysRevA.103.032430","volume":"103","author":"M Schuld","year":"2021","unstructured":"Schuld M, Sweke R, Meyer JJ (2021) Effect of data encoding on the expressive power of variational quantum-machine-learning models. Phys Rev A 103(3):032430","journal-title":"Phys Rev A"},{"issue":"5","key":"86_CR41","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1137\/S0097539704412910","volume":"33","author":"RA Servedio","year":"2004","unstructured":"Servedio RA, Gortler SJ (2004) Equivalences and separations between quantum and classical learnability. SIAM J Comput 33(5):1067\u20131092","journal-title":"SIAM J Comput"},{"key":"86_CR42","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A et al (2018) Graph attention networks. In: ICLR"},{"key":"86_CR43","unstructured":"Verdon G, McCourt T, Luzhnica E et al (2019) Quantum graph neural networks. arXiv:190912264"},{"issue":"2","key":"86_CR44","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1039\/C7SC02664A","volume":"9","author":"Z Wu","year":"2018","unstructured":"Wu Z, Ramsundar B, Feinberg E et al (2018) Moleculenet: a benchmark for molecular machine learning. Chem Sci 9(2):513\u2013530","journal-title":"Chem Sci"},{"key":"86_CR45","unstructured":"Xu K, Hu W, Leskovec J et al (2019) How powerful are graph neural networks?. In: ICLR"},{"key":"86_CR46","unstructured":"Zaheer M, Kottur S, Ravanbakhsh S et al (2017) Deep sets. In: NIPS"},{"key":"86_CR47","unstructured":"Zhang M, Chen Y (2018) Link prediction based on graph neural networks. In: NIPS, pp 5165\u20135175"},{"key":"86_CR48","doi-asserted-by":"crossref","unstructured":"Zheng J, Gao Q, Lv Y (2021) Quantum graph convolutional neural networks. arXiv:210703257","DOI":"10.23919\/CCC52363.2021.9550372"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-022-00086-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-022-00086-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-022-00086-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,19]],"date-time":"2023-06-19T07:28:59Z","timestamp":1687159739000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-022-00086-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,24]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["86"],"URL":"https:\/\/doi.org\/10.1007\/s42484-022-00086-w","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"type":"print","value":"2524-4906"},{"type":"electronic","value":"2524-4914"}],"subject":[],"published":{"date-parts":[[2023,1,24]]},"assertion":[{"value":"25 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 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 was performed as part of an MSc research project, with no funding involved. The authors have no financial or non-financial competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}}],"article-number":"6"}}