SC18 - 量子コンピュータで計算の将来はどうなるのか

量子コンピュータは本当に速いのか

量子コンピュータでは、演算は安価であるが、メモリは高くつき、非常に限定的にしか使用できない。量子コンピュータは重ね合わせを利用して指数関数的なスピードアップを実現する可能性は持っているが、そのためには可逆的な計算を行う必要があり、量子状態の複製を行うこともできない。また、意味のある結果を得るためには、賢いリダクションアルゴリズムの開発が必須であるという。

量子コンピュータでは計算は簡単であるが、メモリは高くつき、限定的にしか使用できない。指数関数的に高速に計算できる可能性は持っているが、量子状態のコピーができないなど制約も多い。さらに、賢いリダクションアルゴリズムが見つからないと結果を読み出すこともできない

データベースのサーチは量子アルゴリズムで高速化できるが、サーチを行うためには、その前にデータをロードする必要がある。このために必要なハードウェアや実行時間を見積もっておくことが重要である。

宇宙の寿命ほどの計算時間がかかるアルゴリズムを指数関数的に高速化しても、計算に何千年も掛かるのでは実用上意味がなく、せいぜい、何日とか何週間で計算が終わる程度までアルゴリズムを高速化できなければ意味がない。

そして、アプリケーションを実際に使用するハードウェアに組み込んだ場合の実行時間を見積もることも重要である。

実用的に計算が行なえるようにするには、(1)指数関数的な高速化ができるアルゴリズムを見つける。(2)これには入出力の方法も確立していなければならない。(3)計算時間が現実的な範囲の収まるようアルゴリズムを最適化する。(4)実行するハードウェアで実行時間を評価する。ことが重要である

最適化問題では、連続的に坂を下っていくとエネルギー最小の点が見つかるとは限らず、最適点は山の向こう側にあり容易には到達できないことも少なくない。アニールを行う場合、熱雑音のエネルギーでこの山を越えることもあり得るが、山が高い場合はなかなか容易ではない。このアニールを量子的に行えば、山をトンネリングで突き抜けてより低いエネルギー状態に移ることができ、より早く、最適点を見つけることが可能になる。

通常のアニールでは熱エネルギーにより山を越えることもあるが、量子アニールの場合は、トンネル効果で山を突き抜けるので、エネルギー最低の点を見つけやすい

この原理を実用化したのがD-Waveの量子アニーラーである。D-Waveは2048qubitのマシンを商用化しており、量子効果を利用したアニールには利点があることが確認されている。しかし量子アニーリングは、普通の古典的コンピュータでシミュレートすることもできる。

D-Waveは2048qubitの量子アニーラーを製品化している

量子的なトンネル効果は通常のコンピュータでシミュレーションすることができ、量子コンピューティングの研究の過程で新しい古典的アルゴリズムが見つかることが多い。その結果、右下のグラフのように、量子アルゴリズムにヒントを得たアニールの方が、本物の量子効果を使った最適化よりも速く最適化ができるという状況になってきている。また、マシンラーニングの学習においても、シミュレーションの方が速いという結果が得られている。

なお、右下のグラフについて詳しい説明がなかったので良く分からないが、このグラフは左の方がqubit数の大きい計算であると思われる。現在はシミュレーションの方が速いが、qubit数が増えるにつれて指数関数的に量子アニールの方が速くなり、逆転することになると思われる。

量子アルゴリズムの研究の過程で、新たな古典アルゴリズムが見つかることが多い。現状では量子アニールよりも、このようにして発見された古典アルゴリズムの方が速いというケースが多い

計算の効率を高めるのに必要なこと

自動車会社は交通の最適化に量子アニーラーを使い始めているが、D-Waveの量子アニーラーでは20秒かかった最適化が量子最適化にヒントを得た古典コンピュータでのシミュレーションでは1コアだけで0.2秒で最適化でき、AzureクラウドでFPGAを使えば、さらに300倍速くなるという結果が得られているという。

交通最適化の例では、D-Waveの量子アニーラーでは20秒かかったが、量子計算にヒントを得た通常コンピュータ用のアルゴリズムでは0.2秒で計算でき、FPGAを使うと、さらに300倍速くなった

MRIの撮影で、パルスのシーケンスを最適化して短時間でより精度の高い診断を可能とするという問題にも量子アニールよる最適化が使われている。

量子アニールからヒントを得た最適化でパルス列のシーケンスを改善し、MRIの診断をより短時間で高精度で行えるようになった

量子アルゴリズムではNエントリのデータベースのサーチをSQRT(N)の時間で行うことができる。これは大きなメリットであるが、量子コンピュータの場合も、まずはNエントリのデータをロードする必要があり、この入出力がどれだけの時間でできるかが問題である。

データベースのサーチは量子コンピュータではSQRT(N)の時間で行うことができるが、サーチを行うためには、すべての要素をロードする必要がある。この入出力にどれだけ時間が掛かるかが問題

Ferredoxin Fe₂S₂の最低エネルギー状態を見つけるという問題は光合成の反応とエネルギー移動の計算に必要である。しかし、これを古典的アルゴリズムで行うのは、実用上、不可能な非常に長い計算時間が掛かる。また、量子コンピュータを使っても、2012年の量子アルゴリズムではおおよそ3000年掛かってしまう。しかし、2015年の改良された量子アルゴリズムでは約3時間で計算できるようになってきている。

このように、計算の効率を高める量子アルゴリズムと量子ソフトウェアの研究は非常に重要である。

Ferredoxinの基底状態を見つける計算は、古典コンピュータでは事実上不可能な長い時間が掛かる。量子コンピュータでも2012年のアルゴリズムでは3000年掛かるが、改良された2015年のアルゴリズムでは3時間に短縮された。量子アルゴリズムとソフトウェアの研究は重要である

118のスピン軌道を持つFe₂S₂のエネルギー状態の計算は以前のアルゴリズムでは10¹⁸ゲートと10¹⁷の並列の回路深度を必要とし、ゲートの演算時間を1μsとすると、計算に3000年を必要としたのであるが、2015年の論文では必要ゲート総数は10¹¹、並列回路深度は10¹⁰に減少し、計算時間が約3時間となっている。これは計算結果の再利用でO(N)の演算回数の減少、並列化が可能になるようなコードの改良でO(N)の実行時間の短縮、その他の最適化で1600倍の高速化などを行った結果である。