⚛️ quantum physics

Local Equivalences of Graph States

This thesis introduces a generalized local complementation rule that fully characterizes LU-equivalence for graph states, thereby establishing an infinite hierarchy between LC- and LU-equivalence, providing a quasi-polynomial decision algorithm, proving equivalence for states up to 19 qubits, and analyzing universal graph states.

Original authors: Nathan Claudet

Published 2026-07-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nathan Claudet

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

Imagine a world where the rules of reality are a bit like a magical game of "connect the dots," but instead of drawing lines with a pencil, you're weaving invisible threads of connection between tiny particles called qubits. This is the realm of quantum computing, a field that promises to solve problems so complex they would take today's supercomputers millions of years to crack. At the heart of this magic is a phenomenon called entanglement, where particles become so deeply linked that what happens to one instantly affects the other, no matter how far apart they are. It's like having a pair of magical dice: if you roll a six on one, the other instantly shows a six, even if it's on the other side of the galaxy.

To study this spooky connection, scientists use special tools called graph states. Think of these as a way to draw a map of the entanglement. In this map, every dot (or vertex) represents a qubit, and every line (or edge) represents a connection between them. The beauty of graph states is that they turn complicated quantum math into simple pictures. If you want to know if two quantum systems have the same "amount" of entanglement, you don't need to solve a physics equation; you just need to see if you can turn one picture into another using specific, allowed moves. For a long time, scientists thought there was only one simple set of moves to do this, but it turns out the game is much more complex than anyone imagined.

This thesis, written by Nathan Claudet, dives deep into the rules of this quantum drawing game. The main question he tackles is: When are two different-looking maps of entanglement actually the same thing? In the language of the paper, this is asking when two graph states are "LU-equivalent" (Local Unitary equivalent). Imagine you have two different drawings of a city. One looks like a grid, the other like a spiderweb. If you can transform the grid into the spiderweb just by rotating or flipping individual blocks without tearing the paper, they are essentially the same city, just viewed differently.

For years, scientists believed there was a simple rule called local complementation that could answer this question. You can think of local complementation as a specific "magic trick" you can perform on a drawing: pick a dot, and flip the connections of all its neighbors (if they were connected, disconnect them; if they weren't, connect them). The big hope was that if you could turn Drawing A into Drawing B using only these magic tricks, then the two quantum states were identical in every way. This idea was so popular it became a famous conjecture: that these simple tricks were enough to describe all ways to transform these states.

However, this paper proves that the old hope was wrong. The author shows that there are pairs of graph states that are indeed the same (they can be transformed into each other using quantum operations), but you cannot turn one into the other using just the simple "local complementation" tricks. It's like realizing that while you can turn a square into a circle by stretching it, you can't do it just by folding the paper; you need a more powerful tool.

To fix this, Nathan introduces a new, more powerful set of magic tricks called r-local complementation. Think of the old trick as a single step, and this new version as a "super-step" that can handle more complex patterns. He proves that if you allow yourself to use these generalized tricks (which are like a sequence of the old tricks combined with some extra moves), you can finally capture every possible way to transform these quantum states. This discovery is a big deal because it gives scientists a complete map of the rules.

Using this new map, the author achieves two major things:

A Faster Way to Check: He designs a new algorithm (a step-by-step recipe for a computer) that can decide if two graph states are the same much faster than before. While previous methods would take an impossibly long time for large systems, this new method is "quasi-polynomial," meaning it scales up much more reasonably. It's like upgrading from a calculator that counts one by one to a super-fast computer.
A New Hierarchy: He discovers that the gap between the "simple tricks" and the "full quantum power" isn't just a tiny gap; it's an infinite staircase. There are many levels of complexity in between. You can have states that are equivalent with a little extra power, but not with a little less. This creates a strict hierarchy of how "connected" these states can be.

One of the most concrete results in the paper is a new limit on when the old, simple rules actually work. For a long time, it was known that for very small systems (up to 8 qubits), the simple local complementation tricks were enough. Nathan's work pushes this boundary significantly, proving that for any graph state with 19 or fewer qubits, the simple rules still hold true. If you have a system with 20 or more qubits, however, you might need the new, more complex tricks. This is a massive improvement over the previous record of 8.

The paper also touches on a concept called vertex-minor universality. Imagine you have a giant, complex web of connections. The question is: can you cut out a small piece of this web that looks exactly like any other small web you can imagine? The author shows that yes, there are specific large graphs that are "universal" in this sense. He provides a probabilistic construction (a recipe that works most of the time) to build these universal graphs, showing that you need a number of dots roughly proportional to the square of the size of the small web you want to create.

In short, this thesis takes a confusing gap in our understanding of quantum entanglement and fills it with a new, more powerful set of rules. It tells us that while the universe of quantum connections is more complex than we thought, we now have the tools to navigate it, check our maps, and understand exactly where the simple rules end and the complex ones begin. It's a step forward in turning the abstract magic of quantum physics into something we can draw, count, and understand.

Technical Summary: Local Equivalences of Graph States

Problem Statement

Graph states are a fundamental family of quantum states in one-to-one correspondence with mathematical graphs, serving as essential resources for measurement-based quantum computation (MBQC), quantum error correction, and quantum networks. A central challenge in the field is classifying these states according to their entanglement. Two graph states are considered to have the same entanglement if they are LU-equivalent (Local Unitary), meaning one can be transformed into the other via single-qubit unitary operations.

A stricter, more tractable notion is LC-equivalence (Local Clifford), where the local operations are restricted to the Clifford group. It is well-established that LC-equivalence is captured exactly by a simple graphical rule called local complementation. For a long time, it was conjectured (the LU=LC conjecture) that LU-equivalence and LC-equivalence were identical for graph states. However, this conjecture was refuted by the discovery of counterexamples (e.g., a pair of 27-vertex graphs that are LU-equivalent but not LC-equivalent). Consequently, a gap exists between these two notions, and the lack of a graphical characterization for LU-equivalence has hindered the development of efficient algorithms to decide it. Prior to this work, deciding LU-equivalence required exponential time, and the structural gap between LC and LU equivalences was not fully understood.

Methodology

The thesis employs a rigorous combination of graph theory, linear algebra over finite fields, and quantum stabilizer formalism. The core methodological approach involves:

Minimal Local Sets (MLS): The author introduces and analyzes "minimal local sets," which are specific subsets of vertices in a graph related to the stabilizers of the corresponding graph state. These sets are proven to be invariant under LU-equivalence. A key theoretical result establishes that every graph admits an MLS cover (a family of minimal local sets covering all vertices), which can be computed efficiently.
Generalized Local Complementation ( $r$ -local complementation): The central innovation is the definition of $r$ -local complementation, a generalization of the standard local complementation parametrized by an integer level $r$ . This operation is defined on independent multisets of vertices and involves toggling edges based on the parity of common neighbors modulo $2^r$ .
Weighted Hypergraph States: To justify the validity of these operations within the quantum formalism, the work utilizes the framework of weighted hypergraph states. It demonstrates that specific local unitary operations (products of Hadamard gates and specific $Z$ -rotations) map graph states to other graph states if and only if the underlying graph transformation corresponds to an $r$ -local complementation.
Standard Forms and Types: By utilizing MLS covers, vertices are assigned "types" (X, Y, Z, or $\perp$ ) based on their role in the stabilizers. This allows any graph to be transformed into a "standard form" via LC operations, simplifying the comparison of LU-equivalent states.
Probabilistic Construction: For the study of universality, the thesis employs probabilistic methods on random bipartite graphs to establish bounds on vertex-minor universality.

Key Contributions and Results

1. Graphical Characterization of LU-Equivalence

The thesis proves that $r$ -local complementation fully captures LU-equivalence. Specifically:

Two graph states are LU-equivalent if and only if there exists an integer $r$ such that one graph can be transformed into the other via a sequence of $r$ -local complementations.
This provides the first purely graphical characterization of LU-equivalence, bridging the gap between the quantum definition (unitaries) and the combinatorial definition (graph operations).

2. Infinite Strict Hierarchy of Equivalences

The work defines $LC_r$ -equivalence as the equivalence relation generated by $r$ -local complementations.

It is proven that for any $r > 1$ , there exist graph states that are $LC_r$ -equivalent but not $LC_{r-1}$ -equivalent.
This establishes an infinite strict hierarchy of local equivalences lying strictly between LC-equivalence ( $LC_1$ ) and LU-equivalence. This hierarchy refines the understanding of the "gap" between local Clifford and local unitary operations.

3. Quasi-Polynomial Algorithm for LU-Equivalence

Leveraging the graphical characterization, the author designs an algorithm to decide LU-equivalence:

The algorithm decides if two graph states are $LC_r$ -equivalent in time $O(n^r)$ .
Crucially, it is proven that if two graphs are LU-equivalent, they are connected by $r$ -local complementations where $r = O(\log n)$ .
Combining these results yields a quasi-polynomial time algorithm ( $O(n^{\log^2 n})$ ) for deciding LU-equivalence, a significant improvement over previous exponential-time methods.

4. Improved Bounds for the LU=LC Property

The thesis investigates when LU-equivalence coincides with LC-equivalence (the LU=LC property):

It provides a new sufficient condition based on the standard form and the implementability of $r$ -local complementations by standard local complementations.
Using this criterion and computer-assisted exhaustive search, the author proves that all graph states on up to 19 qubits satisfy LU=LC. This improves upon the previous best-known bound of 8 qubits.
The work also confirms that certain "repeater graph states" (used in quantum networks) satisfy the LU=LC property.

5. Vertex-Minor Universality

The thesis studies graphs that are $k$ -vertex-minor universal, meaning any graph on $k$ vertices can be induced via local complementations and vertex deletions.

It establishes a lower bound on the size of such graphs, showing they must have at least a quadratic number of vertices in $k$ .
It proves the existence of $k$ -vertex-minor universal graphs with $O(k^2)$ vertices using a probabilistic construction based on random bipartite graphs, demonstrating that the quadratic bound is asymptotically tight.

Significance and Claims

The author claims that the primary contribution of this work is the introduction of generalized local complementation as an exact graphical tool for LU-equivalence. This achievement is significant for several reasons:

Theoretical Unification: It connects the quantum concept of LU-equivalence directly to graph theory, fulfilling a long-standing goal to describe entanglement properties in purely combinatorial terms.
Algorithmic Efficiency: It transforms the decision problem of LU-equivalence from an intractable exponential problem into a quasi-polynomial one, making the analysis of larger graph states feasible.
Structural Insight: The identification of the infinite hierarchy of $LC_r$ equivalences provides a much finer granularity for understanding the landscape of local equivalences, moving beyond the binary distinction of LC vs. LU.
Practical Bounds: The extension of the LU=LC property from 8 to 19 qubits provides a larger domain where efficient classical simulation and verification are possible using only Clifford operations.

The thesis concludes that these results serve as a robust bridge between quantum physics and graph theory, offering new tools for analyzing entanglement in multipartite quantum systems. The author modestly notes that while the quasi-polynomial algorithm is a major step, the existence of a polynomial-time algorithm remains an open question, as verifying the validity of an $r$ -local complementation currently involves checking a non-polynomial number of equations.