Сколько состояний могут подготовить короткие схемы

Пусть $\mathcal H_N$ — множество чистых состояний в базисе $|1\rangle,\ldots,|N\rangle$, то есть единичных векторов в $\mathbb C^N$. Зафиксируйте константу $c>0$.

(a) Докажите, что можно выбрать $T=2^{\Omega(N)}$ состояний с $|\langle\psi_i|\psi_j\rangle|\le c$ для $i\ne j$. Подсказка. Достаточно рассмотреть $N^{-1/2}\sum_{i=1}^N(-1)^{x_i}|i\rangle$. Как это связано с кодами, исправляющими ошибки?

(b) Пусть $G$ — конечный универсальный набор квантовых вентилей. Докажите, что для приближённой подготовки некоторых состояний $n$ кубитов требуется $2^{\Omega(n)}$ вентилей из $G$.

(c) Дополнительный вопрос. При $c$, близком к 1, получите более сильную оценку $T\ge(1/(1-c))^{\Omega(N)}$.