Trouble understanding Nielsen & Chuang exercise

Question

I am probably just stuck on something very simple, but I'm having trouble understanding a premise of Exercise 10.40 in Nielsen & Chuang. The full details of the exercise are not important for my question. The relevant part is this:

Suppose $U$ is an $n+1$ qubit gate in $N(G_{n+1})$ such that $U Z_1 U^\dagger = X_1 \otimes g$ and $U X_1 U^\dagger = Z_1 \otimes g^\prime$ for some $g, g^\prime \in G_n$. [Here, $G_n$ is the Pauli group on $n$ qubits and $N(G_n)$ is the normalizer of this group.] Define $U^\prime$ on $n$ qubits by $U^\prime |\psi\rangle := \sqrt{2}\langle 0 | U(| 0 \rangle \otimes | \psi \rangle )$.

Now, presumably this $U^\prime$ operator is unitary, but I can't figure out why this is necessarily true.

Answer 1

Write $$ U = \frac{1}{2}(I_1 + Z_1) \otimes U'_{00} + \frac{1}{2}(I_1 - Z_1) \otimes U'_{11} + \frac{1}{2}(X_1 + iY_1) \otimes U'_{01} + \frac{1}{2}(X_1 - iY_1) \otimes U'_{10} = \left(\begin{array}{cc} U'_{00} &U'_{01} \\U'_{10}& U'_{11}\end{array}\right) $$ where $U'_{ij} \in G_n$. In terms of the latter, $$ U' |\Psi\rangle = \sqrt{2} \;\langle 0 | U | 0\otimes \Psi \rangle = (\sqrt{2}\; U'_{00})|\Psi\rangle $$ while the unitarity of $U$ gives $$ U'_{00} (U'_{00})^\dagger + U'_{01} (U'_{01})^\dagger = U'_{11} (U'_{11})^\dagger + U'_{10} (U'_{10})^\dagger = I_n $$ and one other condition. Translate condition $UZ_1U^\dagger = X_1\otimes g$ into similar relations for the $U'_{ij}$-s and obtain that $$ U'_{00} (U'_{00})^\dagger = U'_{01} (U'_{01})^\dagger = U'_{10} (U'_{10})^\dagger = U'_{11} (U'_{11})^\dagger = \frac{1}{2} I_n $$ and so on.