1 Rem 2: Notation and Pauli Operators
For qubits labeled by vertices \(v\) of a graph or indices \(i\), we denote by \(X_v\) (or \(X_i\)) the Pauli-\(X\) operator acting on qubit \(v\) (or \(i\)), and similarly \(Z_v\) (or \(Z_i\)) for Pauli-\(Z\). A product of Pauli operators is written as \(\prod _{v \in S} X_v\) for a set \(S\) of qubit labels. The identity operator is denoted \(\mathbb {1}\). For a Pauli operator \(P\), we denote by \(S_X(P)\) the \(X\)-type support (sites where \(P\) acts via \(X\) or \(Y\)) and \(S_Z(P)\) the \(Z\)-type support (sites where \(P\) acts via \(Y\) or \(Z\)).
1.1 Definition of Pauli Operators
A Pauli operator on qubits labeled by a type \(V\) is represented as a pair of binary vectors \((\mathtt{xVec}, \mathtt{zVec}) \in (\mathbb {Z}/2\mathbb {Z})^V \times (\mathbb {Z}/2\mathbb {Z})^V\). The pair \((x, z)\) represents the Pauli operator \(\bigotimes _v X_v^{x_v} Z_v^{z_v}\). At each site \(v\):
\((0, 0)\) means the identity \(I\),
\((1, 0)\) means \(X\),
\((0, 1)\) means \(Z\),
\((1, 1)\) means \(Y\) (up to phase).
The identity Pauli operator on qubits labeled by \(V\) is defined as \(\operatorname {id}(V) := (0, 0)\), i.e., the operator that acts as the identity on all qubits.
For a qubit label \(v \in V\), the Pauli-\(X\) operator acting on qubit \(v\) is defined as \(X_v := (\delta _v, 0)\), where \(\delta _v\) is the indicator function that is \(1\) at \(v\) and \(0\) elsewhere.
For a qubit label \(v \in V\), the Pauli-\(Z\) operator acting on qubit \(v\) is defined as \(Z_v := (0, \delta _v)\), where \(\delta _v\) is the indicator function that is \(1\) at \(v\) and \(0\) elsewhere.
For a qubit label \(v \in V\), the Pauli-\(Y\) operator acting on qubit \(v\) is defined as \(Y_v := (\delta _v, \delta _v)\), representing \(X_v Z_v\) up to phase.
1.2 Multiplication
The product of two Pauli operators \(P = (x_P, z_P)\) and \(Q = (x_Q, z_Q)\) is defined by pointwise addition in \(\mathbb {Z}/2\mathbb {Z}\):
This captures the Pauli group multiplication up to phase.
For all Pauli operators \(P, Q\), we have \(P \cdot Q = Q \cdot P\).
By extensionality, it suffices to show equality at each component for each \(v\). By simplification using commutativity of addition in \(\mathbb {Z}/2\mathbb {Z}\), both the \(x\)-component and \(z\)-component are equal.
For all Pauli operators \(P, Q, R\), we have \((P \cdot Q) \cdot R = P \cdot (Q \cdot R)\).
By extensionality, it suffices to show equality at each component for each \(v\). By simplification using associativity of addition in \(\mathbb {Z}/2\mathbb {Z}\), both the \(x\)-component and \(z\)-component are equal.
For all Pauli operators \(P\), we have \(1 \cdot P = P\).
By extensionality, it suffices to show equality at each component for each \(v\). By simplification (since \(0 + a = a\) in \(\mathbb {Z}/2\mathbb {Z}\)), this holds.
For all Pauli operators \(P\), we have \(P \cdot 1 = P\).
By extensionality, it suffices to show equality at each component for each \(v\). By simplification (since \(a + 0 = a\) in \(\mathbb {Z}/2\mathbb {Z}\)), this holds.
For all Pauli operators \(P\), we have \(P \cdot P = 1\).
By extensionality, it suffices to show equality at each component for each \(v\). By simplification using the characteristic-two property \(a + a = 0\) in \(\mathbb {Z}/2\mathbb {Z}\), both the \(x\)-component and \(z\)-component equal \(0\).
1.3 Products over Finite Sets
For a finite set \(S \subseteq V\), the product of Pauli-\(X\) operators over \(S\) is
where \(\mathbf{1}_S(v) = 1\) if \(v \in S\) and \(0\) otherwise.
For a finite set \(S \subseteq V\), the product of Pauli-\(Z\) operators over \(S\) is
where \(\mathbf{1}_S(v) = 1\) if \(v \in S\) and \(0\) otherwise.
1.4 Supports
The \(X\)-type support of a Pauli operator \(P = (x, z)\) is the set of sites where \(P\) acts via \(X\) or \(Y\):
The \(Z\)-type support of a Pauli operator \(P = (x, z)\) is the set of sites where \(P\) acts via \(Y\) or \(Z\):
The full support of a Pauli operator \(P = (x, z)\) is the set of sites where \(P\) acts non-trivially:
The weight of a Pauli operator \(P\) is the number of qubits on which it acts non-trivially:
1.5 Support Characterizations
For a Pauli operator \(P\) and vertex \(v\),
We rewrite using the membership characterization of \(S_X\) (i.e., \(v \in S_X(P) \iff x_v \neq 0\)), then apply the fact that in \(\mathbb {Z}/2\mathbb {Z}\), \(a \neq 0 \iff a = 1\).
For a Pauli operator \(P\) and vertex \(v\),
We rewrite using the membership characterization of \(S_Z\) (i.e., \(v \in S_Z(P) \iff z_v \neq 0\)), then apply the fact that in \(\mathbb {Z}/2\mathbb {Z}\), \(a \neq 0 \iff a = 1\).
1.6 Identity Support
The \(X\)-type support of the identity operator is empty: \(S_X(\mathbb {1}) = \emptyset \).
By extensionality over \(v\) and simplification: the \(x\)-component of the identity is \(0\) everywhere, so no vertex satisfies the membership condition.
The \(Z\)-type support of the identity operator is empty: \(S_Z(\mathbb {1}) = \emptyset \).
By extensionality over \(v\) and simplification: the \(z\)-component of the identity is \(0\) everywhere, so no vertex satisfies the membership condition.
The full support of the identity operator is empty: \(S(\mathbb {1}) = \emptyset \).
By extensionality over \(v\) and simplification: both components of the identity are \(0\) everywhere, so neither condition for membership holds.
The weight of the identity operator is zero: \(\operatorname {wt}(\mathbb {1}) = 0\).
By simplification using the definition of weight and the fact that \(S(\mathbb {1}) = \emptyset \), we get \(|\emptyset | = 0\).
1.7 Single-Site Operator Supports
For any qubit label \(v\), the \(X\)-type support of \(X_v\) is \(\{ v\} \): \(S_X(X_v) = \{ v\} \).
By extensionality over \(w\), we simplify using the definitions of \(X_v\) and \(S_X\), together with the behavior of the indicator function \(\delta _v\): \(\delta _v(w) \neq 0 \iff w = v\).
For any qubit label \(v\), the \(Z\)-type support of \(X_v\) is empty: \(S_Z(X_v) = \emptyset \).
By extensionality over \(w\) and simplification: the \(z\)-component of\(X_v\) is \(0\) everywhere.
For any qubit label \(v\), the \(X\)-type support of \(Z_v\) is empty: \(S_X(Z_v) = \emptyset \).
By extensionality over \(w\) and simplification: the \(x\)-component of \(Z_v\) is \(0\) everywhere.
For any qubit label \(v\), the \(Z\)-type support of \(Z_v\) is \(\{ v\} \): \(S_Z(Z_v) = \{ v\} \).
By extensionality over \(w\), we simplify using the definitions of \(Z_v\) and \(S_Z\), together with the behavior of the indicator function \(\delta _v\): \(\delta _v(w) \neq 0 \iff w = v\).
For any qubit label \(v\), the \(X\)-type support of \(Y_v\) is \(\{ v\} \): \(S_X(Y_v) = \{ v\} \).
By extensionality over \(w\), we simplify using the definitions of \(Y_v\) and \(S_X\), together with the behavior of the indicator function \(\delta _v\).
For any qubit label \(v\), the \(Z\)-type support of \(Y_v\) is \(\{ v\} \): \(S_Z(Y_v) = \{ v\} \).
By extensionality over \(w\), we simplify using the definitions of \(Y_v\) and \(S_Z\), together with the behavior of the indicator function \(\delta _v\).
1.8 Product Support Characterizations
For a finite set \(S\), the \(X\)-type support of \(\prod _{v \in S} X_v\) is \(S\) itself: \(S_X\! \left(\prod _{v \in S} X_v\right) = S\).
By extensionality over \(v\) and simplification using the definitions of \(\operatorname {prodX}\) and \(S_X\): the \(x\)-component of \(\operatorname {prodX}(S)\) at \(v\) is \(1\) if and only if \(v \in S\).
For a finite set \(S\), the \(Z\)-type support of \(\prod _{v \in S} X_v\) is empty: \(S_Z\! \left(\prod _{v \in S} X_v\right) = \emptyset \).
By extensionality over \(v\) and simplification: the \(z\)-component of \(\operatorname {prodX}(S)\) is \(0\) everywhere.
For a finite set \(S\), the \(X\)-type support of \(\prod _{v \in S} Z_v\) is empty: \(S_X\! \left(\prod _{v \in S} Z_v\right) = \emptyset \).
By extensionality over \(v\) and simplification: the \(x\)-component of \(\operatorname {prodZ}(S)\) is \(0\) everywhere.
For a finite set \(S\), the \(Z\)-type support of \(\prod _{v \in S} Z_v\) is \(S\) itself: \(S_Z\! \left(\prod _{v \in S} Z_v\right) = S\).
By extensionality over \(v\) and simplification using the definitions of \(\operatorname {prodZ}\) and \(S_Z\): the \(z\)-component of \(\operatorname {prodZ}(S)\) at \(v\) is \(1\) if and only if \(v \in S\).
1.9 Support Union Characterization
For any Pauli operator \(P\),
By extensionality over \(v\) and simplification using the definitions of \(S\), \(S_X\), and \(S_Z\): a vertex \(v\) belongs to \(S(P)\) if and only if \(x_v \neq 0\) or \(z_v \neq 0\), which is exactly the condition for membership in \(S_X(P) \cup S_Z(P)\).
1.10 Single-Site and Product Relationships
For any qubit label \(v\),
By extensionality over \(w\) for both components, we simplify using the definitions of \(X_v\) and \(\operatorname {prodX}(\{ v\} )\), together with the behavior of the indicator function: \(\delta _v(w) = \mathbf{1}_{\{ v\} }(w)\).
For any qubit label \(v\),
By extensionality over \(w\) for both components, we simplify using the definitions of \(Z_v\) and \(\operatorname {prodZ}(\{ v\} )\), together with the behavior of the indicator function: \(\delta _v(w) = \mathbf{1}_{\{ v\} }(w)\).