量子アニーリング

量子アニーリング（QA）は、量子ゆらぎを用いたプロセスによって、与えられた候補解（候補状態）の集合に対して与えられた目的関数のグローバル最小値を見つける最適化プロセスである。量子アニーリングは、スピングラスの基底状態を見つける^{[1] 、巡回セールス}マン問題を解決するなど、多くの局所的最小値を伴う離散的な探索空間（組み合わせ最適化問題）の問題に主に用いられる。「量子アニーリング」という用語は、量子にヒントを得た古典的なアルゴリズムとして、1988年にB. Apolloni、N. Cesa Bianchi、D. De Falcoによって初めて提案された。^{[2] [3]}現在の形は1998年にT. KadowakiとH. Nishimori (ja)によって定式化されましたが、^[4]量子コヒーレンスのない虚時間変種は1994年にAB Finnila、MA Gomez、C. Sebenik、JD Dollによって議論されていました。^[5]

量子アニーリングは、すべての可能な状態（候補状態）の等しい重みを持つ量子力学的重ね合わせから始まります。次に、システムは、物理システムの自然な量子力学的発展である時間依存シュレーディンガー方程式に従って進化します。すべての候補状態の振幅は、状態間の量子トンネル効果、または本質的にピークを通るトンネル効果を引き起こす横方向場の時間依存の強度に応じて変化し続け、量子平行性を実現します。横方向場の変化率が十分に遅い場合、システムは瞬間ハミルトニアンの基底状態の近くにとどまります（断熱量子計算も参照）。^{[6]横方向場の変化率が加速されると、システムは一時的に基底状態を離れる可能性がありますが、最終問題のハミルトニアンの基底状態、つまり}非断熱量子計算に到達する可能性が高くなります。^{[7] [8]}横磁場は最終的にオフになり、システムは元の最適化問題の解に対応する古典的なイジングモデルの基底状態に到達すると予想されます。ランダム磁石に対する量子アニーリングの成功の実験的実証は、最初の理論的提案の直後に報告されました。 ^{[9]量子アニーリングは、多くの}NP完全問題を解く際の平方根の高速化のための高速グローバーオラクルを提供することも証明されています。^[10]

量子アニーリングはシミュレーテッドアニーリングと比較することができ、その「温度」パラメータは量子アニーリングのトンネル場の強度と同様の役割を果たします。シミュレーテッドアニーリングでは、温度によって、単一の現在の状態からより高い「エネルギー」の状態に移行する確率が決まります。量子アニーリングでは、横方向の場の強度によって、すべての状態の振幅を並行して変更する量子力学的確率が決まります。分析的^[11]および数値的^{[12] の}証拠は、特定の条件下では量子アニーリングがシミュレーテッドアニーリングよりも優れていることを示唆しています (任意のターゲットハミルトニアンに対する量子アニーリングの完全に解けるモデルとさまざまな計算アプローチの比較については、 Heim ら^[13]および Yan と Sinitsyn ^{[14]を参照してください)。}

トンネル場は基本的に、元のガラスの古典的な位置エネルギー部分と交換されない運動エネルギー項です。プロセス全体は、量子モンテカルロ(またはその他の確率的手法) を使用してコンピューターでシミュレートでき、古典的なガラスの基底状態を見つけるためのヒューリスティック アルゴリズムが得られます。

純粋に数学的な目的関数をアニーリングする場合、問題内の変数を古典的な自由度、コスト関数をポテンシャルエネルギー関数 (古典的なハミルトニアン) と見なすことができます。次に、トンネル場 (運動部分) の役割を果たすために、非交換変数 (つまり、元の数学の問題の変数と非ゼロの交換子を持つ変数) で構成される適切な項をハミルトニアンに人工的に導入する必要があります。次に、上記のように、このように構築された量子ハミルトニアン (元の関数 + 非交換部分) を使用してシミュレーションを実行できます。ここでは、非交換項を選択するオプションがあり、アニーリングの効率はそれに依存する可能性があります。

実験的にも理論的にも、量子アニーリングは、特定のケース、特にポテンシャルエネルギー（コスト）ランドスケープが浅い局所的最小値を囲む非常に高くて薄い障壁で構成されている場合、熱アニーリング（シミュレーテッドアニーリング）よりも優れていることが実証されています。^[15]熱遷移確率（温度 とボルツマン定数で に比例）は障壁の高さのみに依存するため、非常に高い障壁の場合、熱変動によってシステムをそのような局所的最小値から抜け出すことは極めて困難です。ただし、1989 年に Ray、Chakrabarti、Chakrabarti によって論じられたように、^[1]同じ障壁を通過する量子トンネル確率（単独で考えた場合）は、障壁の高さだけでなく幅にも依存し、近似的に で与えられます。ここで はトンネル場です。^[16]量子トンネル効果が存在する場合、幅 を介したこの追加のハンドルは、大きな助けとなる可能性がある。障壁が十分に薄い場合（つまり）、量子ゆらぎによって確実にシステムを浅い局所最小値から抜け出すことができる。 -スピンガラスの場合、障壁の高さはのオーダーになる。 の定数値の場合、 はアニーリング時間に対してに比例する（熱アニーリングの場合はに比例する）が、が減少する場合には は に依存しなくなることさえある。^{[17] [18]}${\displaystyle e^{-{\frac {\Delta }{k_{B}T}}}}$${\displaystyle T}$${\displaystyle k_{B}}$${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle w}$${\displaystyle e^{-{\frac {{\sqrt {\Delta }}w}{\Gamma }}}}$${\displaystyle \ガンマ}$${\displaystyle w}$${\displaystyle は \ll {\sqrt {\Delta }}}$${\displaystyle N}$${\displaystyle \Delta }$${\displaystyle N}$${\displaystyle w}$${\displaystyle \tau}$${\displaystyle e^{\sqrt {N}}}$${\displaystyle \tau}$${\displaystyle e^{N}}$${\displaystyle \tau}$${\displaystyle N}$${\displaystyle w}$${\displaystyle 1/{\sqrt {N}}}$

量子コンピュータでは、手動で追加する必要がなく、直接トンネリングを実行できるため、このようなシミュレーションは従来のコンピュータで行うよりもはるかに効率的で正確になると推測されています。さらに、従来の量子アルゴリズムで使用される量子エンタングルメントを利用するために必要な厳密なエラー制御なしでこれを行うことができる可能性があります。これを裏付けるいくつかの証拠は、正確に解けるモデルで見つかります。^{[19] [20]}

イジングスピングラスにおける量子アニーリングに関連するアイデアのタイムライン:

• 1989年、量子ゆらぎがトンネル効果を利用して局所最小値（高いが薄い障壁を持つ）から脱出することで、古典的なイジングスピングラスの険しいエネルギーランドスケープを探索するのに役立つ可能性があるというアイデアが提示されました。^[1]
• 1998 量子アニーリングの定式化とイジングガラス系におけるその利点を実証する数値テスト^[4]
• 1999年 LiHoYFイジングガラス磁石における量子アニーリングの最初の実験的実証^[21]
• 2011年、D-Wave Systems社が超伝導回路量子アニーリングマシンを開発し販売した。^[22]

2011年、D-Wave SystemsはD-Wave Oneという名前で市場初の商用量子アニーリング装置を発表し、その性能に関する論文をNature誌に発表した。^[22]同社によれば、このシステムは128量子ビットのプロセッサチップセットを使用している。^[23] 2011年5月25日、D-Waveはロッキード・マーティン社がD-Wave Oneシステムを購入する契約を締結したと発表した。^[24] 2011年10月28日、南カリフォルニア大学（USC）の情報科学研究所はロッキード社のD-Wave Oneを受け取った。

2013年5月、 Google、NASAエイムズ研究センター、非営利の大学宇宙研究協会のコンソーシアムが、512量子ビットの断熱量子コンピュータをD-Wave Systemsから購入したことが発表されました。^{[25] [26]}いくつかの古典的なアニーリングアルゴリズムと比較した量子アニーリングとしての性能に関する広範な研究が利用可能です。^[27]

2014年6月、D-Waveは、計算金融会社1QB Information Technologies（1QBit）および癌研究グループDNA-SEQと共同で、量子ハードウェアによる現実世界の問題の解決に重点を置く新しい量子アプリケーションエコシステムを発表しました。^[28]市販の量子コンピュータ用のソフトウェアアプリケーションの開発に特化した最初の企業として、1QBitの研究開発部門はD-Waveの量子アニーリングプロセッサに焦点を当て、これらのプロセッサが現実世界のアプリケーションの解決に適していることを実証しました。^[29]

エンタングルメントの実証が発表されたが、^[30] D-Wave マシンがすべての古典的コンピュータに対して量子スピードアップを実証できるかどうかという疑問は未だに解決されていない。2014 年 6 月にScience 誌に発表された研究は、「D-Wave マシンの性能に関して行われた研究の中でおそらく最も徹底的かつ正確な研究」^[31]であり、「これまでで最も公平な比較」と評され、量子スピードアップの定義と測定を試みた。いくつかの定義が提示されたが、そのうちのいくつかは経験的テストでは検証できないかもしれないが、他の定義は偽りであるにもかかわらず、それでもパフォーマンス上の利点が存在することを許容する。この研究では、D-Wave チップは「量子スピードアップを生み出さなかった」と結論付けられ、将来のテストでその可能性を排除しなかった。^[32]スイス連邦工科大学の Matthias Troyer 率いる研究者らは、テストの全範囲で「量子スピードアップは見られなかった」と結論付け、テストのサブセットを見たときにのみ決定的な結果が得られた。彼らの研究は「量子スピードアップの問題の微妙な性質」を示した。さらなる研究^{[33]により}、これらのテストメトリクスとそれらの平衡システムへの依存についての理解が深まり、量子ダイナミクスによる利点の兆候が見られなくなりました。

量子高速化に関しては未解決の問題が数多くあります。前のセクションの ETH の参照は、ベンチマーク問題の 1 つのクラスに過ぎません。潜在的には、量子高速化が発生する可能性のある他のクラスの問題が存在する可能性があります。Google、LANL、USC、Texas A&M、D-Wave の研究者は、そのような問題クラスを見つけるために取り組んでいます。^[34]

2015年12月、Googleは、D-Wave 2Xが一連の困難な最適化問題において、シミュレーテッドアニーリングと量子モンテカルロの両方を最大1億倍上回る性能を発揮すると発表した。^[35]

D-Waveのアーキテクチャは従来の量子コンピュータとは異なります。汎用量子コンピュータと多項式的に等価であることは知られておらず、特に、ショアのアルゴリズムはヒルクライミングプロセスではないため、ショアのアルゴリズムを実行することはできません。 ^[要出典]ショアのアルゴリズムには汎用量子コンピュータが必要です。D-Waveが開催したQubits 2021カンファレンスで、同社がQAOAやVQEなどの他のゲートモデルアルゴリズムに加えてショアのアルゴリズムを実行できる初の汎用量子コンピュータを開発していることが発表されました^[ 36] 。

「量子アニーリングに基づくアルゴリズムの学際的入門」^[37]では、組合せ最適化（NP困難）問題の紹介、量子アニーリングに基づくアルゴリズムの一般的な構造、最大SAT（最大満足問題）および最小マルチカット問題のインスタンスを解決するためのこの種のアルゴリズムの2つの例、およびD-Wave Systems社が製造する量子アニーリングシステムの概要が示されています。大規模な離散-連続最適化問題のためのハイブリッド量子古典アルゴリズムが、量子の利点を示すために報告されました。^{[38] [39]}

• Bapst, V.; Foini, L.; Krzakala, F.; Semerjian, G.; Zamponi, F. (2013). 「ランダム最適化問題に適用される量子断熱アルゴリズム: 量子スピングラスの観点」. Physics Reports . 523 (3): 127–205. arXiv : 1210.0811 . Bibcode :2013PhR...523..127B. doi :10.1016/j.physrep.2012.10.002. S2CID  19019744.
• Chandra, Anjan K.; Das, Arnab & Chakrabarti, Bikas K.編 (2010)。量子クエンチング、アニーリング、計算。物理学講義ノート。第 802 巻。ハイデルベルク、ドイツ: Springer。ISBN 978-3-64211-469-4。
• Das, Arnab & Chakrabarti, Bikas K. 編 (2005)。量子アニーリングと関連する最適化手法。物理学講義ノート。第 679 巻。ハイデルベルク、ドイツ: Springer。ISBN 978-3-54027-987-7。
• Dutta, A.; Aeppli, G.; Chakrabarti, BK; Divakaran, U.; Rosenbaum, TF & Sen, D. (2015). 横方向場スピンモデルにおける量子相転移: 統計物理学から量子情報へ。ケンブリッジ、イギリスおよびデリー、インド: Cambridge University Press。ISBN 978-1-10706-879-7。
• Li, Fuxiang; Chernyak, VY; Sinitsyn, NA (2013). 「量子アニーリングと計算: 簡単なドキュメンタリーノート」.科学と文化. 79 : 485–500. arXiv : 1310.1339 . Bibcode :2013arXiv1310.1339G.。
• 鈴木 誠、井上 淳一、チャクラバーティ BK (2013)。「第 8 章 量子アニーリング」。横方向イジングモデルにおける量子イジング相と遷移(第 2 版)。ハイデルベルク: シュプリンガー。ISBN 978-3-64233-038-4。
• 田中 誠、田村 亮、チャクラバーティ BK (2017)。量子スピングラス、アニーリング、計算。ケンブリッジ＆デリー：ケンブリッジ大学出版局。ISBN 978-1-10711-319-0。
• 「量子アニーリングと計算：課題と展望」。哲学論文集A。381 。王立協会、ロンドン、イギリス。2023年1月。