Вентиль Тоффоли

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Графическое представление вентиля Тоффоли

Вентиль Тоффоли (CCNOT) — универсальный контролируемый квантовый вентиль, предложенный Томасом Тоффоли в 1980[1]. Было доказано, что, используя только этот вентиль, можно построить любой обратимый процессор.

Вентиль Тоффоли по принципу работы похож на CNOT. Имеет три входа и три выхода, если два первых входа равны единице, то значение последнего бита обращается. В противном случае все входы подаются на выход неизменными. Таблица истинности и матрица для CCNOT выглядят следующим образом:

Таблица истинности Матрица преобразования
ВХОД ВЫХОД
 0   0   0   0   0 

 0 

0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0


\begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{bmatrix}

Докажем, что вентиль является универсальным. Если разложить гейт на простые булевы операции, то можно заметить, что первый и второй кубит всегда равны на входе и выходе, а третий кубит на выходе имеет вид C = C XOR (A AND B), где A, B и C — входы и выходы вентиля. Видно, что вентиль является универсальным, так как он выполняет любую из операций (NOT, AND, XOR и FANOUT) в зависимости от значений на входе.

Примечания[править | править вики-текст]

  1. Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso (1980). "Reversible computing" in Automata, Languages and Programming, Seventh Colloquium. J. W. de Bakker and J. van Leeuwen: 632-644, Noordwijkerhout, Netherlands: Springer Verlag. DOI:10.1007/3-540-10003-2_104. 

Литература[править | править вики-текст]