論文の概要: Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems

• arxiv url: http://arxiv.org/abs/2012.12347v1
• Date: Tue, 22 Dec 2020 20:41:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-19 21:46:59.331632
• Title: Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems
• Title（参考訳）: 量子2局所ハミルトニアン問題の近似のためのビーティングランダムアサインメント
• Authors: Ojas Parekh and Kevin Thompson
• Abstract要約: k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の一般化である 極大絡み合いのインスタンスである厳密な二次インスタンスに対しては、古典的な 0.764 時間 0.764 近似を提供する。 これらは近似するのが最も難しい例であると推測する。 我々の研究は、最近開発されたCSPの古典近似解析技術を採用しており、量子情報科学者と古典計算機科学者の両方にアクセスできることを意図している。
• 参考スコア（独自算出の注目度）: 3.553493344868414
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
• Abstract（参考訳）: 量子k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の自然な一般化であり、NPの量子アナログであるQMAに対して完備である。 k-ローカルハミルトニアン問題の複雑さはよく研究されているが、近似結果はほとんど知られていない。 各項がランク3プロジェクターであるマックス2-局所ハミルトニアンにとって、古典マックス2-SATの自然な量子一般化は、最もよく知られた近似アルゴリズムは自明なランダム代入であり、0.75近似となる。 この境界を破る最初の近似アルゴリズム, 古典多項式時間 0.764 近似法を提案する。 厳密な二次的なインスタンスは、最大絡み合いのインスタンスであり、0.801近似アルゴリズムを提供し、我々のアルゴリズムが0.821近似である可能性を数値的に証明する。 これらを近似する最も難しい例と推測する。 また、他の関連する古典的2-CSPの量子一般化の近似も改善した。 最後に、Grothendieck問題の一般化への量子接続を利用して、2部相互作用グラフ上の厳密な二次トレースレス2-ローカルハミルトニアン(英語版)の物理的特殊ケースに対して古典的な定数係数近似を得る。 本研究は,cspsの古典近似を解析するための最近の手法を用いており,量子情報科学者と古典計算機科学者の両方が利用できることを意図している。

関連論文リスト

• 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)
• Constrained local Hamiltonians: quantum generalizations of Vertex Cover [0.8056359341994941]
  我々は、よく研究された古典的頂点被覆問題をインスピレーションとして、制約付き局所ハミルトン問題に対する近似アルゴリズムについて研究する。 我々は,TVCがStoqMAハードであることを示し,古典的局所比法を量子一般化した近似アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-09-06T17:55:30Z)
• 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)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
  NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。 ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。 近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
  論文  参考訳（メタデータ） (2023-12-11T04:15:55Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• On the complexity of quantum partition functions [2.6937287784482313]
  局所ハミルトニアンの近似量の計算複雑性について検討する。 $mathrmpoly(n)$ の古典的アルゴリズムは与えられた 2$-局所ハミルトニアンの自由エネルギーを近似する。
  論文  参考訳（メタデータ） (2021-10-29T00:05:25Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Quantum Assisted Eigensolver [0.0]
  本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。 アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
  論文  参考訳（メタデータ） (2020-09-23T08:33:18Z)

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

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