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

Вентиль Тоффоли (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

$\text{[math]}$ $\text{[math]}$ ${\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}}$ ${\displaystyle \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) в зависимости от значений на входе.

Существует другой широко известный универсальный обратимый трехвходовый вентиль - Вентиль Фредкина, CSWAP^[1].

ПримечанияПравить

↑ ¹ ² Technical Report MIT/LCS/TM-151 Архивная копия от 4 января 2015 на Wayback Machine (1980), а также вариант: Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen, ed. Reversible computing. Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. pp. 632–644. DOI:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. Параметры |author= и |last= дублируют друг друга (справка)

ЛитератураПравить

Technical Report MIT/LCS/TM-151 (1980), а также
- Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen, ed. Reversible computing (PDF). Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. pp. 632–644. DOI:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. Параметры |author= и |last= дублируют друг друга (справка)

Quantum Computing for Computer Architects: 2nd Edition // Morgan & Claypool Publishers, 2011, ISBN 9781608456192, page 15 "2.4 Example: the 3 qubit quantum Toffoli gate"

[toff1980-1] ¹ ² Technical Report MIT/LCS/TM-151 Архивная копия от 4 января 2015 на Wayback Machine (1980), а также вариант: Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen, ed. Reversible computing. Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. pp. 632–644. DOI:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. Параметры |author= и |last= дублируют друг друга (справка)

[1]