Reduced Graph States: Characterizing Basis States

[Johny Boy]

TL;DR Summary

I have a paper query regarding a fundamental result on graph states, more specifically a result that characterizes a reduced graph state in a particular basis.

Reduced graph states are characterized as follows from page 46 of this paper:

Proposition: Let $A \subseteq V$ be a subset of vertices for a graph $G = (V,E)$ and $B = V\setminus A$ the corresponding complement in $V$. The reduced state $\rho_{G}^{A}:= tr_{B}(|G\rangle\langle G|)$ is given by $$\rho^{A}_{G} = \frac{1}{2^{|A|}}\sum_{\sigma \in \mathcal{S_{A}}}\sigma,~~~~~~~~~~~~~~~~~~(1)$$where $\mathcal{S}_{A}:=\{ \sigma \in \mathcal{S}| \text{supp}(\sigma) \subseteq A \}$ denotes the subgroup of stabilizer elements $\sigma \in \mathcal{S}$ for $|G\rangle$ with support on the set of vertices within $A$. $\rho_{G}^{A}$ is up to some factor a projection, i.e.

$$(\rho_{G}^{A})^2 = \frac{|\mathcal{S}_{A}|}{2^{|A|}}\rho_{G}^{A}~~~~~~~~~~~~~~~~~~~(2)$$It projects onto the subspace in $\mathbf{H}^{A}$ spanned by the vectors $$|\mathbf{\Gamma}'B'\rangle_{G[A]} = \sigma_{z}^{\mathbf{\Gamma}'B'}|G[A]\rangle~~~~~~~(B' \subseteq B)~~~~~~~~~(3)$$where $G[A] = G\setminus B$ is the subgraph of $G$ induced by $A$ and $\mathbf{\Gamma}':=\mathbf{\Gamma}^{AB}$ denotes the $|A| \times |B|-$off diagonal sub-matrix of the adjacency matrix $\mathbf{\Gamma}$ for $G$ that represents the edges between $A$ and $B$:
$$
\begin{align}
\begin{pmatrix}
\mathbf{\Gamma}_{A} & \mathbf{\Gamma}_{AB} \\
\mathbf{\Gamma}^{T}_{AB} & \mathbf{\Gamma}_{B}
\end{pmatrix} = \mathbf{\Gamma}.
\end{align}
$$
In this basis, $\rho_{G}^{A}$ can be written as $$\rho_{G}^{A} = \frac{1}{2^{|B|}}\sum_{B' \subseteq B}| \mathbf{\Gamma}' B' \rangle_{G[A]} \langle \mathbf{\Gamma}'B'|.~~~~~~~~~~~~~(4)$$
Question:
The results of equation (1) and (2) are understood. I'm trying to understand the motivation for defining the basis states $| \mathbf{\Gamma}' B' \rangle_{G[A]}$ as shown in equation (3). As I understand, $\mathbf{\Gamma} B'$ in the exponent of equation (3), is some string in $\{0,1\}^{|B'|}$. In this way they would show that there are sufficient permutations of $\mathbf{\Gamma}' B'$, where $B' \subseteq B$, to produce orthogonal states $| \mathbf{\Gamma}' B' \rangle_{G[A]}$ which spans a subspace of $\mathbf{H}^{A} \subseteq (\mathbb{C})^V$. Explicitly how is the term '$| \mathbf{\Gamma}' B' \rangle_{G[A]}$' defined? I don't really understand why the exponent is chosen as $\mathbf{\Gamma} B'$ into begin with to characterize the basis states?

Thanks for any assistance.

 

[eljose79]

Thank you for your question. The basis states $| \mathbf{\Gamma}' B' \rangle_{G[A]}$ are defined as follows:

First, we take the subgraph $G[A] = G\setminus B$, which is the induced subgraph of $G$ by the vertices in $A$. This means that we only consider the edges that connect vertices within $A$, and we disregard any edges that connect a vertex in $A$ to a vertex in $B$.

Next, we consider the adjacency matrix $\mathbf{\Gamma}$ for the full graph $G$. This is a square matrix with dimension equal to the number of vertices in $G$. The submatrix $\mathbf{\Gamma}'$ is then defined as the $|A| \times |B|$ off-diagonal submatrix of $\mathbf{\Gamma}$, which contains only the entries corresponding to the edges between vertices in $A$ and vertices in $B$. This is why we use the notation $\mathbf{\Gamma}'^{AB}$ to denote this submatrix.

Now, for a given subset $B' \subseteq B$, we can define the string $\mathbf{\Gamma} B'$ as the string of bits representing the presence or absence of edges between vertices in $A$ and vertices in $B'$. For example, if we have four vertices in $A$ and three vertices in $B$, the string $\mathbf{\Gamma} B'$ might look like $011010$, where the first two bits correspond to edges between the first two vertices in $A$ and the first vertex in $B$, the third and fourth bits correspond to edges between the third and fourth vertices in $A$ and the second vertex in $B$, and so on.

Finally, the basis states $| \mathbf{\Gamma}' B' \rangle_{G[A]}$ are defined as the states obtained by applying the $\sigma_{z}^{\mathbf{\Gamma}' B'}$ operator to the state $|G[A]\rangle$. This operator flips the sign of the state whenever there is a 1 in the corresponding position in the string $\mathbf{\Gamma} B'$. For example, in the string $011010$, the operator would flip the sign of the