Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.23160

Efficient Identification of Permutation Symmetries in Many-Body Hamiltonians via Graph Theory

Saumya Shah, Patrick Rebentrost

quant-phcs.DSSubmitted Nov 28, 2025• Announced Dec 1, 2025• 0 citations
arXivHTMLPDF

Abstract

The computational cost of simulating quantum many-body systems can often be reduced by taking advantage of physical symmetries. While methods exist for specific symmetry classes, a general algorithm to find the full permutation symmetry group of an arbitrary Pauli Hamiltonian is notably lacking. This paper introduces a new method that identifies this symmetry group by establishing an isomorphism between the Hamiltonian's permutation symmetry group and the automorphism group of a coloured bipartite graph constructed from the Hamiltonian. We formally prove this isomorphism and show that for physical Hamiltonians with bounded locality and interaction degree, the resulting graph has a bounded degree, reducing the computational problem of finding the automorphism group to polynomial time. The algorithm's validity is empirically confirmed on various physical models with known symmetries. We further show that the problem of deciding whether two Hamiltonians are permutation-equivalent is polynomial-time reducible to the graph isomorphism problem using our graph representation. This work provides a general, structurally exact tool for algorithmic symmetry finding, enabling the scalable application of these symmetries to Hamiltonian simulation problems.

Comments
18 pages, 5 tables

Related papers

The quantum algorithm for graph isomorphism problem

Xi Li, Hanwu Chen

The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph $G_1$ that transforms $G_1$ to another given graph $G_2$ and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.

arXiv:1901.06530•Jan 19, 2019•3 citations

Graph automorphisms to obtain Clifford symmetries in open and closed qudit models

Charlie Nation, Rick P. A. Simon, Shreya Banerjee +4 more

In the recent article [arXiv:2605.18966], we demonstrated that finding Clifford symmetries can be mapped to a Graph Automorphism (GA) problem. Here, we provide an algorithm to obtain such symmetries on general qudit systems, that works on the principle of encoding Clifford invariants of a Hamiltonian onto properties of a graph. Labelling Hamiltonian terms as vertices, a permutation of such vertices that respects the Clifford invariants (a GA) is both a valid Clifford, and a symmetry up to phase correction checks. We test this on multiple physical models and discuss the scaling with respect to the number of qudits and Pauli strings, as well as various strategies for optimisation in different regimes. We further show that the graph automorphism representation of Clifford symmetries can be expanded to open quantum systems.

quant-pharXiv:2605.30428•Jun 1, 2026•0 citations

Testing graph isomorphism using simple quantum circuits

Samuel Beasley, Ashley Montanaro

The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth $p=2$, this invariant numerically distinguishes all $10{,}486$ cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at $θ=π/2$ and $θ=π/4$. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.

quant-pharXiv:2610.19962•Oct 15, 2026•0 citations

Clifford symmetries in quantum many-body systems

Charlie Nation, Rick P. A. Simon, Shreya Banerjee +4 more

Obtaining the symmetries of a model is a critical step towards developing an understanding and ultimately analytically or numerically solving the model. However, finding symmetries is generally extremely complicated, often being the result of insightful thinking. In this work, we complement human ingenuity with an algorithm. We leverage the classically efficient Clifford group to find symmetries for arbitrary many-body Hamiltonians via a graph representation. We demonstrate our method on random and physical Hamiltonians, with instances of up to one thousand qubits and demonstrate how our approach can provide deeper understanding of the model.

quant-pharXiv:2605.18966•May 20, 2026•0 citations

Solution group representations as quantum symmetries of graphs

David E. Roberson, Simon Schmidt

In 2019, Aterias et al. constructed pairs of quantum isomorphic, non-isomorphic graphs from linear constraint systems. This article deals with quantum automorphisms and quantum isomorphisms of colored versions of those graphs. We show that the quantum automorphism group of such a colored graph is the dual of the homogeneous solution group of the underlying linear constraint system. Given a vertex- and edge-colored graph with certain properties, we construct an uncolored graph that has the same quantum automorphism group as the colored graph we started with. Using those results, we obtain the first known example of a graph that has quantum symmetry and finite quantum automorphism group. Furthermore, we construct a pair of quantum isomorphic, non-isomorphic graphs that both have no quantum symmetry.

arXiv:2111.12362•Journal of the London Mathematical Society•Jul 11, 2022•6 citations

Quantum Graphs Built from Observables and Symmetries

Edward Yu. Bormashenko

A graph-theoretical framework for quantum mechanics is developed in which observables and symmetry operators are incorporated into a single complete bi-coloured graph. The proposed Symmetry/Observables Quantum Graph (SOQG) treats Hamiltonians, observables, conserved quantities, and unitary symmetry transformations on equal footing as operators acting on a common Hilbert space. The vertices of the graph represent operators, while the colours of the edges are determined by their commutation relations: commuting operators are connected by maroon edges and non-commuting operators by teal edges. The resulting structure constitutes a finite Ramsey graph that provides a combinatorial representation of operator compatibility. The formalism is applied to several representative quantum systems, including a particle in a central potential, a charged particle in a uniform magnetic field, and a particle in a homogeneous external field. In each case, monochromatic cliques identify maximal compatibility sectors containing both observables and symmetry operators, thereby revealing the interplay between conserved quantities and dynamical symmetries. It is further shown that coloured-graph automorphisms generally differ from the physical symmetry group of the underlying quantum system, leading to the notion of second-order graph symmetry. The SOQG is proved to be invariant under simultaneous unitary transformations of all operators and therefore represents intrinsic properties of the operator algebra rather than a particular Hilbert-space representation. The graph-theoretical structure is analysed using Ramsey theory and the Mantel–Turán extremal theorem, which provide rigorous conditions for the appearance of mutually compatible and mutually incompatible operator subsets. The framework is subsequently generalized to parameter-dependent Symmetry/Observables Quantum Graphs (PSOQGs), whose compatibility structure changes as external parameters modify the underlying commutation relations. For magnetic translation operators, the magnetic flux through the elementary translation cell induces a flux-controlled colour-switching transition between commuting and non-commuting compatibility sectors, accompanied by changes in the graph automorphism group. The proposed framework establishes a direct connection between operator theory, symmetry, graph theory, and extremal combinatorics, providing a new structural perspective on quantum systems.

•Aug 31, 2026•0 citations
The computational cost of simulating quantum many-body systems can often be reduced by taking advantage of physical symmetries. While methods exist for specific symmetry classes, a general algorithm to find the full permutation symmetry group of an arbitrary Pauli Hamiltonian is notably lacking. This paper introduces a new method that identifies this symmetry group by establishing an isomorphism between the Hamiltonian's permutation symmetry group and the automorphism group of a coloured bipartite graph constructed from the Hamiltonian. We formally prove this isomorphism and show that for physical Hamiltonians with bounded locality and interaction degree, the resulting graph has a bounded degree, reducing the computational problem of finding the automorphism group to polynomial time. The algorithm's validity is empirically confirmed on various physical models with known symmetries. We further show that the problem of deciding whether two Hamiltonians are permutation-equivalent is polynomial-time reducible to the graph isomorphism problem using our graph representation. This work provides a general, structurally exact tool for algorithmic symmetry finding, enabling the scalable application of these symmetries to Hamiltonian simulation problems.
The graph isomorphism (GI) problem is the computational problem of finding a permutation of vertices of a given graph G1G_1G1​ that transforms G1G_1G1​ to another given graph G2G_2G2​ and preserves the adjacency. In this work, we propose a quantum algorithm to determine whether there exists such a permutation. To find such a permutation, we introduce isomorphic equivalent graphs of the given graphs to be tested. We proof that the GI problem of the equivalent graphs is equivalent to the GI problem of the given graphs. The idea of the algorithm is to determine whether there exists a permutation can transform the eigenvectors of the adjacency matrix of the equivalent graphs each other. The cost time of the algorithm is polynomial.
In the recent article [arXiv:2605.18966], we demonstrated that finding Clifford symmetries can be mapped to a Graph Automorphism (GA) problem. Here, we provide an algorithm to obtain such symmetries on general qudit systems, that works on the principle of encoding Clifford invariants of a Hamiltonian onto properties of a graph. Labelling Hamiltonian terms as vertices, a permutation of such vertices that respects the Clifford invariants (a GA) is both a valid Clifford, and a symmetry up to phase correction checks. We test this on multiple physical models and discuss the scaling with respect to the number of qudits and Pauli strings, as well as various strategies for optimisation in different regimes. We further show that the graph automorphism representation of Clifford symmetries can be expanded to open quantum systems.
The graph isomorphism problem asks whether two graphs are equivalent up to a permutation of their vertices. Its precise computational complexity remains unresolved, and it is still unknown whether a polynomial-time algorithm exists. We investigate whether simple graph-dependent Instantaneous Quantum Polynomial-time (IQP) and Quantum Approximate Optimisation Algorithm (QAOA) circuits can distinguish non-isomorphic graphs. We first show that suitable IQP and QAOA constructions allow the underlying graph to be reconstructed using a polynomial number of samples. Building on previous work using the QAOA energy, we show that Hamming weight distributions can distinguish graph pairs at circuit depths for which the numerically computed energy gap is zero. We then apply graph invariants to the matrix of ZZ correlators on the output distribution. For the specific case of the graph spectrum, at QAOA depth p=2p=2p=2, this invariant numerically distinguishes all 10,48610{,}48610,486 cospectral regular graph pairs tested on up to 18 vertices. For IQP circuits, we introduce a finer invariant based on probability multiplicities within Hamming weight sectors, which distinguishes every non-isomorphic graph pair tested numerically. Finally, we derive exact graph-theoretic characterisations of the IQP output distribution at θ=π/2θ=π/2θ=π/2 and θ=π/4θ=π/4θ=π/4. These results show that simple graph-dependent quantum circuits encode substantial structural information, while leaving open whether this information can be extracted efficiently for general graph isomorphism.
Obtaining the symmetries of a model is a critical step towards developing an understanding and ultimately analytically or numerically solving the model. However, finding symmetries is generally extremely complicated, often being the result of insightful thinking. In this work, we complement human ingenuity with an algorithm. We leverage the classically efficient Clifford group to find symmetries for arbitrary many-body Hamiltonians via a graph representation. We demonstrate our method on random and physical Hamiltonians, with instances of up to one thousand qubits and demonstrate how our approach can provide deeper understanding of the model.
In 2019, Aterias et al. constructed pairs of quantum isomorphic, non-isomorphic graphs from linear constraint systems. This article deals with quantum automorphisms and quantum isomorphisms of colored versions of those graphs. We show that the quantum automorphism group of such a colored graph is the dual of the homogeneous solution group of the underlying linear constraint system. Given a vertex- and edge-colored graph with certain properties, we construct an uncolored graph that has the same quantum automorphism group as the colored graph we started with. Using those results, we obtain the first known example of a graph that has quantum symmetry and finite quantum automorphism group. Furthermore, we construct a pair of quantum isomorphic, non-isomorphic graphs that both have no quantum symmetry.
A graph-theoretical framework for quantum mechanics is developed in which observables and symmetry operators are incorporated into a single complete bi-coloured graph. The proposed Symmetry/Observables Quantum Graph (SOQG) treats Hamiltonians, observables, conserved quantities, and unitary symmetry transformations on equal footing as operators acting on a common Hilbert space. The vertices of the graph represent operators, while the colours of the edges are determined by their commutation relations: commuting operators are connected by maroon edges and non-commuting operators by teal edges. The resulting structure constitutes a finite Ramsey graph that provides a combinatorial representation of operator compatibility. The formalism is applied to several representative quantum systems, including a particle in a central potential, a charged particle in a uniform magnetic field, and a particle in a homogeneous external field. In each case, monochromatic cliques identify maximal compatibility sectors containing both observables and symmetry operators, thereby revealing the interplay between conserved quantities and dynamical symmetries. It is further shown that coloured-graph automorphisms generally differ from the physical symmetry group of the underlying quantum system, leading to the notion of second-order graph symmetry. The SOQG is proved to be invariant under simultaneous unitary transformations of all operators and therefore represents intrinsic properties of the operator algebra rather than a particular Hilbert-space representation. The graph-theoretical structure is analysed using Ramsey theory and the Mantel–Turán extremal theorem, which provide rigorous conditions for the appearance of mutually compatible and mutually incompatible operator subsets. The framework is subsequently generalized to parameter-dependent Symmetry/Observables Quantum Graphs (PSOQGs), whose compatibility structure changes as external parameters modify the underlying commutation relations. For magnetic translation operators, the magnetic flux through the elementary translation cell induces a flux-controlled colour-switching transition between commuting and non-commuting compatibility sectors, accompanied by changes in the graph automorphism group. The proposed framework establishes a direct connection between operator theory, symmetry, graph theory, and extremal combinatorics, providing a new structural perspective on quantum systems.