よろずQCのZen問答:QCのAlgorithmの分類

このblogは湊氏と氏の会社のBlueqat社の追っかけから始まったのだが、その過程で色々な情報に接してこれは書きたいなあと思うことがある。その場合は、現在のblogの流れを無視して発表する。もともと、このblogは殆ど趣味のようなものだが。湊氏に文句を言ったのだが、このblogを書くために長年無視してきた物理や数学を見直して復習しなければならず、夢にまで出てくるという正に悪夢だ。。。。と言いながら、嬉々としてやっている。はい、この最初のパラグラフは全く必要ありませんでした。

湊氏のQCのalgorithmのblogの解説をQCの味付けで、やっていて色々と調べるに従って１万メートル上空からの眺めはどうなっているか気になってあちこちうろうろしていると、QCWare社が開いてるQ2Bというコンファレンスのビデオシリーズを見つけた。

“Q2B is the major conference to attend to gather key data and developments on significant technological, corporate, and government efforts in the quantum computing space. Q2B speakers are among the most well-informed QC experts and readily share their knowledge and insights.

QCWareのQ2Bのサイトより

毎年行われているが、見つけたのは2018年の分なんで少し前だ。IT業界だと３年前のネタは3日前の新聞みたいなものだが、今のQCの分野のalgorithmの発展のスピードを見ているとまだ十分正しいと言える。このコンファレンスで、Adam Bouland氏の発表がよくまとまっていたので、それをベースにまとめてみる。Bouland氏は現在UC BerkeleyでPos- Doc、兼QCWareのアドバイザー。今秋（2021年）からStanford大学でAssistant Professorの予定。

Bouland氏は湊氏と異なった観点からQC algorithmを解説しており、これを見て湊氏の分類を見直すとなかなか興味深い。Bouland氏はQ2B、2018年の発表では、まとめに以下の形の表を使用した。ここでは、NISQで到達できることとFTQCで到達できることを説明している。

QCを開発する元々の動機は計算の高速化だ。Bouland氏は高速化を指数関数的に加速できる、（まあまあ）加速できる、不明か未確認の３つのケースに分けている。不明・未確認というのは、実機による実際のalgorithmの実測の数が少なすぎて結論が下せない場合のことである。漸く、実機による計算が増加してきたとは言え、実機にアクセスできる人の数が限られている現状では最もなことである。

	NISQ	FTQC
指数関数的加速	ここに到達したい	殆どのalgorithm
加速		殆どのlagorithm
不明・未確認	殆どのalgorithm

適用分野毎の話の前に先に結論を述べておくと。（ところで、最近の日経記事（元はCB Insightsの記事、翻訳して転載）には９つの応用分野が示されている。）一番理想的なalgorithmはNISQ上で古典コンピュータ上で実行されたより指数関数的に加速されるものだ。上の表では「ここに到達したい」と記されている。しかしながら、現実は、殆どのalgorithmは確認できて加速されると言えるのはFTQCに限られる。NISQ上の加速は不明か未確認だということだ。この理由は上で述べた通り、実機による実測の機会が限られているためだ。

まず氏はアプリケーションを５つに分けて説明している。以下の５。

1. 量子システムのシミュレーション
2. 最適化
3. 機械学習
4. 暗号
5. 量子超越性

では、それぞれの分野に関して氏の発表内容を述べる。ここでは、それぞれのalgorithmの詳細は述べない。algorithmの詳細は複数のサイトで解説されている。英語1、英語２と日本語。

1.量子システムのシミュレーション

簡単に言えば、量子システムをシミュレートするなら、それ自体が量子力学に基づいているQCが古典コンピュータよりも有力であるだろう。動的な事象を含む一般の量子システムのalgorithmはHamiltonian Simulationが必要でありそれは、FTQCを必要とする。Hamiltonian simulationというのは量子システムの動的な動きも含め量子システムを完全にシミュレートできることである。NISQに限れば、エネルギーが最低になる様に落とし込んで近似解を求めるVQEだ。

	NISQ	FTQC
指数関数的加速		Hamiltonian Simulation
加速
不明・未確認	VQE

VQEと言えば、化学計算に多く使われると言われている。日本ではこの分野には大阪大学からスピンオフしたQunasysが焦点を当ててビジネス展開をしている。

化学計算にフォーカスし、パートナーとなる企業様と連携しながら、既存のテクノロジーで解決が困難であった社会および産業の課題を解決します。

量子コンピュータという新たな革新的なデバイスの潜在能力を最大化するためには、業界のパートナーの知見とQunaSysが有する量子技術に関する最先端の知見を組み合わせていくことが重要です。QunaSysはパートナーとなる企業様との協業により、量子コンピュータの最初の応用先として期待されている材料シミュレーション分野で、社会および産業の課題を解決していきます。
また、既存の計算機とは全く違うアルゴリズムで動くこのデバイスを使いこなし、実用的な量子コンピュータの登場時に活用のスタートダッシュを切れるようにする準備をサポートします。

QunasysのWeb page のserviceのセクション

2. 最適化

	NISQ	FTQC
指数関数的加速
加速		Groverのalgorithmとその普遍化
不明・未確認	QAOAと 不完全な断熱計算

最適化の問題は問題によっては最小化であったり最大化であったりする。qiskitのサイトで上がっている例は、最小化の場合、コスト、距離、経路、重量、処理時間、資材、エネルギー消費、物体の数など。最大化の場合、利益、値打ち、出力・成果、利益、効率、容積や物体の数などだ。

有名なGroverのalgorithmは現在のQCでは実現可能ではない。その普遍化したものはQAA（Quantum Amplitude Amplification、量子振幅増幅）と呼ばれ、Groverのalgorithmをsubroutineとして使用する。NISQ上ではその代用としてQAOAが広く知られている。

3. 機械学習

	NISQ	FTQC
指数関数的加速		HHL
加速
不明・未確認	Neural Network	Tensor Network

機械学習の領域では、HHL（Harrow-Hassidim-Lloyd）のalgorithmが広く知られているが、これも現在のNISQの上での実行は可能ではない。NISQ上では、Neural NetworkやTensor Networkが可能であるがどれだけの計算速度が加速されるかは不明だ。

4. 暗号

	NISQ	FTQC
指数関数的加速		Shorのalgorithm
加速	QKD
不明・未確認

QKD（Quantum Key Distribution、量子鍵配送）はbouland氏の発表では、NISQで指数関数的加速に上げられていたが、前後の脈絡からこれは筆者が加速に訂正した。また、氏の発表の中では、FTQCで指数関数的に加速の項目には現在の暗号システムを無効にすると記されていたが、それでは他と整合性が取れないので敢えてShorのalgorithmと記した。現在使用されている公開鍵暗号が全て無効になると驚かされたShorのalgorithmはFTQCができないと実用化はできない。しかし、現在米国のNISTは現在の公開鍵暗号の次を決定すべく公開で新しい技術を求めている。現在69の応募の中から15に絞り更なる精査を行うようだ。

After spending more than three years examining new approaches to encryption and data protection that could defeat an assault from a quantum computer, the National Institute of Standards and Technology (NIST) has winnowed the 69 submissions it initially received down to a final group of 15. NIST has now begun the third round of public review. This “selection round” will help the agency decide on the small subset of these algorithms that will form the core of the first post-quantum cryptography standard. 

NISTのサイトより

5. 量子超越性

	NISQ	FTQC
指数関数的加速	量子超越性（証明可能な乱数など）
加速
不明・未確認

この発表は2018年の行われているため、2019年Googleが発表した量子超越性には触れていない。量子超越性を示すには、特に意味がなくても古典コンピュータより圧倒的に指数関数的に速くQCが計算できることを示す必要がある。その１つの候補が証明可能な乱数の製造だ。Googleの発表も乱数に関するものであった。

まとめ

もちろん、QCの応用は上に挙げられているアプリケーション領域以外にもある。それはBouland氏も認めているが時間の都合でこの５つの分野に限られていた。

	NISQ	FTQC
指数関数的加速	量子の超越性	Hamiltonian Simulation HHL Shor’s algorithm
加速	QKD	Groverと普遍化
不明・未確認	VQE QAOA 不完全断熱 Neural Network	Tensor Network

上の５つの表を１つの表にまとめてみた。色によって分野を分けてある。黒字は量子の世界のシミュレーション、緑は最適化、青は機械学習、赤は暗号、で量子超越性はピンクだ。こうやって見ると、NISQで可能なalgorithmはQKDと証明可能な乱数を除いて、現存するが計算速度に関してその優位性が不明や未確認のものが多い。これは、実機が少ないため、実践でalgorithmを多く使用して実験的に結果を集計できないことによると思う。QCのalgorithmで有名な、HHL、Shor、Groverのalgorithmは皆FTQCがなければ、実行できない。つまり、後どう短く見積もっても5-10年先のことだわいと思っていたが、最近のBlueqatの湊氏のビデオがこの期間の見積もりがそう長くないかもと思わされる。まあ、技術の発展は、長くかかると思っていたら、ある発見でこれは意外に短いかと思ったら実はそれより長くかかった。しかし、当初思われたよりは短かったというようなものが多い気がする。これは完全に個人の感想だが。

まず最初の湊氏のビデオは、FTQC用のalgorithmに大手、すなわち先行グループが動きを加速していること。２つ目のビデオは、どうもハードに関しては、NISQ plusとでも呼ぶべきIonQのハードがde facto standardになってきていること。これは、湊氏はblogにもまとめている。この２つの方向が今後加速すると見られるので、シリコンベースや光子ベースのハードに対する投資も進むと予測すると、5-10年と安閑に暮らしてはいられないかも。特に、暗号に関しては心配せずに済むんだろうか。