Toffoliho hradlo

Schematická značka pro Toffoliho hradlo

Toffoliho hradlo nebo také hradlo CCNOT je pojem z oboru logických obvodů. Jedná se o logické hradlo, které je reverzibilní, a zároveň platí, že jakýkoliv reverzibilní logický obvod lze sestavit za použití výhradně Toffoliho hradel. Pojmenováno je po Tommasu Toffolim, italsko-americkém elektroinženýrovi, který jej objevil.

Funkce

Má tři vstupy a tři výstupy. První dva vstupy jsou jen okopírovány na výstupy, zatímco třetí výstup je negací třetího vstupu, je-li na obou prvních vstupech logická jednička, jinak je rovněž kopírován.

Formální vyjádření

Pravivostní tabulka	Permutační matice
VSTUP VÝSTUP  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	$\left[\begin{array}{cccccccc}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{array}\right]$