Каково математическое обоснование универсальности универсального набора квантовых вентилей (CNOT, H, Z, X и π / 8)?

В этом ответе я упомянул, что вентили CNOT, H, X, Z и $\pi/8$ образуют универсальный набор вентилей, которые при достаточном количестве вентилей могут быть сколь угодно близки к репликации любых унитарных квантовых вентилей (я узнал об этом факт из лекций профессора Умеша Вазирани EdX). Но есть ли математическое обоснование для этого? Там должен быть! Я пытался найти соответствующие документы, но не мог найти много.

Ответ, который вы упоминаете, ссылается на книгу Майкла Нильсена и Исаака Чуанга « Квантовые вычисления и квантовая информация» (издательство Кембриджского университета), в которой содержится доказательство универсальности этих ворот. (В моем издании 2000 года это можно найти на стр. 194.) Ключевое понимание заключается в том, что ворота (или π / 8- ворота) вместе с H- воротами генерируют два различных поворота на сфере Блоха с углами, которые иррациональные кратные 2 π . Это позволяет сочетания$T$$\pi/8$$H$$2\pi$затворов T и H плотно заполнить поверхность сферы Блоха и тем самым приблизить любой однокубитный унитарный оператор.$T$$H$

То, что это можно сделать эффективно , показывает теорема Соловая-Китаева . Здесь «эффективно» означает многочлен в $\log(1/\epsilon)$ , где - требуемая точность. Это также доказано в книге Нильсена и Чуана (Приложение 3 в издании 2000 года). Явная конструкция может быть найдена в https://arxiv.org/abs/quant-ph/0505030 .$\epsilon$

Комбинирование вентилей CNOT позволяет аппроксимировать произвольные мультикубитные унитарные, как показано Barenco et al.в физ. Rev. A 52 3457 (1995). (Препринт этого документа можно найти по адресу https://arxiv.org/abs/quant-ph/9503016 .) Это также обсуждается в Nielsen и Chuang (стр. 191 в издании 2000 года).

Вам даже не нужно и X . C N O T , H и T = π / 8 достаточно.$Z$$X$
$\rm{CNOT}$$H$$T=\pi/8$

1) и T достаточно, чтобы совершить любое возможное унитарное преобразование на одном кубите. 2) Добавляя C N O T , вы можете синтезировать общее унитарное преобразование с точностью до любой ошибки ϵ > 0, используя только O ( log 2 ( 1 / ϵ ) ) вентилей.$H$$T$
$\rm{CNOT}$$\epsilon>0$$\mathcal{O}(\log^2(1/\epsilon))$

Если вы хотите , чтобы ошибка была , и вы только готовы добавить фазы ворота π / 2 , это все еще возможно , если и только если элементы унитарной вы хотите сделать , имеют вид: + я $\epsilon=0$$\pi/2$ , где все переменные являются целыми числами. Примечательно, что для этого точного синтеза требуется не более 1 вспомогательного кубита.$\frac{a+ib}{2^n} + \frac{c+id}{2^{n+1/2}}$

Еще один универсальный набор ворота , а на самом деле есть один ворота, это uniersal: 3-кубит Deutsch затвора D ( θ ) .$\{{\rm{CCNOT}},H\}$ ${D(\theta)}$