Trouble understanding Nielsen & Chuang exercise

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.

• Welcome to the site! This looks like a good question to me, but you should still read our guidelines for questions that originate from set exercises. Also, some additional context (why is it useful to have a $U$ with those properties?) would not come amiss. Jul 22 '16 at 13:12

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.