「１量子ビットしか使えない量子コンピューターでも古典コンピューターより強かった」とは実際どういうことなのか解説してみた

何の話かというと

先日、

www.jst.go.jp

・・・というプレスリリースのタイトルを見て、

　本当に 1qbit だけで動作する（有意な）計算モデルがあるのか！？

と一瞬驚愕したのですが、よくよく論文を読んでみると、「初期状態を 0 に設定できるのが 1qbit だけで、その他の n qbit はランダムに初期化される」という量子計算モデル（DQC-1）についての話だと分かりました。

（参考）Impossibility of Classically Simulating One-Clean-Qubit Computation

というわけで、冒頭のタイトルは私の中で、「（１量子ビットを除いて）ランダムに初期化される量子ビットを用いて（古典コンピューターではシミュレーションが困難と考えられる）有意な量子計算を実行するテクニックが考案された」というタイトルに脳内変換されて納得したわけですが、このテクニックが「言われてみれば確かにそうだけど、よく見つけ出したなぁ。いやすごい。」的な、量子回路のアルゴリズムの（私の中で）伝統的なパターンを踏襲していて面白かったので、アルゴリズムのあらましを解説してみたいと思います。最後まで読んでいただくと、きっと、量子アルゴリズムの奥深さを感じてもらえることでしょう。

純粋状態と混合状態の違いについて

量子コンピューターでは、「状態の重ね合わせ」という考え方が登場します。1つの量子ビットは、古典的には ${\mid 0 \rangle}$ もしくは ${\mid 1 \rangle}$ のどちらかの状態に対応するわけですが、量子回路の中（量子計算の途中）では、これら2つが重ね合わせられた状態を取り得ます。数学的には、これらの状態を基底ベクトルとする次のような複素ベクトルで表現されます。

　 ${\mid \psi \rangle} = c_0{\mid 0 \rangle} + c_1{\mid 1 \rangle}$ --- (1)

この時、この量子ビットの状態を観測すると、確率 $|c_0|^2$ で ${\mid 0 \rangle}$ の状態が、確率 $|c_1|^2$ で ${\mid 1 \rangle}$ の状態が観測されます。全確率が 1 になるという条件から、

　 $|c_0|^2+|c_1|^2 = 1$

という束縛条件がつくので、(1) は2次元の複素ベクトル空間内の球面上の1点に対応すると考えられます。何にせよ、量子ビットというのは、観測時において確率的な振る舞いをするという量子力学に固有の性質を持っています。

一方、現実の量子コンピューターを取り扱っていると、このような量子力学に固有の確率現象とは別に、普通の意味での確率的な現象にも遭遇することがあります。先ほどの「その他の n qbit はランダムに初期化される」という量子計算モデルは、もともとは、NMR を用いた常温で動作する量子コンピューターの研究の中で考案されたそうで、NMR の場合は（常温で動作するという特性から）計算に使用する量子ビットをきれいに初期化するのが困難という特徴があります。そこで、1量子ビットだけをがんばって ${\mid 0 \rangle}$ に初期化して、「残りの n 量子ビットの状態はよくわからない」という状態から計算を開始した時に、何か意味のある計算ができるだろうか、という事を考えてみるのが DQC-1 と呼ばれる計算モデルで、DQC-1 で実用的な計算ができれば、（量子ビットの初期化が困難な）NMR でも実用的な計算ができるかも知れない、という期待が持てるというわけです。なお、DQC-1 では、より正確に言うと、最後の計算結果の測定も最初に初期化した1量子ビットに対してのみ行うという制限があります。

また、「残りの n 個の量子ビットの状態はよくわからない」というのは、少し曖昧な言い方ですが、DQC-1 の場合は、シンプルに、「0..00」「0..01」「0..10」「0..11」・・・「1..11」の全部で $2^n$ 通りある状態のどれか1つに等確率でセットされるという前提をおきます。ここで言う「確率」は、 $2^n$ 個の目があるサイコロを振って決める、ということと同じで、あくまで、日常的な意味での確率を表します。

このように、日常的な意味で複数の状態を確率的に取り得る状態のことを量子力学では、「混合状態」と言います。

一方、(1) のような状態は、観測結果が確率的というだけで、量子ビットの状態としては、1つの確定した重ね合わせ状態であり、これを「純粋状態」と言います。

つまり、DCQ-1 は、最初の1量子ビットが純粋状態 ${\mid 0\rangle}$ であり、残りの n 量子ビットが $2^n$ 通りの状態の混合状態、という初期条件から計算をスタートする量子計算モデルということになります。

DQC-1 を用いた量子計算テクニック

冒頭の論文で示された計算テクニックは、比較的汎用性が高いもので、おおざっぱなアイデアは次のようなものになります。

まず、混合状態の n 個の量子ビットは、あらゆる状態がランダムに選択されるわけですが、何度も実験を繰り返せば、 $2^n$ 回に1回ぐらいは、 ${\mid 0..00\rangle}$ と、すべて 0 になった状態が登場する可能性があります。そこで、この n 個の量子ビットが ${\mid 0..00\rangle}$ という状態であるかをチェックして、（ ${\mid 0\rangle}$ に初期化された）最初の量子ビットをその結果を保存するフラグとして利用します。つまり、混合状態の n 量子ビットが ${\mid 0..00\rangle}$ であれば、最初の量子ビットを ${\mid 1\rangle}$ にフリップします。以降、この量子ビットを便宜上、「フラグビット」と呼びます。また、混合状態の n 量子ビットを「計算用量子ビット」と呼びます。

その後、計算用量子ビットを用いて所望の量子計算 Q を行います。この量子計算 Q は、演算先の量子ビットは ${\mid 0..00\rangle}$ に初期化されているという前提で動作するので、そうでない場合、その計算結果はデタラメで意味がありませんが、最終的に、先ほどのフラグビットを見て、計算結果を採用するかどうかを決めれば問題ありません。つまり、フラグビットが ${\mid 1\rangle}$ であれば計算結果を採択して、そうでなければ、計算結果を破棄します。（計算結果の読み出し方法の点については、後ほど説明するのでしばしお待ちを。。。）

この場合、1回の計算で必ずしも解が得られるとは限りませんが、計算理論においては、「確率的に答えを返す」という計算モデルも許容されており、これはこれで十分に役に立ちます。たとえば、

・条件 A が成立していれば確率 $p>0$ で TRUE を返す。（確率 $1-p$ で FALSE を返す。）
・条件 A が成立していなければ必ず FALSE を返す。（確率 0 で TRUE を返し、確率 1 で FALSE を返す。）

という動作をする関数があったとします。実際に条件 A が成立している場合、この関数を m 回実行すれば、確率 $1 - (1-p)^m$ で TRUE が返ってきます。m を十分に大きくすれば、実用上は問題ない範囲でほぼ必ず1回は TRUE が返ってくるので、条件 A をチェックする関数として、実用的に利用することができます。（m 回実行して、1度でも TRUE が返ってきたら全体の結果を TRUE、そうでなければ、全体の結果を FALSE とします。）

さて・・・これで、DQC-1 でも有意な計算ができそうな気がしてきましたが、ここで、計算結果を読み出す方法について考えます。先にちらっと触れましたが、DQC-1 では、最後の計算結果の読み出しは、最初の量子ビット（フラグビット）だけに制限されています。量子計算 Q を行った n 個の量子ビットを観測することは許されていません。そこで、量子計算 Q の結果を最後に、最初の量子ビットに書き出すという処理が必要になります。

しかしながら・・・

今のアルゴリズムでは、最初の量子ビットは、計算用量子ビットの初期状態が ${\mid 0..00\rangle}$ であったかどうかのフラグに使ってしまっています。計算結果を素朴に書き出すとフラグ情報が失われます。

そこで、量子計算 Q の動作を少し明確にして、先に説明した「確率的に答えを返す」という計算モデルだと仮定します。つまり、量子計算 Q は、ある条件 A に対して、

という振る舞いをします。TRUE / FALSE のリターン値は、n 個の量子ビットの最初の 1 量子ビットに 1 / 0 でセットされるものとします。ただし、Q はあくまで量子計算なので、ここで言う確率 p は、量子力学的な意味の確率になります。つまり、Q を演算した結果、計算用量子ビットは、

　 $c_0{\mid 0..00 \rangle} + c_1{\mid 0..01 \rangle} + \cdots + c_{2^n}{\mid 1..11 \rangle}$

という、 $2^n$ 通りの状態の（量子力学的な意味での）重ね合わせ状態になっており、条件 A が成立している場合、先頭部分が 1 の状態が観測される確率が p、先頭部分が 0 の状態が観測される確率が 1-p ということになります。条件 A が成立していない場合は、先頭部分が 1 の状態が観測される確率は 0 になります。

そして最後に、（ここがちょっとテクニックのいる所なのですが）、ある手法によって、

・Q の演算結果が FALSE であれば、フラグビットを 0 にリセットする

という事を行います。もう少し正確に言うと、実際の動作としては、

・Q の演算結果に TRUE が混じっていれば、フラグビットは一定の確率でそのままに保持されて、そうでなければ 0 にリセットされる。

というような形になります。

そうすると何がおきるかというと・・・

条件 A が実際に成立している場合、「計算用量子ビットの初期状態が ${\mid 0..00\rangle}$ であり、かつ、Q の演算結果が TRUE になって、かつ、フラグビットが保持される」という組み合わせが一定の確率で成立して、その結果、フラグビットは 1 の状態で残ります。（言い換えると一定の確率で 0 になる場合もあります。）逆に条件 A が成立していない場合は、フラグビットはかならず 0 になります。

つまり、最終的にフラグビットの 1 / 0 を TRUE / FALSE として返却すれば、先に説明した「条件 A について確率的に答えを返す」という計算モデルが実装されることになります。

いやー。長かった。

これ、文章で説明すると長くてわかりにくいのですが、実際の量子回路演算を数式で計算すれば、もう少しすっきりと説明ができちゃいます。次は、実際の演算内容を説明したいと思います。

DQC-1 による量子演算回路

ここからは、ある程度、量子回路をご存知の方向けの説明になります。

まず、論文に記載の量子回路はこちらになります。

最初と最後にあるのが n qbit を入力とする Toffoli gate で、n 個全部が 0 の場合に最上段の qbit を ${\mid 0\rangle} \Leftrightarrow {\mid 1\rangle}$ とフリップします。これが、計算用量子ビット（混合状態の n qbit）が ${\mid 0..00\rangle}$ であるかをチェックするフラグの役割になります。

その後、所望の量子演算 Q を施しますが、これは、Q を演算した後に n qbit のうちの最初の 1 個を観測した際に、

・条件 A が成立していれば確率 $p_A>0$ で ${\mid 1\rangle}$ が観測される。（確率 $1-p_A$ で ${\mid 0\rangle}$ が観測される。）
・条件 A が成立していなければ確率 $p_{\overline A} = 0$ で ${\mid 1\rangle}$ が観測される。（確率 $1-p_{\overline A}=1$ で ${\mid 0\rangle}$ が観測される。）

という演算であると仮定します。計算用量子ビットの中の最初の 1 量子ビットを ${\mid 1\rangle}$ に射影する演算子を

　 $\Pi = {\mid 1\rangle}{\langle 1\mid}\otimes 1^{\otimes n-1}$

とすれば、上記の確率 $p=p_A,\,p_{\overline A}$ は、次で計算されます。

　 $p = |{\langle 0..00\mid} Q^\dagger \Pi Q{\mid 0..00\rangle}|^2$ --- (2)

続いて、その後のちょうど真ん中にあるゲートは、Controlled-Z です。つまり、「最上段のフラグが 1 で、かつ、Q を演算した n qbit のうちの最初の 1 つが 1」という条件を満たした際に、状態ベクトル全体に -1 を掛けます。

話がやや複雑になってきたので、これ以降は、計算用量子ビットが ${\mid 0..00\rangle}$ で、フラグビットが 1 になった場合に限定して考えてみましょう。この場合、フラグビットが 1 であることは保証されているので、Controlled-Z は、計算用量子ビットの最初の量子ビットが ${\mid 0\rangle}$ か ${\mid 1\rangle}$ かで条件分岐して、（計算用量子ビット部分に対する）次の演算子と同等になります。

　 $\left\{{\mid 0\rangle}{\langle 0\mid}-{\mid 1\rangle}{\langle 1\mid}\right\}\otimes 1^{\otimes n-1} = 1^{\otimes n}-2\Pi$ --- (3)

ここでは、恒等式 $1 = {\mid 0\rangle}{\langle 0\mid}+{\mid 1\rangle}{\langle 1\mid}$ を用いて変形しています。

前述の量子回路では、この後、計算用量子ビットに $Q^{-1}=Q^\dagger$ を演算して、計算用量子ビットを初期状態 ${\mid 0..00\rangle}$ に戻します。

――― と、ここで重大な注意が必要です。

正確に言うと、先の Controlled-Z、つまり、(3) の演算が入っているので、 $Q^{-1}=Q^\dagger$ によって計算用量子ビットは完全な初期状態 ${\mid 0..00\rangle}$ に戻ることはありません。 $Q^{-1}=Q^\dagger$ を演算した直後の状態は、次になります。

　 $Q^\dagger(1^{\otimes n}-2\Pi)Q{\mid 0..00\rangle} = {\mid 0..00\rangle} - 2Q^\dagger\Pi Q{\mid 0..00\rangle}$

つまり、この状態には、 $- 2Q^\dagger\Pi Q{\mid 0..00\rangle}$ という、 ${\mid 0..00\rangle}$ 以外の状態が混ざっています。

したがって、この後、一番最後の Toffoli gate によって、再度、フラグビットを 0 にリセット（フリップ）にするわけですが、実際にリセットされる確率、すなわち、計算用量子ビットが ${\mid 0..00\rangle}$ に戻っている確率は次になります。

　 $|{\langle 0..00\mid}\left\{{\mid 0..00\rangle} - 2Q^\dagger\Pi Q{\mid 0..00\rangle}\right\}|^2 = (1-2p)^2$

最後の変形には、(2) を用いました。言い換えると、フラグビットがリセットされずに 1 のままで残る、すなわち、この関数が TRUE を返す確率は、

　 $1 - (1-2p)^2 = 4p(1-p)$ -- (4)

と決まります。たとえば、実際に条件 A が成立しており、かつ、計算用量子ビットが ${\mid 0..00\rangle}$ に初期化されておれば、(4) で $p=p_A$ とした確率 $4p_A(1-p_A)$ で TRUE を返します。ちなみに、計算用量子ビットが ${\mid 0..00\rangle}$ に初期化されている確率は $1/2^n$ であり、さらに、計算用量子ビットが ${\mid 0..00\rangle}$ に初期化されていなければ、フラグビットはずっと 0 のままになります。（真ん中の Controlled-Z が発動することも無いので、Q の処理は、 $Q^{-1}$ で完全にキャンセルされます。）

したがって、計算用量子ビットの初期状態を限定せずに考えた場合、実際に条件 A が成立していれば、この関数は、確率 $\displaystyle \frac{4p_A(1-p_A)}{2^n}$ で TRUE を返します。一方、条件 A が成立していない場合は、 $p=p_{\overline A}=0$ として同じ議論をすればよく、この関数は、確率 0 で TRUE を返します。（ここ、意外と絶妙なポイントで、 $p=0$ の場合は、(4) の確率もちゃんと 0 になるんですよね・・・）

以上により、この量子回路は、条件 A が成立していれば一定の確率で TRUE を返し、条件 A が成立していなければ必ず FALSE を返すという意味で、条件 A の成立を判定するという非自明な処理の実行に成功したわけです。この条件判定の実体は、量子演算 Q で実装されていますので、この部分に古典コンピューターでは効率的に実行できないアルゴリズムを持ってくれば、DQC-1 は、古典コンピューターよりも優れているということになります。

このアルゴリズムのポイント

・・・言われてみればそのとおりですが、それでもなんだか不思議な気がしませんか？これ。

実は、このアルゴリズムでは、「量子演算 Q の実行結果が確率的に決まる」という点が重要な役割を果たしています。仮に量子演算 Q の結果が確定的で、

・条件 A が成立していれば確率 $p_A=1$ で ${\mid 1\rangle}$ が観測される。（確率 $1-p_A=0$ で ${\mid 0\rangle}$ が観測される。）
・条件 A が成立していなければ確率 $p_{\overline A} = 0$ で ${\mid 1\rangle}$ が観測される。（確率 $1-p_{\overline A}=1$ で ${\mid 0\rangle}$ が観測される。）

であったと仮定すると、この処理はうまくいきません。実際、条件 A が成立している場合にこの関数が TRUE を返す確率 $\displaystyle \frac{4p_A(1-p_A)}{2^n}$ は、この場合、なんと 0 になってしまいます。 $1-p_A=0$ に注意してください。

実際の量子回路の動作としては、こんな感じです。

量子演算 Q を実行した直後の状態は、一般には、Q の結果が TRUE と FALSE の量子的な重ね合わせ状態になりますが、Q の結果が確定的な場合は、これは重ね合わせ状態にはなりません。TRUE の状態だけを含みます。したがって、その後、Controlled-Z を演算しても、これは状態全体に -1 を掛けるという、実質的に意味のない操作になってしまい、その後の $Q^{-1}=Q^\dagger$ によって、計算用量子ビットはきれいに初期状態にもどってしまいます。（逆に言うと、A が成立していない場合、Q の演算結果は FALSE の状態だけを含むので、計算用量子ビットは必ず初期状態に戻ります。）

言い換えると、Q の結果が TRUE と FALSE の重ね合わせ（Entanglement）だからこそ、Controlled-Z が non-trivial な演算となり、その影響が最後まで残って、計算用量子ビットが初期状態に戻らないというわけです。つまり、量子演算 Q が確率的に答えをだすことによってこそ、その状態を検知してフラグビットに反映することができたのです。断定的な答えは外部に伝えることができず、あいまいな答えをだすことによって Entanglement を生み出して、その結果、情報の伝達に成功する ―― なにやら量子アルゴリズムの奥深さが感じられるのではないでしょうか。