Clifford Orbits from Cayley Graph Quotients

This article presents a state-independent quotient procedure on the Cayley graph of the Clifford group to construct reduced graphs that precisely map the orbits of both stabilizer and non-stabilizer states under Clifford gate actions, thereby generalizing earlier reachability results and yielding deeper insights into state evolution.

The Gist

Imagine you are trying to follow a very complicated dance performed by a group of quantum particles. In the quantum world, these particles (qubits) can exist in many states simultaneously, and the "dance moves" they perform are called Clifford gates.

Normally, attempting to track every possible move of a quantum system is like trying to map every single path through an infinite labyrinth. This is overwhelming. However, this article focuses on a specific, special set of dance moves (the Clifford group) that, while complex, are actually finite. There is a limited number of unique outcomes they can produce.

The authors of this article have developed a new method to visualize and understand these quantum dances using a mathematical concept called a Cayley graph.

The Big Idea: The Master Map versus the Personal Journey

Imagine the Cayley graph as a massive, state-independent "Master Map" of the entire dance troupe.

• The Nodes (Points): Each individual point on this map represents a unique combination of dance moves (a specific sequence of gates) that the group can perform.
• The Edges (Lines): The lines connecting the points represent the individual moves (gates such as the Hadamard or CNOT gate) that take you from one combination to the next.

This map is enormous. For just two qubits, there are over 90,000 different points (group elements). It is a complete, abstract blueprint for all possible moves, regardless of what the dancers are actually doing.

The Problem: Too Much Noise

If you want to know what happens to a specific quantum state (a specific dancer starting in a specific pose), looking at the entire Master Map is confusing. Many different sequences of moves may look different on the map but actually lead to the exact same result for this specific dancer.

For example: If a dancer spins in place, they end up looking exactly the same as if they had not spun at all. On the Master Map, "spinning" and "not spinning" are different points. But for the dancer's final position, they are the same.

The Solution: The "Quotient" Method

The authors introduce a clever trick called quotienting. Imagine taking this huge Master Map and folding it up.

1. Identifying the "Stabilizer": First, they determine which moves leave the pose of your specific dancer unchanged. These are the "invisible" moves for this specific state.
2. Folding the Map: They take all the points on the Master Map that represent moves leading to the same result for this specific dancer and glue them together into a single point.
3. The Result: What remains is a much smaller, simplified map. This new map is the Reachability Graph. It shows you exactly which poses the dancer can reach and how many steps it takes to get there, with all redundant "spins in place" removed.

What They Found

The article uses this method to investigate two-qubit systems (a pair of dancers). Here are their key discoveries, translated into everyday terms:

• Restoring Old Maps: They successfully reconstructed "Reachability Graphs" that they had drawn in a previous article, but this time they built them from scratch using their new "Master Map" folding technique. This proved that their new method works.
• New Types of Dancers: They looked not only at the standard "Stabilizer" dancers (the simple ones). They applied their folding technique to more complex, "Non-Stabilizer" dancers (such as the W-state and Dicke states).
  • The Analogy: Imagine that the standard dancers fit into a neat, predictable grid. The new, complex dancers fit into grids that look completely different—some have more points, others have different shapes. This shows that these complex states evolve in unique ways that standard maps could not reveal.
• Connecting the Points: They found that adding "Phase" gates (a specific type of move) acts like a bridge. It connects previously isolated islands on the map, showing how the full group of moves links various states that were previously isolated.

Why This Matters (According to the Article)

The authors argue that by applying this "folding" technique to the abstract group map, they can:

1. Understand Entanglement: They can see exactly how "entanglement" (a quantum connection between particles) is created or altered as the dance progresses.
2. Find Shortcuts: The map shows the shortest path between two states. This helps in understanding the "complexity" of a quantum circuit—essentially the minimum number of moves needed to get from point A to point B.
3. See the Invisible: They discovered that some long sequences of moves that look complicated on the Master Map actually change nothing in the entanglement (they are just "spins in place"). This helps in optimizing quantum circuits by removing unnecessary steps.

In short, the article offers a new, precise "GPS" for quantum states. Instead of getting lost in the infinite possibilities of the quantum world, you can now look at a folded, simplified map that tells you exactly where you can go and how to get there, whether you are a simple Stabilizer state or a complex, exotic quantum state.

Technical Summary

Technical Summary: Clifford Orbits from Cayley Graph Quotients

Problem Statement
The article addresses the challenge of tracking the evolution of quantum information under Clifford circuits. While the general evolution of quantum states requires tracking continuous parameters ($4^n - 2$ real parameters for $n$ qubits), restricting the dynamics to Clifford gates (Hadamard, Phase, CNOT) acting on stabilizer states enables a discrete, finite description. Previous works introduced "reachability graphs" to visualize these evolutions, where nodes represent states and edges represent gate applications. However, these graphs were constructed by simulating gate actions on specific states, a method that is state-dependent, difficult to generalize to non-stabilizer states, and fails to provide the underlying group-theoretic understanding of why certain gate sequences do not generate entanglement. The authors seek a more fundamental, state-independent framework to describe Clifford orbits and generalize reachability graphs to arbitrary quantum states.

Methodology
The authors propose a group-theoretic approach using Cayley graphs and quotient spaces.

1. Construction of Cayley Graphs: Instead of starting with states, they begin with the abstract Clifford group $C_n$. They construct Cayley graphs where nodes represent group elements and edges represent chosen generators (e.g., $\{H_i, P_i, C_{i,j}\}$).
2. Group Presentations: The article derives formal presentations (sets of generators and relations) for the one-qubit ($C_1$) and two-qubit ($C_2$) Clifford groups. This includes identifying non-trivial relations between generators, such as $(C_{i,j}H_j)^4 = P_i^2$, which are independent of the specific quantum state being acted upon.
3. Quotient Procedure: To recover the reachability graph for a specific state $|\Psi\rangle$, the authors apply a two-step quotient procedure to the Cayley graph:
   • Global-Phase Quotient: First, the group is quotiented by the subgroup of global phase $\langle \omega \rangle$ (where $\omega = (H_1 P_1)^3$), reducing the group size and identifying elements that differ only by a global phase.
   • Stabilizer Subgroup Quotient: Second, the graph is quotiented by the stabilizer subgroup of the target state, $Stab_G(|\Psi\rangle)$. Nodes in the Cayley graph representing group elements that act identically on $|\Psi\rangle$ (i.e., elements in the same left coset of the stabilizer subgroup) are identified (summarized) into a single node.
4. Application: This protocol is applied to various subgroups of $C_2$ (generated by subsets of $\{H, P, CNOT\}$) and to both stabilizer states and non-stabilizer states (specifically W-states and Dicke states).

Main Contributions and Results

• Formal Presentation of $C_2$: The authors provide a comprehensive set of relations for the two-qubit Clifford group and its subgroups. They explicitly construct the Cayley graphs for all subgroups generated by subsets of the standard Clifford gates and calculate their orders and graph diameters.
• Reproduction and Generalization of Reachability Graphs: By applying the quotient procedure to the $C_2$ Cayley graph, the authors successfully reproduce the reachability graphs for stabilizer states previously found in [1]. They demonstrate that the complex graphs encoding Clifford circuit actions decompose into highly structured subgraphs based on the stabilizer properties of the initial state.
• Extension to Non-Stabilizer States: The state-independent nature of the Cayley graph allows the authors to extend reachability analysis to non-stabilizer states. They construct orbits for:
  • W-States: They show that $|W\rangle_n$, although not a stabilizer state, possesses a non-trivial stabilizer subgroup within the Clifford group, resulting in a reachability graph with 288 nodes, whose topology differs from graphs for stabilizer states.
  • Dicke States: They analyze states such as $|D_4^2\rangle$, which are stabilized by only two elements of the relevant subgroup, yielding an orbit with 576 nodes—a size not observed for stabilizer states.
• Connectivity via Phase Gates: The article details how adding phase gates ($P_1, P_2$) to the generator set $\{H_1, H_2, C_{1,2}, C_{2,1}\}$ connects previously disconnected subgraphs. For example, the largest orbit under the restricted subgroup (1152 nodes) connects 9 isomorphic copies of itself via phase operations, forming a larger, fully connected structure.
• Graph Diameter and Entanglement: The authors calculate the diameter of Cayley graphs for various subgroups, both before and after quotienting. They note that certain relations (e.g., $(H_1 C_{2,1})^4 = P_1^2$) imply that some sequences of CNOT gates do not modify entanglement, providing a group-theoretic explanation for entropy bounds.

Significance and Claims
The article claims that this quotient-based construction offers a "more precise understanding of state evolution under Clifford circuit action." By shifting focus from state simulation to group theory, the authors can:

1. Systematically classify the variety of subgraph structures arising from different initial states and gate sets.
2. Generalize reachability analysis to any quantum state, including those with "magic" (non-stabilizer resources), simply by identifying the corresponding stabilizer subgroup.
3. Understand entanglement constraints: The relations derived in the presentation provide insight into why seemingly entangling gate operations sometimes fail to generate entanglement, a feature crucial for limiting the dynamics of entanglement entropy (a topic further explored in [10]).
4. Optimize circuits: The authors suggest that the graph-theoretic description enables the identification of minimal paths (shortest circuits) between states and the reduction of complex gate sequences to simpler equivalents (e.g., reducing a 9-gate sequence to a single phase gate).

The authors maintain a modest scope, focusing on $C_1$ and $C_2$ as a proof of concept. They note that extending to $C_n$ for $n > 2$ requires additional relations but is theoretically feasible. The work serves as a fundamental tool for analyzing circuit complexity and resource overhead in quantum computation, particularly for near-term devices where certain gate sets are preferred.