Универсальность ворот Тоффоли

Относительно квантовых ворот Тоффоли :

1. это классически универсально, и если так, то почему?
2. это квантово универсально и почему?

Toffoli универсален для классических вычислений (как показано @Victor). Однако Toffoli НЕ универсален для квантовых вычислений (если только у нас нет чего-то сумасшедшего, например, ).$P = BQP$

Чтобы быть универсальным для квантовых вычислений (по обычному определению), группа, генерируемая вашими воротами, должна быть плотной в унитарных. Другими словами, при произвольном и целевом унитарном есть некоторый способ применить конечное число ваших квантовых вентилей, чтобы получить унитарный такой, что .$\epsilon$$U$$U'$$||U - U'|| < \epsilon$

Toffoli сам по себе явно не универсален в этом определении, поскольку он всегда переводит базовые состояния в базовые состояния и поэтому не может реализовать то, что принимает , например. Другими словами, это не может создать суперпозицию.$|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

Из статьи Википедии, которую вы цитировали :

Ворота Тофоли универсальны; это означает, что для любой булевой функции f (x1, x2, ..., xm) существует схема, состоящая из вентилей Toffoli, которая принимает x1, x2, ..., xm и некоторые дополнительные биты, установленные в 0 или 1, и выводит x1, x2, ..., xm, f (x1, x2, ..., xm) и некоторые дополнительные биты (называемые мусором). По сути, это означает, что можно использовать вентили Тофоли для построения систем, которые будут выполнять любые желаемые вычисления булевых функций обратимым образом.

Это означает, что любая булева функция может быть построена только с помощью элементов Тофоли.

Булевы функции обычно создаются из вентилей OR, AND и NOT, которые могут быть объединены для формирования любой логической функции. Широко известно, что то же самое возможно только с воротами NOR или только с воротами NAND.

Ворота Тофоли можно обобщить так:

$\rm{Toffoli}(a, b, c) = \begin{cases} (a, b, ¬c) & \mbox{when }a=b=1 \\ (a, b, c) & \mbox{otherwise.}\end{cases}$

Поскольку первый и второй выходы всегда равны первому и второму входам, мы можем их не учитывать. Итак, мы имеем:

$\rm{Toffoli}'(a, b, c) = \begin{cases} ¬c & \mbox{when }a=b=1 \\ c & \mbox{otherwise.}\end{cases}$

При этом возможно определить шлюз NAND как:

$\operatorname{NAND}(a, b) = \rm{Toffoli}'(a, b, 1)$

Поскольку ворота NAND универсальны, а ворота NAND могут быть определены как ворота Тофоли, то ворота Тоффоли универсальны.

Есть еще один способ доказать, что Toffoli универсален, путем прямого конструирования вентилей AND и NOT:

$\operatorname{NOT}(x) = \rm{Toffoli}'(1, 1, x)$

$\operatorname{AND}(a, b) = \rm{Toffoli}'(a, b, 0)$

Затем мы можем построить ворота ИЛИ, используя законы Де Моргана :

$\operatorname{OR}(a, b) = \operatorname{NOT}(\operatorname{AND}(\operatorname{NOT}(a), \operatorname{NOT}(b)) = \rm{Toffoli}'(1, 1, \rm{Toffoli}'(\rm{Toffoli}'(1, 1, a), \rm{Toffoli}'(1, 1, b), 0))$

РЕДАКТИРОВАТЬ, так как вопрос был отредактирован, а его рамки изменились:

Во-первых, я не понимаю квантовые вычисления, поэтому, если что-то не так, добавьте комментарий. Я провел небольшое исследование, чтобы попытаться завершить этот ответ, и закончил так:

Ворота Тофоли обратимы (но использованное выше Тофоли не является). Это означает, что любое вычисление, выполненное с ним, может быть отменено. Это:

$(a, b, c) = \rm{Toffoli}(\rm{Toffoli}(a, b, c))$

Это означает, что для любой тройки (a, b, c), если Toffoli применяется дважды, исходный вход получает как выход.

Обратимость важна, потому что квантовые ворота должны быть обратимыми, поэтому (классические) ворота Тоффоли могут быть использованы в качестве квантовых ворот из-за этого.

Как показано здесь , ворота Дойча определяются так же, как и ворота Тоффоли, но вместо классических ворот они являются количественными:

$\operatorname{Deutsch}(a, b, c) = |a,b,c\rangle \mapsto \begin{cases} i \cos(\theta) |a,b,c\rangle + \sin(\theta) |a,b,1-c\rangle & \mbox{for }a=b=1 \\ |a,b,c\rangle & \mbox{otherwise.}\end{cases}$

Таким образом, ворота Toffoli являются частным случаем ворот Deutsch, где:

$\rm{Toffoli}(a, b, c) = \operatorname{Deutsch}(\frac{\pi}{2})(a, b, c)$

Ворота Тофоли выполняют классические вычисления, в них отсутствует операция фазового сдвига, это будет означать, что ворота Тофоли могут использоваться только для фазовых сдвигов на 90 градусов ( ) (и путем объединения нескольких вентилей, чтобы получить кратные 90 градусов). Но это также означает, что он не может быть использован для создания совмещений состояний, потому что для этого потребуются сдвиги фаз на углах, не кратных 90 градусам, поэтому вентиль Тоффоли не является универсальным квантовым вентилем.$\frac{\pi}{2}$

Универсальное квантовое множество Тгейта может быть получено, если мы объединим ворота Тоффоли с воротами Адамара. Это именно то, что делают немецкие ворота.

Интересные ссылки можно найти здесь , здесь и здесь . Возможная ценная ссылка, показывающая основы преобразования Дойча, должна быть здесь , однако ссылка защищена паролем.