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

Question

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

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

Answer 1

Тоффоли универсален для классических вычислений (как показано @Victor). Тем не менее, Toffoli не является универсальным для квантовых вычислений (если у нас нет чего -то сумасшедшего, например, $ p = bqp $).

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

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

Answer 2

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

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

Что означает в простых терминах, что любая логическая функция может быть построена только с Toffoli Gates.

Логические функции обычно строится из OR, а не Gates, которые могут быть объединены, чтобы сформировать любую логическую функцию. Широко известно, что то же самое возможно только с ними, или только с Нанд Гейтс.

Ворота Тоффоли могут быть обобщены как:

$ rm {toffoli} (a, b, c) = begin {case} (a, b, Âc) & mbox {когда} a = b = 1 (a, b, c) & mbox {иначе.} end {case} $

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

$ rm {toffoli} '(a, b, c) = begin {case} âc & mbox {when} a = b = 1 c & mbox {иное.} end {case} $

При этом можно определить ворота Нанда как:

$ operatorName {nand} (a, b) = rm {toffoli} '(a, b, 1) $

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

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

$ OperatorName {не} (x) = rm {toffoli} '(1, 1, x) $

$ OperatorName {и} (a, b) = rm {toffoli} '(a, b, 0) $

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

$ OperatorName {или} (a, b) = operatorname {не} ( operatorname {и} ( operatorname {не} (a), operatorname {не} (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 применяется дважды, исходный вход Get в качестве вывода.

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

Как показано здесь, Врата Deutsch определяется аналогичным образом, как ворота Тоффоли, но вместо классических ворот они квантовы:

$ operatorName {deutsch} (a, b, c) = | a, b, c rangle mapsto begin {case} i cos ( theta) | a, b, c rangle + sin ( theta ) | a, b, 1-c rangle & mbox {for} a = b = 1 | a, b, c rangle & mbox {иначе.} end {case} $

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

$ rm {toffoli} (a, b, c) = operatorname {deutsch} ( frac { pi} {2}) (a, b, c) $

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

Можно получить универсальный набор квантовых TGATE, если мы объединим ворота Тоффоли, которые дают ворота хадамарда. Это именно то, что делают ворота Deutsch.

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