論文の概要: A complexity phase transition at the EPR Hamiltonian

• arxiv url: http://arxiv.org/abs/2604.13026v1
• Date: Tue, 14 Apr 2026 17:57:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 19:11:32.603987
• Title: A complexity phase transition at the EPR Hamiltonian
• Title（参考訳）: EPRハミルトニアンにおける複雑性相転移
• Authors: Kunal Marwaha, James Sud,
• Abstract要約: 正重対称相互作用項によって生成される2-局所ハミルトン問題の計算複雑性について検討する。 これらの問題は、QMA完全(英語版)、StoqMA完全(英語版)完全(英語版)完全(英語版)、EPR*と呼ばれる新しい問題に再現可能な3つの複雑性フェーズのうちの1つに属することを示す。
• 参考スコア（独自算出の注目度）: 0.11458853556386796
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the computational complexity of 2-local Hamiltonian problems generated by a positive-weight symmetric interaction term, encompassing many canonical problems in statistical mechanics and optimization. We show these problems belong to one of three complexity phases: QMA-complete, StoqMA-complete, and reducible to a new problem we call EPR*. The phases are physically interpretable, corresponding to the energy level ordering of the local term. The EPR* problem is a simple generalization of the EPR problem of King. Inspired by empirically efficient algorithms for EPR, we conjecture that EPR* is in BPP. If true, this would complete the complexity classification of these problems, and imply EPR* is the transition point between easy and hard local Hamiltonians. Our proofs rely on perturbative gadgets. One simple gadget, when recursed, induces a renormalization-group-like flow on the space of local interaction terms. This gives the correct complexity picture, but does not run in polynomial time. To overcome this, we design a gadget based on a large spin chain, which we analyze via the Jordan-Wigner transformation.
• Abstract（参考訳）: 正重対称相互作用項によって生じる2-局所ハミルトン問題の計算複雑性について検討し、統計力学および最適化における多くの正準問題を含む。 これらの問題は、QMA完全(英語版)、StoqMA完全(英語版)完全(英語版)完全(英語版)、EPR*と呼ばれる新しい問題に再現可能な3つの複雑性フェーズのうちの1つに属することを示す。 位相は物理的に解釈可能であり、局所項のエネルギー準位に対応する。 EPR*問題はキングのEPR問題の単純な一般化である。 EPRのアルゴリズムに触発されて、EPR* は BPP に含まれると推測する。 もしそうなら、これはこれらの問題の複雑さの分類を完了し、EPR* は容易かつハードな局所ハミルトン群の間の遷移点であることを意味する。 我々の証明は摂動ガジェットに依存している。 1つの単純なガジェットは、再帰すると局所的な相互作用項の空間上の正規化のような流れを誘導する。 これは正確な複雑性図式を与えるが、多項式時間では実行されない。 これを解決するために、我々はJordan-Wigner変換を用いて解析する大きなスピンチェーンに基づくガジェットを設計する。

関連論文リスト

• Generalizable Reasoning through Compositional Energy Minimization [91.76056742068813]
  一般化は機械学習、特に推論タスクにおいて重要な課題である。 より小さく、よりトラクタブルなサブプロブレムの解空間上のエネルギーランドスケープを学習することで一般化を推論する新しい手法を提案する。 提案手法は既存の最先端手法よりも優れており,より大規模で複雑な問題に一般化できることを示す。
  論文  参考訳（メタデータ） (2025-10-23T14:38:36Z)
• Fast attention mechanisms: a tale of parallelism [52.7657529272906]
  準四分法的時間複雑性を有する近似近傍注意(ANNA)という,効率的な注意機構を導入する。 我々は,ANNA変換器が従来確立されていた表現力を維持し,MPCアルゴリズムの能力に適合することを示す。
  論文  参考訳（メタデータ） (2025-09-10T20:59:44Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Circuit complexity and functionality: a thermodynamic perspective [2.2988732018837177]
  機能等価回路における複雑性と熱力学の関係について検討する。 特に、我々のフレームワークは任意の長さのプログラムの難読化に関する新しい視点を提供する。 我々は、複雑性クラス NP と coNP が一致しない限り、断片化は避けられないと主張する。
  論文  参考訳（メタデータ） (2023-09-11T18:02:21Z)
• Circuit Complexity through phase transitions: consequences in quantum state preparation [0.0]
  量子多体系の基底状態を作成するための回路の複雑さを解析する。 特に、基底状態が量子相転移に近づくにつれて、この複雑さがどのように成長するか。
  論文  参考訳（メタデータ） (2023-01-11T19:00:10Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Relevant OTOC operators: footprints of the classical dynamics [68.8204255655161]
  OTOC-RE定理(OTOC-RE theorem)は、作用素の完備な基底にまとめられたOTOCを第二レニイエントロピー(Renyi entropy)に関連付ける定理である。 関係作用素の小さな集合に対する和は、エントロピーの非常によい近似を得るのに十分であることを示す。 逆に、これは複雑性の別の自然な指標、すなわち時間と関連する演算子の数のスケーリングを提供する。
  論文  参考訳（メタデータ） (2020-07-31T19:23:26Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)
• Aspects of The First Law of Complexity [0.0]
  我々は、arXiv:1903.04511で提案される最初の複雑性の法則、すなわち、ターゲット状態が摂動した際の複雑性の変動について検討する。 Nielsenの量子回路複雑性に対する幾何学的アプローチに基づいて、変動は最適回路の端にのみ依存する。
  論文  参考訳（メタデータ） (2020-02-13T21:15:57Z)

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

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