ドイチュのアルゴリズム

有名なドイチュのアルゴリズム（1985）についてです。いろいろな本の中でも「量子アルゴリズム（中山茂著）」がもっとも分りやすいように思います。その本には量子コンピュータでの qubit の流れがほとんど省略されずに書かれているので、数式というよりパズルをしっかりと追いかけることができます。その後で他の本や HP を見ると、後者で省略されている既知の流れの箇所も理解しやすいでしょう。

しかし、一度は理解したように思ったものの、本を閉じると「全体としてこういう原理に基づいているんだよ」という（木ではなく）森の部分がどうしても分からないのです。

ここで、上記の本に基づいて、「ちゃんとしたコイン」と「偽のコイン」を例にとって考えることにしました。偽のコインは、表と裏が同じなのです。両面に 0 が書かれているかもしれないですし、1 かもしれません。 f(0) は「おもて面は何ですか？」 f(1) は「裏面は何ですか？」という問いかけに相当します。ここで 0 が返ってきたら「 f(0)=0 おもて面には 0 が書かれています」「 f(1)=0 裏面には 0 が書かれています」という意味になります。一方、1 が返ってきたら「 f(0)=1 おもて面には 1 が書かれています」「 f(1)=1 裏面には 1 が書かれています」という意味になります。

コインの表と裏が異なる、つまり「ちゃんとしたコイン」であることを確かめようとすると、普通は f(0) と f(1) の両方を尋ねる必要があります。同様にコインが偽造されていて、表と裏が同じであることを確かめようとしても、やはり f(0) と f(1) の両方を尋ねる必要があります。ここで、両面とも 0 であるのか、あるいは 1 であるのかは問題ではなく、両面が "同じ" であること（両面とも 0 か、あるいは両面とも 1 であること）が知りたいことなのです。この場合、古典的な方式ですと、必ず f(0) と f(1) の合計２回尋ねる必要が出てきます。

ところが、量子コンピュータの場合、f(0) と f(1) を同時に尋ねることができます。何故でしょうか？量子の世界では重ね合わせが可能であり、f(0 and 1) と問いかけを共存させることができるためです。ここでの注意点は f(0 or 1) ではないということです。この f(0 or 1) の問いかけは古典的方式であり、量子方式では f(0 and 1) の "共存" という概念が鍵となります。

ちょうど１つの電子（光子）を２本のスリットに通すと背面に縞模様ができる原理と同じです。電子という１つの粒子のように見えますが、これは波動性も持っているため、左と右の両方のスリットを同時にすり抜けます（これが and）。そして、この二つが波としての干渉性をもつために背面に縞模様ができるわけです。多世界解釈では、左のスリットを通る電子の世界と、右のスリットを通る電子の二つの世界があり、それぞれがマクロの世界で観測されない限りは両世界の間で干渉性をもつことができます（これが縞模様）。しかし、どちらかが観測されてしまうと、観測によってマクロの世界に爪痕を残してしまうため、左と右はもはや干渉しあうことができず（デコヒーレンス）、縞模様も消えてしまうのでした。したがって、量子コンピュータでもその縞模様を見ようとすると、オラクル f(x) の中身を観ることができません。そっとしておいて、出てきた結果だけを見て計算結果を知ることになります。

それでは (x=0 and 1) と重ね合わせ状態をとにかく作り、同時におもて面と裏面を尋ねることにしましょう。答として f(0 and 1) = 0+0, 0+1, 1+0, 1+1 が返ってきそうです。f(0) と f(1) の両方を同時に尋ねることができるのだから、もうこれで正常コインか偽コインかは分かりそうなものです。しかし、これが返ってきても、正常コインなのか、それとも偽造コインなのかが分からないのだそうです。私もこの理由はよく分からなかったのですが、一つの考えられる理由として、量子コンピュータは可逆的でないといけないという制約のためです。もし可逆的であるとすると、二回同じ動作をさせると元に戻ります（１回目の出力を２回目の入力にする）。しかし、上記の方法では元に戻らないとのことです。また直接観測してしまうと、波動が収縮して f(0 or 1) と同じ結果となってしまい、ある時は f(0) が、またある時には f(1) が返ってくるだけのでしょうか？

そこで、出力にちょっと工夫を凝らして、最終的には f(x) の結果を直接観測しないような仕組みが入出力に組み込まれています。そこがややこしいのです。まず、単純な f(x) ではなくて、f(x) - 逆(f(x)) が出力されるようにします。ここで、逆(f(x)) とは、f(x) が 0 の場合はその逆の 1 を、1 の場合はその逆の 0 を出力します。この逆を出すという操作は、二進数では１を足すことに相当します（XOR, 排他的論理和）。0+1 = 1 のように 0 に 1 を足すと 1 になります。逆に 1+1 = 0 のように 1 に 1 を足すと 0 になります（二進数で桁が上がるため）。

では、まず「おもて面」x=0 から尋ねてみましょう。

(a) f(0)=0 ---------> f(0) - 逆(f(0)) = 0 - 1 = +(0 - 1)
(b) f(0)=1 ---------> f(0) - 逆(f(0)) = 1 - 0 = -(0 -1)

本当は同時になのですが、ここでは、次に「裏面」x=1 を尋ねてみましょう。

(c) f(1)=0 ---------> f(1) - 逆(f(1)) = 0 - 1 = +(0 - 1)
(d) f(1)=1 ---------> f(1) - 逆(f(1)) = 1 - 0 = -(0 - 1)

ここで (0 - 1) の前についているプラスとマイナスの符号が重要なのです。x が 0 か 1 かにかかわらず f(x)=0 であれば、プラス符号となっています。逆に f(x)=1 であればマイナス符号となっています。f(x) - 逆(f(x)) は、f(x) の値が 0 であれば -1 を、f(x) の値が 1 であれば +1 を返します。 これを波に例えると、お互いに振幅が逆になっているだけで、もし一方をひっくり返すと、他方にぴたりと一致します。このように波の振幅の符号だけが異なるようにしてあげると、波そのものを観測して収縮させてしまうことなしに、符号だけを別の qubit で拾い上げることができるらしいです。

量子方式では、f(0) と f(1) を同時に尋ねることができました。もし、この応答が -1 どうしであれば f(0)=0, f(1)=0 であり、偽コインであることが判明します。また、+1 どうしであっても f(0)=1, f(1)=1 であり、やはり偽コインです。逆に正常コインであれば、プラスとマイナスの組み合わせとなるはずです。

古典方式の場合、「f(0) 表面は何ですか？」と尋ねた時と、続けてその後に「f(1) 裏面は何ですか？」と尋ねた時の答が同じであれば、両面同じの偽コインであり、逆に異なれば正常コインであることが判明します。一方、量子方式ではこの質問を同時に（共存させて１回で）おこなうことができ、その答が同符号であれば、両面同じの偽コインであり、異符号であれば正常コインであることが判明します。

古典方式

表と裏を順番に一回ずつ尋ねる x=0 or 1 ----> 尋ねられた面に刻まれている数値 0 か 1 がそれぞれの回で出力される。

量子方式

表と裏を同時に一回だけ尋ねる x=0 and 1 ----> 尋ねられた面に刻まれている数値が 0 の場合は -1 が、1 の場合は +1 が表裏同時に出力される。

では、f(0) + f(1) の足し算を出力値として作ってはダメなのでしょうか？
0 + 0 = 0, 1 + 1 = 0（偽コイン）
二進数に注意 1+1 = 2 ではなく桁が一つあがって０になります。
1 + 0 = 1, 0 + 1 = 1（正常コイン）
と分かり易いような気がします。
しかし、この値を直接読み取ってしまうと波動の収縮が起きてしまい、古典方式のように、ある時は f(0) だけ、またある時は f(1) だけの結果になってしまい、コインの真偽が分からないのでしょう。

f(x) - 逆(f(x)) = ＋－1 となりましたが、実は、これを直接読み取っているわけではありません。＋ か － かの符号だけを別の qubit に抱き合わせて、これを読み取ることによってコインの真偽を判定しています。f(x) - 逆(f(x)) を直接読み取ってしまうと、ここでも波の収縮が起こってしまい、f(0) - 逆(f(0)) か、あるいは f(1) - 逆(f(1)) しか観えてこないためでしょう。f(x) を含んだ出力は覗かずに、別の差しさわりのない qubit を使って符号だけを静かに読み取れば、f(0) と f(1) の重ね合わせを壊さない状態で f(0) - 逆(f(0)) の符号と f(1) - 逆(f(1)) の符号の両方を同時に見ることができるのです。

このように符号だけを別の qubit に抱き合わせる方法を「位相のキックバック」と呼ぶそうです。その場合、符号を見るための qubit と f(x) - 逆(f(x)) の qubit をうまい具合に切り離す必要があります。これらがエンタングルメント（もつれ）状態にあると、符号の qubit を読んだとたんに、その影響が f(x) - 逆(f(x)) に及んでしまいます。つまり、符号用 qubit ともつれている項だけが残り、もつれていない項は消滅してしまいます（観測による収縮）。よって、符号用 qubit を読んでも、これが f(x) - 逆(f(x)) に影響を与えないようにするには、これらの間に "もつれ" がない状態にする必要があります。それには f(x) - 逆(f(x)) を x の値にかかわらず同じ共通項に何とかしてやるのです。このもつれの解除は、数学的にはちょっと因数分解に似ています。因数分解のように、{符号用 qubit} x {f(x) - 逆(f(x)) qubit} のような形に分けられると、両者の間に「もつれ」がない状態となるわけです。そこで 1 を共通項として括り出してやると、その前の符号だけが、もう一つの {符号用 qubit} にキックバックされるという仕組みです。この符号だけが {符号用 qubit} に転送される仕組みは、私もよく理解できないのですが、とにかく「プラスマイナス何かの共通数値 s」という結果が f から出力されるように作ると、因数分解のように +-s で括り出すことができて、{符号用 qubit} に前の符号 + - だけが伝わると考えるとよいのでしょうか？

ドイチュのアルゴリズムにおける実際のオラクル部分はいろいろな教科書やウェブサイトに載っていますので、上記を頭に入れながらそれらを読むと、また新たな視点からこのオラクルを見ることができるのではないでしょうか？特に「量子コンピュータ（竹内繁樹著）」には、他書とはちょっと違ったオラクルが載っており、頭が混乱してしまいます。しかし、オラクルの中でゲートが対称的に配置されており、なるほど可逆的な操作であることが納得できるようになっています。

オラクルでは、二つ目の出力に y+f(x) という値が設定されています。この y には 0 と 1 が対応します。y=0 の時 y+f(x)=f(x) となります。y=1 の時は y+f(x)=1+f(x)= 逆(f(x)) となります。二進数の世界ですので、1+0=1, 1+1=0 となるためです。よって、y qubit への入力に 1 を与え、これをアダマール変換して (|0>-|1>) の重ね合わせ状態を作り出してやると、f(x) - 逆(f(x)) を作り出すことができます。一方、x qubit への入力には 0 を与え、これをアダマール変換して (|0>+|1>) の重ね合わせ状態を作り出します。これで同時に「おもて面は何？」と「裏面は何？」を尋ねることができるようになるわけです。

当然、出力値も重ね合わせ状態になっています。そこで、これをアダマール変換して、重ね合わせ状態をもとに戻してやり、観測します。

全然 NMR の話ではないではないか？と言われそうですが、最初の量子コンピュータは、これよりももっと複雑な素因数分解を扱ったもので、実は NMR で実装されたのでした。1H, 13C, 15N, 19F はスピン量子数 1/2 ですので、電子スピンと同じです。よって、NMR そのものがすでに量子コンピュータなのです。私がちょっと分からないのは、NMR のように多数のスピンが集合したアンサンブル状態でも、今走っている 1 スピン = 1 qubit の量子コンピュータと同じ概念で考えてよいのかどうかです。

これを書くのにいろいろと勉強してみたのですが、やはり難しく、疑問点がいっぱい出てきてしまいました。上記には間違いがたくさん含まれていると思いますが、気づいたらまた修正していきたいと思います。いずれにしても、NMR を触りながら、たとえ単純な 1H 90 度パルス幅決めであっても、上記のような不思議な量子重ね合わせ状態（あるいは多世界と考えてもよいでしょう）が今そこにあるんだと思うと、面白くならないでしょうか？病院の MRI でもそうです。

しかし、ここで「"緩和" さえ無ければねえ」と思うのは、量子コンピュータでも NMR でも同じ？