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.

Circuit for part 2. Source: Nielsen and Chuang

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.