⚛️ quantum physics

Local equivalence of stabilizer states: a graphical characterisation

This paper introduces a generalization of local complementation based on minimal local sets to provide a complete graphical characterization of LU-equivalence for stabilizer states, thereby revealing a strict infinite hierarchy of graph state equivalences.

Original authors: Nathan Claudet, Simon Perdrix

Published 2026-07-23

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Nathan Claudet, Simon Perdrix

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Quantum Puzzle: When Looks Deceive

Imagine you are trying to solve a massive, three-dimensional jigsaw puzzle, but the pieces are made of pure energy and can exist in two places at once. This is the world of quantum computing, where scientists build machines using "qubits" instead of bits. To make these machines work, researchers need to create special groups of qubits that are "entangled," meaning they are linked together in a spooky, invisible dance where changing one instantly affects the others, no matter how far apart they are. These groups are called stabilizer states, and a popular way to visualize them is as graph states: imagine a drawing where dots represent qubits and lines represent their entanglement.

For a long time, scientists had a simple rulebook for knowing if two of these drawings represented the exact same quantum dance. The rule was called local complementation. Think of it like a magic trick where you pick a dot and flip all the connections around it: if two dots were connected, you disconnect them; if they weren't, you connect them. If you could turn one drawing into another using only these flips, they were considered "equivalent"—they held the same amount of quantum magic. But recently, a problem emerged. Scientists found pairs of drawings that were actually the same quantum state (they could be transformed into each other using complex local moves) but could not be turned into each other using just the simple flip trick. It was like finding two different-looking maps that led to the exact same treasure, but the old compass couldn't tell you they were the same. This left a big gap in our understanding: how do we know when two quantum states are truly the same if the simple rules fail?

The New Map: A Hierarchy of Magic Tricks

In this paper, Nathan Claudet and Simon Perdrix from France introduce a powerful new set of tools to close that gap. They propose a "generalized local complementation," which is essentially an upgrade to the old flip trick. Instead of just flipping connections around a single dot, their new method allows for flipping connections based on a specific group of dots, but with a catch: the group has to follow a very strict mathematical pattern. They call this an $r$ -local complementation, where the number $r$ acts like a "level" or "rank" of complexity.

Think of the old trick as a Level 1 move. The authors discovered that by moving up to Level 2, Level 3, and so on, you can unlock transformations that were previously impossible. They proved that these new moves correspond to specific, slightly more complex quantum operations (using special rotations of the qubits). The most exciting part of their discovery is that these levels form a strict hierarchy. They showed that there are pairs of graph states that are equivalent at Level 2 (you can turn one into the other with a Level 2 move) but are not equivalent at Level 1. Even more surprisingly, they proved that this goes on forever: for any level $r$ , there are pairs of states that are equivalent at level $r+1$ but not at level $r$ . This means the gap between the simple rules and the full truth isn't just a small hole; it's an infinite staircase of complexity.

To make this work, the authors had to invent a new way to organize these quantum drawings. They developed a "standard form," a specific way of arranging the dots and lines so that every graph has a unique "fingerprint" based on the types of dots it contains. By forcing every graph into this standard form, they could easily compare them and see exactly which level of the hierarchy was needed to transform one into the other.

This new framework doesn't just solve the mystery of the missing equivalences; it also settles a long-standing debate about a specific family of graphs called "repeater graph states." For years, scientists wondered if the simple Level 1 rules were enough for these specific shapes. Using their new standard form, the authors proved that for these graphs, the simple rules do work, confirming a conjecture that had been open for some time.

In short, Claudet and Perdrix have handed us a new, more powerful magnifying glass. They showed us that the relationship between quantum states is far richer and more layered than we thought. While the old rules were like a basic map, their new "generalized local complementation" is a detailed topographical chart that reveals an infinite landscape of quantum connections, proving that to fully understand these entangled states, we need to be willing to climb higher up the ladder of complexity.

Technical Summary: Local Equivalence of Stabilizer States: A Graphical Characterisation

Problem Statement

Stabilizer states, and specifically graph states, are fundamental resources in quantum information processing, utilized in measurement-based quantum computing, error correction, and secret sharing. A central challenge in this domain is determining when two such states possess the same entanglement. According to quantum information theory, two states share the same entanglement if they are LU-equivalent (Local Unitary equivalent), meaning they can be transformed into one another via local unitary operations.

While LC-equivalence (Local Clifford equivalence) has a well-established graphical characterisation via local complementation (a graph transformation that complements the neighborhood of a vertex), it was conjectured that LU-equivalence and LC-equivalence coincide for graph states. This conjecture was disproven by counterexamples (e.g., pairs of graph states that are LU-equivalent but not LC-equivalent). Consequently, the problem of finding a complete graphical characterisation for LU-equivalence remained an open question. Existing tools, such as the cut-rank function, were insufficient to fully distinguish LU-equivalence classes, and the gap between LC and LU equivalence lacked a structured, graphical description.

Methodology

The authors address this problem by introducing a hierarchy of graphical transformations that generalise the standard local complementation. The methodology relies on three core pillars:

Generalised Local Complementation ( $r$ -local complementation):
The paper defines a new transformation, the $r$ -local complementation, parametrised by a positive integer $r$ . This operation is performed on an independent multiset of vertices $S$ that satisfies a specific counting condition called $r$ -incidence.
- For $r=1$ , this coincides with the standard local complementation.
- For $r > 1$ , the transformation toggles edges based on the number of common neighbours in $S$ modulo $2^r$ .
- The authors prove that these transformations can be implemented on graph states using local unitaries from the group $LC_r = \langle H, Z(\pi/2^r) \rangle$ , which extends the local Clifford group.
Minimal Local Sets and Vertex Types:
To characterise the action of local unitaries, the authors utilise minimal local sets (subsets of vertices that are invariant under LU-equivalence). They introduce a classification system for vertices based on their relationship to the generators of these minimal local sets, assigning each vertex a type: $X$ , $Y$ , $Z$ , or $\perp$ .
- This typing allows the authors to define a Standard Form for graphs. Any graph can be transformed into a standard form (where vertices of type $X$ form an independent set, neighbors of $X$ are type $Z$ , and specific ordering constraints are met) using only standard local complementations.
Standard Form Analysis:
By transforming LU-equivalent graphs into their standard forms, the authors demonstrate that the local unitary mapping between them is constrained. Specifically, if two graphs in standard form are LU-equivalent, the mapping reduces to a specific structure involving $X$ and $Z$ rotations. The constraints on the rotation angles derived from the graph structure align exactly with the conditions required for an $r$ -local complementation.

Key Contributions and Results

1. Graphical Characterisation of $LC_r$ -Equivalence

The paper establishes that two graph states are $LC_r$ -equivalent (transformable by local unitaries in $LC_r$ ) if and only if their corresponding graphs are $r$ -locally equivalent.

Theorem 32: $LC_r$ -equivalence is captured graphically by a sequence of standard local complementations and at most one $r$ -local complementation.
This generalises the known result that $LC_1$ -equivalence (LC-equivalence) is captured solely by sequences of standard local complementations.

2. Full Characterisation of LU-Equivalence

The authors prove that LU-equivalence is fully captured by the union of these generalised transformations.

Theorem 33: If two graph states are LU-equivalent, they are $(\lfloor n/2 \rfloor - 1)$ -locally equivalent, where $n$ is the number of qubits.
This implies that any LU-equivalence can be exhibited graphically by a sequence of generalised local complementations, providing a complete graphical description of the LU-equivalence class.

3. Strict Infinite Hierarchy of Equivalences

A major result is the proof of a strict infinite hierarchy of graph state equivalences.

The paper constructs families of bipartite graphs (variants of Kneser graphs, denoted $C_{t,k}$ and $C'_{t,k}$ ) to demonstrate that for any integer $r$ , there exist pairs of graph states that are $LC_{r+1}$ -equivalent but not $LC_r$ -equivalent.
This confirms that the gap between LC-equivalence and LU-equivalence is not a single step but an infinite ladder of intermediate equivalences.
The construction recovers known counterexamples (e.g., the 27-vertex counterexample to the LU-LC conjecture) as instances of $LC_2$ -equivalence that are not $LC_1$ -equivalent.

4. Resolution of the LU $\Leftrightarrow$ LC Conjecture for Specific Families

Using the new graphical characterisation, the authors provide a necessary and sufficient condition for when LU-equivalence and LC-equivalence coincide for a given graph.

Proposition 34: LU $\Leftrightarrow$ LC holds for a graph $G$ if and only if, in its standard form, any $r$ -local complementation over vertices of type $X$ can be implemented by standard local complementations.
This criterion is applied to prove that repeater graph states (both complete-graph-based and biclique-graph-based) satisfy LU $\Leftrightarrow$ LC, resolving an open question from previous literature.

Significance

The paper claims that its primary significance lies in providing the first complete graphical characterisation of LU-equivalence for stabilizer states. By introducing $r$ -local complementations and the associated standard form, the work:

Bridges the gap between the combinatorial properties of graphs and the algebraic properties of local unitaries.
Reveals a structured, infinite hierarchy of entanglement equivalences that were previously uncharacterised.
Offers a new toolset for determining the equivalence of quantum states, potentially aiding in the search for minimal counterexamples to the LU-LC conjecture and simplifying the analysis of entanglement in quantum protocols.

The authors note that while determining LC-equivalence is known to be in polynomial time, the complexity of the general LU-equivalence problem remains an open avenue for exploration using this new graphical framework.