Лекция 8. Универсальность в смысле приближений

На этой Лекции мы обсудили, возможно ли проводить квантовые вычисления эффективно, если нам доступен только конечный набор квантовых операций. В таком случае, произвольные квантовые операции можно выражать только с некоторой точностью $\varepsilon>0$. Точность падает линейно с ростом числа операций. Благодаря теореме Соловея-Китаева, мы можем переписать любую квантовую схему размера $\mathrm{SIZE}$ как квантовую схему с конечным универсальным алфавитом операций, c размером $\mathrm{SIZE}' = \mathrm{SIZE}\cdot \mathrm{polylog}\frac{\mathrm{SIZE}}{\varepsilon}$. Доказательство теоремы опирается на свойства группы $\mathrm{SU}(2)$. Можно считать, что эта теорема гарантирует возможность, как и в классическом случае, оцифровывать непрерывные величины. Также, это свойство оказывается важным для достижения помехоустойчивости квантовых вычислений.