Regarding the inductive proof that any Clifford gate can be made of Hadamard, phase and c-not

Question

In Exercise 10.40 of Nielsen and Chunang's textbook, the reader is supposed to construct an inductive proof of Theorem 10.6 that any Clifford gate can be made of Hadamard, phase and c-not. There it is claimed that a Clifford gate $U$ satisfying $UZ_1U^\dagger = X_1\otimes g$ and $UX_1U^\dagger = Z_1\otimes g'$ where $g$ and $g'$ are n-qubit Pauli operators can be constructed by the following quantum circuit.

$U'$ is an n-qubit Unitary defined by $U'\vert\psi\rangle = \sqrt{2}\langle0\vert U (\vert 0 \rangle\otimes\vert\psi\rangle)$.

I can see that if $U'$ is a Clifford gate, this essentially completes the inductive proof. However I do not seem to be able to prove that $U'$ is actually Clifford from its definition.

I looked at Gottesman's original paper (PRA 57, 127 (1998)). In its appendix, the proof is constructed in more or less the same way. But it only says "$U'$ is an n-qubit operation, so we can build it out of R, P, and CNOT" (in the paper Hadamard is denoted R). This is only true when $U'$ is a Clifford gate but its proof is not given there as well.

Does anyone have any idea?

Answer 1

This question is about the second part of the cited exercise. The first part is the single qubit case. In the second part, one is basically supposed to prove by induction that with the given assumptions, $U$ is a product of $O(n^2)$ Hadamard, phase, and $\mathrm{\small CNOT}$ gates. The third part is about generalizing this to all unitary operators.

For the second part, all you really need to show is that the given circuit implements $U$. Namely, then $I \otimes U^\prime \in N(G_{n + 1})$ which cannot be true unless $U^\prime \in N(G_n)$. That $U^\prime$ is a product of $O(n^2)$ Hadamard, phase, and $\mathrm{\small CNOT}$ gates is of course the inductive hypothesis. Then the claim of the second part follows by the circuit.

To show that the circuit corresponds to $U$, it is perhaps easiest to consider input states $|0\rangle \otimes |\psi\rangle$ and $|1\rangle \otimes |\psi\rangle$. For example, the state $|0\rangle \otimes |\psi\rangle$ is seen to be transformed to $$ (|0\rangle\langle 0| \otimes I) U (|0\rangle \otimes |\psi\rangle) + (|1\rangle\langle 0| \otimes g) U (|0\rangle \otimes |\psi\rangle). $$ Now we use the fact that $U(|0\rangle \otimes |\psi\rangle)$ is an eigenstate of $X \otimes g = U Z_1 U^\dagger$ to write the above state as $$ \begin{align*} & (|0\rangle\langle 0|X \otimes g) U (|0\rangle \otimes |\psi\rangle) + (|1\rangle\langle 0| \otimes g) U (|0\rangle \otimes |\psi\rangle) \\ =\ & \big((|0\rangle\langle 1| + |1\rangle\langle 0|) \otimes g \big) U (|0\rangle \otimes |\psi\rangle) \\ =\ & (X \otimes g) U (|0\rangle \otimes |\psi\rangle) \\ =\ & U Z_1 U^\dagger U (|0\rangle \otimes |\psi\rangle) = U (|0\rangle \otimes |\psi\rangle). \end{align*} $$ A similar calculation shows that $|1\rangle \otimes |\psi\rangle$ is mapped to $U(|1\rangle \otimes |\psi\rangle)$.

Notice that the definition $U^\prime |\psi\rangle = \sqrt{2} (\langle 0| \otimes I) U (|0\rangle \otimes |\psi\rangle)$ alone is not enough to guarantee that $U^\prime$ is unitary even if $U$ was a Clifford gate. However, $U^\prime$ can be explicitly shown to be unitary with the additional assumptions $U Z_1 U^\dagger = X \otimes g$ and $U X_1 U^\dagger = Z \otimes g^\prime$.