よろずQCのZen問答: QC(量子コンピュータ)のAlgorithm の進化は突然世界のどっかで起こる。期待できますなあ。1例はVQE/QAOAを大幅に進化させる Algorithm(F-VQE)—さわりだけ。。

勝手にこう思っている。QCに関しては、スポーツ新聞の見出しレベルはWhite Hatで専門家用の説明はBlack Hat(Dark Side)。筆者はその真ん中を行くGray Hatのつもり。しかし、QC全体を分かりやすい図にまとめようと思うと、専門家の領域のDark Sideに足を踏み込まなければならない。ある程度(完全でないにしても)理解しないと説明できない。もちろん、そう簡単には踏み込めない。

基礎的な量子力学、物理数学などはまずまず復習などできたはずなので、後は論文を実際に当たるだけなんだけど。まだ踏み込めていない。しかも、まあないだろうけど、ひょっとしてDark Sideに取り込まれたら、筆者が始めたGray Hatの方向が絶えてしまう。しかしながら、少し突っ込んだ話だとBlack Hatと話をするためには難解な数式も理解せねばならず悩み多い初秋である。

まあ、戯言はこのくらいで、真面目な専門家の話はこのblogの兄弟Blogの「いちから始める量子コンピュータ」を参照。

現状

QCの現状に関しては、最近のBCGのレポートを解説した筆者のblogを参照。さらに、8月に発表されたGartnerの最先端技術のハイプサイクル(HC)の解説blogも参照。

BCGは以下のような今後の進展を予想している。図はこのblogから。

もちろん幅はあるけれど、NISQ時代は後10年で(2030年くらいまでで)FTQCの最低条件であるエラー自動訂正が実現できて、完全実用まで後20年ほど(2040年くらいまで)。では、完全な実用まで、もしくは自動エラー訂正が終わらないとNISQでは何もできないのか。特にソフトの分野はハードがあるレベルまで発展しないと足踏みしないといけないのか。そんなことはない。今後10年の間、自動エラー訂正ができるまで、世界の研究者や実務者が冬眠するはずもない。毎日必死に努力しているはずだ。QCのAlgorithmの進化は、ある日突然に発表されるかも知れない。まだまだ、Gray Hatの筆者は物理数学と量子力学に励む毎日である。

このBlogでは、VQE/QAOAの改良型のF-VQEについて書いてみたい。もちろん、触りだけ。詳細な解説は後で発表される兄弟Blogの「いちから始める量子コンピュータ」に乞うご期待。まずVQEとQAOAの最低限の話だが、それは囲みを参照。

VQEとQAOAの関係

VQEは量子化学計算に主に使われる量子Algorithmである、しかし、組み合わせ最適化にも利用できる。QAOAは主に組み合わせ最適化に使用される量子Algorithmだ。どちらのAlgorithmもNISQ用に考案されている。

幾つかの問題(組み合わせ最適化や量子化学計算など)の解法はある環境にある量子が取り得るエネルギーの最小の値に対応することになる。そのためには:

  1. 与えられた問題を、Algorithmを適用するために数式で表す。
  2. その数式をAlgorithmを適用してとく。

このうち、それぞれの問題が物理の問題に置き換えられることを知っていることが必須だが、この場合、量子化学計算と組み合わせ最適化は置き換えられる。次に厄介なのがそれぞれの問題を翻訳・変換して数式化することだ。

その関係を簡単に下の図でまとめた。専門家からは絶賛ツッコミどころ満載だけど、直感的に理解するためだから。まあ、専門家がこのblogを読むわけもないか。

更に、VQE(Variational Quantum Eigensolver)はQPE(Quantum Phase Estimation)のNISQ版だ。QPEは他のAlgorithmの基本となる重要なAlgorithmだけれど、NISQ版ではリソースを食いすぎて実行できない。そのため、VQEが開発された。簡単に言うと、QPEの計算をheuristcsを使って近似的に求めるものだ。その関係を以下の図に示した。

QPEとVQE、VQEとQAOAの関係を示した図

更に、詳細はQAOAはVQEの特別な場合である。細かいことを言い出すと、筆者もdark sideに落ちてしまうのでここで止めておく。この関係を集合的に表すと、以下のようだ。

つまり、QAOAで解ける問題はVQEで解くことができる。VQEは量子化学計算などに使われて、QAOAは組み合わせ最適化に使われることが多い。しかし、実はVQEでも組み合わせ最適化問題を解くこともできる。このblogの兄弟blogではその手法を示している。しかし、逆は必ずしもそうではない。VQEで解ける問題をQAOAで解けるとは限らないと言うことだ。

VQEとQAOAを直感で説明(専門家の閲覧禁止)

VQEとQAOAは量子化学計算や組み合わせ最適化などの問題を量子のエネルギー問題に置き換え、その最低のエネルギーを求める解法である。一般的にそのエネルギーの推移は以下の左のような綺麗な放物線を描くとは限らない。

というか、普通は凸凹の右側のような線をたどる。右側で難しいのは、局地的な谷に差し掛かった際(谷がある程度以上深ければ)局地的にしか最小値でないのに、全体としての最小値に達したと結論づけてしまうかもしれない。谷が浅ければ、そこで止まらずさらに他の点を模索するかもしれない。この図はイメージを表すもので、実在のエネルギー図ではない。更にイメージ的にだけいうと、どちらからでも良いが、上の右の図のような状況で、ボールを転がすとしよう。ボールは低い方へ移動する、局地的に最小の値を持つ谷に遭遇した時、谷が浅ければ、ボールに勢い(運動エネルギーが十分であれば)があれば、その谷を脱して更に転がり続ける。最終的に一番深い谷に遭遇した際、ボールが勢いがあっても、その谷を抜け出せるだけの勢いが無ければ、その谷で止まる。それが最適解だ。もちろん、谷の深さとボールの勢いとの関係などは、algorithmのparameterで調整するのだが、それは、このblogの範囲を超えるので、ここでは触れない。

F-VQE: VQEとQAOAを更に改良する

Cambridge Quantum Computing社(CQC)* は新しいAlgorithmのFiltering VQE(F-VQE)を開発した。元の論文は十分難解だが、この開発の責任者のMattia Fiorentini平易な言葉で論文を解説している。VQEやQAOAの実行スピードを増加したり、より少ないリソースで計算ができるとのことだ。それが出来れば、素晴らしい。特に、NISQではそれが求められる。

注:* CQCはHoneywell Quantum Solutions合併して新たな会社を2021年の3Qに設立の予定

ちょっとだけ詳細

要は、谷に遭遇した際ある谷に関して、深さを場所は変えずに深くすることで、(そしてボールの勢いを増加すると)他の浅い谷から早く抜け出し易くすると言うことだ。その状況をイメージで示す。本当の最低値に対応する谷の場所は変えずにその深さをより大きくして谷を深くする。右の図で、赤い太くした線で示した。そうするとその場所に早く到達することになり、全体としての本当の最小値を求める可能性が増える。(これもイメージのみで、正確のalgorithmを表現したものではない)。どうやってるのか?詳細を語ると筆者もdark side に落ちるので、イメージ的に。例えば、ボールの転がる勢いを増加すれば浅い谷は簡単に超えられる。一方、深くした谷は、ボールの勢いが増しても、そこから脱することができない。あくまでも、これはイメージ的な話。実際にはAlgorithmのパラメータを調整するのであろう。

F-VQEが成し遂げたこと

Fiorentiniは以下のようにF-VQEの成果をまとめている。

  • 最適解を求めるのが、従来のVQEやQAOAに比較すると10-100倍早いとsimulatorで実験の結果を得た。その後、HoneywellのQCの実機でそれを確認した。
  • VQEやQAOAによって導かれる解は最適な解の近似である。F-VQEがもたらす解は、従来のVQEやQAOAに比較してより最適解に近い。
  • VQEやQAOAへの批判は比較的小さな問題にしか適用できないことである。問題が小さすぎると、algorithmを適用しなくても、自明の場合が多い。F-VQEは従来のものと比較して、大きな問題にも適用可能である。CQCはこれ以前に開発していた「casual cones」と言う技術で大きな量子回路を小さな部分に分割して、少ない数のqubitを利用し演算を実行することを可能にした。

筆者所感

BCGやGoogleの予想を信じるならば、2030年頃に自動エラー訂正が可能になるまで、今のNISQの時代があと10年近く続く事になる。それまで、何もしないで待っているわけにはいかない。今や、QCは世界中で研究されてプロトタイプの開発や実証実験があちこちで行われている。明日にもどこかで、新しい発見や新しいAlgorithmが開発されて発表されるかも知れない。確かに、QCへの道は平坦ではなく、2-3年のうちに目処が立つものでもないだろう。思い出すのが、ネットのアクセス環境だ。あの当時9,600baudのモデムの遅かったこと。。。そのうちにそれが、56KとなりDSLが登場するまで暫くは動かなかった。それが待てずに、色々な珍解法が開発された。56Kモデムを2つつけて112Kにする方法とか。まあ、この方法はあまり成功したとは言えなかったが、DSLが出現して大きく変わった。

NISQがこの2つのモデムを使った解法と同じだとは言わないけれど、色々な制限の中で工夫を重ねる人々は世界中で五万といる。いつの日か筆者がまだまともに動けるうちにQCが日の目を見て欲しい。それにしてもF-VQEの開発は頼もしい限りだ。そして、こういった新しい動きは決してここで止まらない。CQCの人々も、また今全然知られていない会社や個人も、素晴らしい発見・開発・実験結果を見せてくれると信じて疑わない。