よろずQCのZen問答:組み合わせ最適化はFTQC上でどう進化するか。

最初にお断りをひと草。このblogは技術的な話を無理やりにmarketingやビジネスに結びつけて、数式などは排除してお届け中。若干QCで味付けした読み物という位置で。もっと、まともな技術の話はこのblogの兄弟blogの「いちから始める量子コンピュータ」を参照ののこと。

初めに

QCの応用の有名なもの１つは組合せ最適化だ。湊氏のblogやビデオ発信を見ていると、組み合わせ最適化問題に限らず、概要を掴むことができ非常に役に立つ。他の人は知らないけど、自称文系の電気工学科卒で５０年間数学と物理から逃げてきた身としては、概要を掴めないと全く分からない。

湊氏の追っかけをしている理由は、1) オープンソース的に多くの情報やコードを惜しげもなく開示していること、2) 日本市場だけでなく世界市場を意識して世界規模でQCを見ていること、3) ものをはっきりと言うことだ。特に3に関しては、立場上意見をはっきり言わない専門家が多い中、QCを実機で稼働しビジネスを展開しているので発言には説得力がある。生の声が聞けるのが嬉しい。

このblogは湊氏の「NISQからFTQCへ移行する組合せ最適化問題を技術的に読み解き予想する」に触発されて書いている。（ビデオは下に貼ったてある）。湊氏はこのビデオでQCの適用分野の１つである組み合わせ最適化の話を比較的簡単に述べている。。

[注：実は、4月19日によろずQCのZen問答: 世界規模でみた現在の量子コンピューター市場を端的にまとめる （その3-2：ソフト）でそれぞれのQC algorithmの話を始めてQAOAの話をするとか言ってたが、それ以降違う方向に向かってしまっていた。実はこのblogはその3-3に対応する。]

湊氏のビデオのまとめと筆者の補足

湊氏は、七年QCやってるが、本当にQCが古典コンピュータより速くなるかは分からないと発言、しかもどっちかと言うと速くなるというのは都市伝説レベルだと述べた。実にわかりやすい。以下は湊氏がよく使うQC algorithmの変遷の図だ。今回は組み合わせ最適化の部分を強調してある。

次の図は湊氏の話に筆者が調べて組合せ最適化問題用のalgorithmの変遷をまとめたものだ。図の下には簡単な説明を加えた。

• ずっと昔からあるAnnealing（焼きなまし）という物理的現象に、1928年にMax Born と Vladimir Fockが断熱定理（Adiabatic Theorem）というAnnealingの物理的な断熱変遷という理論を確立。
• 焼きなましを参考に擬似Annealing方式(simulated annealing, SAまたは焼きなまし法）が1983年にS. Kirkpatrick、C. D. Gelatt、とM. P. Vecchiよって確立。
• 1998年に西森・門脇のチームが擬似annealing方式を温度の変化を量子状態の遷移を応用して、量子annealing（QA)の理論を確率。最初にQAの方がSAよりも良いと示した。
• 2000年にEdward Farhi, Jeffrey GoldstoneとSam GutmannがQuantum Adiabatic Algorithm（QAA、量子断熱時間発展、Adiabatic Time Evolution、ATE）を開発。この時点では、QAAがgate型の量子回路と等価かどうかは不明だった。
• 2005年にAharonov等がQAAはgate型と等価と証明。
• 2012年にD Wave社が西森・門脇チームの理論を実現。
• 2014年にEdward Farhi, Jeffrey Goldstone, とSam GutmannによりNISQ上のQAOAが発表された。
• 現時点では、どちらも断熱定理に基づくが、QAとFTQC上で実行されるATE/QAAは別に発展している。
• （注：FTQC上のATE/QAAは未だ実装されたという情報は確認できていない。）

QCと組み合わせ最適化問題

以下では、それぞれのalgorithmの内容には触れず変遷のみを述べる。次回のblogではそれぞれのalgorithmや理論の簡単な説明を加える。

Annealingの手法をQCに応用するという論文が1998年にその当時東工大の教授の西森秀稔氏と大学院生だった門脇正史氏によって発表された。その後、2012年にカナダのD-Wave社が最初のQC annealingを元にしたQCコンピュータを発表した。（これを湊氏はアナログ型と呼んでいる。）

D-Waveに続き2015年頃、IBM/Googleがgate 型のQCを開発・発表した。元々組合せ最適化の問題はATE/QAA（断熱時間発展型algorithm）で解くことができると知られている(2000年の論文）が、このalgorithmをgate型で実装するにはgateがたくさん必要で、計算が複雑で時間がかかる。そのため、NISQでは実行ができないので、古典コンピュータとのhybrid型でその近似解を求めるためにQAOAが考案された。上の湊氏と筆者の図をそれぞれ参照のこと。英語（その短縮形も含め）と日本語が混在しているので、と筆者の英語・日本語語句対比のblogも参照。

英語の短縮形だと同じでややこしいが、このQAOAにGoogleがQuantum Alternative Operator Ansatz（QAOA）という方式を開発した。元々のQAOAと区別するために、筆者のblog上だけだが、これをQAOA2と表記する。これを応用することで、元のQAOAが速くなる。VQEにも応用可能である。

湊氏が何度もあちこちで繰り返すように、2020-2021年は、IonQやHoneywellのIon trap型が注目を浴びるようになり、NISQからFTQCに流れが変わってきた。もともとQAOAはNISQ用にATE/QAAを改造してQAOAを作ったので、FTQC用には元に戻すだけで、QAOQ2も使用できる。

全部が全部良い訳ではなく、ATE/QAAに改造すると、プログラマーが介在しなくてはならない部分が出てくる。この部分はQAOAでは自動的に設定してくれていたが、FTQC版は自分で行わなければならない。簡単にいうと、アナログ型のD-Wave Annealing は自然界を模倣しているので、人間が介入するとこはないが、ATE/QAAはデジタルなため、アナログを分割する必要がある。その分割の粒度が問題となる。この粒度は、問題によって異なるためそれも面倒である。

次回のblogでは、以下それぞれを簡単に述べて何が違うのか、書いてみたい。

• 断熱定理
• 擬似annealing
• 西森・門脇論文
• D-Wave
• ATE
• QAOA