論文の概要: An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

• arxiv url: http://arxiv.org/abs/2412.19623v1
• Date: Fri, 27 Dec 2024 12:57:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:24:57.383320
• Title: An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
• Title（参考訳）: 非ホリートリニティ:TFNP、多項式系、および量子充足可能性問題
• Authors: Marco Aldi, Sevag Gharibian, Dorian Rudolph,
• Abstract要約: 複素系の研究に基づいて, 完全関数NP (TFNP) の2つの新しいサブクラスを定義する。 我々の研究の中心は、SDR(System of Distinct Representatives)を用いた量子SAT(Quantum SAT)として知られる計算問題である。 本稿では, SFTA がゼロエラー版 SDR に含まれることから, 疎度・高次複雑さの根源を SDR で QSAT に埋め込む方法を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on B\'ezout's theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, L\"auchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA is contained in MHS.
• Abstract（参考訳）: トータル関数NP(TFNP)とそのサブクラスの理論は、問題に対して効率的に検証可能な証明が存在することを約束されているとしても、この証明は難解である。 ブローワーの不動点やナッシュ平衡のような問題の難解性を示す理論が成功したにもかかわらず、TFNPのサブクラスは間違いなく少ない。 本研究では、複素多項式系の研究に基礎を置く2つの新しいサブクラス、MHS(Multi-homogeneous Systems)とSFTA(Sparse Fundamental Theorem of Algebra)を定義する。 そのうちの1つは、代数幾何学のB\'ezoutの定理に基づいており、代数幾何学の原理に基づく最初のTFNPサブクラスである。 本研究の核心は量子SAT(Quantum SAT, QSAT)と呼ばれる固有代表系(SDR)の計算問題であり, [Laumann, L\"auchli, Moessner, Scardicchio, Sondhi 2010] が最初に研究した。 以上の結果から,量子複雑性理論とTFNPとの最初のリンクを与えるだけでなく,古典的変法(SAT with SDR)が簡単であるが量子的変法が難しい最初のTFNP問題となる。 また,SDRを用いたQSATに,疎度・高次・一変量多項式の根を埋め込む方法を示し,SFTAがMHSのゼロエラーバージョンに含まれることを示す。 我々は、この構造は低エラー設定でも機能し、これは、SFTAがMHSに含まれることを意味する。

関連論文リスト

• A unified approach to quantum de Finetti theorems and SoS rounding via geometric quantization [0.0]
  我々は、量子デ・フィネッティの定理に関連するSOS階層のエルミート版の間の関係について研究する。 従来のHSoSラウンドリングアルゴリズムは,対象関数の定量化として再キャスト可能であることを示す。
  論文  参考訳（メタデータ） (2024-11-06T17:09:28Z)
• Bosonic Quantum Computational Complexity [0.0]
  私たちはそのような研究計画の基礎をつくった。 本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。 ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-05T19:43:41Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem [14.693394941317843]
  本稿では,ブール充足可能性解法と計算機代数システムを組み合わせた検証可能な新しい証明生成法を提案する。 提案手法は、3次元のKS系が少なくとも24個のベクトルを含む必要があることを示す。 また, KS問題に対して, 順序23の40.3 TiBの低い値のコンピュータ検証証明を初めて提供した。
  論文  参考訳（メタデータ） (2023-06-23T06:42:59Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• TheoremQA: A Theorem-driven Question Answering dataset [100.39878559382694]
  GPT-4のこれらの問題を解決する能力は非並列であり、Program-of-Thoughts Promptingの精度は51%である。 TheoremQAは、350の定理をカバーする800の高品質な質問を含むドメインの専門家によってキュレートされる。
  論文  参考訳（メタデータ） (2023-05-21T17:51:35Z)
• T-SciQ: Teaching Multimodal Chain-of-Thought Reasoning via Mixed Large Language Model Signals for Science Question Answering [59.63860993280275]
  大規模言語モデル(LLM)は、様々な自然言語処理(NLP)タスクにおいて例外的な性能を示した。 LLM信号を用いた科学質問応答の指導を目的とした,T-SciQと呼ばれる新しい手法を提案する。 提案手法は,ScienceQAベンチマークで96.18%の精度で,最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2023-05-05T11:56:30Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。 これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。 我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
  論文  参考訳（メタデータ） (2022-10-12T03:01:00Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)

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

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