TECHNICAL NOTE

何故量子コンピュータはこんなにも強力なのか?

もう1つの理由。

前半の解説記事では、量子コンピュータはどうしてそんなに強力な計算能力を持つのか？を指数関数的なメモリという観点から説明を行った。今回の後半部分では、量子コンピュータを強力にするもう1つの要因である超並列アルゴリズムについてフォーカスし、説明していく。私はかねてより、量子コンピュータアルゴリズムはあぶり出しであると言っている。その心を以下で解説していく。

REASON

LOGIC

古典（従来型）コンピュータで解く組合せ最適化 - 正攻法で解く

古典コンピュータで組み合わせ最適化問題を解くことを考える。愚直に問題を解こうとすると、全ての解の可能性を１つ１つ試していって全パターンを網羅することにより、真の解を求めようとするものである。まだ全パターン数が少ない時は大して問題にならない。厄介なのは、扱うシステムサイズが大きくなって行った時に、問題サイズに対して指数関数的にパターン数が増える問題である。その代表的な問題にNP困難な問題というものがある。NP困難な問題に関する説明は別の解説記事で行うこととする。代表的なNP困難な問題としては、巡回セールスマン問題や、ナップサック問題、Maxcut問題などがある。下では少しでもイメージを持ってもらうために、比較的簡単なMaxcut問題を紹介する。さて、これらNP困難な問題に対して、古典コンピュータの正攻法で全パターン網羅的にアタックするとどうなるか？指数関数通りのパターンがあるので、システムサイズに対して計算時間は指数関数的にかかることになる。

すご〜くシンプルだけど手強い問題：Maxcut問題

今、5人の幼稚園児を２台のバス（”バス０”と”バス１”と呼ぶことにする）に乗せる乗せ方を考える。ここで、5人の園児の間には、図に示すような互いに嫌いな関係を持ったペアがいる。さて、この５人を２台のバスに乗せるのだが、出来るだけ嫌いな者同士は一緒にならないようにバスに乗せたい。最善なバスの乗せ方はどういった乗せ方か？すごくシンプルな問題設定である。しかしこの最善なバスの乗せ方を決める問題、実は解を求めるのがとても難しい問題として知られている。嫌いな者同士を出来るだけ引き離すというところから、Maxcut問題と呼ばれている問題である。さて、そもそも5人の園児を彼らの好き嫌いを完全無視してバスに乗せる乗せ方は何通りあるか？答えは2^5=32通りである。32通りしかなければ、大したことはない。全パターン調べ上げて、最適な乗せ方を見つければ良い。しかし、問題は、５人であれば良いが、１０人、１００人、１０００人となった時に、2^1000通りを調べ尽くすことは不可能である。これがシステムサイズが大きくなった時に、計算コストが指数関数的に増加する、ということを意味する。

もう一度、古典コンピュータでMaxcut問題を解く

N人の園児の２台のバスの乗せ方は実はNビット列で表すことができる。A君のバス番号（0か1か）、B君のバス番号（0か1か）、C君のバス番号（0か1か）、、、、を一列に並べると、確かにN個の数字列からなるビット列（『Nビット列』と呼ぶことにする）はN人の園児のバスの乗せ方と等価であることがわかる。さて、ということは古典コンピュータで正攻法でこの園児の問題を解くには、Nビット列の異なるインプット状態を次々に生成し、それらに対し計算機でそのインプット状態に対してどの程度仲の悪いペアを引き裂くことに成功したか？を順繰りに計算していく。そして、全てのNビット列の組み合わせに対して計算を行った後、最も仲の悪いペアを引き裂いた最善のバスの乗せ方がどれだったかを確認する。これが古典コンピュータでMaxcut問題を解く流れになる。そしてシステムサイズ（園児の数）が増えると計算コスト（計算時間と思ってもらって良い）が指数関数的に増加して行ってしまう。

STRUCTURE

量子コンピュータアルゴリズムは炙り出し -超並列アルゴリズム

上では、古典コンピュータでは、指数関数的に時間がかかる問題があることがわかった。では、このような問題を量子コンピュータはどうやって解こうというのか？量子コンピュータの問題を解く解き方は、古典コンピュータのそれとは全く異なる。私か兼ねてから、量子コンピュータが問題を解く解き方は「炙り出し」ににているよと言う。その心を以下で説明する。まず、量子コンピュータのアルゴリズムを理解する上で、何より大事なことは量子コンピュータは”量子重ね合わせ状態”を利用することができることである。つまり、先ほどのMaxcut問題で説明をしよう。入力状態としてNビット列の異なるインプット状態を次々に生成し、それぞれのNビット列に対して古典コンピュータで計算を順次行っていく。一方、量子ビットでは、重ね合わせ状態を作ることができるのでそれら全てのインプット状態を重ね合わせた１個の状態を作り出すことができる。ここが古典コンピュータとの決定的な違いである。量子コンピュータでは、この１個にまとめ上げられたあらゆる答え候補が重ね合わされた状態に対して、ある一連の操作（これが「アルゴリズム」と呼ばれるもの）を行っていくその操作はどのような操作なのか？それは、インプットされた様々な解候補が重ね合わされた状態の中から、正解の解だけを残して、正解以外の解状態の振幅を減衰させるように作られる。まさに正解を”炙り出す”ことをする。このように、量子コンピュータのアルゴリズムと、古典コンピュータのそれとは全く感げ方が異なるのである。そのため、古典コンピュータで良いアルゴリズムが、量子コンピュータでそのまま良いアルゴリズムになるとは限らない。同様に、量子コンピュータの素晴らしいアルゴリズムがそのまま古典コンピュータで良いとも限らない。このことは、是非とも知っていてもらいたい。量子コンピュータの使い方は、大事なノウハウである。

量子コンピュータの炙り出しアルゴリズム

どうやってそんな都合よく、人間が欲しい答えの成分のみを増幅させて、欲しくない解候補の成分を減衰させるのか？大概、人間が知りたい答えは、ある問題の”最大”か”最小”なのである。例えば、先ほどのMaxcut問題の園児の問題の場合、いかにして不仲の者同士を”最大限に”引き裂くか？と言う問題である。他のNP困難な問題に分類される問題でも、”最小”時間で経路を一周してくるのか？と言う巡回セールスマン問題などである。全ての解候補のうち、”最大”または”最小”の状態を見つけ出してくる問題である。さらに、量子化学計算（材料シミュレーション）では、まずは基底状態計算と言うものを行うことになるのだが、これはあるシュレーディンガー方程式を満たす”最小固有値”を求める問題である。最大または最小を見出す量子コンピュータのアルゴリズムには、いくつかの方法が提案されている。次回以降では、そういったアルゴリズムも紹介予定である。さて、ここでもう１つ重要な話として、古典コンピュータでは、１つ１つ違う入力状態に対して、計算を行い、全ての入力状態を網羅した後、出力結果を確認して正解を見出すと言うアルゴリズム。それに対して、量子コンピュータのアルゴリズムは、あらゆる入力状態を１つに重ね合わせ状態を作り出すことによって、その１つの入力に対する計算を実行する。もし仮に、１つの入力に対してであったとしても、計算操作数がめちゃくちゃ多くなり、トータルとして古典コンピュータよりも早くなったのかどうかが微妙になるケースも実はある。かえって遅くなっている場合もある。なので、量子アルゴリズムはどんな計算も”必ず速くなる”訳ではない点は注意すべきである。さて、我々Quemixでは、この量子アルゴリズムとしてゼロから開発を行ってきたものがある。それが確率的虚時間発展法（PITE）である。そして、PITEは、確かに古典コンピュータと比べて計算加速することが数学的に確認されたまだ数少ない、アルゴリズムの１つである。これに関しても、後ほど、アルゴリズムの解説を行う予定である。是非、そちらも読んでいただければと思う。

　ここまで、量子コンピュータの凄さをメモリとアルゴリズムの観点から一般論として説明してきた。この後では、具体的なアルゴリズムや問題を取り上げながら、もっと詳細に量子コンピュータの理解を深めていく。