論文の概要: Computational complexity of the homology problem with orientable filtration: MA-completeness

• arxiv url: http://arxiv.org/abs/2510.07014v1
• Date: Wed, 08 Oct 2025 13:40:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.519065
• Title: Computational complexity of the homology problem with orientable filtration: MA-completeness
• Title（参考訳）: 配向フィルターによるホモロジー問題の計算複雑性:MA完全性
• Authors: Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad, Vedran Dunjko,
• Abstract要約: 単体錯体のある種のサブクラスに対して、MA完全ホモロジー問題が存在することを示す。 この問題は、単純錯体の配向性という新しい概念によって定義される。 そこで我々は,MA硬化型確率満足度問題から低減できる新しいガジェットを設計する。
• 参考スコア（独自算出の注目度）: 3.173215823388563
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show the existence of an MA-complete homology problem for a certain subclass of simplicial complexes. The problem is defined through a new concept of orientability of simplicial complexes that we call a "uniform orientable filtration", which is related to sign-problem freeness in homology. The containment in MA is achieved through the design of new, higher-order random walks on simplicial complexes associated with the filtration. For the MA-hardness, we design a new gadget with which we can reduce from an MA-hard stoquastic satisfiability problem. Therefore, our result provides the first natural MA-complete problem for higher-order random walks on simplicial complexes, combining the concepts of topology, persistent homology, and quantum computing.
• Abstract（参考訳）: 単体錯体のある種のサブクラスに対して、MA完全ホモロジー問題が存在することを示す。 この問題は、ホモロジーにおける符号-確率自由性に関連する「一様オリエンタブルフィルター」と呼ばれる、単体複体のオリエンタビリティという新しい概念によって定義される。 MAの包含は、濾過に関連する単純錯体上の新しい高次ランダムウォークの設計によって達成される。 そこで我々は,MA硬化型確率満足度問題から低減できる新しいガジェットを設計する。 したがって、この結果は、トポロジー、永続ホモロジー、量子コンピューティングの概念を組み合わせることで、単純複体上の高階ランダムウォークに対する最初の自然なMA完全問題を与える。

関連論文リスト

• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。 思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。 SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
  論文  参考訳（メタデータ） (2025-04-13T13:35:41Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  量子グラフに対するclique問題を紹介し,研究する。 我々のアプローチは量子グラフと量子チャネルの間のよく知られた接続を利用する。 全てのチャネルで量子化され、QMA(2)ではこの問題が完備であることを示す。 また、QMA(k) を QMA(2) に減少させる新たな証拠を与える。
  論文  参考訳（メタデータ） (2023-09-22T14:20:14Z)
• Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
  我々は、ユニタリティ制約の研究に現代の機械学習技術を適用した。 我々は、そのような解に対する既知の限界を以前の境界を超えるような新しい位相あいまいな解を求める。
  論文  参考訳（メタデータ） (2023-08-18T10:29:26Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Clique Homology is QMA1-hard [0.0]
  simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
  論文  参考訳（メタデータ） (2022-09-23T18:14:16Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。 我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。 特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
  論文  参考訳（メタデータ） (2022-04-11T14:11:24Z)
• Complex matter field universal models with optimal scaling for solving combinatorial optimization problems [0.0]
  我々は、多くの実生活NP-ハード最適化問題の最適マッピングを可能にする普遍モデルを開発する。 グラフカラー化、旅行セールスマン、モジュラーN-クエンス問題という3つの有名な問題に対して、1対1のマッピングを明示的に定式化する。
  論文  参考訳（メタデータ） (2022-01-18T21:53:47Z)
• Complexity continuum within Ising formulation of NP problems [0.0]
  イジング・ハミルトニアンの最小化は、ある相互作用行列類に対するNPハード問題であることが知られている。 我々は、最適化単純度基準で計算学的に単純なインスタンスを特定することを提案する。 このような単純さはスピングラスからk規則の最大カット問題まで幅広いモデルで見られる。
  論文  参考訳（メタデータ） (2020-08-02T11:36:38Z)
• Complex Markov Logic Networks: Expressivity and Liftability [10.635097939284751]
  マルコフ論理ネットワーク(MLN)の表現性について検討する。 複素数値重みを用いた複素MLNを導入する。 実数値重みを持つ標準MLNとは異なり、複素MLNは完全に表現可能であることを示す。
  論文  参考訳（メタデータ） (2020-02-24T13:50:59Z)

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

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