論文の概要: Clique Homology is QMA1-hard

• arxiv url: http://arxiv.org/abs/2209.11793v1
• Date: Fri, 23 Sep 2022 18:14:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-25 09:58:13.061751
• Title: Clique Homology is QMA1-hard
• Title（参考訳）: Clique Homology は QMA1-hard である
• Authors: Marcos Crichigno and Tamara Kohler
• Abstract要約: simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We tackle the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch 20 years ago. We show that this decision problem is QMA1-hard. Moreover, we show that a version of the problem satisfying a suitable promise and certain constraints is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we are able to significantly strengthen this by showing that the problem remains QMA1-hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and homological algebra. We discuss potential implications for the problem of quantum advantage in topological data analysis.
• Abstract（参考訳）: 20年前にkaibel と pfetsch が提唱した計算トポロジーの基本課題である単純複体のホモロジー群を決定する計算複雑性に関する長年の疑問に挑戦する。 この決定問題はQMA1-hardである。 さらに,問題のバージョンが適切な約束を満足し,一定の制約がQMAに含まれることを示す。 これは、一見古典的な問題は実際には量子力学であることを示唆している。 実際、この問題は、トポロジカルデータ解析の問題に関連するグラフによって定義された単体錯体の族であるクリッド錯体の場合、QMA1-ハードのままであることを示すことで、これを著しく強化することができる。 この証明はハミルトン複雑性とホモロジー代数の多くの技法を組み合わせたものである。 トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。

関連論文リスト

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。 複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。 我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
  論文  参考訳（メタデータ） (2024-11-06T07:29:52Z)
• Quantum computing and persistence in topological data analysis [41.16650228588075]
  トポロジカルデータ解析(TDA)は、そのトポロジにおけるホールの数と持続性を調べることによって、データセットからノイズ・ロバストの特徴を抽出することを目的としている。 TDAのコアタスクと密接に関連する計算問題は$mathsfBQP_1$-hardであり、$mathsfBQP$に含まれることを示す。 我々のアプローチは、誘導されたスパースハミルトニアン問題(英語版)の変種における穴の永続化を符号化することに依存している。
  論文  参考訳（メタデータ） (2024-10-28T17:54:43Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。 複雑性は量子複雑性クラスによって特徴づけられる。 我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
  論文  参考訳（メタデータ） (2023-11-28T21:15:30Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum Parameterized Complexity [1.01129133945787]
  パラメータ化複雑性クラスの範囲の量子アナログを導入する。 このフレームワークは、QMAハード問題のパラメータ化バージョンの複雑さの豊富な分類を公開している。
  論文  参考訳（メタデータ） (2022-03-15T15:34:38Z)
• Simultaneous Stoquasticity [0.0]
  確率ハミルトニアンは、局所ハミルトニアン問題の計算複雑性において重要な役割を果たしている。 2つ以上のハミルトニアンがユニタリ変換によって同時に確率的になるかどうかという問題に対処する。
  論文  参考訳（メタデータ） (2022-02-17T19:08:30Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。 これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
  論文  参考訳（メタデータ） (2021-06-30T18:00:01Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。 ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。 この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
  論文  参考訳（メタデータ） (2020-08-03T18:00:05Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)
• Quantum computation of thermal averages in the presence of a sign problem [45.82374977939355]
  本稿では,量子コンピューティング技術の簡単なシステムの熱力学特性の研究への応用について述べる。 量子アルゴリズムがいかにしてこの問題を完全に解決するかを示し、より複雑な物理的関心のシステムにどのように適用できるかを議論する。
  論文  参考訳（メタデータ） (2020-01-15T14:01:11Z)

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

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