Solving graph problems using permutation-invariant quantum machine learning

Maximilian Balthasar Mansky, Tobias Rohe, Gerhard Stenzel, Alejandro Bravo de la Serna, Santiago Londoño Castillo, Gautham Sathish, Dimitra Nikolaidou, Dmytro Bondarenko, Linus Menzel, Claudia Linnhoff‐Popien

Abstract

Many computational problems are unchanged under some symmetry operation. In classical machine learning, this can be reflected with the layer structure of the neural network. In quantum machine learning, the ansatz can be tuned to correspond to the specific symmetry of the problem. We investigate this adaption of the quantum circuit to the problem symmetry on graph classification problems. On random graphs, the quantum machine learning ansatz classifies whether a given random graph is connected, bipartite, contains a Hamiltonian path or cycle, respectively. We find that if the quantum circuit reflects the inherent symmetry of the problem, it vastly outperforms the standard, unsymmetrized ansatzes. Even when the symmetry is only approximative, there is still a significant performance gain over non-symmetrized ansatzes. We show how the symmetry can be included in the quantum circuit in a straightforward constructive method.

Introduction

In classical machine learning, "inductive biases"—assumptions about the data's structure—are fundamental to model success. Convolutional Neural Networks (CNNs), for instance, leverage translation invariance in images. Graphs present a similar challenge: they are permutation-invariant. Relabeling nodes does not change intrinsic properties like connectedness or bipartiteness. Standard Quantum Machine Learning (QML) models often treat every qubit as a unique entity, forcing the model to learn symmetries from scratch. This research explores building quantum circuits that inherently respect graph symmetries to improve learning efficiency and performance.

Methods

The researchers developed a constructive method based on Lie algebras to design quantum circuits that respect specific symmetries. They compared four distinct ansatzes:

  1. Permutation-invariant ($S_n$): Parameters are shared across all possible node permutations.
  2. Cyclic-invariant ($C_n$): A weaker symmetry where parameters are shared only across cyclic shifts.
  3. Free parameters: Uses the same geometric structure as the permutation-invariant circuit but allows independent weights for every gate, serving as a structural control.
  4. Standard ansatz: A generic "Strongly Entangling Layer" representing a typical black-box QML approach.
Comparison of the four quantum circuit architectures used in the study.

The models were trained using the Quantum Natural Gradient on balanced datasets of 3,000 Erdős–Rényi random graphs (8 nodes/qubits) for tasks including connectedness, bipartiteness, and finding Hamiltonian paths/cycles.

Results

The performance gap between symmetry-aware and standard models was substantial across all tasks. The permutation-invariant ansatz consistently achieved high accuracy (0.8–0.9) within a few epochs, while standard and free-parameter models often failed to significantly exceed the 0.5 random-guessing baseline.

Validation accuracy over training epochs for the connectedness problem on 8-qubit graphs.

Crucially, the "Free parameters" model performed poorly despite having the same circuit depth as the permutation-invariant one. This indicates that the enforcement of symmetry via parameter sharing, rather than just the circuit's geometric layout, is the primary driver of performance. Furthermore, even partial symmetry (Cyclic-invariant) provided a notable advantage over non-symmetric baselines.

Discussion and Conclusion

Symmetry acts as a powerful filter, removing irrelevant solutions from the search space and accelerating convergence. By hard-coding permutation invariance, QML models naturally generalize to isomorphic graphs—a task that typically poses a significant challenge for standard architectures.

Future work will need to address scalability beyond small qubit counts and the adaptation of these methods to weighted graphs, where pure permutation symmetry is broken. Nevertheless, these results demonstrate that incorporating problem-specific symmetries is a vital step toward practical and efficient quantum machine learning.

Reference: Mansky, M. B., et al. (2025). Solving graph problems using permutation-invariant quantum machine learning. arXiv:2505.12764v2 [quant-ph].

Summary updated

Abstract

Many computational problems are unchanged under some symmetry operation. In classical machine learning, this can be reflected with the layer structure of the neural network. In quantum machine learning, the ansatz can be tuned to correspond to the specific symmetry of the problem. We investigate this adaption of the quantum circuit to the problem symmetry on graph classification problems. On random graphs, the quantum machine learning ansatz classifies whether a given random graph is connected, bipartite, contains a Hamiltonian path or cycle, respectively. We find that if the quantum circuit reflects the inherent symmetry of the problem, it vastly outperforms the standard, unsymmetrized ansatzes. Even when the symmetry is only approximative, there is still a significant performance gain over non-symmetrized ansatzes. We show how the symmetry can be included in the quantum circuit in a straightforward constructive method.
BibTeX
@misc{mansky2025solving,
  author = {Maximilian Balthasar Mansky and Tobias Rohe and Gerhard Stenzel and Alejandro Bravo de la Serna and Santiago Londoño Castillo and Gautham Sathish and Dimitra Nikolaidou and Dmytro Bondarenko and Linus Menzel and Claudia Linnhoff‐Popien},
  title = {{Solving graph problems using permutation-invariant quantum machine learning}},
  year = {2025},
  eprint = {2505.12764},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.12764},
  howpublished = {arXiv},
}
Figure