よろずQCのZen問答:　　　　　　　　断熱：物理現象からQC アルゴリズム

前回のblogから大分時間が経ってしまった。前回では、組み合わせ最適化に向いている断熱計算の変遷の話で終わった。歴史的な変遷をもう一度示しておく。この図で一部変更があった。このあたりは、囲みで詳しく。

断熱量子計算がらみの語句と変遷

断熱量子計算の周辺の語句の定義は複雑ではっきりとした記述がなかったが、色々とリサーチしていく中で、Albash等の「Adiabatic Quantum Computing」と言う論文に辿りついた。2018年に発表された第二版で、この辺りを詳細に論じている。以下はその一部を抜粋して筆者が訳した。

Tameem Albash教授、University of New Mexico（現）、論文を共著した当時はUniverstiy of Southern California

Adiabatic Quantum Computing (AQC)は元々あったQCのゲートモデルとは異なった計算のモデルであり一番最初は1988年に発表されて「Quantum Stochastic Optimization」と呼ばれた。後にQauntum Annealing（QA）と改名された。何度かの変遷を遂げた。（この中には西森教授と門脇氏の論文も含まれる）。両氏の論文が最初（1998年）に疑似アニーリング（SA、1983年）とQAを比較してQAの優位性を議論した。ちなみに、D Waveのサイトでは両氏の論文に言及している。

2000年になってQAとは異なっているがAQCに基づき従来の量子計算に近い形の「Quantum Adiabatic Algorithm（QAA）」がFarhi等によって提唱された。2005年になってQAAが通常のゲート型モデルと等価であることがは証明された。このあたりは前のblogを参照。

まとめると、AQCは実際の物理の現象を観察してそれに基づいた計算のモデルであり、その実装にはQAとQAAがある。QAはより物理現象に近いが、QAAはより論理的なものである。現在もQAとQAAは独自に発展している。本当に「量子」が先に来るか「断熱」先に来るかで意味が変わってきており、非常にややこしい。当初ど素人の筆者が混乱したのも無理はない。

歴史的な図

機能的な図

今回はそれぞれのコンポーネントを説明する予定であったが、この歴史的変遷とは違った機能的な観点から述べてみる。ちなみに、断熱とは外部からの熱の出入りがないということで、それ以上に詳細には語らない。以下に機能的な観点から断熱計算を数式や難解な語句を極力省略して解説してみる。これは、何時誰が発見・発明したとかいうこと（上記参照）は抜きにしてそれぞれのコンポーネントがどのように関連しているかのみを述べる。

この方式のベースになっている法則は断熱定理であり、それに基づいたモデル（断熱量子計算、Adiabatic Quantum Computation）である。そのモデルの実装には大きく分けて２種類あるということだ。

断熱定理とは、メチャクチャ簡単に言うと

あるシステムに、それを取り巻く状況を十分にゆっくり変更を加えると、そのシステムは状況の変化に応じて（それぞれの時点で）その変化に対応する変化を遂げる。
Adiabatic Theorem Wikiより、一部を筆者が翻訳
では、なんのことか分からないので、言い直すと。ある特定の環境のシステムの最小エネルギーを求めたい場合。一番エネルギーの低い状態にある（一番安定している）システムの既知の環境を徐々に変化させて、ある特定環境に誘導していけば、（システムは常に一番低いエネルギーの状態にあるので）、その特定の環境になった時のエネルギーも一番低い。それが求めるエネルギーだ。
組み合わせ最適化に応用すると（最小化の場合）、（組み合わせ最適化の問題を）数式化したものを出力が分かっている既知の状態から徐々に環境を変化させて、求めたい特定の状態に持っていけば、その時点での数式の出力が最小値である。
ここで、大切なのは、徐々にと言うことである。このことで、一番エネルギーの低い状態で変化していくことを保証している。
Adiabatic Theorem Wiki　とその内容を筆者が意訳

これに基づいた計算モデルが断熱量子計算（AQC）で、その実装には量子アニーリング（QA）と量子断熱algorithm（QAA）がある。それを表したものが、下の図だ。

因みにD WAveもYoutubeでAQCが量子アニーリングと汎用量子コンピュータの元になっていることをわかり易い図で示している。

ここでの説明は、それぞれの方式の詳細は述べずに、それぞれの方式が全体図の中でどのような位置にあり、どのように関連づけられているかのみ述べる。それぞれの方式の詳細は次のblog（もともとこのblogの前に予定していた）で述べる。

焼きなましと疑似アニーリング

最初に一番左の焼きなまし（アニーリング、annealing）の技術は何百年もの間知られており、物理現象であって、直接はQCに関係ないようには思える。しかし、湊氏共著の「IBM Quantumで学ぶ量子コンピュータ」で書いているように、QCの問題の多くの解は物理現象の解に置き換えられことが多い。焼きなましは鉄などの金属に熱を加え、ある一定の温度を超えるとその結晶が崩れて原子・電子が自由に運動をするようになる。次にゆっくりと冷ますと、再結晶化が起こりその時点で一番エネルギーの低い安定状態になることが知られている。このように、エネルギーが最低の安定の状態を得たように、組み合わせの最適化（最小化または最大化）計算に応用したのが、SA（擬似アニーリング）だ。当然SAはソフト（理論的な土俵）で行われるので、実際に温度は関係ないが、その計算式の中に温度というパラメータを利用して擬似的に焼きなましを模倣（simulation）している。上の図で左上の焼きなましとSAは熱を利用して量子エネルギーを変化させるという意味でまとめてある。

AQC

そののち、量子にエネルギーを与える方法を熱から磁場にして計算しようとというのが断熱量子計算（Adiabatic Quantum Computation, AQC）だ。AQCは計算のモデルであり、実装には２種類ある。１つはハードによるもので、もう１つはソフトによる。

QA

QAは、２つの実装方式のうち、より自然の物理現象に近い解で、実際のハードで解くことができる。量子アニーリングという特別な計算機で処理される。Blueqat社の湊氏はアナログ方式と呼んでいる。一番有名なものはD Wave社のものだ。必要なパラメータをこの専用計算機に送ると自動的に計算してくれる。これは上の図では右上の部分で示されている。量子に対するエネルギーの変化は磁場で調節される。

QAA

もう１つはソフトによる解で、これはゲート型の汎用マシンで実行することができる。ソフトであるため物理的なシステムとは異なり論理的に処理する（量子断熱 algorithm、Quantum Adiabatic Algorithm, QAA）。当初この方式をゲート型で実装するには複雑すぎ、現状（NISQ）の汎用マシンでは実現できないため、それを近似するalgorithmのQAOAが考察された。今後、NISQからFTQCへと発展していく中、QAOAは元来のQAAに置き換えられていく。この様子を右下で示している。

このblogを書く動機は、組み合わせ最適化問題の解法に関して、色々な技術的な語句が飛び交い、非常にわかりにくいと感じたので、自分なりに色々と調べてみた。数式を使わず、非常に簡単に説明しているものがなかったので、全く初めからこれを学ぼうとする人には役立つのではないかと思った。次は、それぞれの方式をもう少し詳しく述べたい。