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

This paper presents an algorithm that maps the identification of Clifford symmetries in both closed and open qudit systems to a graph automorphism problem by encoding Hamiltonian invariants into graph properties, enabling efficient symmetry detection and optimization across various physical models.

The Gist

Imagine you have a giant, incredibly complex machine made of thousands of tiny, spinning gears. This machine is a quantum system, and the gears are called qudits (a fancy word for quantum bits that can have more than just two states).

Physicists love finding symmetries in these machines. A symmetry is like a secret rule: if you rearrange the gears in a specific way, the machine still works exactly the same. Knowing these rules is like having a cheat code; it helps scientists predict how the machine behaves, find its lowest energy state, or understand how it moves without having to simulate every single gear turning.

However, finding these hidden rules is usually like looking for a needle in a haystack. The haystack is the "Hamiltonian," which is just the mathematical blueprint of all the gears and how they interact.

The Big Idea: Turning a Puzzle into a Map

The authors of this paper, Charlie Nation and his team, have invented a new way to find these hidden rules. They realized that finding a symmetry is mathematically the same as solving a Graph Automorphism problem.

Here is the analogy:

• The Blueprint: Imagine the quantum machine's blueprint as a list of instructions.
• The Graph: The team turns this list into a map (a graph). Each instruction (or "Pauli string") becomes a dot (a vertex) on the map.
• The Connections: They draw lines (edges) between the dots. The color and direction of these lines tell you how the instructions interact with each other (do they cancel out? do they amplify?).
• The Colors: They also paint the dots different colors based on how "heavy" or important each instruction is (its coefficient).

The Detective Work

Now, finding a symmetry becomes a game of matching.

• You are looking for a way to shuffle the dots around on the map.
• The Rule: You can only move a dot to a new spot if the new spot has the same color and the same pattern of lines connecting to it.
• If you can shuffle the dots and the map looks exactly the same as before, you've found a symmetry!

The paper provides a computer algorithm to do this shuffling efficiently. Instead of guessing randomly, the algorithm uses "clues" (invariants) to narrow down the possibilities, much like a detective eliminating suspects who don't fit the description.

Handling the "Open" Systems

Most quantum machines in the real world aren't perfectly isolated; they leak information to their surroundings. This is called an open system.

• Closed System: A sealed box where the gears only talk to each other.
• Open System: A box with a hole in it, where the gears also talk to the air outside.

The authors show that their map-making trick works for both. For open systems, they simply double the size of the map to account for the "leakage," allowing them to find symmetries even in messy, real-world scenarios.

The "Phase" Problem

There is one tricky part. Sometimes, when you shuffle the dots, the machine works the same way except for a tiny, invisible twist (called a phase). It's like spinning a gear 360 degrees plus a tiny bit extra.

• The algorithm finds the perfect shuffle first.
• Then, it performs a quick "phase correction" check to see if that tiny twist can be fixed. If it can, the shuffle is a valid symmetry.

What They Tested

The team tested their method on several famous quantum models:

1. Random Machines: They built random machines with a hidden symmetry and successfully found it every time.
2. Realistic Models: They tested it on models like the Ising model (used for magnets) and the Fermi-Hubbard model (used for superconductors).
3. The Toric Code: This is a very complex model used for error correction in quantum computers. It has a huge number of hidden rules. The algorithm found symmetries in systems with up to 28 qubits (a lot for this type of problem) and helped them figure out the pattern for even larger systems.

The Results

The paper shows that this "Map Game" approach is fast and scalable.

• For many models, the time it takes to find a symmetry grows reasonably as the machine gets bigger (roughly quadratically).
• It works for systems with different types of gears (different dimensions).
• It works for both sealed boxes (closed) and leaking boxes (open).

Summary

In short, the authors took a hard math problem (finding hidden rules in quantum mechanics) and turned it into a visual puzzle (shuffling colored dots on a map). By using existing computer tools designed to solve map puzzles, they can now quickly find the secret symmetries of complex quantum systems, helping us understand how these machines work without having to simulate every single move.

Technical Summary

Technical Summary: Graph Automorphisms to Obtain Clifford Symmetries in Open and Closed Qudit Models

Problem Statement
The identification of symmetries in quantum systems is crucial for understanding ground state properties, dynamics, and thermodynamics, as well as for reducing computational costs in numerical simulations through block-diagonalization. While symmetries are often discovered by inspection, they can be non-obvious in complex models. Existing algorithmic approaches are largely limited to Pauli symmetries or become computationally prohibitive as system sizes increase. Specifically, there is a lack of efficient algorithms to find Clifford symmetries—a class of symmetries efficiently implementable on classical computers—for general qudit systems, including both closed (Hamiltonian) and open (Liouvillian) quantum systems.

Methodology
The authors propose an algorithm that maps the problem of finding Clifford symmetries to a Graph Automorphism (GA) problem. The methodology relies on the symplectic representation of qudit operators and proceeds through the following steps:

1. Symplectic Representation: The system is represented using a tableau formalism. For a closed system, the Hamiltonian $\hat{H}$ is encoded as a weighted sum of Pauli strings, defined by a coefficient vector $\vec{c}$, an exponent matrix $p$ (representing Pauli strings as vectors in $\mathbb{Z}_d^{2n}$), and a phase vector $\vec{\eta}$. For open systems, this is extended to the Liouville space, doubling the number of qudits to represent the GKSL master equation generator $\mathcal{L}$ as a superoperator tableau.
2. Graph Construction: The Hamiltonian (or Liouvillian) is mapped to a colored directed graph $G = (V, E, X_V, X_E)$:
   • Vertices ($V$): Each Pauli string in the tableau corresponds to a vertex.
   • Vertex Colors ($X_V$): Vertices are colored by their coefficients $c_i$. Since Clifford operations preserve the magnitude of coefficients, a valid symmetry must map vertices to others with identical colors.
   • Edge Labels ($X_E$): Directed edges between vertices represent the symplectic product $\langle \vec{p}_i, \vec{p}_j \rangle \pmod d$, which encodes the commutation relations between Pauli strings. A valid symmetry must preserve these edge labels.
3. Dependency and Phase Handling:
   • Linear Dependencies: To ensure the permutation respects the linear dependence structure of the Pauli strings, the authors employ two strategies: (a) augmenting the graph with auxiliary vertices representing minimal circuits (dependent subsets), or (b) performing a post-hoc "code automorphism" check on candidate permutations to verify they preserve the row space of the generator matrix.
   • Phase Correction: Since Clifford gates include phase vectors that are not strictly invariant, the algorithm first finds a candidate permutation (GA) that satisfies the structural invariants. It then solves a linear system to determine if a valid phase vector $\vec{\phi}$ exists to correct the residual phase mismatch, effectively checking if the candidate is a true symmetry up to a Pauli gate.
4. Search Algorithms: The GA problem is solved using two approaches:
   • Bliss/igraph: Utilizing existing libraries to find generators of the automorphism group.
   • MRV Heuristic: A custom backtracking search using a Minimum Remaining Values heuristic to prune the search space efficiently, often accelerated by Weisfeiler-Leman (WL) color refinement to distinguish vertices based on local commutation neighborhoods.

Key Contributions

• Algorithmic Framework: The paper provides the first detailed algorithm to find Clifford symmetries for arbitrary finite open or closed qudit systems by mapping the problem to Graph Automorphisms.
• Extension to Open Systems: The formalism is generalized from Hamiltonians to GKSL master equations, allowing for the discovery of symmetries in dissipative open quantum systems by treating them as doubled-qudit Liouvillian tableaux.
• Efficiency and Scalability: The approach leverages the symplectic representation to keep the problem classically efficient. The use of graph coloring and heuristics significantly prunes the search space compared to brute-force permutation checks.
• Handling Dependencies: The work details methods to incorporate linear dependence structures (circuits) either via graph augmentation or code automorphism checks, ensuring the found permutations correspond to valid physical symmetries.

Results
The authors benchmarked the algorithm on various models:

• Random Pauli Hamiltonians: Demonstrated quadratic scaling with system size for finding injected symmetries, limited primarily by the graph construction time ($O(M^2)$).
• Physical Models: Successfully identified symmetries in Transverse Field Ising (TFI) models (ladder, square, triangular geometries), Fermionic models (Fermi-Hubbard, disordered $t-V$ chains), and Heisenberg XXZ models.
• Scaling: For models with local interactions (e.g., TFI, $t-V$), the time to find symmetries scales approximately quadratically with the number of qudits $n$. For all-to-all models (e.g., Heisenberg XXZ with all-to-all couplings), scaling depends on the number of Pauli terms $M$, which scales as $n^2$, leading to different performance characteristics.
• Toric Code: In highly symmetric regimes, the algorithm found symmetries for up to $n=28$ qubits. For larger instances, the authors used the algorithmic output to analytically extrapolate the symmetry structure for arbitrary system sizes. The graph augmentation strategy proved beneficial for the Toric code to avoid combinatorial explosion in checking dependencies.
• Open Systems: The algorithm successfully handled open systems (e.g., TFI with dephasing), noting the increased computational cost due to the doubling of the Hilbert space dimension required for the Liouvillian representation.

Significance and Claims
The paper claims to fill a critical gap in the literature by providing a practical algorithm for finding Clifford symmetries, a task for which no general solution previously existed. The authors emphasize that their method is not limited to specific models but applies to any system representable as a Pauli sum on qudits.

The significance lies in the ability to:

1. Automate Symmetry Discovery: Move beyond manual inspection to algorithmic detection of non-trivial Clifford symmetries.
2. Handle Open Systems: Extend symmetry analysis to dissipative dynamics, identifying invariant operator-space sectors in open quantum systems.
3. Enable Analytical Insight: Use numerical results from small-to-medium systems to inductively derive analytical forms of symmetries for arbitrary system sizes (as demonstrated with the Toric code).

The authors remain modest regarding the computational complexity, acknowledging that while the GA problem is generally hard, the specific structure of Clifford symmetries (via invariants like coefficients and commutation relations) allows for efficient solutions in many physical regimes. They note that phase correction and dependency checks are necessary steps that distinguish this problem from a standard GA, though empirically, these checks do not significantly increase the complexity for the tested models. The work provides a Python implementation ("Sympleq") to facilitate further research and application.