量子回路
つまり、上記のような任意の古典的結合に関連して、 fの代わりにn-量子ビットゲートUが、 gの代わりにm-量子ビットゲートWがある場合、可逆な量子回路を生成できる。ここでは以下の図を例に説明する。
この方法でゲートを接続することで、 (n+m-k)-量子ビット空間におけるユニタリ作用素が生成されるという事実は簡単に確認できる。 実際の量子コンピュータでは、ゲート間の物理的な接続は、 デコヒーレンスが発生する可能性がある場所の1つであるため、工学上の課題である。
普遍性、すなわち、少数の種類のゲートの組み合わせのみで、任意の量子回路が構成できることも証明されている。こうした量子回路の普遍性定理(universality theorems)は、たとえばあるθに対する1-量子ビットの位相ゲートUθと、2-量子ビットCNOTゲート W CNOTの組に対してのものが知られている。
ただし、量子回路の普遍性定理は、古典的回路の普遍性定理よりも弱い主張になっている。なぜなら、任意の可逆n-量子ビット回路が、これら2つの基本ゲートから組み立てられた回路によって任意に適切に近似できることのみを主張しているからである。また、古典的回路とは異なり、非可算な角度θに対して同じ量だけの位相ゲートが存在するため、少なくともこれらは有限の{(Uθ, WCNOT)}のみでは表現できないことにも注意が必要である。
一般に、NOTゲート以外の古典的コンピュータの基本論理ゲートは不可逆演算であり、入力から出力にかけて情報が失われる。たとえば2入力ANDゲートにおいて出力ビットが0であったという結果のみから、それが01, 10, 00のどの入力ビットの組み合わせから得られたものなのか知ることは不可能である。
ただし、古典的コンピュータにおいても、NOTゲートに代表されるように、任意の長さのビット列に対して可逆ゲートを構成することができないわけではない。理想的には、可逆ゲートは情報の損失と物理学的エントロピーの増加に伴う電力消費や熱損失の問題を生じないため、応用面でも関心が寄せられている。一般に可逆ゲートは、ビット列を入力として受け取り、同じ長さのビット列を出力する可逆な関数として表される。長さnのビット列は、0と1だけで構成される文字列x1x2 ... xn∈{0,1}として表現され、このようなビット列は全部で2通り存在する。
より厳密には、可逆ゲートとは、ビット列の集合{0,1}から自身への全単射写像fとして表現される。このような可逆ゲートfの例としては、たとえば入力に定められた置換を適用する写像などが挙げられる。現在、こうした置換を用いて可逆な古典的論理ゲートを構成する手法は、真偽表などを用いて簡単に表現できる範囲の小さいn(例: n = 1, 2, 3)についてのみ研究されている。
この回路をビット列の古典的写像に関連付けるには、次のように指定する。
入力レジスタ:m-古典的ビット列 'X' = {0,1}
出力レジスタ:n-古典的ビット列 Y = {0,1}
入力レジスタの内容x = x 1 .. x mは、量子ビットレジスタを何らかの方法で初期化するために使用される。 理想的には、これは以下の計算基底状態として与えられる。
| x → , 0 ⟩ = | x 1 , x 2 , ⋯ , x m , 0 , ... , 0 ⏟ r − m ⟩ , {\displaystyle |{\vec {x}},0\rangle =|x_{1},x_{2},\cdots ,x_{m},\underbrace {0,\dots ,0} _{r-m}\rangle ,}
ただし、前述の通りこのように理想的な初期状態を用意することは現実的には不可能であるため、初期状態がいくつかの適切な近似尺度の理想化された入力に近い密度演算子Sによって与えられた混合状態であると仮定する。
Tr  ( | | x → , 0 ⟩ ⟨ x → , 0 | − S | ) ≤ δ . {\displaystyle \operatorname {Tr} \left({\big |}|{\vec {x}},0\rangle \langle {\vec {x}},0|-S{\big |}\right)\leq \delta .}
これは、任意の可逆的な古典的なnビット回路hが与えられた場合、上記の方法でトフォリゲートの古典的結合により、次のような( n + m )ビット回路fを生成できることを意味する。
f ( x 1 , ... , x n , 0 , ... , 0 ⏟ m ) = ( y 1 , ... , y n , 0 , ... , 0 ⏟ m ) {\displaystyle f(x_{1},\ldots ,x_{n},\underbrace {0,\dots ,0} _{m})=(y_{1},\ldots ,y_{n},\underbrace {0,\ldots ,0} _{m})}
さらに次式が成立する。
( y 1 , ... , y n ) = h ( x 1 , ... , x n ) {\displaystyle (y_{1},\ldots ,y_{n})=h(x_{1},\ldots ,x_{n})} .
この最終結果では、常に補助ビットとしてm個のゼロの文字列があることに注意。 いわゆる「ゴミ」は生成されないため、この計算は実際には、物理学的エントロピーを増加させない。 この問題は、Kitaevの論文で注意深く説明されている。
より一般に、任意の関数f は、(全単射・それ以外どちらであっても)トフォリゲートのみ回路によって模倣できることが知られている。 写像が単射でない場合は、計算途中(たとえば、最後のステップ)で「ゴミ」が生成されることは明らかである。
量子回路については、量子ビットゲートの同様の構成を定義できる。