トフォリゲート
論理ゲート L が可逆であるとは、ゲートの表す関数が単射であること、すなわち任意の出力 y に対して L(x) = y を満たす入力 x がただ一つ定まることをいう。出力に対応する入力を求める L′(y) = x を逆ゲートという。例えば、以下のようにNOTゲートは可逆である。
一方、ANDゲートは可逆ではない。00、01、10に対する出力がすべて0となるため、出力0に対する入力が一つに定まらないためである。
可逆ゲートの研究は1960年代頃に始まった。その動機は、通常のゲートに比べて可逆ゲートは計算に使うエネルギーの消費が少ない(理想的にはゼロとなる)ことだった。通常論理ゲートでは入力する情報量に比べて出力する情報量が減り、入力された状態は失われる。これによって熱的エントロピーが下がり、生じた差分のエネルギーが周囲に熱として放出される。別の言い方をすると、回路の状態が変化する時電子がアースに流れ、エネルギーが僅かに回路外に持ち出されるということである。可逆ゲートは状態を交換して回るだけなので、情報は失われず、回路内のエネルギーは保存される。
可逆ゲートは、近年量子計算の分野で注目されている。量子計算では全ての遷移は可逆であり、重ね合わせによってより多くの計算機の状態を持つことができる。したがって、可逆ゲートは量子ゲートの機能の一部を再現するものであり、可逆的に計算できるものは量子コンピュータ上でも計算できる。