Лекция 6. Универсальность в квантовых схемах

На этой лекции мы обсуждали явление универсальности в случае квантовых схем. При помощи принципа отложенных измерений любая квантовая схема может быть эффективно сведена с обратимой квантовой схеме. При этом любую унитарную операцию можно реализовать при помощи композиции однокубитных вентилей и запутывающих вентилей $C\mathrm{NOT}$. Реализация произвольной унитарной операции может требовать не менее чем $\mathcal{O}(4^n)$ элементарных операций. Кроме того, мы начали обсуждать универсальность в смысле приближений, и доказали теорему Соловея-Китаева: если на кубите задан конечный универсальный набор вентилей, то этот набор может реализовать любую однокубитную операцию эффективным образом.