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

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?

• At first you need to prove that the circuit is correct. From the circuit it follows that $I \otimes U'$ is Clifford on $n+1$ qubits. From this it's easy to show that $U'$ must be Clifford on $n$ qubits. Aug 27, 2022 at 16:40
• Thanks for the comment. Yes, you are right. I think the way to prove $U'$ is Clifford is as follows. 1, Prove that $U'$ is unitary. This can be proved easily from the definition of the operator. 2, Prove that the above circuit generates (n+1)-qubit Clifford gate $U$ (See Gottesman's proof in the paper). 3, Then $I\otimes U'$ must be Clifford by inverting the circuit as @CraigGidney pointed out. 4, Then $U'$ must be Clifford. Sep 14, 2022 at 10:00
• If U is the X gate on the top qubit then U' would end up equal to the zero matrix. Which is not unitary so not Clifford. I think this induction is easier using the stabilizer tableau of the operation rather than the unitary matrix of the operation. Sep 18 at 19:23

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$$.