論文の概要: Quantum Hamiltonian Algorithms for Maximum Independent Sets

• arxiv url: http://arxiv.org/abs/2310.14546v3
• Date: Sun, 7 Jul 2024 15:48:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-10 03:18:28.587844
• Title: Quantum Hamiltonian Algorithms for Maximum Independent Sets
• Title（参考訳）: 最大独立集合に対する量子ハミルトンアルゴリズム
• Authors: Xianjue Zhao, Peiyun Ge, Hongye Yu, Li You, Frank Wilczek, Biao Wu,
• Abstract要約: 最大独立集合問題に対処する2つの量子ハミルトンアルゴリズムを比較する。 それらが数学的に等価であることを示すが、一見すると全く異なるように見える。 数値シミュレーションにより,性能に有意な差が見られ,実験プロトコルの改善が示唆された。
• 参考スコア（独自算出の注目度）: 6.772902928686719
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We compare two quantum Hamiltonian algorithms that address the maximum independent set problem: one based on emergent non-abelian gauge matrix in adiabatic evolution of an energetically isolated manifold of states; and one based on designed application of single-qubit operations. We demonstrate that they are mathematically equivalent, though at first sight they appear quite different. Despite their mathematical equivalence, their most straightforward physical implementations are different. Our numerical simulations show significant differences in performance, and suggest improved experimental protocols.Intriguingly, this equivalence unveils a deeper connection. We also demonstrate that the PXP model, recently prominent in quantum dynamics research, arises as the non-abelian gauge matrix governing quantum diffusion over the median graph of all independent sets.
• Abstract（参考訳）: 我々は、最大独立集合問題に対処する2つの量子ハミルトンアルゴリズムを比較する: 1つは、エネルギー的に孤立した状態多様体の断熱的進化における創発的非アーベルゲージ行列に基づく。 それらが数学的に等価であることを示すが、一見すると全く異なるように見える。 数学的等価性にもかかわらず、それらの最も単純な物理的実装は異なる。 我々の数値シミュレーションは性能に有意な違いを示し、実験プロトコルの改善を示唆するが、興味深いことに、この等価性はより深い接続を明らかにする。 また、最近量子力学研究で顕著なPXPモデルは、すべての独立集合の中央値グラフ上の量子拡散を管理する非アーベルゲージ行列として現れることを示した。

関連論文リスト

• A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
  本稿では, 線形対流拡散方程式を, 新しい近似確率的想像時間進化(PITE)演算子を用いて解く量子アルゴリズムを提案する。 我々は, 対流拡散方程式から得られるハミルトニアンの想像時間進化を実現するために, 明示的な量子回路を構築した。 我々のアルゴリズムは、Harrow-Hassidim-Lloyd (HHL)アルゴリズムに匹敵する結果を与える。
  論文  参考訳（メタデータ） (2024-09-27T08:56:21Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Quantum algorithms for anomaly detection using amplitude estimation [5.20363732303968]
  密度推定に基づく異常検出アルゴリズム(ADDEアルゴリズム)は広く使われているアルゴリズムの1つである。 本稿では振幅推定に基づく新しい量子ADDEアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-28T15:47:56Z)
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy [22.31288740171446]
  PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。 条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。 これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。 本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
  論文  参考訳（メタデータ） (2021-09-10T02:22:10Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  本稿では,リッジ回帰モデルに基づく量子アルゴリズムを提案する。 提案アルゴリズムは幅広い応用範囲を持ち,提案アルゴリズムは他の量子アルゴリズムのサブルーチンとして利用することができる。
  論文  参考訳（メタデータ） (2021-04-27T11:03:52Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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