論文の概要: Many bounded versions of undecidable problems are NP-hard

• arxiv url: http://arxiv.org/abs/2211.13532v2
• Date: Wed, 7 Dec 2022 15:41:58 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-18 23:00:00.710447
• Title: Many bounded versions of undecidable problems are NP-hard
• Title（参考訳）: 決定不能問題の多くの有界バージョンはNPハードである
• Authors: Andreas Klingler, Mirte van der Eyden, Sebastian Stengele, Tobias Reinhart, Gemma De las Cuevas
• Abstract要約: 有界バージョンにおけるNP硬度は、問題の縮小により容易に従うことを示す。 これにより、ポスト対応問題、行列死亡問題、到達可能性問題、タイリング問題、基底状態エネルギー問題のNP-hardnessの新たなより単純な証明が導かれる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Several physically inspired problems have been proven undecidable; examples are the spectral gap problem and the membership problem for quantum correlations. Most of these results rely on reductions from a handful of undecidable problems, such as the halting problem, the tiling problem, the Post correspondence problem or the matrix mortality problem. All these problems have a common property: they have an NP-hard bounded version. This work establishes a relation between undecidable unbounded problems and their bounded NP-hard versions. Specifically, we show that NP-hardness of a bounded version follows easily from the reduction of the unbounded problems. This leads to new and simpler proofs of the NP-hardness of bounded version of the Post correspondence problem, the matrix mortality problem, the positivity of matrix product operators, the reachability problem, the tiling problem, and the ground state energy problem. This work sheds light on the intractability of problems in theoretical physics and on the computational consequences of bounding a parameter.
• Abstract（参考訳）: 物理的にインスパイアされたいくつかの問題は決定不能であることが証明されており、例えばスペクトルギャップ問題や量子相関のメンバシップ問題がある。 これらの結果のほとんどが停止問題、タイリング問題、ポスト対応問題、行列死亡問題など、決定不能な問題のほんの一握りの削減に依存している。 これらの問題はすべて共通の性質を持ち、NPハードな有界バージョンを持つ。 この研究は、決定不能な未有界問題とその有界NPハードバージョンとの関係を確立する。 具体的には、有界バージョンにおけるNP硬度は、非有界問題の減少により容易に従うことを示す。 これにより、ポスト対応問題、行列死亡問題、行列積演算子の正当性、到達可能性問題、タイリング問題、基底状態エネルギー問題のNP硬度の新しいより単純な証明が導かれる。 この研究は、理論物理学における問題の難解性やパラメータ境界の計算結果に光を当てている。

関連論文リスト

• A Quantum Unique Games Conjecture [0.0]
  本稿では,ラベル・コーバーとユニク・ラベル・コーヴァーの量子拡張の定義を紹介する。 これらの問題は、古典的な設定で行うように、量子制約満足度問題の非近似性を研究する上でも同様に重要な役割を果たすことを示す。
  論文  参考訳（メタデータ） (2024-09-30T07:34:41Z)
• 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)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。 これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
  論文  参考訳（メタデータ） (2023-11-28T01:06:03Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。 量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか? QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
  論文  参考訳（メタデータ） (2023-09-28T13:30:20Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。 また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
  論文  参考訳（メタデータ） (2023-01-16T10:30:04Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering [13.70673475846529]
  以下の問題に対する時間量子アルゴリズムを示す。 我々の主な貢献は、LWEに似た量子状態と興味深いパラメータをフィルタリング技術を用いて解くことである。
  論文  参考訳（メタデータ） (2021-08-25T02:23:37Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more [0.0]
  量子制約問題はすべて、古典的制約問題と共有されない性質である量子ビット上で実現可能であることを示す。 結果は、量子制約問題に存在するクラスの顕著な多様性を示唆している。
  論文  参考訳（メタデータ） (2021-01-21T01:08:04Z)

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

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