量子アニーリングアルゴリズムの物理実装

Question

から その質問 量子アニーリングとシミュレーテッド アニーリングの違いについて、私たちは量子アニーリングの物理的な実装が存在することを (回答へのコメントで) 発見しました (D-Wave 量子コンピューター)。

そのアルゴリズムを量子ゲートと量子アルゴリズムの観点から、あるいは物理的な観点（量子ハードウェアに依存するアルゴリズムの一部）の観点から説明できる人はいますか?

それについて何かアイデアがある人はいますか?この質問に関連するリンクを知っている場合は教えてください。

Answer 1

から FT11 （強調が追加されました）：

量子アニーリング（QA）はaです クラシック ランダム化されたアルゴリズム...量子システムの動作によって提案されています。

したがって、QAには、必ずしも「量子ハードウェアに依存する」部分はありません。

古典的なアニーリング（CA）で、に類似した用語 温度 アルゴリズムが問題のソリューション空間を調査できるようにするランダム摂動の原因です。 QAでは、温度用語は、 量子トンネルフィールド強度. 。おそらく、QAの量子実装では、量子トンネリングを含むステップがハードウェアで直接実行されるでしょう。

2つの手法の比較を見つけることができます ここ, 、およびD-Waveの説明 ここ.

編集：D-Wave'sから プロセッサ操作ドキュメント （強調追加）：フォームの最適化の問題があるようにしましょう

$ e（ vec {s}）= - sum limits_ih_is_i + sum limits_ {i、j> i} k_ {ij} s_is_j $

ここで、$ -1 leq h_i $、$ k_ {ij} leq +1 $および$ s_i = pm1 $。目的$ e $を最小化する最適なソリューション$ vec {s} _ {gs} $が存在します。問題をQuantum Ising Spin Glass（QSG）ハミルトニアンにマッピングする

$ frac { mathcal {h} _ {qsg}（t）} {e_0（t）} = - sum limits_ih_i sigma_z^{（i）}+ sum rimits_ {i、j> i} k_ {ij} sigma_z^{（i）} sigma_z^{（j）} - gamma（t） sum limits_i sigma_x^{（i）} $ $

物理システムを使用します $ | vec {s_ {gs}} rangle $を見つけるには、$ gamma（t）$を進化させて$ rangle $を見つけます。

$ gamma（0） ll h_i、k_ {ij} $

$ gamma（t_f） gg h_i、k_ {ij} $

Answer 2

あなたが言及している量子コンピューティングへのアプローチは、断熱モデルと呼ばれるものです。実際には、離散化時間モデルではなく、量子システムの連続時間進化に基づいています。ゲートはありません）。離散的なゲートのセットを使用して連続時間発展を近似することが可能であるため、このアルゴリズムは量子計算のあらゆる汎用モデルに実装できることがわかりました。

アルゴリズムとその仕組みを理解するには、物理​​学の知識が必要です。ハミルトニアン $H$ は、系の総エネルギーに対応するオブザーバブルです。$H$ の固有状態 $\psi$ は、$H$ の対応する固有値に等しい明確なエネルギー $E$ が存在する系の構成に対応します。

量子システムのダイナミクスはそのハミルトニアンによって決定され、固定ハミルトニアンの場合、発展は $\psi(t) = e^{-iHt/\hbar}\psi(0)$ によって与えられます。

断熱アルゴリズムは断熱定理に基づいています。この定理は、大まかに言えば、あるハミルトニアン $H_0$ の基底状態 (システムの最低エネルギー状態) から開始し、時間の関数としてハミルトニアンをゆっくりと変化させると、ハミルトニアンの変化速度が十分に遅い場合には、瞬間的なハミルトニアンの基底状態 (あるいはそれに非常に近い) に留まり続けることになります。これをどの程度遅くする必要があるかは、基底状態と次に低いエネルギー準位との間の最小ギャップに依存し、ハミルトニアンごとに異なります。

断熱アルゴリズムは、基底状態の準備が簡単な単純なハミルトニアン $H_0$ から開始し、基底状態でエンコードするターゲット ハミルトニアン $H_1$ との間をゆっくりと補間するだけです。あなたが解決しようとしている問題の解決策。したがって、時変ハミルトニアンは $H(t) = (1-t/T)H_0 + (t/T)H_1$ のようになります。ここで $T$ は断熱発展の合計時間です。$T$ が十分に大きい限り、断熱定理により、時刻 $T$ での結果の状態が $H_1$ の基底状態に非常に近くなることが保証されます。

上記の線形補間が唯一の可能な選択肢ではないことに注意してください。実際、$H_0$ と $H_1$ の間のより良いパスを探すことは、活発な研究分野です。なぜなら、パスは、次の関数が取り得る最小値を決定するからです。 $T$。それでもなお、上記の内容から、アルゴリズムがどのように機能するかを理解できるはずです。

Answer 3

これは、Quoraに関するLaymanの用語で断熱量子コンピューティングがどのように機能するかについての質問に私が与えた答えです。ただ警告するために、それは少し単純で冗長です。これがリンクです： https://www.quora.com/quantum-computation/how-does-adiabatic-quantum-computation-work-in-laymans-terms/answer/hadayat-seddiqi

断熱量子コンピューティング（AQC、以降）は、ほとんどの研究者が取り組んでいる量子回路またはゲートモデルと根本的に異なるパラダイムです。後者の詳細をspareしみ、次のような質問を参照します。

https://www.quora.com/quantum-computation/how-does-quantum-computing-work

しかし、断熱モデルとゲートモデルが等価であることが数学的に示されていることを指摘します。そのため、あるタイプのマシンで実行できる等価アルゴリズムを見つけることができますが、保証はありませんが、保証はありません。効率。注意が重要です。誰かがShorのアルゴリズムの断熱バージョンを見つけるかもしれませんが、古典的な計算方法に勝てない可能性があります。

断熱モデルには、いくつかの重要なことがあります。以下に概説します。

- 問題（ブールSATの問題の観点から）をエンコード - キュービットの初期状態の準備（問題をプログラムする） - アニールプロセス（初期状態から最終状態にゆっくりと変更） - システムを測定して回答を得る

そのように見て、AQCを使用した計算は非常に簡単に思えます。

問題をエンコードします最初は、問題をAQCが処理できるものに変換する必要があります。一般に、これはブールの満足度問題の形になります。これには数学表記法の観点から特定の形式がありますが、その背後にある主な考え方は、最小または最大値を見つける必要がある最適化の問題があるということです。また、多くの制約があります。グラフの観点から考えてください。グリッドにノードのコレクションがあり、最初はすべて接続されています。このグラフは、AQCの「プログラム」に類似しており、キュービットの初期状態が特定の方法で接続されています。

初期状態QCの場合、初期状態が必要です。古典的なコンピューティングでは、それらはビットであり、量子コンピューティングではQubitsです。上記のQCがどのように機能するかについてのより広範な質問を再度紹介し、一般的なQCとQCがどのように機能するかを理解します。

AQCでは、Qubitsには特定の接続があります。たとえば、Qubitsが磁場方向である場合（電流が時計回りに進むか、反時計回りに行くかによって、またはJosephsonのジャンクションのために、2つの重ね合わせになります）。 （イカ）、これらのイカを接続する超伝導ワイヤがあります。これらのワイヤーは、最初の問題をデバイスにエンコードするために、必要に応じて「オフ」することができます。

これは、ジョセフソンジャンクションを備えたRF-Squidが次のように見えるものです。

これがD-Waveのブログの別の図です。正しい図は、独自のマシンの接続性を示しています。

ここで注意する必要があるのは、D-Waveのシステムが完全に接続されていないことです。これは、ノード1,2,3と4が互いに接続されていないためにわかります。これは、彼らのマシンがより強力な理論的AQCのサブセットであることを意味しますが、実験的な制約のために、それらは示されているアーキテクチャで行ったものです。

アニーリングプロセスこれは、計算が実際に発生する場所です。私はまともな類推だと思うものを思いついたので、それがあなたにとって理にかなっているかどうかを確認してください。

カップに氷のブロックを入れて、熱を上げて溶かすと想像してください。あなたの目標は、氷をできるだけゆっくりと溶かすことです。そうすれば、水を飲むと、振動や波が絶対にゼロになります。氷の立方体が瞬時に水に変わると、水がカップの壁に急いで行くので、どこにでも波があると想像できます。あなたがやりたいことは、これが決して起こらないようにゆっくりと加熱することです。あなたの寛容は、たとえば99％です。アイスキューブがAQCである場合、最終状態（水）の振動は「興奮」であり、基本的にエラーを意味し、したがって間違った答えを与えます。それらは近いかもしれませんが、最適ではありません。

したがって、この接続されたキュービットのシステムがイカの形であることは、特定の方法で進んでいる磁場でこのシステムを準備することです。その後、最終的な状態をゆっくりとオンにしながら、ゆっくりと初期状態をオフにします。したがって、基本的には初期エネルギーと最終エネルギーの混合状態を通過していますが、最後には基本的に州に問題の初期部分はなく、最終的な状態のみが残ります。別の方法は、両方の状態から始めることですが、初期状態を州の最終部分よりもはるかに強くし、その後、非常に大きな初期状態をゆっくりとオフにします。これを混乱させる場合は、この方程式を見てください

Hは、システムの総エネルギー状態を定義するマトリックスの名前にすぎないハミルトニアンの略です。 3つの用語は、本当に2つの用語にグループ化できます。大きなZとXは、スピンマトリックスを指しています。したがって、この方程式に関しては、初期状態は最後の期間に支配され、最終状態は最初の2つの用語によって支配されます。スピンマトリックスは、X-basis状態からZベース状態への変化を示しています。 Qubitsの最初のシステムを準備すると、それらをすべてX-Spin状態に入れてから、Zスピン状態にアニールします。 HとJは、最初はKよりもはるかに小さいと想像してください。アニールすると、ゆっくりとKをオフにして、完了したら、最初の2つの条件にあるものだけが残ります。これがアニーリングプロセスの仕組みです。対称Xのように見えるプロットを考えることができます。 xの1つの十字は、線形に減少するk係数であり、もう1つの十字は線形に増加するhおよびj係数です。

正しい答えを得るために適切にアニールするために、興奮なしに落ち着くのに十分な時間を与えていることを確認する必要があります。上記の方程式は時間依存性であり、より具体的には、H、J、およびKの用語は時間依存性です。これで、断熱定理は、T = Infinityのために実行されない限り、100％の精度に達しないことを教えてくれます。それでも、私たちは近づくことができます。 90％でさえ、やや最適なソリューションにすぐに到達していることを考えると、それほど悪くはありません。

数学と量子力学の観点から、状態ベクターは常にハミルトニアンの最低固有状態にある必要があります。線形代数の固有状態は、いくつかのマトリックスの固有ベクトルに相当します。量子力学に精通している場合、粒子は離散エネルギー状態にすぎないことがわかります。このシステムのエネルギーは、マトリックスであるハミルトニアンであり、最も低いエネルギー状態は、このハミルトニアンの最低の固有ベクトルによって与えられます。実際のエネルギーレベルを知りたい場合、それは前述の固有ベクトル/固有状に合う最低の固有値になります。今、あなたがアニーリングするとき、あなたは常に基底状態になりたいです。これがゆっくりと移動する必要がある理由です。なぜなら、速すぎると、システムにエネルギーを与え、励起とジャンプがより高いエネルギーレベルにジャンプするからです。これはあなたのエラーがどこから来たのかというので、これは良くありません。

最終状態アニーリングプロセスを実行したら、いくつかのことを疑問に思うでしょう。正しい答えを得たことをどうやって知ることができますか？実行するためにプログラムをどのくらいの時間に渡す必要がありますか？いくつかのオンザフライエラー修正を行う方法はありますか？

さて、あなたはあなたが正しい答えを得たかどうかを知るためにあなたの問題についてテストをする必要があります。通常、NP不完全な問題を解決している場合は、ソリューションがかなり迅速に正しいかどうかを確認できます。それでも、深刻なケースで使用する特定のアルゴリズムを配置するまで、計算を何度も実行する必要があります。ただし、これにも対策があり、ハミルトニアンの実際のエネルギーを追跡し、基底状態の固有ベクトルを見つけること、そしてそれを実際の状態と比較することに関係しています。 2つの内部産物があなたのエラーを示します。これは理論的にのみ行うことができることに注意してください。それは、それを観察せずに量子状態を追跡できないためです（したがって、それを変更する）。

フライでは、AQCのシミュレーションでもエラーの修正が可能です。ここにバックアップさせてください。アニーリングプロセスをシミュレートし、特定のアルゴリズムのタイムスキームを作成できるように、いくつかの数値ソフトウェアを作成できるという考えがあります。シミュレーションであるため、常に状態ベクトルにアクセスでき、数学に応じて予測エラーを測定できます。エラーと正確性の測定値を調べ、それに応じてアニーリングタイムステップを調整することにより、オンザフライエラー修正を行うことができます。このグラフを見てください：

これは、1キットシミュレーションの固有スペクトルと呼ばれるものです。基本的に、1キットのアニーリング時間を通してエネルギーを示しています。 X軸を時間として見てください。底部の曲線は基底状態であり、上の曲線は最初の励起状態です。ある時点で、2つの曲線が非常に近いことをどのように得るかに注意してください。これは重要なポイントです。なぜなら、このエネルギーの「ギャップ」が小さいほど、システムの状態が基底状態にとどまるのではなく、この高いエネルギー状態にジャンプする可能性が高いからです。明らかに、これはあなたが非常にゆっくりと動きたい時です。逆に、エネルギーのギャップが非常に大きい場合、それはかなりありそうもないので、より高い状態にジャンプする場合、心配することなくかなり速く動くことができます。 n = 0.5ポイントになるまで非常に速く進むことを意味するタイムスキームを思いつくことができ、小さなギャップのしきい値を渡すまではるかにゆっくりと進み始めます。

とにかく、それは基本的にそれです。 AQCは長い間存在していなかったので、そのエネルギーギャップをどのように特徴付ける方法や、アニーリングの時代にどのように関連しているかなど、人々はまだそれについて多くのことを考えています。多くの潜在的なアプリケーションがあり、その答えで私がこの答えの一番上でリンクした質問に私の答えでメモします。

Answer 4

この質問を基本的に「のアプローチを説明/明確にする ドワー システムコンピューター 量子アニーリング & QM計算「。最初のOrionコンピューターでのアプローチの基本的な発表は[1]にあり、明らかに後の反復で使用される設計でもあります。

それを見るもう1つの方法は、彼らのアイデアは、量子機械的キュービットシステムの自然な物理的ダイナミクスとエネルギー状態の進化に密接に関連するNP完全な問題を見つけることです。この場合、そうです ISINGモデル, 、統計力学における強磁性の数学的モデル。 ISINGモデルの解決策を見つけることがNP完全であることが理論的に証明されています（Dwave Computersに実装された2Dバージョンを含む）。[2]ただし、[1]で参照されている詳細があるようです。

そのため、NP完全な問題は2D ISINGモデルの問題に変換できるという考えです。ただし、ほとんどの実用的な問題の間の変換には多くのQBITが含まれ、Dwaveの現在の制限は128 QBIT（Dwave1 "Ranier"）であることに注意してください。彼らは、まだリリースされていない512 QBITバージョン「Vesuvius」を発表しました。 Dwaveは最近、Dwave1マシンのLockheed Martinへの販売を発表しました。詳細な科学論文が自然界でリリースされました[5]。

[1] Quantum Computing Demo発表、2007年 ドワーブシステム、ジョードローズ博士

[2] ISINGモデルはNP不完全です バリーA.シプラ

[3] 「磁場の2次元ISINGモデル」 現在404

[4] 奇妙なコンピューターは大きなスピードを約束します

[5] 製造されたスピンを使用した量子アニーリング ジョンソン等