量子回路
再び、最初の「可逆な」古典計算について考える。 概念的には、可逆なnビット回路と可逆なnビット論理ゲートの間に違いはない。なぜならどちらも、 nビット列空間上の単なる可逆関数だからである。 ただし前節で述べたように、工学的な理由から、可逆回路を構成するために組み合わせられる少数の単純な可逆ゲートが必要である。
この構成の過程を説明するために、可逆なn-ビットゲートfと、可逆なm-ビットゲートgがあるとする。 これらを合成することは、次の図のように、 fのk-ビットの出力を、gのk-ビットの入力に接続して新しい回路を作成することを意味する。 以下の例では、 n = 5, k = 3, m = 7である。 結果の回路も可逆で、(n +m-k)-ビットで動作する。
この方法は古典的結合(classical assemblage)と呼ばれる。(この概念は、以下に引用するKitaevの先駆的な論文の技術的定義に対応している。)。これらの可逆機械を構成するために、中間的な機械も可逆であることを確認することが重要である。 この条件は、 計算の途中で「ゴミ」が生成されないことを保証する。(正味の物理的効果は、エントロピーを増加させることである。これは、この演習を行う動機の1つである。)
これで、 トフォリゲートが汎用ゲートであることを示すことができる。