論文の概要: Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

• arxiv url: http://arxiv.org/abs/2306.13131v1
• Date: Thu, 22 Jun 2023 18:00:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-26 14:36:38.732450
• Title: Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Title（参考訳）: 量子断熱最適化のハードインスタンスに対する超指数ランタイムの回避
• Authors: Benjamin F. Schiffer, Dominik S. Wild, Nishad Maskara, Madelyn Cain, Mikhail D. Lukin, Rhine Samajdar
• Abstract要約: 本稿では,最小ギャップがシステムサイズに比例して崩壊する問題の例について概説する。 この小さなギャップは、局所的に独立した選択から生じ、システムが最初に進化し、ソリューションから遠く離れた構成に局所化する。 これらのモデルにおける量子クエンチは、量子多体傷の徴候を示すことができ、それによって超指数的ギャップを回避できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classical optimization problems can be solved by adiabatically preparing the ground state of a quantum Hamiltonian that encodes the problem. The performance of this approach is determined by the smallest gap encountered during the evolution. Here, we consider the maximum independent set problem, which can be efficiently encoded in the Hamiltonian describing a Rydberg atom array. We present a general construction of instances of the problem for which the minimum gap decays superexponentially with system size, implying a superexponentially large time to solution via adiabatic evolution. The small gap arises from locally independent choices, which cause the system to initially evolve and localize into a configuration far from the solution in terms of Hamming distance. We investigate remedies to this problem. Specifically, we show that quantum quenches in these models can exhibit signatures of quantum many-body scars, which in turn, can circumvent the superexponential gaps. By quenching from a suboptimal configuration, states with a larger ground state overlap can be prepared, illustrating the utility of quantum quenches as an algorithmic tool.
• Abstract（参考訳）: 古典的な最適化問題は、問題を符号化する量子ハミルトニアンの基礎状態を作成することで解決することができる。 このアプローチのパフォーマンスは、進化中に遭遇した最小のギャップによって決定される。 ここでは、リドベルク原子配列を記述するハミルトニアンで効率的に符号化できる最大独立集合問題を考察する。 本稿では,最小ギャップがシステムサイズに超指数的に減衰する問題の例を概説し,断熱的進化による解への超指数的に大きな時間を示唆する。 この小さなギャップは、システムを最初に進化させ、ハミング距離の点で解から遠く離れた構成へと局所化する局所的な選択から生じる。 我々はこの問題に対する治療について調査する。 具体的には、これらのモデルの量子クエンチが量子多体傷のシグネチャを示し、それが超指数ギャップを回避できることを示す。 準最適構成からクエンチすることで、より大きな基底状態のオーバーラップ状態が作成でき、量子クエンチをアルゴリズムツールとして利用することができる。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Observation of disorder-free localization and efficient disorder averaging on a quantum processor [117.33878347943316]
  我々は、量子並列性を利用して、量子プロセッサ上で効率的な手順を実装し、すべての障害実現を効率的にサンプリングする。 1次元と2次元の量子多体ダイナミクスにおいて、乱れのない局所化を観察する。
  論文  参考訳（メタデータ） (2024-10-09T05:28:14Z)
• Quantum quench dynamics as a shortcut to adiabaticity [31.114245664719455]
  本研究では,クエンチステップを組み込んだ量子アルゴリズムを,変分するアディバティック・タイムスケールに対する対策として開発・テストする。 実験の結果,本手法は断熱アルゴリズムよりも有意に優れていることがわかった。
  論文  参考訳（メタデータ） (2024-05-31T17:07:43Z)
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem [0.0]
  断熱的進化は、固定された有限トロッターステップで行うことができることを示す。 行列積-状態シミュレーションを用いてマックス・カッツ問題を最適に解くことのできる数値的な証拠を与える。 計算結果を外挿すると、量子コンピュータが古典的正確な解法や近似解法と競合するために必要なリソースを推定する。
  論文  参考訳（メタデータ） (2024-04-24T17:29:03Z)
• Dense outputs from quantum simulations [5.295277584890625]
  量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。 この問題は量子制御や分光計算などの応用で頻繁に発生する。 我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
  論文  参考訳（メタデータ） (2023-07-26T18:16:51Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Diabatic Quantum Annealing for the Frustrated Ring Model [0.7046417074932257]
  断熱的な進化は、システムサイズと指数関数的にスケールする進化の時間につながる可能性がある。 最適化されたアニーリングスケジュールによる非断熱的進化は、この指数的な減速を回避できることを示す。
  論文  参考訳（メタデータ） (2022-12-05T22:16:17Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Hardware-Efficient, Fault-Tolerant Quantum Computation with Rydberg Atoms [55.41644538483948]
  我々は中性原子量子コンピュータにおいてエラー源の完全な特徴付けを行う。 計算部分空間外の状態への原子量子ビットの崩壊に伴う最も重要なエラーに対処する,新しい,明らかに効率的な手法を開発した。 我々のプロトコルは、アルカリ原子とアルカリ原子の両方にエンコードされた量子ビットを持つ最先端の中性原子プラットフォームを用いて、近い将来に実装できる。
  論文  参考訳（メタデータ） (2021-05-27T23:29:53Z)
• Unraveling the origin of higher success probabilities in quantum versus semi-classical annealing [0.0]
  我々は、量子力学の完全な量子表現が、いつ、より高い確率で所望の基底に到達するかを調査する。 最適解に近づくためには絡み合いの重要性が強く証明されている。
  論文  参考訳（メタデータ） (2020-10-27T12:52:09Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。 ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。 この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
  論文  参考訳（メタデータ） (2020-08-03T18:00:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。