Efficient Identification of Permutation Symmetries in Many-Body Hamiltonians via Graph Theory
Preprint
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.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Symmetry Breaking Slows Convergence of the ADAPT Variational Quantum EigensolverJournal of Chemical Theory and Computation, 2022
- Classical symmetries and the Quantum Approximate Optimization AlgorithmQuantum Information Processing, 2021
- Reducing Qubit Requirements for Quantum Simulations Using Molecular Point Group SymmetriesJournal of Chemical Theory and Computation, 2020
- Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithmnpj Quantum Information, 2020
- Practical graph isomorphism, IIJournal of Symbolic Computation, 2014
- Conflict Propagation and Component Recursion for Canonical Labeling2011
- Graph isomorphism problemJournal of Mathematical Sciences, 1985
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- Zur Theorie des FerromagnetismusThe European Physical Journal A, 1928
- Beitrag zur Theorie des FerromagnetismusZeitschrift für Physik, 1925