My solutions to select exercises in chapter 10 of Nielsen+Chuang’s QCQI.

## 10.5

**Exercise 10.29**: Let \(\left|\psi_1\right>, \left|\psi_2\right> \in V_S\). We consider an arbitrary linear combination of these two vectors

\[\left|\psi\right> = a\left|\psi_1\right> + b \left|\psi_2\right>, \text{ for some } a, b, \in \mathbb{C}.\]

Now consider the action of some \(M \in S\) on \(\left|\psi\right>\).

\[M\left|\psi\right> = M (a\left|\psi_1\right> + b \left|\psi_2\right>) = aM\left|\psi_1\right> + b M\left|\psi_2\right> = a\left|\psi_1\right> + b \left|\psi_2\right> = \left|\psi\right>.\]

Therefore, \(\left|\psi\right> \in V_S\).

If \(V_S\) contains any element from an eigenvalue -1 subspace, we could easily construct a state that violates the above property, so the second statement is true.

**Exercise 10.30**:

Suppose that \(\pm iI \in S\). Then, by the group operation this implies that \(-I \in S\). By contraposition, this proves the statement.

**Exercise 10.31**: Let \(S\) be a subgroup of \(G_n\) generated by elements \(g_1, \ldots, g_l\).

\((\Rightarrow)\). Suppose that all elements in \(S\) commute. That is, for any \(M, N \in S\), we have \(MN = NM\). Since \(g_i, g_j \in S\), the generators must commute too..

\((\Leftarrow)\). Suppose that each pair of generators \(g_i\) and \(g_j\) commute for all \(i, j\). Let \(M, N \in S\), meaning they can be written as products \(M = g_1^{m_1} \cdots g_l^{m_l}\) and \(N = g_1^{n_1} \cdots g_l^{n_l}\) for \(m_i, n_i \in \{0, 1\}\). Then

\[MN = (g_1^{m_1} \cdots g_l^{m_l})(g_1^{n_1} \cdots g_l^{n_l}) = (g_1^{n_1} \cdots g_l^{n_l})(g_1^{m_1} \cdots g_l^{m_l}) = NM\]

since we can swap elements one at a time until we go from the second term to the third term in the above equation. Therefore all elements of \(S\) commute.

**Exercise 10.32**: Can be easily verified directly.

**Exercise 10.33**:

\((\Rightarrow)\) Suppose that \(g\) and \(g'\) commute. Since both are elements of the Pauli group, this means that in each index we have either 1) a non-identity Pauli on one generator and identity on the other or 2) the same Pauli on each position. If both generators are built with identities and the same Pauli, they trivially commute and it is not necessary to test. Another possibility is that the total number of indices with non-commuting terms is even, since in a non-commuting index the commutator picks up a phase of -1. To determine this, we represent \(g = (x_1, \ldots, x_n, z_1, \ldots, z_n)\) and \(g' = (x_1', \ldots, x_n', z_1', \ldots, z_n')\), where we have used a length \(2n\) bit vector to represent indices of the generator that have (or don’t have) an \(X\) component with 1 (or 0), and the same in the second half of the matrix for \(Z\). For \(Y\) we simply set the corresponding index for both terms to 1. Now if the two generators commute, then we should have

\[\sum_{i=1}^n (x_iz_i' + z_ix_i') = 0,\]

which is exactly what the ‘twisted’ inner product computes between different rows.

\((\Leftarrow)\) Suppose that for \(g, g' \in S\), we have \(r(g)\Lambda r(g')^T = 0\). This implies that the total number of non-commuting indices of \(g\) and \(g'\) is even. This implies \(g\) and \(g'\) commute since each non-commuting index contributes a phase of -1 when taking the commutator, which when taken to an even power gives 1.

**Exercise 10.34**: Let \(S = \left< g_1, \ldots, g_l \right>\). Show that \(-I\) is not an element of \(S\) if and only if \(g_j^2 = I\) for all \(j\), and \(g_j \neq -I\) for all \(j\).

\((\Rightarrow)\) Suppose \(-I \not \in S\). Then, since \(S\) is a subgroup of the Pauli group, we have \(g_j^2 = I\) for all \(j\), but \(g_j \neq -I\) for all \(j\) by assumption.

\((\Leftarrow)\) Suppose \(g_j^2 = I\) for all \(j\), and \(g_j \neq -I\) for all \(j\). By the first condition, we know that \(g_j \neq \pm i M\) for any \(n\) Pauli string \(M\). By exercise 10.30, we conclude that \(-I \not \in S\).

**Exercise 10.35**: Let \(S\) be a subgroup of \(G_n\) such that \(-I\) is not an element of \(S\).

Seems trivial? And very similar to 10.34.

**Exercise 10.36**:

\[UX_1U^\dagger = \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} \begin{bmatrix}0&0&1&0 \\ 0&0&0&1 \\ 1&0&0&0 \\ 0&1&0&0\end{bmatrix} \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} = \begin{bmatrix}0&0&0&1 \\ 0&0&1&0 \\ 0&1&0&0 \\ 1&0&0&0\end{bmatrix} = X_1X_2\]

\[UX_2U^\dagger = \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} \begin{bmatrix}0&1&0&0 \\ 1&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} = \begin{bmatrix}0&1&0&0 \\ 1&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} = X_2\]

\[UZ_1U^\dagger = \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&-1&0 \\ 0&0&0&-1\end{bmatrix} \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} = \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&-1&0 \\ 0&0&0&-1\end{bmatrix} = Z_1\]

\[UZ_2U^\dagger = \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} \begin{bmatrix}1&0&0&0 \\ 0&-1&0&0 \\ 0&0&1&0 \\ 0&0&0&-1\end{bmatrix} \begin{bmatrix}1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0\end{bmatrix} = \begin{bmatrix}1&0&0&0 \\ 0&-1&0&0 \\ 0&0&-1&0 \\ 0&0&0&1\end{bmatrix} = Z_1Z_2\]

**Exercise 10.37**: \[UY_1U^\dagger = iUX_1Z_1U^\dagger = iUX_1U^\dagger U Z_1 U^\dagger = i (X_1 X_2) Z_1 = Y_1 X_2.\]

**Exercise 10.38**:

Got some hints from enakai blog.

Let \(M \in \{Z_1, Z_2, X_1, X_2\}\). By assumption, \(U\) and \(V\) act on \(M\) in the same way under conjugation:

\[UMU^\dagger = VM V^\dagger \Leftrightarrow M(U^\dagger V) = (U^\dagger V)M.\]

Note that we can express any \(4 \times 4\) matrix \(U^\dagger V\) as \(I_1 \otimes A + Z_1 \otimes B + X_1 \otimes C + Y_1 \otimes D\) where \(A, B, C, D\) are linear combinations of the 1 qubit Paulis.

Suppose \(M = Z_1\). Consider \[Z_1(U^\dagger V) = Z_1(I_1 \otimes A + Z_1 \otimes B + X_1 \otimes C + Y_1 \otimes D) = Z_1 \otimes A + I_1 \otimes B + Z_1(X_1 \otimes C + Y_1 \otimes D)\] and \[(U^\dagger V)Z_1 = (I_1 \otimes A + Z_1 \otimes B + X_1 \otimes C + Y_1 \otimes D)Z_1 = Z_1 \otimes A + I_1 \otimes B - Z_1(X_1 \otimes C + Y_1 \otimes D).\]

Since the two must be equal by assumption, we see that \(X_1 \otimes C + Y_1 \otimes D = 0\) and \((U^\dagger V) = I_1 \otimes A + Z_1 \otimes B\).

The same equality must hold for the case \(M = X_1\) which we consider next. \[X_1(U^\dagger V) = X_1(I_1 \otimes A + Z_1 \otimes B)\] and \[(U^\dagger V)X_1 = (I_1 \otimes A + Z_1 \otimes B)X_1\] from which we can see that \(B = 0\). This implies that \(U^\dagger V = I_1 \otimes A\).

To determine what \(A\) is, we can use a similar analysis with \(M = Z_2, X_2\), from which we conclude that \(U^\dagger V = I\), which implies that \(U = V\).

**Exercise 10.39**: \[SXS^\dagger = \begin{bmatrix}1&0 \\ 0&i\end{bmatrix} \begin{bmatrix}0&1 \\ 1&0\end{bmatrix} \begin{bmatrix}1&0 \\ 0&i\end{bmatrix} = \begin{bmatrix} 1 & -i \\ i & 1 \end{bmatrix} = Y\]

\[SZS^\dagger = \begin{bmatrix}1&0 \\ 0&i\end{bmatrix} \begin{bmatrix}1&0 \\ 0&-1\end{bmatrix} \begin{bmatrix}1&0 \\ 0&i\end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & =1 \end{bmatrix} = Z\]

**Exercise 10.40**:

**Exercise 10.43**: Show that \(S \subseteq N(S)\) for any subgroup \(S\) of \(G_n\).

\[N(S) \equiv \{E\in G_n | EgE^\dagger \in S, \forall g \in S.\}\]

Let \(E \in S\) where \(S\) is a subgroup of \(N(S)\). Then for all \(g \in S\), \(EgE^\dagger \in S\) because \(S\) is a subgroup.

**Exercise 10.44**: Show that \(N(S) = Z(S)\) for any subgroup \(S\) of \(G_n\) not containing \(-I\).

(\(N(S) \subseteq Z(S)\)) Take \(E\in N(S)\). Consider the equality \(EgE = \pm EE g = \pm g\) for some \(g \in S\), where the sign depends on the commutation relation between \(E\) and \(g\). Suppose there exists an \(E\) such that the sign is negative. Since \(S\) is a subgroup we have \(EgE = -g \in S\). Then, we find that \(-I \in S\) by

\[(EgE) g = -EggE = -I,\]

which is a contradiction, so we know that \(EgE = g\). From this we conclude that \(Eg = gE\), so \(E \in N(S)\).

(\(Z(S) \subseteq N(S)\)) Take \(E \in Z(S)\). Then, \(Eg = gE\) for all \(g \in S\). This implies by properties of the Pauli group that \(EgE^\dagger = g\).

**Exercise 10.45**:

**