# Construction of arbitrary Normalizer Gates using H, S and CNOT Gates

This question is in reference to Exercise 10.40 of Nielsen and Chuang's textbook, which is an attempt to prove the theorem that any $$n$$ qubit Normalizer gate can be built out of $$H$$, $$S$$, and $$CNOT$$ gates. For reference, a normalizer gate is any gate $$U$$ such that $$UVU^\dagger \in G_n$$ whenever $$V \in G_n$$. Here, $$G_n$$ is the $$n^{th}$$ order Pauli Group. The problem attempts to prove this theorem in three steps using mathematical induction.

• First, we prove that any single qubit normalizer can be built using $$H$$ and $$S$$ gates.
• Second, we are given an $$n + 1$$ qubit Normalizer $$U$$ that satisfies the conditions $$UZ_1U^\dagger = X_1 \otimes g$$ and $$UX_1U^\dagger = Z_1 \otimes g'$$ for some $$g, g' \in G_n$$. We are given a circuit (shown below) that implements $$U$$ in terms of controlled $$g, g'$$, a Hadamard $$H$$ and an $$n$$ qubit unitary $$U'$$ defined by $$U'|\psi\rangle = \langle0|U(|0\rangle \otimes |\psi\rangle)$$. We are asked to show by induction that the circuit uses $$O(n^2)$$ $$H$$, $$S$$, and $$CNOT$$ gates to build $$U$$.
• Third, we use the above results to prove that any $$n$$ qubit Normalizer gate can be built out of $$H$$, $$S$$, and $$CNOT$$ gates.

Now, part 1 is easily done, once you realize that single-qubit normalizers are essentially $$90^o$$ rotations on the Bloch sphere which are generated by $$\sqrt{X}$$ and $$\sqrt{Z}$$ and hence by $$H$$ and $$S$$.

For part 2, there are several things to show. First, if $$g$$ is a single qubit operator in $$G_1$$, then it is easily implemented using around 5 $$H$$ or $$S$$ and a single CNOT. For $$g \in G_n$$, we need $$O(n)$$ such gates. Now, if an inductive proof is in play, we will recursively break down $$U'$$ using a similar circuit so the total number of gates is

$$O(n) + O(n - 1) + \dots + O(1) = O(n^2)$$

There are a few other things to do before part 2 is done though. First, we need to show that $$U'|\psi\rangle = \langle0|U(|0\rangle \otimes |\psi\rangle)$$ defines a unitary operator. This is done in this question. Next, we need to show that the shown circuit really does implement $$U$$. This is also easy to do using the same procedure as outlined in the same question (and a little bit of tedious math).

However, showing this requires the use of the two conditions $$UZ_1U^\dagger = X_1 \otimes g$$ and $$UX_1U^\dagger = Z_1 \otimes g'$$, so to complete the induction, we need to show that $$U'$$ satisfies similar conditions. Also, it is easy to see that these two conditions are not true for a general Normalizer $$U$$ (consider the $$SWAP$$ gate for which $$UZ_1U^\dagger = Z_2$$ and $$UX_1U^\dagger = X_2$$), which is a problem for proving part 3.

So, summarizing, here are my questions:

• Is it necessarily true that $$U'$$ as defined above satisfies the two conditions $$UZ_1U^\dagger = X_1 \otimes g$$ and $$UX_1U^\dagger = Z_1 \otimes g'$$? If so, how? If not, how do we complete the inductive proof?
• What if $$U$$ in general does not satisfy these conditions? How do we generalize this for an arbitrary $$n + 1$$ qubit normalizer $$U$$?