可逆論理回路
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/07 09:25 UTC 版)
再び、最初の「可逆な」古典計算について考える。 概念的には、可逆なnビット回路と可逆なnビット論理ゲートの間に違いはない。なぜならどちらも、 nビット列空間上の単なる可逆関数だからである。 ただし前節で述べたように、工学的な理由から、可逆回路を構成するために組み合わせられる少数の単純な可逆ゲートが必要である。 この構成の過程を説明するために、可逆なn-ビットゲートfと、可逆なm-ビットゲートgがあるとする。 これらを合成することは、次の図のように、 fのk-ビットの出力を、gのk-ビットの入力に接続して新しい回路を作成することを意味する。 以下の例では、 n = 5, k = 3, m = 7である。 結果の回路も可逆で、(n +m-k)-ビットで動作する。 この方法は古典的結合(classical assemblage)と呼ばれる。（この概念は、以下に引用するKitaevの先駆的な論文の技術的定義に対応している。）。これらの可逆機械を構成するために、中間的な機械も可逆であることを確認することが重要である。 この条件は、 計算の途中で「ゴミ」が生成されないことを保証する。（正味の物理的効果は、エントロピーを増加させることである。これは、この演習を行う動機の1つである。） これで、 トフォリゲートが汎用ゲートであることを示すことができる。 これは、任意の可逆的な古典的な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 は、（全単射・それ以外どちらであっても）トフォリゲートのみ回路によって模倣できることが知られている。 写像が単射でない場合は、計算途中（たとえば、最後のステップ）で「ゴミ」が生成されることは明らかである。 量子回路については、量子ビットゲートの同様の構成を定義できる。 つまり、上記のような任意の古典的結合に関連して、 fの代わりにn-量子ビットゲートUが、 gの代わりにm-量子ビットゲートWがある場合、可逆な量子回路を生成できる。ここでは以下の図を例に説明する。 この方法でゲートを接続することで、 (n+m-k)-量子ビット空間におけるユニタリ作用素が生成されるという事実は簡単に確認できる。 実際の量子コンピュータでは、ゲート間の物理的な接続は、 デコヒーレンスが発生する可能性がある場所の1つであるため、工学上の課題である。 普遍性、すなわち、少数の種類のゲートの組み合わせのみで、任意の量子回路が構成できることも証明されている。こうした量子回路の普遍性定理(universality theorems)は、たとえばあるθに対する1-量子ビットの位相ゲートUθと、2-量子ビットCNOTゲート W CNOTの組に対してのものが知られている。 ただし、量子回路の普遍性定理は、古典的回路の普遍性定理よりも弱い主張になっている。なぜなら、任意の可逆n-量子ビット回路が、これら2つの基本ゲートから組み立てられた回路によって任意に適切に近似できることのみを主張しているからである。また、古典的回路とは異なり、非可算な角度θに対して同じ量だけの位相ゲートが存在するため、少なくともこれらは有限の{(Uθ, WCNOT)}のみでは表現できないことにも注意が必要である。
※この「可逆論理回路」の解説は、「量子回路」の解説の一部です。
「可逆論理回路」を含む「量子回路」の記事については、「量子回路」の概要を参照ください。
- 可逆論理回路のページへのリンク
