よろずQCのZen問答: QCに関する基本データ（Version-1.2）
このシリーズのblogでは英語の名前と日本語の名前が多く出てきて、その対比のために対比表をblog毎に載せていたのでは、blogが長くなりすぎるので、今後このblogで、その対比表と各algorithm間の相互関係の図も載せておく。今後はこのblogを参照することにする。最後尾に編集のlogを記載。
日本語と英語のalgorithmの名前
| VQE (Variational Quantum Eigensolver): | 変分量子固有値解方（ソルバー） |
| OAOA (Quantum Approximate Optimization Algorithm): | 量子近似最適推定 |
| QPE (Quantum Phase Estimation): | 量子位相推定 |
| QAE (Quantum Amplitude Estimation): | 量子振幅推定 |
| QAA (Quantum Amplitude Amplifier): | 量子振幅増幅 |
| QATE (Quantum Amplitude Time Estimation): | 量子振幅時間推定 |
| QTE (Quantum Time Evolution): | 量子時間発展 |
| ATE (Adiabatic Time Evolution): | 断熱時間発展 |
| QML (Quantum Machine Learning): | 量子機械学習 |
| QCBM (Quantum Circuit Born Machine): | 量子回路ボルンマシン |
| QFT (Quantum Fourier Transform): | 量子フーリエ変換 |
| Shor’s algorithm | ショアのアルゴリズム |
| Grover’s algorithm | グローバーのアルゴリズム |
| HHL (Harrow-Hassidim-Lloyd) algorithm | HHL アルゴリズム |
| QAOA (Quantum Alternative Operator Ansatz): |
Algorithmの相関関係
以下に主なQCのAlgorithmの相関関係を示す。全てのalgorithmを網羅している訳ではない。更に、専門家に言わせれば、あちこち異議があると思うし、明らかな間違いがあるかもしれない。今後は、問題が発見されれば訂正しし、QC理解に不可欠だと思われるが、「今更聞けないけど、有ったら便利」という情報を追加していく。最初はversion 1としておく。この情報の一部はblueqatの湊氏の著書、blog、ビデオ （ビデオ１、ビデオ２、ビデオ３）などを利用した。
この図で、一番上にQCが適用される分野（Optimization、Finance、ML、Chemistry/Materialsと暗号）を示している。矢印の始点は、終点に対して不可欠なものという意味である。例えば、MLを例にとると、MLにはHHLが不可欠である。HHLが矢印の始点でMLが終点である。これは、MLを実現するのにHHLが必要なことを示している。上の図を見ると、瞬時にQPEが多くの他の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は未だ実装されたという情報は確認できていない。）
編集log:
- Version 1からの変更：組み合わせ最適化用のalgorithmの変遷を追加
- Version 1.1 からの変更：組み合わせ最適化用のalgorithmの変遷を大幅に修正
- 将来のto-dos: 日本語と英語の対比表を英語のalphabet順に並べ替える
