Clique detection using symmetry-restricted quantum circuits

Maximilian Balthasar Mansky, Tobias Rohe, Dmytro Bondarenko, Linus Menzel, Claudia Linnhoff‐Popien

Abstract: We show the application of permutation-invariant quantum circuits to the clique problem. The experiment asks to label a clique through identification of the nodes in a larger subgraph. The permutation-invariant quantum circuit outperforms a cyclic-invariant alternative as well as a standard quantum machine learning ansatz. We explain the behavior through the intrinsic symmetry of the problem, in the sense that the problem is symmetric under permutation of both the feature and the label.

Introduction

In classical machine learning, architectures like Convolutional Neural Networks (CNNs) succeed by hard-coding spatial symmetries, such as translation invariance, directly into their structure. Quantum Machine Learning (QML) is currently seeking its own "CNN moment" by moving away from generic, problem-agnostic ansatzes toward architectures that respect the inherent symmetries of the data. This paper demonstrates that "baking" permutation symmetry into quantum circuits allows them to solve the graph clique problem—an NP-complete task—with significantly higher efficiency than standard models.

Problem Formulation: The Max-Clique Problem

The authors address the Max-clique problem, which involves identifying a subset of nodes in a graph where every node is connected to every other node. In this study, the problem is framed as a node-labeling task: given a graph embedding where nodes are represented by qubits and edges by Controlled-Z (CZ) gates, the circuit must output a label for each node (1 for clique members, -1 otherwise).

Symmetry-Restricted Quantum Architectures

The researchers compared three distinct quantum circuit designs to evaluate the impact of symmetry constraints:

  1. Permutation-Invariant Quantum Circuits (PIQC): These circuits are restricted to operations that remain invariant regardless of how the qubits (nodes) are reordered, representing the strongest form of symmetry ($S_n$).
  2. Cyclic-Invariant Circuits: A weaker symmetry ($C_n$) where the circuit is only invariant under cyclic shifts of the qubits.
  3. Strongly Entangling Layer: A standard, "off-the-shelf" QML ansatz used as a baseline, which possesses no built-in symmetry restrictions.

By restricting the PIQC to permutation-invariant operations, the search space is effectively reduced. The model does not need to learn that swapping node labels results in an equivalent graph structure; the architecture already "knows" this through its intrinsic symmetry.

Permutation-invariant quantum circuit architecture.

Experimental Results

The study utilized synthetic datasets of Erdős-Rényi random graphs, specifically focusing on detecting 4-cliques in 6-node graphs and 5-cliques in 8-node graphs. The models were trained using the Quantum Natural Gradient optimizer.

The permutation-invariant ansatz was the clear winner in all tests. In the 6-qubit task, it reached approximately 90% accuracy almost immediately. In the 8-qubit task, it maintained a significant performance gap over the alternatives, converging rapidly within a few epochs. Conversely, the standard "strongly entangling" ansatz failed to converge, performing no better than random guessing. This highlights that for graph problems, symmetry is not just an optimization but a fundamental requirement for effective learning.

Accuracy vs. training epochs for 8-qubit graph clique detection.

Conclusion and Future Work

The success of permutation-invariant circuits suggests a new path for practical QML. By aligning the circuit architecture with the global symmetry of the problem, researchers can achieve faster convergence and higher accuracy. While current experiments are limited to small graphs (6-8 nodes) due to hardware constraints, the theory suggests these benefits should scale. Future work will explore whether these symmetrized circuits can generalize to find maximum cliques of arbitrary sizes and solve other graph-based challenges like connectivity or bipartiteness.

Summary updated

Abstract

We show the application of permutation-invariant quantum circuits to the clique problem. The experiment asks to label a clique through identification of the nodes in a larger subgraph. The permutation-invariant quantum circuit outperforms a cyclic-invariant alternative as well as a standard quantum machine learning ansatz. We explain the behavior through the intrinsic symmetry of the problem, in the sense that the problem is symmetric under permutation of both the feature and the label.
BibTeX
@misc{mansky2025clique,
  author = {Maximilian Balthasar Mansky and Tobias Rohe and Dmytro Bondarenko and Linus Menzel and Claudia Linnhoff‐Popien},
  title = {{Clique detection using symmetry-restricted quantum circuits}},
  year = {2025},
  eprint = {2506.03339},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.03339},
  howpublished = {arXiv},
}
Figure