Reversible Evolution/可逆発展

量子力学において、測定とデコヒーレンスと言われる状態にダメージを与えるノイズ(ノイズについては第４週目でハードウェアや量子誤り訂正について議論する時に学びます)以外の全ての変化は可逆でなければならなりません。(数学的な用語では、ユニタリー行列によって表すことができるということを意味しています。) これは、出力されたの状態のみを利用して、それ以外の情報を必要とせず、入力した初期状態を再構築可能であることを意味しています。 ここでは、ゲートと呼ばれている離散的な操作とその可逆性について説明していきます。

基本的な古典論理ゲート

従来型のコンピュータを作る際に必要となる基本的な論理ゲートについて既に知見がある方々もいるかもしれませんが、まだよく知らない人のために一度復習していきましょう。 ゲートには、一つの入力ビットと一つの出力ビットを持ったゲートもあれば、二つの入力ビットと一つの出力ビットを持つものもあります。

NOT

NOTゲートは、その名の通り一つのビットを反転させます。

NOTゲートは可逆な操作です。例えば、同じ信号に二度NOTゲートをかければ、操作の後に出力される値は操作を始める前のものと同じものになることが分かるかと思います。

AND

ANDゲートは2つの入力ビットを持ち、両方の入力ビットが1だった場合のみ、出力値として1を返します。

ANDゲートは不可逆な操作です。異なる四つの入力状態 (00, 01, 10, 11)と二つの出力状態(0, 1)があり、出力だけからは入力がどんな値だったのかは分からなくなってしまいます。出力Cが1の場合は、両方の入力が1であったことが分かりますが、それ以外の場合は入力の値が何だったかは知ることができません。

OR

ORゲートは二つの入力ビットを持ち、両方の入力ビットが0だった場合のみ、出力値として0を返します。

ANDゲートと同様に、ORゲートも不可逆な操作です。 異なる四つの入力状態(00, 01, 10, 11)と二つの出力状態 (0, 1)があり、出力だけからは入力がどんな値だったのかを推測することはできません。 この場合、出力Cが0の場合のみ、両方の入力が0であったことが分かりますが、それ以外では入力値が何だったかを知ることはできません。

実際、ANDかORゲートの場合、たとえ出力値に加えて、２つの入力値のうち一つがわかっていたとしても、もう一つの入力値が何だったのかを、すべてのケースに対して知ることはできません。

XOR

XORゲート(exclusive OR)は、二つの入力ビットをとり、一つの入力ビットだけが1だった場合にのみ出力は1になります。

XORゲートは可逆に近い操作です。 二つの入力ビットと一つの出力ビットをもち、出力値だけで入力値を逆算することはできませんが、２つの入力値のどちらか一つを与えられれば、もう片方の入力値についても自動的に知ることができます。 続いて、最も重要な2量子ビットゲートが、XORゲートに関連していることを学んでいきます。

可逆古典ゲート

エントロピーと情報

1970年代前半、カルフォルニア工科大学のRichard Feynman、IBMのCharles Bennett、MITのTommaso Toffoli と Ed Fredkin等によって可逆論理演算の基礎が築かれました。 Bennettは当時、Rolf Landauerの助手として働いていました。Rolf Landauer 教授は、情報の破壊が宇宙のエントロピーを増大し廃熱をもたらすことを発見した研究者です。

エントロピーとは、何かに存在する無秩序の度合いを示す物理量です。 皆さんが、物理や化学の授業を受けていれば、その中で熱力学を学ぶ際にエントロピーについて勉強したことがあると思います。 ある場所にエネルギーを蓄えれば、それをモーターの回転などの仕事に使うことができます。 こういった仕事はエネルギーを周囲に拡散します。 一度エネルギーが広がりきると、エントロピーは最大化し、もはや有効な仕事に使うことができなくなります。

コンピュータサイエンスの分野においても、「情報のエントロピー」という概念があります。もしあながた一定量のデータを持っていたら、それが全て0か全て1のどちらかだとすると、友達にどのように同じ状態を再構築するかを教えるのはとても簡単です。単に、「私は700個の1を持っています」と教えるだけです。もしデータがより複雑になると、それを記述することは難しくなり、これを「エントロピーが高い」と表現します。

私(Van Meter)はカルフォルニア工科大学でFeynmanの講義を受けていたときのことを思いまします。 彼は講義で、熱力学の観点から情報とエントロピーの関係性を説明していました。 私は長い間、Feynman先生が只単に比喩的な話をしていると信じており、なぜ物理定数が関係してくるのか理解できていませんでした。 後に、彼が比喩ではなくまさにそのことを話していたのだということがわかった時、鳥肌が立ってしまいました。 これは、私が今まで出会った考え方の中で最も驚いたものの一つです。

可逆計算

一般的に、エントロピーは情報を失った時か消された時に増大します。 以前議論したANDゲートやORゲートは必ず情報の一部が失われることを思い出してください (2つの入力ビットから始まり、一つの出力ビットで終わるため、全ての情報を保持することができません)。

もし、全ゲートについて入力と出力が同じ数であるなら、、処理を元に戻すことが可能かもしれません。 それでも、完全なる「可逆」のためには、もう一つの条件が必要になります。その条件とは、すべての出力状態は、それぞれ一意に決まる入力状態と対応付けられている、という場合です。そのとき、関数は”one to one”、もしくは全単射であると言えます。

すべての論理関数は、1ビット、2ビット、3ビットの可逆ゲートを用いて計算することができます。 そういった論理関数をいくつか見ていきましょう。

単位(Identity)ゲート

単位ゲートは入力値に変化を与えず、そのまま出力値として同じ値を返します。 出力と入力は常に同じ値であるため、明白に可逆であることが分かります。 出力値から入力値に逆戻りしたい時、単位ゲートの場合は何か特別な処理を施す必要性はありません。

NOTゲート

既にNOTゲートについては学びました。 NOTゲートを２回連続して実行すると、初期入力値に戻すことが可能です。

NOT(NOT(X)) = X

CNOTゲート

CNOT(controlled NOT gate, or CNOT)は二つの入力ビットをとり、二つの出力ビットを生み出します。 もし片方のビット(制御ビットと呼ばれる)が1の場合、もう片方のビット(ターゲットビットと呼ばれる)は反転されます。 もし制御ビットが0の場合、ターゲットビットの状態は変わらず、そのまま出力されます。

A は (A′) の値と常に同じであり、 (B′)は(A)と(B)を XOR でかけた(B’ = A oplus B)であることが分かります。もしCNOTゲートを２回連続で適用した場合、(A)は同様に同じ状態を保持し、ターゲットビットである(B)は(B” = A oplus (A oplus B) = B)になり、結果、初期値に戻すことができます。

CCNOTゲート (Toffoliゲート)

CCNOT(control-control-NOT gate)はTommaso Toffoli.に因んで、Toffoli （トフォリ）ゲートとも呼ばれています。CCNOTは二つの制御ビットを必要とします。

このゲートは3ビットの入出力をもちます。最初の2ビットはそのまま出力します。もし入力の最初の2ビットが1なら、第3のビットは反転して出力されます。

CSWAPゲート (Fredkinゲート)

CSWAPゲート(control-SWAP gate)は、Ed Fredkinに因んでFredkinゲートとも呼ばれます。 もし制御ビット（入力A）が0の場合、他のビット（入力B、入力C）の状態は何も変化せずに出力されます。 逆に、1だった場合、他の2つのビット状態は交換され、出力されます。

制御ビットはそのまま出力されます。

CCNOTやCSWAPゲートは、其々のゲートだけで任意の古典論理回路を組むことができる、強力なゲートの一例として挙げられます。

単一量子ビットゲート

上記の可逆ゲートには、其々対応した量子ゲートが存在しており、一般的にはそれらを用いることで量子アルゴリズムを構築していきます。 しかし、量子ビットは、ユニタリに分類される多様な演算を施すことができるため、古典ビットのケースより複雑になります。 まずは、上記の単位ゲートとNOTゲートを超える単一量子ゲートを見てみましょう。

ブロッホ球上での回転

量子ビットについて学んだ時に、ブロッホ球表記についても紹介しました。 一文で復習すると、ブロッホ球は球面状の一点を指すベクトルを使って、任意の単一量子ビットの状態を視覚的に表す手法です。 単一量子ゲートは、それぞれブロッホ球の(X)軸、(Y)軸、(Z)軸を中心とした回転として理解することができます。

回転は自然に反転する操作で、同じ量だけ反対方向に回転させればいいのです。球体上のすべての点には始点と終点があり、二つの点が一緒になることはありません。二つの異なる出発点が同じ終点に来ることはありません。これは可逆性を維持するための重要な要素です。もし二つの点が一緒になったとしたら、操作を逆に行おうとしたときに、二つの点を区別して別々の開始位置に戻す方法がありません。

NOTゲートとその他のXゲート

古典的なNOTゲートのように、可逆な(X)ゲートは0を1に、1を0に変換します。 実際には、量子状態は重ね合わせの場合もあるため、0と1の値、すなわち0と1のダイアルの中身を交換します。 ブロッホ球上では、ある状態に(X)ゲートの演算を行うことは、(X)軸を中心として状態ベクトルを180度((pi))回転する処理に値します。 実際は任意の角度で回転させることができるので、0の値と1の値を部分的に交換することが可能です。

位相ゲート

(X)軸を中心とした回転は古典的なNOTゲートに似ている操作ですが、(Z)軸を中心に状態を回転させる操作に対応する古典的なゲートは存在しません。(Z)回転は、その量子状態の位相を変換します。 (Z)軸を中心に180度((pi))の回転を加える操作を「Zゲート」と呼びます。もちろん、他の角度の場合は、「Z回転」、もしくは「位相ゲート」と呼び、その角度を明記します。

アダマール ゲート

アダマールゲートは重ね合わせを作るために用いる、最も基本的な操作です。(vert0rangle)の状態を50/50の割合で(vert0rangle)と(vert1rangle)の重ね合わせに変換します。

[vert0rangle rightarrow frac{vert0rangle + vert1rangle}{sqrt{2}}]

もしアダマールゲートを(vert1rangle)の状態にかけて、上記と同じ50/50の重ね合わせになってしまったら、それは不可逆な操作になってしまいます。(vert1rangle)の状態にアダマールゲートをかけるときは、位相をねじって重ね合わせます。

[vert1rangle rightarrow frac{vert0rangle + (pi)vert1rangle}{sqrt{2}}]

アダマールゲートを同じ量子ビットに２回連続して適用すれば、出力状態は初期の入力状態と常に同じになります。 物理的には、この操作は波の干渉にあたります（はじめて登場しますね！）(vert0rangle)にアダマールゲートをかければ、新しい(vert0rangle)状態は元の(vert0rangle)状態と(vert1rangle)状態の強め合い干渉によって生成され、(vert1rangle)状態は弱め合い干渉によって消滅します。

[frac{vert0rangle + vert1rangle}{sqrt{2}}rightarrow vert0rangle]

ここで位相が重要になってきます。

位相が180度ずれている場合、アダマールゲートをかければ、新しい(vert1rangle)状態は元の(vert0rangle)状態と(vert1rangle)状態の強め合い干渉によって生成され、(vert0rangle)状態は弱め合い干渉によって生成されます。

[frac{vert0rangle + (pi)vert1rangle}{sqrt{2}}rightarrow vert1rangle]