トフォリゲート
すべての可逆ゲートは同じ数の入力ビットと出力ビットをもつ。これは鳩の巣原理による。
1ビットに対しては、恒等写像とNOTゲートのふたつの可逆ゲートがある。この二種類はどのビット数に対しても同様のゲートが定義できる。
2ビットに対しては、上の二種類と交換などの自明なものを除くと、制御NOTゲートが唯一の演算である。このゲートは一つ目の入力を二つ目の入力にXORし、二つ目に出力する。一つ目の入力はそのまま出力される。動作を以下に示す。
また、論理式で表すと次のようになる(複数ビットの出力をタプルで表した)。
C N O T ( x , y ) = ( x , x ⊕ y ) {\displaystyle CNOT(x,y)=(x,x\oplus y)}
しかし、この演算のみでは表現できない可逆計算が存在する。つまり、CNOTは機能的完全性を持たない。機能的完全性(英語版)を持つ演算の一つがトマソ・トフォリによって提案されたトフォリゲートである。