Конструктивное доказательство теоремы Готтесмана — Книлла

Вентили Адамара, CNOT и Паули не универсальны: схемы из них со стандартными входными состояниями и измерениями в вычислительном базисе эффективно моделируются классическим компьютером. Это теорема Готтесмана — Книлла. Докажите лежащее в её основе утверждение.

Пусть $G_n$ — группа Паули на $n$ кубитах: тензорные произведения матриц Паули с множителями $\pm1,\pm i$. Её нормализатор равен $N(G_n)=\{U:UG_nU^\dagger=G_n\}$.

Требуется доказать: если унитарный оператор $U$ на $n$ кубитах переводит каждый $g\in G_n$ в $UgU^\dagger\in G_n$, то с точностью до общей фазы $U$ составлен из $O(n^2)$ вентилей Адамара, фазовых вентилей и CNOT.

(a) Докажите, что $H$ и фазовый вентиль $S$ реализуют любую операцию нормализатора на одном кубите.

(b) Пусть $U\in N(G_{n+1})$ удовлетворяет

$$UZ_1U^\dagger=X_1\otimes g,\qquad UX_1U^\dagger=Z_1\otimes g',$$

где $g,g'\in G_n$. Определим оператор на $n$ кубитах:

$$U'|\psi\rangle=\sqrt2\langle0|U(|0\rangle\otimes|\psi\rangle).$$

Используя индукцию, докажите, что изображённая конструкция $U$ реализуется $O(n^2)$ вентилями Адамара, фазовыми вентилями и CNOT.

(c) Докажите, что любая операция $U\in N(G_{n+1})$ реализуется таким числом перечисленных вентилей.