Трёхкубитное преобразование Фурье в кластерной модели

В кластерной модели квантовых вычислений фиксированное начальное состояние многих кубитов и последовательность измерений с классическим управлением реализуют произвольную квантовую схему. Постройте в этой модели изображённое трёхкубитное квантовое преобразование Фурье.

$S,T$ — фазовый вентиль и вентиль $\pi/8$. Последний SWAP исправляет порядок выходных битов. При $\omega=e^{2\pi i/8}=\sqrt i$ все элементы матрицы преобразования заданы формулой

$$U_{jk}=\frac{\omega^{jk}}{\sqrt8},\qquad j,k\in\{0,1,\ldots,7\}.$$

(a) Замените вентили схемы операциями с известными реализациями в кластерной модели — например, однокубитными вентилями и CNOT. Оцените число кубитов начального кластерного состояния.

(b) Нарисуйте кластер, пронумеруйте кубиты и опишите последовательность измерений и шагов классического управления, реализующую преобразование. Подсказка: управляемый $R_z(\theta)$ просто выражается через однокубитные операции и CNOT.

(c) Обсудите эффективность реализации. Можно ли, по вашему мнению, обойтись меньшим кластером?