論文の概要: Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms
- arxiv url: http://arxiv.org/abs/2609.40336v1
- Date: Wed, 30 Sep 2026 17:57:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:28.344848
- Title: Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms
- Title（参考訳）: 量子基底状態エネルギーの局所緩和階層:収束保証とメッセージパッシングアルゴリズム
- Abstract要約: 凸緩和階層は量子多体系の基底状態エネルギーに低い境界を与える。
我々は、局所緩和階層と、緩和された基底状態エネルギーを推定するための効率的で並列性の高いメッセージパッシングアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 3.5812110340574113
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy---based on local consistency of pairwise reduced density matrices---is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/ε^2)$ and $\mathcal{O}(n/ε)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $ε$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm---a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.
- Abstract（参考訳）: 凸緩和階層は、古典的コンピュータ上の多項式時間で計算できる量子多体系の基底状態エネルギーに対して、任意の固定階層レベルで低い境界を与える。
しかし、従来の計算コストと効率保証の不足のため、これらの手法を大規模システムに拡張し、正確な近似を行うことは依然として困難である。
本研究では, 局所緩和階層と効率的に並列化可能なメッセージパッシングアルゴリズムを開発し, 緩和された基底状態エネルギーを推定する。
木上のハミルトニアンを通勤するためには,一対還元密度行列の局所的整合性に基づく階層構造の最初のレベルが正確であることを示す。
さらに、一貫した間隔に基づく別の階層は、鎖上の分離可能なハミルトニアンの弱い摂動に対する基底状態エネルギーに指数関数的に高速に収束し、これらの系に対して効率的な古典的アルゴリズムを提供する。
次に、有界グラフ上の局所階層の任意の固定レベルに対して、$\mathcal{O}(n/ε^2)$と$\mathcal{O}(n/ε)$timeの2種類のメッセージパッシングアルゴリズムを導入する。
これは、最適なメッセージが$\mathcal{O}(1)$ normを持つことを仮定する。
これらのアルゴリズムは、エントロピー平滑な目的に応用された下次法とネステロフ型加速勾配降下法に基づいている。
最後に、異なる量子ハミルトン、格子ジオメトリ、緩和レベルにまたがるメッセージパッシングアルゴリズムをベンチマークし、理論的予測と、この問題に対する標準凸最適化解法を超える可能性を検証する。
生成されたライブラリはgithub.com/rick1924/gse-message-passingでリリースします。
関連論文リスト
- Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
フェデレーション行列の2レベル最適化は、機械学習に広く応用されているため、近年積極的に研究されている。
既存のフェデレートされた双レベル最適化アルゴリズムは、二階ヘッセン行列とヤコビ行列の計算を必要とする。
本稿では,一階オーラクルのみに依存する新しいフェデレーション収束分散誘導二段降下アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-14T21:12:59Z) - Preparation Circuits for Matrix Product States by Classical Variational Disentanglement [0.0]
行列積状態(MPS)の作成のための量子回路の古典的コンパイルについて検討する。
提案アルゴリズムは, 逆アンタングル法により, 従来の逐次的アプローチに準じて, 短期的な代替となる。
複数の量子ビット間の絡み合いを人工的に広げるだけでなく、一次元の局所ハミルトニアンの基底状態に対する数値的な結果を示す。
論文 参考訳（メタデータ） (2025-04-30T04:13:01Z) - Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation [0.5097809301149342]
我々は、勾配推定を必要としない連続的な最適化のために、いくつかの量子アルゴリズムを提供する。
我々は、最適化問題を物理系の力学にエンコードし、時間進化をコヒーレントにシミュレートする。
論文 参考訳（メタデータ） (2025-02-06T18:32:26Z) - Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians [0.39886149789339326]
我々は、任意の$k$局所ハミルトニアンが$n$ qubitsで作用する基底状態エネルギーの近似を計算する古典的アルゴリズムを構築する。
定数近似が古典的に$mathrmpolyleft (1/chi,nright)$ time と $mathrmpoly(n)$ space で計算可能であることを示す。
論文 参考訳（メタデータ） (2024-10-29T07:56:38Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。