⚛️ quantum physics

What are local complementations, really?

This paper reframes local complementations on graphs as switchings of matroid bases for stabilizer states, a perspective that simplifies existing proofs and reveals deeper structural properties of graph states relevant to quantum information theory.

Original author: Kenneth Goodenough

Published 2026-11-09

📖 4 min read🧠 Deep dive

CC0 1.0

Original author: Kenneth Goodenough

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the strange and powerful world of quantum computing, information is stored in delicate systems called qubits. Unlike the bits in a standard computer that are either zero or one, qubits can exist in a blend of both states simultaneously. To manage these fragile systems, scientists use a mathematical framework known as the stabilizer formalism. Within this framework, a specific type of quantum state, called a graph state, is particularly useful. These states are defined by a network of connections, much like a social network or a map of roads, where the links between points determine how the qubits behave and interact. For decades, researchers have studied how these graph states change when we apply specific local operations, a process known as local complementation. This operation flips the connections around a single point: if two neighbors were connected, they become disconnected, and if they were not, they become connected. While this seems like a simple geometric trick, it turns out to be the key to understanding when two different-looking quantum states are actually the same in terms of their entanglement.

A researcher named Kenneth Goodenough has now offered a fresh way to look at this problem, shifting the focus from the graphs themselves to the measurements performed on the quantum system. Instead of thinking about the network of connections, Goodenough suggests we think about the set of measurements we can make on every single qubit at once. Specifically, he focuses on a special collection of measurements that, when performed, produce completely random results. In a quantum world where outcomes are often correlated or predictable, finding a set of measurements that yields total randomness is a rare and special property. Goodenough calls these special sets "bases." He demonstrates that these bases are not just random collections of measurements; they are the fundamental building blocks that generate the graphs we see. Every graph state corresponds to a specific basis, and the connections in the graph are simply a reflection of the relationships between the measurements in that basis.

The most significant discovery in this work is how these bases change when we perform operations on the system. Goodenough shows that the complex geometric operation of local complementation on a graph is actually just a simple switch in the choice of measurement for a single qubit. When a scientist changes the measurement on one qubit from one type of orientation to another, the entire underlying graph of connections flips its local structure. This insight transforms a difficult geometric puzzle into a straightforward algebraic one. By tracking how these measurement sets switch, researchers can navigate the landscape of quantum states more easily. The paper proves that this method of switching bases is not just a different way of drawing the same picture, but a more powerful tool that reveals hidden structures. For instance, it simplifies the proof of how many different graphs can represent the same quantum state and helps determine exactly how many steps are needed to transform one state into another.

Furthermore, this perspective clarifies what happens when we measure a part of a quantum system. In the traditional graph view, removing a node and its connections can be messy and hard to predict. However, using the language of bases, the process becomes clear: measuring a qubit simply removes the corresponding measurement from the set, leaving behind a smaller, well-defined set of measurements for the remaining qubits. This allows scientists to see exactly which new quantum states can be created from an original one, a concept known as a vertex-minor. The paper also addresses a subtle issue where different sets of measurements can sometimes produce the exact same graph. This happens when the quantum state has hidden symmetries, meaning it looks the same even after certain changes. Goodenough's approach makes it possible to count these symmetries and understand why some graphs appear more frequently than others in the mathematical landscape.

Ultimately, this work bridges the gap between abstract mathematics and physical quantum systems. It connects the study of these quantum states to a broader field of mathematics called matroids, which deals with the general properties of independence and structure. By viewing quantum states through the lens of these measurement bases, Goodenough provides a clearer, more unified way to understand entanglement. The findings suggest that the complex web of connections in a quantum computer is best understood not by looking at the web itself, but by observing the specific ways we choose to measure the individual threads. This shift in perspective offers a more natural path for proving difficult theorems and understanding the deep structure of quantum information, turning a peculiar geometric operation into a simple, intuitive act of changing a measurement.

Technical Summary: Local Complementations as Switchings of Stabilizer Bases

Problem Statement
Local complementation is a graph operation where the induced neighborhood of a vertex $v$ is replaced by its complement. In quantum information theory, this operation is fundamental because two graph states are related by local Clifford (LC) operations if and only if their underlying graphs are equivalent up to a sequence of local complementations. While this connection has motivated extensive research into stabilizer states via graph theory, the graph-theoretic description often obscures structural properties of the states, such as local symmetries and measurement statistics. Furthermore, proofs regarding graphs modulo local complementation can be technically cumbersome. The paper addresses the need for a more natural framework to understand local complementations and the structural properties of stabilizer states, moving beyond the specific case of graph states to arbitrary stabilizer states.

Methodology
The paper adopts a framework rooted in combinatorial mathematics, specifically the theory of matroids and multimatroids, as developed by Bouchet. The core methodology involves:

Defining Bases: The author defines a "basis" of a stabilizer state $|\psi\rangle$ as a full-weight Pauli string $B$ such that no non-empty subset of $B$ is a stabilizer of $|\psi\rangle$ . Physically, these correspond to local Pauli measurements that yield completely random (uncorrelated) outcomes.
Fundamental Graphs: For any basis $B$ , a unique "fundamental graph" $G_B$ is constructed. The vertices of $G_B$ are the qubits, and the closed neighborhood of a vertex $v$ is defined by the support of the "fundamental circuit" $g^B_v$ , which is the unique non-identity stabilizer contained in $B \cup \omega_v$ (where $\omega_v$ is the skew class of Paulis at $v$ ).
Switching: The paper introduces "switching" as an operation on bases. For a basis $B$ and a qubit $v$ , the switched basis $B \star v$ is the unique basis neighboring $B$ at $v$ (differing only at the entry for $v$ ).
Mapping: The author establishes a mapping $B \mapsto G_B$ and demonstrate that switching a basis $B$ at $v$ corresponds exactly to performing a local complementation on the fundamental graph $G_B$ at vertex $v$ .

Key Contributions and Results

Equivalence of Graphs and Bases: The paper proves (Theorem 2.11) that a graph $H$ is locally equivalent to a stabilizer state $|\psi\rangle$ if and only if $H$ is the fundamental graph $G_B$ for some basis $B$ of $|\psi\rangle$ . This establishes that the set of graphs locally equivalent to $|\psi\rangle$ is isomorphic to the set of fundamental graphs generated by its bases.
Local Complementation as Switching: Theorem 3.6 demonstrates that the operation of local complementation on graphs is precisely the image of "switching" on bases under the map $B \mapsto G_B$ . Specifically, $G_{(B \star v)} = G_B \star v$ . This reinterprets local complementations not as active transformations of a state, but as changes in the representation (basis) of a fixed state.
Simplified Proofs: The basis framework simplifies proofs for several known results regarding local equivalence:
- Upper Bound on Equivalence Class Size: It provides a straightforward proof that there are at most $3^n$ graphs locally equivalent to an $n$ -vertex graph (Theorem 4.1), derived from the fact that there are at most $3^n$ full-weight Pauli strings.
- Transformation Bounds: It offers a sketch for an upper bound on the number of local complementations required to transform one locally equivalent graph into another (Theorem 4.2).
- Circuit Properties: It simplifies the proof that any circuit $P$ of a stabilizer state can be mapped to the neighborhood of a vertex in a graph state (Theorem 4.3).
Switching Graphs vs. LC-Orbits: The paper defines the "switching graph" $S(|\psi\rangle)$ , where vertices are bases and edges represent single switchings. It shows that this graph contains more information than the standard LC-orbit graph (where vertices are graphs and edges are local complementations). The LC-orbit is a "lossy" projection of the switching graph; multiple bases can map to the same fundamental graph if the state possesses local Clifford symmetries. The ratio of the size of the switching graph to the LC-orbit equals the size of the local Clifford symmetry group (up to Paulis).
Vertex-Minors and Measurements: The paper characterizes the bases of vertex-minors (states obtained via local Pauli measurements) in terms of the bases of the original state (Theorem 4.12). It shows that the switching graphs of vertex-minors correspond to induced subgraphs of the original switching graph. This allows for the determination of entanglement properties of post-measurement states by analyzing the topology of these subgraphs (e.g., distinguishing between entangled and separable outcomes in a GHZ state).

Significance
The paper claims that viewing stabilizer states through the lens of bases and switchings provides a more general and structurally transparent perspective than restricting attention to graph states and local complementations alone. By framing these concepts within the context of multimatroids, the work:

Unifies Concepts: It connects graph states, stabilizer states, and multimatroid theory, showing that local complementations are a specific instance of basis switchings.
Clarifies Symmetries: It explicitly links the "lossiness" of the graph representation to the local Clifford symmetries of the underlying state, a connection that is obscured in the standard graph-theoretic approach.
Facilitates Analysis: It offers a simplified toolkit for analyzing entanglement, measurement statistics, and vertex-minors, turning complex graph-theoretic problems into more tractable combinatorial problems on bases.
Foundational Role: The paper serves as an introduction to the application of multimatroids in quantum information, suggesting that the rank functions and cryptomorphisms of multimatroids offer a powerful language for describing stabilizer states beyond the graph state formalism.

The author emphasizes that while concepts related to bases and switchings have appeared implicitly in previous quantum literature, this work provides the first explicit physical interpretation of these combinatorial objects and demonstrates their utility in simplifying proofs and revealing structural properties of stabilizer entanglement.

Technical Summary: Local Complementations as Switchings of Stabilizer Bases

More like this