⚛️ quantum physics

The 27-qubit Counterexample to the LU-LC Conjecture is Minimal

This paper proves that the 27-qubit graph state counterexample to the LU-LC conjecture is minimal, establishing that local unitary and local Clifford equivalence coincide for all graph states with 26 or fewer qubits.

Original authors: Nathan Claudet

Published 2026-03-27

📖 4 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 you have a giant, complex Lego structure made of 27 special blocks. In the world of quantum physics, these blocks are called qubits, and when they are linked together in a specific pattern, they form what scientists call a "graph state."

For a long time, physicists had a big question: Are there two different ways to build the exact same quantum structure?

The Big Question: The "LU vs. LC" Puzzle

Think of the "rules" for building these structures as two different toolkits:

The "Local Unitary" (LU) Toolkit: This is the Master Builder's Toolkit. It contains every possible tool you could ever need to twist, turn, and rotate a single block to change the structure. If you can turn Structure A into Structure B using any combination of these tools, they are considered "equivalent."
The "Local Clifford" (LC) Toolkit: This is the Beginner's Toolkit. It only has a few specific, simple tools (like a standard screwdriver or a basic wrench). It's much more limited.

The Conjecture (The Guess):
For years, scientists guessed that the Beginner's Toolkit was actually just as powerful as the Master Builder's Toolkit. They thought: "If you can turn Structure A into Structure B using the Master Builder's tools, you could have done it with the Beginner's tools too."

In 2007, this guess was proven wrong. Scientists found a specific 27-block structure where you could transform it using the Master Builder's tools, but it was impossible to do so with the Beginner's tools. This was the "27-qubit counterexample."

The New Discovery: "Is 27 the Smallest?"

The big mystery that remained was: Is 27 the smallest number of blocks where this trick works? Or could we find a smaller structure (say, 10 blocks or 20 blocks) that also breaks the rules?

Nathan Claudet's paper answers this with a definitive "No."

He proves that 27 is the minimum.

If you have 26 blocks or fewer, the Beginner's Toolkit is just as good as the Master Builder's Toolkit. You can always transform one structure into another using the simple tools.
You need at least 27 blocks to find a structure that requires the complex, "forbidden" tools.

How Did He Prove It? (The Detective Work)

Proving this for every possible shape of 26 blocks would be like trying to count every grain of sand on a beach. There are too many shapes (more than the number of atoms in the universe!). So, Claudet used a clever shortcut.

1. The "Magic Mirror" (Triorthogonal Codes)
Instead of looking at the Lego blocks directly, he looked at them through a "magic mirror" called Triorthogonal Codes. These are mathematical patterns used in error-correcting codes (like the ones that keep your data safe on a hard drive).

He discovered that any structure that could break the rules (the "counterexample") would have to look like a very specific, rare pattern in this mirror.

2. The "Two Rare Patterns"
When he looked in the mirror for patterns that fit the rules for 26 blocks or fewer, he only found two possible shapes.

Shape A: A 16-block structure.
Shape B: A 24-block structure.

3. The Final Check
He then tested these two shapes.

For the 16-block shape, the "complex transformation" didn't actually change the structure at all. It was a trick that did nothing.
For the 24-block shape, the "complex transformation" could actually be done with the simple Beginner's Toolkit after all.

The Conclusion:
Since the only two candidates that could have broken the rules turned out to be innocent, no structure with 26 or fewer blocks can break the rules.

The Takeaway

Think of it like a video game level.

Levels 1–26: The game is "fair." The simple controls work just as well as the advanced cheats.
Level 27: This is the first level where the game changes. You suddenly need the advanced controls to solve the puzzle.

This paper closes the door on the question of "how small can this get?" It confirms that 27 is the magic number where the complexity of quantum entanglement reveals a hidden depth that simple rules can't explain. This helps scientists understand exactly where the "magic" of quantum computing begins to get truly strange.

1. Problem Statement

The paper addresses a fundamental question in quantum information theory regarding the classification of graph states (a versatile family of entangled quantum states). The core problem revolves around the relationship between two equivalence relations:

LU-equivalence (Local Unitary): Two states are equivalent if they can be transformed into one another using single-qubit unitary operators.
LC-equivalence (Local Clifford): A stricter subset of LU-equivalence where the single-qubit operators must belong to the Clifford group.

The LU-LC Conjecture: It was previously conjectured that for any graph state, LU-equivalence implies LC-equivalence ($LU = LC$).
The Counterexample: In 2007, Ji et al. disproved this conjecture by discovering a pair of 27-qubit graph states that are LU-equivalent but not LC-equivalent.
The Open Question: Since 2007, it remained unknown whether this 27-qubit example was the minimal counterexample. Specifically, does $LU = LC$ hold for all graph states with $n \leq 26$ qubits?

2. Methodology

The author employs a novel approach combining graph theory, quantum error correction, and algebraic coding theory to solve the minimality problem without resorting to brute-force enumeration (which is computationally impossible for 26 qubits due to the sheer number of graphs, $\sim 10^{71}$ ).

A. $r$ -local Complementation

The paper utilizes the recently introduced formalism of $r$ -local complementation:

Local Complementation (1-local): Captures LC-equivalence.
$r$ -local Complementation: Captures LU-equivalence for specific classes of states.
Key Insight: For graph states with up to 31 qubits, two states are LU-equivalent if and only if their graphs are related by a sequence of local complementations containing at most one 2-local complementation.
Therefore, a counterexample for $n \leq 31$ must involve a 2-local complementation that cannot be simulated by standard local complementations.

B. Reduction to Bipartite Graphs and Triorthogonal Codes

The author reduces the search space using Lemma 1, which proves that if a counterexample exists for $n \leq 31$ , there must exist a specific type of bipartite graph satisfying five strict properties:

At most $n+1$ vertices.
Every vertex has an odd degree $\geq 3$ .
No two distinct vertices are "twins" (sharing the exact same neighborhood).
One partition set ( $S$ ) is 2-incident (a specific parity condition on common neighbors).
The 2-local complementation on $S$ cannot be achieved by any local complementation on a subset of $S$ .

The paper then establishes a bijection between these specific bipartite graphs and unital triorthogonal subspaces (a class of quantum error-correcting codes used in magic state distillation).

Mapping: A bipartite graph $G$ with partitions $S$ and $V \setminus S$ maps to a matrix $M_G = [I | A]$ , where $A$ is the biadjacency matrix.
Triorthogonality: The graph properties (odd degrees, no twins, 2-incidence) correspond exactly to the conditions defining a unital triorthogonal code (columns have odd weight, no repeated columns, and the product of any three rows has even weight).

3. Key Contributions

Proof of Minimality: The paper provides a rigorous proof that the 27-qubit counterexample is minimal. It demonstrates that no graph state with $n \leq 26$ qubits can violate the LU-LC conjecture.
Classification via Coding Theory: Instead of generating graphs, the author leverages the classification of small unital triorthogonal subspaces (previously classified by Nezami and Haah).
Exhaustive Verification of Candidates: The author identifies that only two unital triorthogonal subspaces correspond to graphs with $\leq 27$ $\leq 27$ vertices:
- A subspace corresponding to a 16-vertex graph.
- A subspace corresponding to a 24-vertex graph.
Disproof of Counterexamples in Candidates:
- For the 16-vertex graph, the 2-local complementation leaves the graph invariant (it does not change the graph structure), so it cannot generate a distinct LU-equivalent, non-LC-equivalent state.
- For the 24-vertex graph, the 2-local complementation can be implemented using standard local complementations (specifically, a single local complementation on a specific vertex).
- Consequently, neither candidate satisfies Property 5 of Lemma 1, proving no counterexample exists for $n \leq 26$ .

4. Results

Theorem 1: $LU = LC$ holds for all graph states on up to 26 qubits.
Corollary 1: Since any stabilizer state is LC-equivalent to a graph state, $LU = LC$ holds for all stabilizer states on up to 26 qubits.
Minimality Confirmed: The 27-qubit counterexample (and its 28-qubit variant) is indeed the smallest possible system where LU-equivalence does not imply LC-equivalence.
Hierarchy Definition: The paper defines $c(r)$ as the minimal number of qubits required for a pair of graph states to be equivalent under level $r+1$ of the Clifford hierarchy but not level $r$ . The paper proves $c(2) = 27$ .

5. Significance

Resolution of a Long-standing Open Problem: This work closes the question of the minimality of the LU-LC counterexample, which had been open since 2007.
Methodological Advancement: It demonstrates a powerful technique of translating quantum state equivalence problems into the language of triorthogonal codes and Reed-Muller codes. This avoids the intractable combinatorial explosion of graph enumeration.
Implications for Quantum Computing:
- Error Correction: The connection to triorthogonal codes (crucial for magic state distillation) deepens the understanding of the relationship between graph state entanglement and fault-tolerant quantum computing.
- Algorithmic Complexity: The results inform the complexity of deciding LU-equivalence. While the paper notes that an efficient algorithm for general LU-equivalence remains an open question, the structural insights provided here are vital for developing such algorithms.
Future Directions: The paper opens the door to investigating higher-order counterexamples ( $c(r)$ for $r \geq 3$ ), suggesting a potential strict hierarchy of local equivalences that grows exponentially or super-exponentially with $r$ .

In summary, the paper proves that the "breakdown" of the LU-LC conjecture is a phenomenon that only occurs in systems of 27 qubits or larger, achieved by mapping the problem to the classification of small triorthogonal codes and showing that no smaller codes possess the necessary structural properties to generate a counterexample.