What are local complementations, really?

Introduction

Motivation

A local complementation at a vertex $v$ replaces the induced neighborhood of that vertex with its complement [38]. Famously, two graph states $|G\rangle$ and $|H\rangle$ are related by local Cliffords if and only if $G$ and $H$ are equivalent up to a sequence of local complementations [61]. This connection has motivated substantial work in quantum information on studying stabilizer states through graphs modulo local complementation [32, 43, 41, 24, 4, 60, 29, 31, 2, 27, 26, 28, 47, 22, 49, 19, 48, 46, 36].

Characteristically, local complementations were studied by mathematicians decades before they made their way to the quantum world. One of the first mathematicians to do so was Kotzig [51], followed by Rosenstiehl, Read [59], and de Fraysseix [35], showing surprisingly deep connections with other topics in combinatorics. These ideas were taken up by Bouchet [7, 10], who soon realized the connection between graphs up to local complementations, 4-regular multigraphs [11, 16], and isotropic systems [5, 8, 6], the latter of which are known to be stabilizer groups when ignoring phases of the stabilizers [29]. Bouchet’s line of thought culminated with his introduction of multimatroids, a combinatorial object that vastly generalizes matrices and graphs, in an attempt to better understand local complementations [12, 13, 15, 14]. More specifically, Bouchet found that graphs up to local complementations are better understood as (matroid) bases up to switching. This leads, among other things, to simpler proofs on stabilizer entanglement, of which we provide several examples. We note that some of these concepts have implicitly appeared already in the quantum literature, albeit without providing a physical interpretation of bases and switchings, see e.g. Refs. [32, 30, 31].

This paper provides an exposition of some of Bouchet’s ideas in terms of quantum information, alongside some new results. We are hopeful that these ideas will provide a more general perspective on stabilizer entanglement than can be obtained by restricting attention to graph states alone [44].

Overview

The connection between graphs and bases can be summarized with the following diagram.

At the bottom we have the familiar picture: a graph $G_B$ is transformed to another graph $G_B \star v$ by locally complementing at the vertex $v$. At the top we have a basis $B$ being mapped to a new basis $B \star v$ by switching at qubit $v$; we will define bases and switchings later. For now, suffice to say that a basis of a stabilizer $|\psi\rangle$ is a full-weight Pauli string satisfying a certain property with respect to $|\psi\rangle$. Furthermore, for each qubit $v$, switching a basis $B$ at $v$ yields a new basis $B \star v$. Note the analogy with graphs and local complementations: for each $v$, locally complementing $G$ at $v$ yields a graph $G \star v$.

This analogy is made precise by the map $B \mapsto G_B$; for each basis $B$, there is a unique graph—called the fundamental graph $G_B$ with respect to $B$—such that $G_B \star v = G_{(B\star v)}$. That is, locally complementing a fundamental graph $G_B$ at $v$ yields the fundamental graph $G_{(B\star v)}$ with respect to the switched basis $B \star v$.

In section 2 we will define and explain bases and fundamental graphs; we show how switchings on bases abstract local complementations in section 3. In section 4 we will discuss some of the benefits bases have over graphs. We will show that 1) bases allow for simplified proofs of statements of graphs up to local complementations, 2) show that the map $B \mapsto G_B$ is ‘lossy’, and how this is connected with local symmetries of the underlying state, and 3) that bases are well-behaved under local Pauli measurements, and use this to relate bases to so-called vertex-minors. We conclude in section 5 by discussing how the study of bases naturally leads one to study stabilizer states through the lens of multimatroids.

Notation, conventions and terminology

We will assume basic familiarity with graph theory/graph states, linear algebra, and the stabilizer formalism. We’ll freely convert between vertices and qubits depending on the context, and use $V = \{1, 2, \ldots, n\}$ for the set of vertices/qubits. Adjacency of two vertices $v, w$ of a graph $G$ is denoted by $v \sim_G w$. The neighborhood of a vertex $v$ in a graph is denoted by $N_v$, and the closed neighborhood by $\overline{N}_v = N_v \cup\{v\}$. For a Pauli string $P$, $P_v$ denotes the entry of $P$ at $v$. The canonical generators of a graph state $|G\rangle$ are of the form $X_v Z_{N_v}$ for each qubit $v$. A local complementation at a vertex $v$ is denoted by $G \mapsto G \star v$, and we say that two graphs are locally equivalent if they are related by a sequence of local complementations. Following [44], we extend this terminology to arbitrary stabilizer states: $|\psi\rangle$ and $|\phi\rangle$ are locally equivalent if the states are equivalent up to local Cliffords, and write this as $|\psi\rangle\simeq_{\mathrm{LC}} |\phi\rangle$.

We’ll ignore phases of all Pauli strings, since it is in this setting that the connection with multimatroids/bases becomes most apparent. This also means that we treat $X$, $Y$, $Z$ as just labels, and not as matrices. For each $v$, the skew class is $\omega_v = \{X_v,Y_v,Z_v\}$, the set of non-identity Paulis acting on $v$. Single-qubit Cliffords have then a simple interpretation: they are precisely the six ways of relabeling a skew class. Importantly, it will be convenient to treat Pauli strings $P$ not just as the tensor product of all the $\{P_v\}_{v\in V}$, but as sets containing the non-identity elements of $P$. As an example, $P = IXYZ \simeq\{X_2,Y_3,Z_4\}$, so that $IY Z \subseteq P$, but $XYXI \not\subseteq P$. Finally, $A\mathbin{\triangle}B$ denotes the symmetric difference of the sets $A$ and $B$.

Fundamental graphs and bases

We first motivate fundamental graphs by showing how they recover the graphs of graph states. Afterwards we define bases and give them a physical interpretation, and show how bases can be used to define fundamental graphs for arbitrary stabilizer states.

A simple graph state example

Assume we fix some graph state $|G\rangle$ on qubits $V$, with $|V|=n$. Let $B=Z^{\otimes n}$ be the all-$Z$ string. We’ll use the graph state below as an example in this subsection.

The element $Z_v\in B$ is highlighted inside each skew class $\omega_v:=\{X_v,Y_v,Z_v\}$, where we interpret the Pauli string $B$ as a set containing all the $Z_v$ elements, see subsection 1.3. For each $v\in V$, the set $B\cup\omega_v=\{Z_1,Z_2,\ldots,Z_n,X_v,Y_v\}$ contains the canonical graph state generator $g_v=X_vZ_{N_v}$. See below the case of $v=2$, yielding $g_2=ZXZIZ$ (highlighted in red).

In fact, $g_v$ is the unique non-identity stabilizer in $B\cup\omega_v$. Note that the uniqueness of $g_v$ implies that the only stabilizers contained in $g_v$ itself are the identity and $g_v$ itself. Stabilizers such that the only stabilizers contained in them are themselves and the identity are called circuits², and the reader might find it helpful to compare this definition with that of a prime number³. In particular, we will call $g_v$ the fundamental circuit with respect to $B$ and $v$. Note that the graph $G$ can be reconstructed from the fundamental circuits $\{g_v\}_{v\in V}$, since the support of each $g_v$ is just the closed neighborhood $N_v$ of $v$.

Bases

In the previous example we showed how one can recover the canonical graph state generator $g_v = X_v Z_{N_v}$ as the unique circuit contained in $B \cup\omega_v$, when $B = Z^{\otimes n}$. So far, this appears to be a rather contrived way to think of the canonical generators of a graph state. This approach has the benefit, however, that it extends to arbitrary stabilizer states $|\psi\rangle$, and more general Pauli strings than $Z^{\otimes n}$. The Pauli strings we consider are called (matroid) bases of the state $|\psi\rangle$ and are defined in the following manner.

When the state under consideration is unimportant or clear from the context, we will write $\mathcal{B} = \mathcal{B}_{\psi}$. Here are some examples of bases.

Bases can be interpreted as Pauli measurements that yield maximally random outcomes. To make this concrete, assume the setting where each qubit of a stabilizer state is separated in space, such that only local measurements can be performed. A Pauli string $P$ then specifies a measurement in the following manner: perform the local Pauli measurement $P_v$ for each qubit $v \in\operatorname{supp}(P)$, where $\operatorname{supp}(P)$ denotes the support of $P$. Bases then have the following clean physical interpretation: measuring each qubit $v$ according to $B_v$ will yield all $2^n$ possible measurement outcomes uniformly at random, see [44]. In particular, this means there are no correlations whatsoever among the outcomes.

Example 2.8. Measuring every qubit of a graph state in the computational basis yields completely random outcomes. This can be seen from the well-known expansion of graph states in the computational basis [49]:

where $A$ is the adjacency matrix of $G$. Since this is a superposition over all computational basis vectors whose amplitudes all have equal magnitude $\frac{1}{\sqrt{2^n}}$, measuring every qubit in $Z$ yields a uniformly random computational basis state. This reconstructs the statement from example 2.4, namely that $Z^{\otimes n}$ is a basis for every graph state $|G\rangle$.

The term ‘basis’ comes from matroid theory, where they generalize the notion of a basis in linear algebra. Note that a basis in linear algebra is a set of vectors $B$ that is linearly independent, and for which it is impossible to add any other vector to $B$ such that the new set remains linearly independent. Note how this is analogous to bases of stabilizer states: a basis $B$ is a collection of measurements such that 1) the measurement outcomes are independent, in the sense that all possible bitstrings are equally likely as outcome, and 2) for which one cannot add any other measurements, for the simple fact that all qubits have been measured already. For more information on this analogy, see [44, 12].

At first sight, bases appear to be rather useless measurements, since they yield completely random outcomes. In the next subsection, however, we show that they provide a natural abstraction of graphs up to local complementations.

Fundamental graphs of bases

Generalizing the example from subsection 2.1, we now show how to assign a fundamental graph $G_B$ to each basis $B \in\mathcal{B}_\psi$.

We will deal with the general case, but show as a running example in the figures the case of a three-qubit GHZ state $|\mathrm{GHZ}\rangle\propto|000\rangle+ |111\rangle$ and the basis $B = XYZ$. This state has, up to phases, the following stabilizer group

from which it can be checked that $B = XYZ$ is indeed a basis.

To start, let $|\psi\rangle$ be an arbitrary stabilizer state, and $B \in\mathcal{B}_\psi$ an arbitrary basis.

For each qubit $v$, the fundamental circuit $g_v^B$ of $|\psi\rangle$ with respect to $B$ and $v$ is the unique circuit contained in $B \cup\omega_v$. This is the exact same definition as from section 2, but extended to arbitrary bases and stabilizer states.

We show below the fundamental circuits of $|\mathrm{GHZ}\rangle$ with respect to $B$.

With the fundamental circuits with respect to $B$ in hand, we can define the fundamental graph $G_B$.

For the example of a GHZ state $|000\rangle+ |111\rangle$ and $B = XYZ$, $G_B$ is the star graph with vertex $3$ as its center. This follows from the fact that $\operatorname{supp}(g_1^{XYZ}) = \{1,3\}$, $\operatorname{supp}(g_2^{XYZ}) = \{2,3\}$, and $\operatorname{supp}(g_3^{XYZ}) = \{1,2,3\}$.

The choice of basis $B$ in the above was arbitrary. What happens if we choose a different basis $B'$? As an example, the fundamental graph $G_{B'}$ with $B' = XYX$ for $|\mathrm{GHZ}\rangle$ is the complete graph on $3$ vertices. This follows since, with respect to this new basis $B'$, the fundamental circuits all have full support:

Comparing $G_B$ and $G_{B'}$, we find them to be equivalent after a local complementation at vertex $3$. This is not a coincidence, as the following theorem shows.

This theorem states that the fundamental graphs associated to a state $\lvert\psi\rangle$ are precisely the graphs whose graph states are locally equivalent to $\lvert\psi\rangle$. Since a fundamental graph $G_B$ is defined relative to a basis $B \in\mathcal{B}$, it is natural to wonder if local complementations have an analogue in terms of bases. As a hint for what is to come, observe that for the example of the GHZ state, the two bases $B = XYZ$ and $B' = XYX$ differ only in their third entry, while the two fundamental graphs $G_B$ and $G_{B'}$ are related by a local complementation on the third vertex.

Local complementations as switching on bases

Recall that we are looking to complete the following diagram,

Constructing the fundamental graph $G_B$ from a given basis $B$ was discussed in the previous section, so it remains to define the appropriate operation $B \mapsto B \star v$ on bases in the above diagram. We refer to this operation as switching $B$ at $v$ [15].

Two natural constraints for a switching $B \mapsto B \star v$ are to 1) demand that $B \star v$ is a basis, and 2) that $B$ and $B \star v$ differ only in the entry at $v$. The following theorem by Bouchet—which we reformulate and reprove in quantum information terms—states that these constraints are enough to define $B \star v$.

We will prove this shortly. In the meantime, theorem 3.2 allows us to define switchings on bases.

Before proving theorem 3.2, we will need the following incredibly useful property of stabilizer states under Pauli measurements [45, 1]. We provide a proof in the appendix for completeness, see A.7.

As a simple example, measuring the first qubit of $|00\rangle+ |11\rangle$ in $Z$ will collapse the second qubit to either $|0\rangle$ or $|1\rangle$ depending on the measurement outcome. Property 3.5 now allows for a simple proof of theorem 3.2.

Proof of theorem 3.2. We want to prove that, for every basis $B \in\mathcal{B}$ and every qubit $v$, there exists a unique basis $B' \in\mathcal{B}$ such that $B$ and $B'$ are neighboring at $v$.

Let $|\psi\rangle$ be an arbitrary stabilizer state, with qubits $1,2,\ldots,v,\ldots,n$. We visualize this as follows.

Let $B$ be a basis, and imagine that every qubit $i$ of $|\psi\rangle$ has been measured in $B_i$, save for the qubit $v$. In other words, we measure according to $P = B \setminus\{B_v\}$. Using property 3.5, the qubit $v$ will be projected into an eigenstate $|R_{\pm}\rangle$ of some single-qubit Pauli operator $R$. Here $R$ is an element of the skew class $\omega_v = \{X_v,Y_v,Z_v\}$ of $v$, independent of the measurement outcomes on the other qubits.

Since the qubit at $v$ is an eigenstate of $R$, measuring $v$ in $R$ will lead to a non-random outcome. As such, $P \cup R$ is not a basis. The converse also holds: measuring qubit $v$ in any of the two remaining Pauli operators $R'$ that is not $R$ will lead to random measurement outcomes on $v$. This means that $P \cup R'$ is a basis as long as $R \ne R'$. One of the two options for $R' \in\omega_v \setminus\{R\}$ is $B_v$. Since we want $B'$ to be different from $B$, the only option is to change $B_v$ to the unique remaining element in $\omega_v \setminus\{B_v,R\}$.

We now show that switchings really do generalize local complementations.

Proof. Recall that the closed neighborhood of a vertex $v$ in a fundamental graph $G_B$ is given by $\operatorname{supp}(g^B_v)$, where $g^B_v$ is the unique non-identity stabilizer contained in $B \cup\omega_v$ (definitions 2.10 and 2.9). Let $D = B \star v$, and $w$ an arbitrary vertex distinct from $v$. To prove the above theorem, we compare the supports of $g^B_v$ and $g^D_v$, and $g^B_w$ and $g^D_w$. We split the latter case in two: when $w$ is not adjacent to $v$ and when $w$ is adjacent to $v$. We show that these supports match exactly the closed neighborhoods after locally complementing $G_B$ at $v$, proving the claim.

First, $\operatorname{supp}(g^B_v) = \operatorname{supp}(g^D_v)$. This follows from the fact that $B \cup\omega_v = D \cup\omega_v$, since $B$ and $D$ are neighboring at $v$. Second, $\operatorname{supp}(g^B_w) = \operatorname{supp}(g^D_w)$ when $w$ is not adjacent to $v$. To see this, note that by definition of the fundamental graph (definition 2.10), we have that $v \notin\operatorname{supp}(g_{w}^{B})$. Since $B$ and $D$ are neighboring at $v$, it follows that $g_{w}^{B}$ is also contained in $D \cup\omega_{w}$, so that $g_{w}^{B} = g_{w}^{D}$, and in particular their supports are the same. We thus find that the closed neighborhoods of $v$ and any $w$ not adjacent to $v$ in $G_{B\star v}$ are the same as the closed neighborhoods of $G_{B}\star v$.

The remaining case of $w$ adjacent to $v$ is more complicated. As before, we need to find the support of $g_{w}^{D}$. We claim that $g_{w}^{D} = g_{v}^{B} \cdot g_{w}^{B}$ (where we ignore phases as usual). To prove this, we need to show that $g_{v}^{B} \cdot g_{w}^{B}$ is a stabilizer contained in $D \cup\omega_{w}$. Clearly $g_{v}^{B} \cdot g_{w}^{B}$ is a stabilizer, since it is a product of stabilizers, so it remains to show that $g_{v}^{B} \cdot g_{w}^{B} \subseteq D \cup\omega_{w}$. But for every $i \ne v,w$, both $g_{v}^{B}$ and $g_{w}^{B}$ have either $I_i$ or $B_i$ as their entry at $i$. Their product therefore has either $I_i$ or $B_i$ as its $i$’th entry. At $i = w$ there is no restriction, since the entire skew class $\omega_w$ is contained in $D \cup\omega_w$. It remains only to consider the entry at $v$. The $v$’th entry of $g_{v}^{B}$ is the unique element in $\omega_v \setminus\{B_v,D_v\}$, while the $v$’th entry of $g_{w}^{B}$ is $B_v$. As such, their product equals $D_v$, so that indeed $g_{v}^{B} \cdot g_{w}^{B} \subseteq D \cup\omega_w$. Thus, by the uniqueness of fundamental circuits, we have that $g_{w}^{D} = g_{v}^{B} \cdot g_{w}^{B}$.

The fundamental circuit $g_{w}^{D}$ has the desired support of

since the closed neighborhood of $w$ after complementing the graph $G_B$ at $v$ equals $N_v \mathbin{\Delta} N_w$. The equality in Eq. (2) holds since both $g_{v}^{B}$ and $g_{w}^{B}$ have either $I_i$ or $B_i$ for their $i$’th entry, as long as $i \ne v,w$. For $i \in\{v,w\}$, the entries of $g_{v}^{B}$ and $g_{w}^{B}$ at $i$ are two distinct non-identity Paulis, so that their product is a non-identity Pauli as well.

So what are local complementations, really?

We now briefly summarize how graphs up to local complementations are better thought of as bases up to switchings. Bases are precisely the local Pauli measurements on all qubits that yield completely random outcomes on a given state $|\psi\rangle$ (property 2.6). For each such basis $B$, there is an associated fundamental graph $G_B$ (definition 2.10), such that $|\psi\rangle\simeq_{\mathrm{LC}} |G_B\rangle$, and every graph state $|H\rangle$ locally equivalent to $|\psi\rangle$ satisfies $H = G_B$ for some $B$ (theorem 2.11). Finally, switchings on bases (definition 3.3) generalize local complementations, in the sense that $G_{B\star v} = G_B \star v$.

Switching a basis $B$ at a vertex $v$ has a concrete physical interpretation: measuring according to $B \setminus\{B_v\}$ leaves qubit $v$ in an eigenstate of a Pauli operator $R$. Of the three Paulis at $v$, measuring in $R$ would yield a deterministic outcome, while the other two measurements yield random outcomes. Switching $B$ at $v$ replaces $B_v$ by the unique other Pauli that is not equal to $R$.

The fundamental graphs $G_B$ also carry a concrete physical interpretation. Measuring each qubit according to $B$ yields random measurement outcomes. By changing the measurement $B_v$ at a qubit $v$ appropriately, the outcomes are no longer random. More specifically, correlations will now be observed among the measurement outcomes on the support of the fundamental circuit $g_{v}^{B}$. The fact that $g_{v}^{B}$ is the unique circuit contained in $B \cup\omega_v$ implies that these are the only correlations observed.

Note how the fundamental graphs and bases are properties of a fixed stabilizer state $|\psi\rangle$. This is quite different from how local complementations are normally interpreted in the quantum info literature. Namely, a local complementation at $v$ corresponds to a Clifford operator $\sqrt{X_v}\prod_{w\in N_v}\sqrt{Z_w}$, mapping $|G\rangle$ to $|G\star v\rangle$. Arguably the perspective where the state is fixed and one considers different representations is more natural than actively changing the state. We provide an interactive visualization of the above ideas in [23], which—perhaps not surprisingly—was created entirely by ChatGPT.

In the next section, we will see what the vantage point above gives us.

What use are bases?

Bases as a proof technique

At this point, it is natural to wonder what switchings on bases buy us that we cannot get from local complementations on graphs. Indeed, in many settings, working with bases is more natural than working with graphs. For example, bases have been used in [31] to prove that the so-called vertex-minor problem is NP-complete, in [29] to prove that counting the number of graphs locally equivalent to a given graph is #P-complete, and in [3] to understand local equivalence for the qudit case⁴.

We now provide three statements on graphs up to local complementations that are more easily proved using bases.

Proof. Theorem 2.11 tells us that for each graph $H$ locally equivalent to $G$, there is a basis $B$ of $|G\rangle$ such that $G_B = H$. This implies that there are at least as many bases of $|G\rangle$ as there are graphs locally equivalent to $G$. Thus, to upper bound the number of elements in the equivalence class, it suffices to upper bound the number of bases.

Here is a seemingly ‘cheap’ such upper bound: since bases need to be full-weight Pauli strings, clearly there can be no more bases than there are full-weight Pauli strings, i.e. $|B| \le3^n$.

The above bound might sound loose, but random graph states achieve $|B| \sim c \cdot3^n$ for some explicitly known constant $c$! We prove this result in follow-up work.

How about bounding the number of local complementations needed to go from $G$ to $H$ when $G$ and $H$ are locally equivalent?

Proof. We provide here a sketch of the proof, see theorem A.2 in the appendix for more details.

It suffices to prove that we need at most $\frac{3}{2}n$ switchings to map any basis $B$ to another basis $B'$. We first perform switchings at vertices $v$ that take $B_v$ to $B'_v$. At a certain point, no such vertices exist anymore. We then show that so-called pivots [56, 15] on certain pairs of vertices $v,w$ allow us to map both $B_v$ and $B_w$ to $B'_v$ and $B'_w$, respectively. Such pivots are implemented by switching on $v$, $w$ and again on $v$, and thus allow us to map two entries of $B$ to two entries of $B'$. Since three switches ‘fix’ two entries, we find an upper bound of $\frac{3}{2}n$. The technical part of the proof involves showing that such pairs $v,w$ always exist, i.e. that one cannot get ‘stuck’ during this process.

While the bound in theorem 4.2 achieves the right scaling, it is not tight. See reference [37] for the stronger upper bound of $\max\left(n+1,\frac{10}{9}n\right)$ (see also Ref. [9]).

Recall from section 2 that a circuit is a Pauli string $P$ such that the only stabilizers in $P$ are the identity and $P$ itself. The following theorem on circuits is surprisingly messy to prove without using the concept of a basis, see for example Ref. [42].

Theorem 4.3 (Circuits to canonical generators of graphs [18]). Let $P$ be a circuit of a stabilizer state $|\psi\rangle$, and let $v \in\operatorname{supp}(P)$ be arbitrary. Then $|\psi\rangle$ is local-Clifford equivalent to a graph state $|G\rangle$ such that the neighborhood of $v$ in the graph $G$ equals $\operatorname{supp}(P) \setminus\{v\}$.

To prove it, we use the following lemma.

Proof. See lemma A.1 in the appendix.

Proof of theorem 4.3. Consider the case where each qubit $i \in\operatorname{supp}(P) \setminus\{v\}$ is measured according to $P_i$. Since $P$ is a stabilizer, qubit $v$ will be left in an eigenstate of $P_v$ (see property 3.5).

Now change $P_v$ to one of the two non-identity Paulis $P'_v$, yielding another Pauli string $Q := P \triangle\{P_v, P'_v\}$. Since $P$ is a circuit, measuring the qubits according to $Q$ yields completely random outcomes. Using lemma 4.4, we can extend $Q$ to a basis $B$, i.e. there exists $B \in\mathcal{B}_{\psi}$ such that $Q \subseteq B$.

By construction, the neighborhood of the vertex $v$ in the fundamental graph $G_B$ equals $\operatorname{supp}(P) \setminus\{v\}$. To see this, note that $B \cup\omega_v$ contains the stabilizer $P$, so that $g_v^B = P$ by definition 2.9. Thus by definition 2.10, $|\psi\rangle$ has a basis $B$ such that the fundamental graph $G_B$ has the desired closed neighborhood of $v$. From theorem 2.11 we have then that $|\psi\rangle\simeq_{\mathrm{LC}} |G_B\rangle$, proving the claim.

Switching graphs

The set of bases $\mathcal{B}_{\psi}$ of a state $|\psi\rangle$ carries more than just a set structure. Namely, two bases $B$ and $B'$ are ‘close’ if they differ by a single switching. This motivates the definition of a switching graph [9].

The switchings at qubits 1 and 2 are labelled by red and blue edges, respectively. E.g., performing a switching at qubit 1 on $B = YX$ yields $XX$ for the $|00\rangle$ state; switching at qubit 2 on $B = YZ$ yields $YX$ for $|00\rangle+ |11\rangle$.

Here red corresponds to switching on the first qubit, and blue and green correspond to the second and third qubit, respectively.

Since local Cliffords only relabel the vertices, the switching graphs (up to isomorphism) are an invariant under local Cliffords. In fact, something stronger is true: the bases (and thus the labelled switching graph as well) specify a stabilizer state uniquely up to Pauli unitaries, see [12].

The reader may have noticed the similarities between the switching graph and LC-orbits of graphs/graph states [2]. Here, the LC-orbit of $G$ is itself a graph $\mathit{LC}(|G\rangle)$, whose vertex set equals the whole equivalence class of $G$, and where $H$ and $K$ are adjacent $\Longleftrightarrow$ $H$ and $K$ are related by a single local complementation [2].

LC-orbits have been studied in [2, 20, 19, 58, 33, 39], where in particular attempts have been made to connect entanglement properties of $|G\rangle$ with properties of the graph $\mathit{LC}(|G\rangle)$. It is however easy to see that $\mathit{LC}(|G\rangle)$ cannot say much about entanglement of $|G\rangle$ itself. This is because both $|\bullet\bullet\rangle:= |++\rangle$ and $|\bullet\text{-}\bullet\rangle:= CZ|++\rangle$ are invariant under local complementations, meaning that both $\mathit{LC}(|\bullet\bullet\rangle)$ and $\mathit{LC}(|\bullet\text{-}\bullet\rangle)$ are trivial graphs! In contrast, the switching graphs $S(|\bullet\bullet\rangle)$ and $S(|\bullet\text{-}\bullet\rangle)$ are isomorphic to the switching graphs from example 4.6, and thus can distinguish the two states (and their entanglement) from one another.

Let us briefly detail why the LC-orbit loses information that is contained in the switching graph. From subsection 2.3, every basis $B$ has an associated fundamental graph $G_B$. In certain cases, different bases $B, B'$ have the same fundamental graph, i.e. $G_B = G_{B'}$. The states $|00\rangle$ and $|00\rangle+ |11\rangle$ are extreme examples of this, where every basis has the same fundamental graph.

This phenomenon was already observed by Bouchet in [10], where he noted that the preimage of any $G_B$ under the map $B \mapsto G_B$ has the same cardinality $k$, independent of $G_B$. This implies that

Bouchet describes in [10] a technique to calculate the quantity $k$, which he calls the index. These observations were used in [29] to prove that counting the number of locally equivalent graphs is #P-complete.

Bouchet expresses the computation of $k$ in terms of the so-called bineighborhood of graphs [10]. There is, however, a simple conceptual interpretation of the parameter $k$ in terms of quantum information. Two bases $B, B' \in\mathcal{B}_{\psi}$ map to the same fundamental graph $G_B = G_{B'}$ if and only if there is a local Clifford symmetry $C = \bigotimes_{v \in V} C_v$ of $\lvert\psi\rangle$ such that $B' = CBC^{\dagger}$.⁵ As such, $k$ is equal to the cardinality of the group of local Clifford symmetries of $\lvert\psi\rangle$. We provide two examples of this fact, and leave a proof to the appendix, see theorem A.3.

In the above example, the local Clifford symmetries of $\lvert K_3\rangle$ cause four distinct bases to share each fundamental graph, so that the LC-orbit $\mathcal{LC}(\lvert K_3\rangle)$ loses information that the switching graph $\mathcal{S}(\lvert K_3\rangle)$ retains. Luckily such symmetries are not generic: we show in theorem A.4 in the appendix that, with high probability, $k = 1$ for random graph states. In this case, the map $B \mapsto G_B$ is a bijection from bases to the fundamental graphs of the state.

Vertex-minors

Bases are particularly well-behaved with regard to so-called vertex-minors. Vertex-minors are a well-studied subject in both the math [55, 56, 21] and the quantum information literature [32, 31, 44, 34]. Informally, the vertex-minors of a stabilizer state $|\psi\rangle$ are all the states that can be reached from $|\psi\rangle$ using local operations within the stabilizer formalism.

We note that vertex-minors are commonly expressed in terms of graphs/graph states only; we use the more general notion for stabilizer states, as used in [44].

The bases of vertex-minors of $|\psi\rangle$ are easily expressed in terms of the bases of $|\psi\rangle$. To provide some intuition, we will consider the particularly simple setting where $P$ is contained in at least one basis $B$ of $|\psi\rangle$; we give the general case in the appendix, see theorem A.5.

Proof. Since $P$ is a subset of some basis $B$, the outcomes of measuring $P$ are themselves uniform. A Pauli string $B'$ on the remaining qubits is a basis after the measurement exactly when the joint measurement $P \cup B'$ was completely random before the measurement.

Here are some examples.

Proof. The case where $P \subseteq B$ for some basis follows from theorem 4.12. The case when $P$ is not contained in any basis $B$ is dealt with in theorem A.5 in the appendix, and does not introduce any new vertex-minors. This last fact follows from the scum theorem for multimatroids [13, 25].

Here we have highlighted the three subgraphs of the switching graph $\mathcal{S}(|K_3\rangle)$ whose vertices are the bases with their first entry equal to $X$, $Y$ and $Z$, respectively. The subgraph corresponding to $X$ (red vertices) forms a six-cycle, and we recognize this as the switching graph of a two-qubit entangled stabilizer state, see example 4.6. In other words, measuring the first qubit of $|K_3\rangle$ in $X$ yields (up to rotations) a Bell pair on the remaining two qubits. Something similar holds for measuring in $Z$: the subgraph of bases with first entry equal to $Z$ forms a six-cycle as well (green vertices), so measuring the first qubit in $Z$ will yield an entangled state. Conversely, measuring the first qubit in $Y$ will leave the remaining two qubits unentangled, since the subgraph corresponding to $Y$ (blue vertices) is a four-cycle, i.e., the switching graph of a separable two-qubit state.

Last but not least, bases serve as a natural introduction to multimatroids.

Multimatroids

In this paper the bases $\mathcal{B}$ were the main actors. These are the local Pauli measurements on all qubits such that each of the $2^n$ outcomes is equally likely. Naively such measurements would seem useless to understand entanglement. We have seen, however, that bases suitably generalize the notion of graphs, and that switchings generalize the notion of local complementations.

Instead of considering only bases (which yield $2^n$ outcomes at random), we can ask for each Pauli string $P$ how many outcomes occur. Each such measurement will have $2^r$ outcomes, all equally likely, for some integer $r$. The integer $r$ we call the rank of $P$, and quantifies the randomness observed when measuring according to $P$ [44]. Bases are then exactly the Pauli strings with the maximum rank of $n$.

A multimatroid⁶ can then be defined by the function that assigns to each Pauli string $P$ its rank (with respect to a given stabilizer state) [12, 13, 15, 18, 17, 44]. The rank function determines a great deal of the measurement statistics when performing local Pauli measurements [44], and suitably generalizes the notion of a rank function from matroid theory [57]. While we will not define matroids here, it suffices to say that the notions of bases and circuits discussed in this work are natural multimatroid generalizations of bases and circuits in matroid theory. Similarly, the construction of $G_{\mathcal{B}}$, which seems rather strange at first sight, is a direct analogue of the well-studied notion of fundamental graphs from matroid theory [52, 53].

Rank functions, bases and circuits all provide ways to define (multi)matroids, but there are many more. Another example is given by the cycles of a (multi)matroid, which are the analogue of the more familiar notion of stabilizers in the quantum community. The fact that there are many definitions of (multi)matroids that are not obviously equivalent allows one to use the perspective most effective for the problem at hand. These equivalent definitions are endearingly referred to as cryptomorphisms in the matroid community. The follow-up work [40] is devoted to further establishing these deep connections between stabilizer states and multimatroid theory.

Acknowledgements

I am grateful for discussions with Robert Brijder, Nathan Claudet, Rose McCarty, Axel Dahlberg, Gecia Bravo-Hermsdorff, Lee Gunderson, Ismaël Septembre, Paul Gunnells, and Steven Noble (in no particular order). I am in particular indebted to Fynn Otto, Nathan Claudet, Adam Fredriksson and Raphaël Mothe for feedback on the writing.

I acknowledge support from the Alexander von Humboldt Foundation. I used ChatGPT to clean up my writing, to find a proof of theorem 4.2 using only notions introduced here, to fully prove theorem A.4, to create all figures in TikZ, and to create the code that visualizes basis switchings and fundamental circuits in [23].

Proofs

Proof. If $Q$ is full-weight we are done, since then $Q$ is a basis. So suppose that $Q$ is not full-weight. Consider an arbitrary qubit $w$ not in the support of $Q$, and let $P_w$ be an arbitrary non-identity Pauli on $w$. Consider measuring according to $Q \cup P_w$. Since $Q$ yields random outcomes, $Q \cup P_w$ will yield non-random outcomes iff measuring according to $Q$ leaves qubit $w$ in an eigenstate of $P_w$ (in particular, random outcomes are obtained independent of $P_w$ if qubit $w$ is entangled with any other qubit). Since $Q$ is fixed, we can choose $P_w$ such that this never happens by using property 3.5.

This implies that $P_w$ can be chosen such that $Q \cup P_w$ yields random outcomes, similar to the original $Q$. Iterating the above procedure yields a full-weight Pauli string $B$ such that measuring according to $B$ yields all $2^n$ outcomes with equal probability (so that $B \in\mathcal{B}_{\psi}$), and $Q \subseteq B$. This proves the claim. □

Proof. Rephrasing this in terms of bases, we aim to show that the number of switchings needed to go from one basis $B$ to any other basis $B'$ is bounded by $\frac{3}{2}n$. Part of our proof follows Bouchet’s approach from [9] (albeit with slightly different notation). We prove the result by inducting on the number of entries $d$ in which $B$ and $B'$ differ. We first show that the induction step holds when $B$ and $B'$ have an entry $v$ such that $(B \star v)_v = B'_v$; this is the easy case. We then show that the induction also holds when switching $B$ at $v$ does not map that entry to $B'_v$.

Let $D(B,B') := \{v \in V \mid B_v \ne B'_v\}$ be the entries in which $B$ and $B'$ differ. Let $d := |D(B,B')|$, and let $s(B,B')$ be the smallest number of switchings needed to go from $B$ to $B'$. We will prove the slightly stronger claim that $s(B,B') \le\frac{3}{2}d$, from which $s(B,B') \le\frac{3}{2}n$ follows directly.

We prove the claim by induction on $d$. Clearly if $d=0$, then $s(B,B') \le\frac{3}{2}d$, so suppose $d>0$.

If there exists a $v \in D(B,B')$ such that $(B \star v)_v = B'_v$, then $|D(B \star v,B')|=d-1$. By induction,

We may thus assume that $(B \star v)_v \ne B'_v$ for every $v \in D(B,B')$.

Choose any $v \in D(B,B')$, and consider the fundamental circuit $g^B_v$. By definition, $g^B_v$ is the unique circuit in $B \cup\omega_v$. Note that $(g^B_v)_v$ is equal to $B'_v$, since changing the $v$'th entry of $B$ to $(B \star v)_v$ yields a basis, which cannot contain a stabilizer by definition 2.1. Together with our assumption that $(B \star v)_v \ne B'_v$, we thus have that $g_v^B$ is contained in $B \cup\{B'_v\}$, and thus $(g_v^B)_v = B'_v$. Now $g_v^B$ cannot be contained in $B'$ since $B'$ is a basis, yet $(g_v^B)_v = B'_v$ by the previous argument. This must then mean that there exists an entry $w$ different from $v$ such that $w \in\operatorname{supp}(g_v^B)$ and that $(g_v^B)_w \ne B'_w$, since otherwise $B'$ would contain the stabilizer $g_v^B$. Since $(g_v^B)_w = B_w$, we have that both $v,w$ are in $D(B,B')$. More strongly, $w \in D(B,B') \cap\operatorname{supp} g_v^B$, i.e., $v$ and $w$ are adjacent in $G_B$.

For such pairs $v,w$, the pivot on $B$ at $\{v,w\}$ is defined as

where we dropped the set notation [55, 15]. This is motivated by the fact that the order does not matter for pivots, i.e. $B \wedge vw = B \wedge wv$ [56].

We now show that $(B \wedge vw)_v = B'_v$ and $(B \wedge vw)_w = B'_w$, i.e. a pivot maps both the $v$ and $w$ entries of $B$ to $B'_v$ and $B'_w$, respectively. Let $K = B \setminus\{B_v,B_w\}$. Pivoting on $vw$ then gives

as desired since both the $v$ and $w$ entries now match $B'$ (without changing any of the other entries). The above follows from the fact that $(B \star v \star w)_w \ne(B \star w)_w \Longleftrightarrow v \sim_{G_B} w$, which is implicit from theorem 7.6 of [6] and theorem 13.4 of [50].

Thus, by performing three switchings, the entries $v,w$ of $B$ and $B'$ can be made to match. By the induction hypothesis, we have that

Together with the case where a single switching decreases $d$, this proves that

as desired.

In the below we define the index $k$ as the cardinality of the preimage of the map $B \mapsto G_B$, see [10], which we also show to be well-defined.

Proof. It suffices to show that 1) two bases $B$, $B'$ map to the same fundamental graph (i.e. $G_B = G_{B'}$) if and only if $CBC^\dagger= B'$ for some $C \in\mathcal{C}_\psi$, and that 2) the action of the group $\mathcal{C}_\psi$ on the set of bases $\mathcal{B}_\psi$ by conjugation is free, i.e. for every pair $B$, $B'$, there exists at most one $C \in\mathcal{C}_\psi$ such that $CBC^\dagger= B'$. The first condition implies that the preimage of a fundamental graph $G_B$ is precisely the orbit of $B$ under the action of $\mathcal{C}_\psi$. The second condition then implies that the size of this orbit is equal to the size of $\mathcal{C}_\psi$.

We show now the first condition. We first consider the forward direction. Let $B$, $B'$ be such that $G_B = G_{B'}$. By the proof of theorem 2.11, we have that there exist local Cliffords $C_B$ and $C_{B'}$ such that $(C_B)B(C_B)^\dagger= Z^{\otimes n}$, and a similar statement for $B'$ and $C_{B'}$. Theorem 2.11 then also implies that $C_B|\psi\rangle= |G_B\rangle= |G_{B'}\rangle= C_{B'}|\psi\rangle$, so that $(C_{B'})^\dagger C_B$ is a symmetry of $|\psi\rangle$ (modulo Paulis), which maps $B$ to $B'$ under conjugation.

For the other direction, note that if $C \in\mathcal{C}_\psi$ and $C$ maps $B$ to $B'$, then applying $C$ to the state and to $B$ preserves the supports of the fundamental circuits. This implies that $G_B = G_{B'}$.

Now we show that this action is free. We use the fact that $\mathcal{C}_\psi$ acts freely on the set of bases iff $CBC^\dagger= B$ implies that $C$ is the identity. So assume that $C$ fixes some $B$. $C$ then necessarily fixes $B \cup\omega_v$, and, by definition 2.9, fixes $g^B_v$ for every qubit $v$. But since $g_v^B$ and $B_v$ are two distinct Paulis that are fixed by $C$, $C$ needs to fix all elements in $\omega_v$ for each $v$, proving the claim. $\square$

Using the characterization of the index as the cardinality of the group of local Clifford symmetries, we can now show that such local Clifford symmetries are rare, as made precise by the following theorem.

Proof. We sketch now the proof idea. We show that, with high probability, the canonical graph state generators $\{g_v\}_{v \in V}$ are the only stabilizers of $|G\rangle$ with support equal to the closed neighborhoods $\{N_v\}_{v \in V}$. To make the above statement more plausible before proving it (which we do in a different manner than the argument we show now), note that the normalized weight distribution of stabilizers of a random graph state is well-approximated by a binomial distribution $\mathbb{B}(n,p = \frac{3}{4})$ [54]. Now each generator $g_v$ has weight approximately $n/2$, which can be checked to have exponentially small probability when sampled from $\mathbb{B}(n,p = \frac{3}{4})$. Having made this step more plausible, let us assume that the supports of the generators $g_v$ are indeed unique. Then since local Clifford unitaries cannot change the support of stabilizers, we have that every putative local Clifford symmetry maps every canonical graph state generator to itself. In particular, if there are no isolated vertices then there always exists a $w$ that is a neighbor of $v$, such that both $(g_v)_v = X_v$ and $(g_w)_v = Z_v$ are fixed under the local Clifford symmetry. This implies that the local Clifford symmetry is trivial.

We now show that $g_v$ is the only stabilizer with support $\overline{N}_v$, with high probability. First, the case where $G$ has any isolated vertex happens with exponentially small probability, so we do not need to consider it. So let us assume that the graph has no isolated vertices. We use that every stabilizer can be written uniquely as

where $W \subseteq V$ is an arbitrary subset of vertices. The stabilizer $\Gamma_W$ has support $W \cup\operatorname{Odd}(W)$, where $\operatorname{Odd}(W)$ is the set of vertices in $V$ that have an odd number of neighbors in $W$. Fix a vertex $v$. For the support of another stabilizer $\Gamma_W$ to agree with the support $\operatorname{supp}(g_v)=\overline{N_v}$ of $g_v$, we necessarily require that $W$ satisfies $\varnothing\ne W \subseteq\overline{N_v}$, and that $W \ne\{v\}$.

Let us condition on $N_v=D$, and set $d=|D|$. All edges not incident to $v$ remain independent, each being present with probability $1/2$. The standard terminology is that the edges we have not conditioned on/assumed anything about are unrevealed. There are two cases to consider for $W$, either $v\notin W$, or $v\in W$ so that we can write $\Gamma_W=g_v\Gamma_T$, where $T=W\setminus\{v\}$.

Fix such a set $T$, and write $t=|T|$. For each vertex $u\notin T\cup\{v\}$, $\Gamma_T$ has a $Z$ at $u$ iff $u\in\operatorname{Odd}(T)$, iff the parity of $|N_u\cap T|$ is $1$. But note that $|N_u\cap T|$ is a uniformly random bit. In fact, these bits are independent for distinct vertices $u,w\notin T\cup\{v\}$, since they depend on disjoint sets of unrevealed edges.

Consider first the case $v\notin W$, so that $W=T$. The stabilizer $\Gamma_T$ already acts nontrivially on every qubit in $T$. To have support precisely $D\cup\{v\}$, $\Gamma_T$ needs to have a $Z$ on every qubit in $D\setminus T$, and $I$ on every qubit outside $D\cup\{v\}$. This thus fixes the parity of $|N_u\cap T|$ at each of the $n-1-t$ vertices in $u\notin T\cup\{v\}$. The additional requirement at $v$ is that $t$ be odd, since every vertex of $T$ is adjacent to $v$. Ignoring this additional requirement gives

which is independent from $d$.

Consider next the case $v\in W$, so that we can write $W=T\cup\{v\}$. The stabilizer $g_v\Gamma_T$ already acts nontrivially on every qubit in $T\cup\{v\}$. For its support to equal $D\cup\{v\}$, we require $\Gamma_T$ to act trivially on every qubit $u\notin T\cup\{v\}$. Indeed, a $Z$ in $\Gamma_T$ would either cancel the $Z$ in $g_v$ (if $u\in D$) or introduce a $Z$ where $g_v$ acts trivially (if $u\notin D$). Equivalently, $|N_u\cap T|$ must be even for every $u\notin T\cup\{v\}$. Equivalently, $|N_u\cap T|$ must be even for every $u\notin T\cup\{v\}$. These are again $n-1-t$ independent parity requirements, and hence

Let $B_v$ denote the event that some stabilizer other than $g_v$ has support $\overline{N_v}$. Taking a union bound over the two cases where $v\in W$ and $v\notin W$, and all nonempty subsets $T\subseteq D$ yields

It remains to account for the randomness of $N_v$. Note that the size $d$ of the neighborhood of $v$ follows a binomial distribution, i.e. $d\sim\operatorname{Bin}(n-1,1/2)$. A standard tail bound then yields

where the choice of constant $\frac{3}{5}$ will be shown to be convenient in not too long.

We now show the claim for every small enough neighborhood $D$, i.e. $d\le3(n-1)/5$. Equation (3) gives

Thus, averaging over $N_v$ and taking a union bound over all vertices,

which goes to zero as $n$ tends to infinity since $\frac{3^{3/5}}{2}<1$, motivating the choice of constant in Eq. (4). Finally, the above analysis was for a single vertex $v$. Repeating the same argument for all $n$ vertices and using a union bound gives the desired result, since Eq. (5) decays exponentially fast in $n$.

Below we provide the fully general scenario of how the set of bases changes when performing local Pauli measurements according to some Pauli string $P$. In particular, we consider the case where there does not need to exist a basis $B$ that contains $P$. The following theorem covers that case.

Proof. We briefly recall the proof for the case where $P$ is contained in at least one basis, say $B$. Since $B$ is a basis, measuring any subset of qubits according to $B$ yields uniformly random outcomes as well. Thus measuring according to $P$ yields random outcomes. A Pauli string $B'$ on the unmeasured qubits is a basis for the post-measurement state iff $P\cup B'$ would have yielded completely random outcomes on the original state, i.e. $P\cup B'$ is a basis of the initial state.

Now consider the case where $P$ need not be contained in a basis. Let $B$ be any basis such that $\lvert B\cap P\rvert=r$. Let $R=\operatorname{supp}(B\cap P)$, and let $P|_R$ be the restriction of $P$ to $R$, i.e. $(P|_R)_v=P_v$ for $v\in R$, and $(P|_R)_v=I_v$ for $v\notin R$. Note that $P|_R$ is contained in $B$, and thus measuring according to $P|_R$ yields $2^{\lvert\operatorname{supp}(P|_R)\rvert}=2^r$ random outcomes. Let $Q=B|_W$, which is clearly contained in the basis $B$. As such, theorem 4.12 applies to $Q$, so that when measuring according to $Q$, the post-measurement state has $B|_{V\setminus W}$ as a basis.

We now claim that the post-measurement state when measuring according to $P$ or $Q$ are the same. This is because the measurements $P_i$ for $i\in\operatorname{supp}(P)\setminus R$ yield deterministic outcomes, conditioned on the measurement outcomes in $R$. This follows from the fact that both measuring according to $P$ and $P|_R$ yield $2^r$ outcomes uniformly at random. This in particular implies that after measuring according to $P|_R$, each qubit in $i\in W\setminus R$ needs to be a single-qubit stabilizer state, i.e. not entangled with anything else. Since measuring single-qubit stabilizer states cannot change the state of the other qubits, and our statement was independent of the choice of $B$, we have that the post-measurement states when measuring according to either $P$ or $Q$ are the same. Thus, since $B|_{V\setminus W}$ is a basis of the post-measurement state when measuring according to $Q$, $B|_{V\setminus W}$ is also a basis for the post-measurement state when measuring according to $P$. This holds for any $B$ such that $\lvert B\cap P\rvert=r$.

We now show that every basis $B'$ of $|\phi\rangle$ arises in the above fashion. To this end, note that by the above argument we can restrict to the case where we measure $Q$ instead of $P$. Since $Q$ is contained in a basis, theorem 4.12 applies, i.e. $B'$ is a basis of $|\phi\rangle$ iff $B'\cup Q=B$ is a basis of $|\psi\rangle$. Moreover, since $B'$ has support disjoint from $P$, we have $\lvert B\cap P\rvert=\lvert Q\cap P\rvert=r$, and $B|_{V\setminus W}=B'$. This proves the converse inclusion, completing the proof.

Here is a simple example of the more general case of vertex-minors.

Example A.6. Consider measuring the first qubit of $|00\rangle$ in the $Z$ basis. None of the bases

agree with the measurement on the first qubit. Hence the maximal possible agreement with $P=Z$ is zero, so in this case we retain all four bases. Restricting them to the unmeasured qubit gives

which are again precisely the bases of the remaining state $|0\rangle$.

Here we show that, when performing Pauli measurements on a stabilizer state, the post-measurement states corresponding to different outcomes are always equivalent up to Pauli unitaries.

Proof. We use the standard update rule for stabilizer states from [1]. That is, if $P$ is a stabilizer, the measurement outcome is deterministic and there is only one post-measurement state, so there is nothing left to prove.

If $P$ is not a stabilizer, find a generating set $\{g_1,g_2,\ldots,g_n\}$ of the stabilizer group of the initial state $|\psi\rangle$, such that $g_1$ anti-commutes with $P$ and commutes with all other $g_i$. This is always possible, since if there exist two distinct generators $g_i,g_j$ that anti-commute with $P$, then $g_j$ can be replaced with $g_i \cdot g_j$, which preserves the stabilizer group, while ensuring that $g_i \cdot g_j$ commutes with $P$. The two post-measurement states then have stabilizer groups $\langle\pm P,g_2,\ldots,g_n\rangle$, which are Pauli equivalent since there always exists a Pauli $Q$ that commutes with every generator besides $g_1$ [1].

The argument extends to two Pauli measurements, since the choice of $Q$ did not depend on the phases in front of the stabilizers. That is, after performing a second measurement $P'$, the associated Pauli correction $Q'$ is independent of which outcome was observed for the first measurement. This can then be extended to any number of Pauli measurements.