論文の概要: Constrained local Hamiltonians: quantum generalizations of Vertex Cover

• arxiv url: http://arxiv.org/abs/2409.04433v1
• Date: Fri, 6 Sep 2024 17:55:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-09 15:05:01.194555
• Title: Constrained local Hamiltonians: quantum generalizations of Vertex Cover
• Title（参考訳）: 制限された局所ハミルトニアン:頂点被覆の量子一般化
• Authors: Ojas Parekh, Chaithanya Rayudu, Kevin Thompson,
• Abstract要約: 我々は、よく研究された古典的頂点被覆問題をインスピレーションとして、制約付き局所ハミルトン問題に対する近似アルゴリズムについて研究する。 我々は,TVCがStoqMAハードであることを示し,古典的局所比法を量子一般化した近似アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 0.8056359341994941
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent successes in producing rigorous approximation algorithms for local Hamiltonian problems such as Quantum Max Cut have exploited connections to unconstrained classical discrete optimization problems. We initiate the study of approximation algorithms for constrained local Hamiltonian problems, using the well-studied classical Vertex Cover problem as inspiration. We consider natural quantum generalizations of Vertex Cover, and one of them, called Transverse Vertex Cover (TVC), is equivalent to the PXP model with additional 1-local Pauli-Z terms. We show TVC is StoqMA-hard and develop an approximation algorithm for it based on a quantum generalization of the classical local ratio method. This results in a simple linear-time classical approximation algorithm that does not depend on solving a convex relaxation. We also demonstrate our quantum local ratio method on a traditional unconstrained quantum local Hamiltonian version of Vertex Cover which is equivalent to the anti-ferromagnetic transverse field Ising model.
• Abstract（参考訳）: 量子マックスカットのような局所ハミルトン問題に対する厳密な近似アルゴリズムの生成は、制約のない古典的な離散最適化問題との接続を利用している。 我々は、よく研究された古典的頂点被覆問題をインスピレーションとして、制限された局所ハミルトン問題に対する近似アルゴリズムの研究を開始する。 We consider natural quantum generalizations of Vertex Cover, and one of them called Transverse Vertex Cover (TVC) is equivalent to the PXP model with additional 1-local Pauli-Z terms。 我々は,TVCがStoqMAハードであることを示し,古典的局所比法を量子一般化した近似アルゴリズムを開発した。 これにより、凸緩和の解法に依存しない単純な線形時間古典近似アルゴリズムが得られる。 また、反強磁性逆場イジングモデルと等価であるVertex Coverの非拘束量子局所ハミルトンバージョン上で、我々の量子局所比法を実証する。

関連論文リスト

• 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)
• Hybrid Quantum-Classical Multilevel Approach for Maximum Cuts on Graphs [1.7720089167719628]
  我々は、Max-Cutの大規模インスタンスを解決するために、スケーラブルなハイブリッドマルチレベルアプローチを導入する。 フレームワークでのQAOAの使用は、古典的なアプローチに匹敵するものであることを示す。
  論文  参考訳（メタデータ） (2023-09-15T23:54:46Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• Lower bounds for adiabatic quantum algorithms by quantum speed limits [0.0]
  本稿では,アディバティック量子アルゴリズムのランタイム上での下位境界を推定するためのフレームワークを提案する。 ランダムグラフにおけるk-cliqueを求めるためのアディバティックアルゴリズムの下位境界を解析的に取得する。
  論文  参考訳（メタデータ） (2022-07-04T17:36:58Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems [3.553493344868414]
  k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の一般化である 極大絡み合いのインスタンスである厳密な二次インスタンスに対しては、古典的な 0.764 時間 0.764 近似を提供する。 これらは近似するのが最も難しい例であると推測する。 我々の研究は、最近開発されたCSPの古典近似解析技術を採用しており、量子情報科学者と古典計算機科学者の両方にアクセスできることを意図している。
  論文  参考訳（メタデータ） (2020-12-22T20:41:34Z)
• Quantum Assisted Eigensolver [0.0]
  本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。 アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
  論文  参考訳（メタデータ） (2020-09-23T08:33:18Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。 我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。 論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-12T16:44:27Z)

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

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