論文の概要: Quantum Hamiltonian Algorithms for Maximum Independent Sets
- arxiv url: http://arxiv.org/abs/2310.14546v5
- Date: Wed, 4 Sep 2024 05:17:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-07 04:41:34.198875
- Title: Quantum Hamiltonian Algorithms for Maximum Independent Sets
- Title（参考訳）: 最大独立集合に対する量子ハミルトンアルゴリズム
- Authors: Xianjue Zhao, Peiyun Ge, Hongye Yu, Li You, Frank Wilczek, Biao Wu,
- Abstract要約: PKアルゴリズムと呼ばれる別のアルゴリズムは、独立集合が創発的PXPモデルの非アーベルゲージ行列によって支配されるメディアグラフ上で拡散することを明らかにする。
2つのアルゴリズムは数学的に等価であるが、PKアルゴリズムはより効率的でリソース節約性能を示す。
- 参考スコア（独自算出の注目度）: 6.772902928686719
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With qubits encoded into atomic ground and Rydberg states and situated on the vertexes of a graph, the conditional quantum dynamics of Rydberg blockade, which inhibits simultaneous excitation of nearby atoms, has been employed recently to find maximum independent sets following an adiabatic evolution algorithm hereafter denoted by HV [Science 376, 1209 (2022)]. An alternative algorithm, short named the PK algorithm, reveals that the independent sets diffuse over a media graph governed by a non-abelian gauge matrix of an emergent PXP model. This work shows the above two algorithms are mathematically equivalent, despite of their seemingly different physical implementations. More importantly, we demonstrated that although the two are mathematically equivalent, the PK algorithm exhibits more efficient and resource-saving performance. Within the same range of experimental parameters, our numerical studies suggest that the PK algorithm performs at least 25% better on average and saves at least $6\times10^6$ measurements ($\sim 900$ hours of continuous operation) for each graph when compared to the HV algorithm. We further consider the measurement error and point out that this may cause the oscillations in the performance of the HV's optimization process.
- Abstract（参考訳）: 量子ビットが原子基底とリドベルク状態にエンコードされ、グラフの頂点に位置することにより、近辺の原子の同時励起を阻害するリドベルク封鎖の条件量子力学が近年、HV (Science 376, 1209 (2022)) で表されるアディアベート進化アルゴリズムに従って、最大独立集合を見つけるために用いられるようになった。
PKアルゴリズムと呼ばれる別のアルゴリズムは、独立集合が創発的PXPモデルの非アーベルゲージ行列によって支配されるメディアグラフ上で拡散することを明らかにする。
この研究は、上述の2つのアルゴリズムが数学的に等価であることを示している。
さらに、PKアルゴリズムは数学的に等価であるが、より効率的かつ省資源性を示すことを示した。
同じ実験パラメータの範囲内では、HVアルゴリズムと比較して、PKアルゴリズムは平均で25%以上の性能を示し、各グラフに対して最低6\times10^6$(約900ドル)の連続演算を省くことが示唆されている。
さらに、測定誤差を考慮し、これがHVの最適化プロセスの性能の振動を引き起こす可能性があることを指摘する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。