Clifford symmetries in quantum many-body systems

This paper introduces an algorithm that leverages the classically efficient Clifford group and a graph representation to automatically discover symmetries in arbitrary many-body Hamiltonians, successfully demonstrating its effectiveness on systems with up to one thousand qubits.

The Gist

The Big Problem: Finding Hidden Rules in a Messy Room

Imagine you have a giant, incredibly complicated machine made of thousands of tiny switches (called qubits). This machine is governed by a set of rules called a Hamiltonian. Physicists want to understand how this machine works, but the machine is so complex that calculating its behavior is like trying to solve a puzzle with a billion pieces.

Usually, the only way to make this puzzle easier is to find a symmetry. A symmetry is like a hidden rule that says, "If you flip this switch or rotate that part, the machine looks exactly the same." If you find these rules, you can break the giant puzzle into smaller, manageable pieces.

However, finding these rules is incredibly hard. Traditionally, it relies on a human genius staring at the equations and having a "Eureka!" moment. But many of these rules are so weird and non-local (involving switches that are far apart) that even geniuses can't spot them. Existing computer programs can only find simple, obvious rules, but they miss the complex ones.

The Solution: A "Graph Detective"

The authors of this paper have built a new algorithm that acts like a detective. Instead of staring at the math equations, the detective turns the entire machine into a map (a graph).

• The Map: Imagine every switch in your machine is a dot on a map.
• The Connections: If two switches interact with each other, you draw a line between them.
• The Colors: Each dot is colored based on how strong its connection is.

The detective's job is to look at this map and find Graph Automorphisms. In plain English, this means finding ways to rearrange the dots on the map (shuffling the switches) so that the pattern of lines and colors looks exactly the same as before.

If the map looks the same after you shuffle it, that shuffle corresponds to a Clifford Symmetry in the real machine. The paper claims this method is fast enough to handle machines with 1,000 switches, a size that was previously impossible to analyze this way.

The Second Challenge: Making the Rules Usable

Finding the rule is only step one. The second step is using the rule to simplify the machine.

Imagine you found a symmetry, but it's a messy, tangled knot that involves 100 switches all at once. To use this rule, you would still need a supercomputer to untangle it. The authors realized that just finding the rule isn't enough; you need to "untangle" the rule itself.

They developed a second part of their algorithm that acts like a tangle-remover. It finds a new way to look at the machine (a new reference frame) where that messy knot of 100 switches is actually just 50 separate, simple knots of 2 switches each.

They call this the "Qubit Cost."

• High Cost: The rule involves a huge, tangled group of switches. (Hard to use).
• Low Cost: The rule involves small, independent groups. (Easy to use).

Their algorithm automatically finds the "untangled" version of the rule, making it possible to actually use the symmetry to solve the problem.

What They Did (The Results)

The team tested their detective and tangle-remover on several types of machines:

1. Random Machines: They created fake machines with hidden rules injected into them. Their algorithm found the rules quickly, even for machines with 1,000 switches.
2. Real Physics Models: They applied it to famous models used to describe magnets and particles (like the Heisenberg XXZ model and the Transverse Field Ising model).

The Payoff:
By using their method, they could simulate these systems 256 times larger than what is possible without it.

• Time: It took them much less time to find the "ground state" (the lowest energy setting) of the machine.
• Memory: It required significantly less computer memory (RAM) to run the calculations.

The Bottom Line

This paper introduces a two-step automated process:

1. Translate a complex quantum machine into a map.
2. Detect hidden patterns (symmetries) in that map using graph theory.
3. Simplify those patterns so they are easy to use.

The result is a tool that can find hidden rules in massive quantum systems that humans couldn't find and that other computers couldn't use, allowing scientists to understand and simulate much larger quantum systems than ever before.

Technical Summary

Technical Summary: Clifford Symmetries in Quantum Many-Body Systems

Problem Statement
Identifying symmetries in quantum many-body Hamiltonians is a critical step for analytical understanding, ground state energy determination, and efficient simulation. While symmetries can lead to block-diagonalization of the Hamiltonian and significant computational savings, finding them is generally an intractable problem often reliant on human intuition ("thinking really hard"). Existing algorithmic approaches are limited to finding Pauli symmetries (operators that commute with the Hamiltonian), which, while useful, are often non-local and do not provide fundamentally new insights into complex physical models. Furthermore, methods capable of finding more complex, non-Pauli symmetries typically require explicit construction of the Hamiltonian in Hilbert space or solving challenging optimization problems, leading to prohibitive scaling that restricts their application to systems with only dozens of qubits. There is currently no algorithmic approach capable of reliably finding non-Pauli symmetries in large systems (hundreds to thousands of qubits).

Methodology
The authors propose an algorithmic framework to find and exploit Clifford symmetries for arbitrary many-body Hamiltonians. The method leverages the classical efficiency of the Clifford group and graph theory. The workflow proceeds in three main stages:

1. Graph Representation via Symplectic Formalism:
   The input Hamiltonian $\hat{H}$, expressed as a sum of Pauli strings, is mapped to a tableau representation using the symplectic formalism. In this representation, Pauli strings are treated as $2n$-dimensional vectors over $\mathbb{Z}_2$ rather than $2^n \times 2^n$ matrices. The authors construct a graph where:

   • Vertices represent Pauli terms in the Hamiltonian.
   • Vertex colors encode the coefficients of the Pauli terms.
   • Edges connect vertices if the corresponding Pauli strings anticommute (symplectic product is 1).
   • Auxiliary vertices and dashed edges represent linear dependencies (circuits) among the Pauli strings.

   This construction ensures that Graph Automorphisms (GAs) of the graph correspond directly to Clifford symmetries of the Hamiltonian. Since GAs can be solved in quasi-polynomial time using heuristic search strategies, this allows for the identification of symmetries in systems with up to 1,000 qubits.

2. Minimization of Qubit Cost:
   Finding a symmetry $\hat{S}$ is insufficient for simulation; it must be exploited by diagonalizing it. However, diagonalizing general Clifford circuits is NP-hard. To address this, the algorithm finds a basis transformation (a Clifford operator $\hat{B}$) that maps the symmetry $\hat{S}$ to a minimal form $\hat{S}_{\text{min}}$. This minimizes the "qubit cost" $Q(\hat{S})$, defined as the maximum number of qubits any single tensor factor of the symmetry acts upon. By reducing $Q(\hat{S})$, the symmetry becomes concentrated on a minimal number of interacting qubits, making numerical diagonalization feasible.

3. Exploitation via Block Decomposition:
   Once $\hat{S}_{\text{min}}$ is obtained and diagonalized, the authors decompose the transformed Hamiltonian $\hat{H}_{\text{sym}} = \hat{B}^\dagger \hat{H} \hat{B}$ into effective Hamiltonians $\hat{H}_\alpha$ acting on specific symmetry subsectors. These subsectors are defined by the eigenvalues of the symmetry. The effective Hamiltonians are derived numerically without ever constructing the full $2^n \times 2^n$ matrices, relying instead on the reduced dimensionality determined by the qubit cost and eigenvalue degeneracies.

Key Contributions

• Algorithmic Discovery of Clifford Symmetries: The paper introduces the first algorithmic approach capable of finding non-Pauli (Clifford) symmetries in large-scale quantum systems (up to $n=1000$ qubits), filling a gap left by previous methods restricted to Pauli symmetries or small system sizes.
• Graph-Theoretic Mapping: The work establishes a rigorous mapping between the search for Clifford symmetries and the Graph Automorphism problem, enabling the use of efficient, quasi-polynomial time solvers.
• Qubit Cost Minimization: The authors develop a method to minimize the qubit cost of a symmetry, ensuring that the subsequent diagonalization and exploitation of the symmetry remain classically tractable.
• Automated Block Decomposition: The framework automatically generates the effective operators describing each block of the decomposed Hamiltonian, facilitating direct application to simulation tasks.

Results
The method was tested on random Hamiltonians with injected symmetries and various physical models, including Fermi-Hubbard ladders, disordered Fermionic $tV$ chains, Transverse Field Ising (TFI) ladders, and Heisenberg XXZ models.

• Scalability: The algorithm successfully identified Clifford symmetries for instances with up to 1,000 qubits. The computational cost is dominated by finding the symplectic product matrix, which scales quadratically with the number of Pauli terms ($M$).
• Pattern Recognition: For the TFI ladder, the algorithm identified symmetries that followed a clear pattern, allowing for the inductive construction of a symmetry valid for arbitrary system sizes.
• Simulation Efficiency: In the Heisenberg XXZ model, exploiting the found symmetries allowed for the determination of ground states and time evolution of Haar-random states.
  • For $n=24$, a speed-up of approximately $\times 2$ was achieved for ground state finding.
  • For $n=20$, a speed-up of approximately $\times 4$ was achieved for time evolution.
  • Crucially, the method enabled Exact Diagonalization (ED) to solve systems 256 times larger than would be possible without symmetry exploitation, limited only by the available RAM (64 GB).
  • If the initial state were confined to a single subspace, potential speed-ups could range from $\times 40$ to $\times 6 \cdot 10^4$.

Significance and Claims
The authors claim that this work represents a major step toward fully automated symmetry finding in many-body physics. By complementing human ingenuity with an algorithm, the method provides deeper analytical understanding of physical models and enables the simulation of systems previously inaccessible to classical methods. The approach is not limited to finding symmetries but also ensures their exploitability by minimizing the computational resources required for diagonalization. The paper suggests that this framework can advance both classical simulation techniques (by providing symmetry-inspired ansatzes for solvers like DMRG or tensor networks) and quantum algorithms (by optimizing variational eigensolvers). The authors note that future directions include automated pattern recognition for analytical insights, extensions to non-Clifford and chiral symmetries, and further optimization of the disjoint subsector decomposition.