О том из чего квантовые компьютеры собираются
(или о плотных подмножествах SU(2ⁿ))

Возьмём n кубитов и зададимся вопросом сделать с ними всё что угодно унитарное — реализовать некоторый квантовый алгоритм U через набор доступных гейтов {Gⱼ} (fig. a). Квантовый алгоритм U — просто унитарная 2ⁿ-мерная матрица, гейт Gⱼ — операция которую мы делаем с поднабором кубитов, тоже сводится к действию унитарной матрицы. То есть мы хотим представить одну матрицу U в виде произведения U=Gⱼ₁ Gⱼ₂ ... Gⱼₘ . Возникает естественный вопрос, а для какого вообще набора {Gⱼ} мы может так сделать?

Оказывается достаточным взять 3 вида матриц (fig. b): две действующие на один кубит (T,H) и одну действующую на два кубита (CNOT, изображается точкой с плюсом). Действуя ими на разные кубиты получается всего n(n-1)+2n доступных матриц {Gⱼ}. И ограничиваясь только такими матрицами, мы можем приблизить сколь угодно точно любую другую унитарную матрицу — то есть они образуют плотное подмножество SU(2ⁿ).

Было бы интересно подумать, а как для минимального m найти такое разложение U=Gⱼ₁ Gⱼ₂ ... Gⱼₘ — очередная, к слову, NP-complete задача.

// говоря про вид комплексных элементов z матрицы U (fig. c) — формула приведена в title, распределение построено для k=1, n_q={-1,0,1} (другие варианты в комментариях), собственно пост возник скорее из желания поделиться этими узорами)
// опечатка: сумма по q от 0, а не от 1