論文の概要: Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs
- arxiv url: http://arxiv.org/abs/2412.15147v1
- Date: Thu, 19 Dec 2024 18:27:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-20 13:30:42.852098
- Title: Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs
- Title（参考訳）: ランダム正規グラフ上の局所ハミルトン問題に対する変分アルゴリズムの性能
- Authors: Kunal Marwaha, Adrian She, James Sud,
- Abstract要約: グラフ上に定義された2-局所ハミルトニアンを最適化する2つの変分アルゴリズムを設計する。
無限大極限におけるランダム正則グラフに対して,これらのアルゴリズムによって達成されるエネルギーを高い確率で解析する公式を開発する。
アルゴリズムの5つの層だけで、QMCの基底状態エネルギーの1.62%の誤差を無限の1Dリングで生成できることが示される。
- 参考スコア（独自算出の注目度）: 0.13654846342364307
- License:
- Abstract: We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.
- Abstract（参考訳）: グラフ上に定義された2-局所ハミルトニアンを最適化する2つの変分アルゴリズムを設計する。
我々のアルゴリズムは量子近似最適化アルゴリズムにインスパイアされている。
我々は, [arXiv:2110.14206] の手法を用いて, 無限大極限におけるランダム正則グラフよりも高い確率で, これらのアルゴリズムによって達成されるエネルギーを解析する公式を開発した。
これらの式の評価の複雑さはアルゴリズムの層数に比例して指数関数的にスケールするので、数値的な評価は少数の層数に制限される。
我々はこれらのアルゴリズムを、単純な古典的アプローチと最先端の最悪のアルゴリズムと比較する。
これらの特定の変分アルゴリズムに固有の対称性は、一般グラフ上で量子マックスキュート(QMC)ハミルトニアンを最適化するのに、主要な \emph{obstacle} を示す。
にもかかわらず、アルゴリズムはランダムな正則グラフ上の[arXiv:2209.02589]のEPRハミルトニアンを最適化するための既知の方法と、グラフが二部グラフであるときのQMCハミルトニアンよりも優れている。
特別な場合として、我々のアルゴリズムの5つの層だけで、反強磁性ハイゼンベルクスピン鎖に対応する無限1次元リング上のQMCの基底状態エネルギーの1.62%の誤差で状態を作ることができる。
関連論文リスト
- Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
パラメタライズド量子ゲートのツリー配置を導入し、1ラウンド$i$HVAを用いて任意のツリーグラフを正確に解けるようにする。
我々のアンサッツは、最大24ノードと$D leq 5$のグラフに対して、MaxCutを正確に解く。
論文 参考訳（メタデータ） (2024-08-17T03:34:17Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
ハミルトニアンサイクル問題(HCP)は、n 個のノードと m 個のエッジを持つグラフ G を持ち、各ノードを正確に1度に接続する経路を見つけることである。
本稿では、計算の異なるモデル、特に確率的および量子的モデルを用いて、aHCPを解くアルゴリズムを比較する。
論文 参考訳（メタデータ） (2023-11-18T02:36:10Z) - Quantum Hamiltonian Algorithms for Maximum Independent Sets [6.772902928686719]
PKアルゴリズムと呼ばれる別のアルゴリズムは、独立集合が創発的PXPモデルの非アーベルゲージ行列によって支配されるメディアグラフ上で拡散することを明らかにする。
2つのアルゴリズムは数学的に等価であるが、PKアルゴリズムはより効率的でリソース節約性能を示す。
論文 参考訳（メタデータ） (2023-10-23T04:00:34Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳（メタデータ） (2023-06-10T23:28:13Z) - Faster quantum mixing of Markov chains in non-regular graph with fewer
qubits [0.0]
量子の場合、マルコフ連鎖からのqsamplingは、定常分布の平方根に任意に近い振幅を持つ量子状態の準備として構成することができる。
本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークを用いて構築する。
非正規グラフでは、量子高速フォワードアルゴリズムの起動は、離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。
論文 参考訳（メタデータ） (2022-05-12T14:08:08Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。