論文の概要: Satisfiability of commutative vs. non-commutative CSPs

• arxiv url: http://arxiv.org/abs/2404.11709v3
• Date: Mon, 04 Nov 2024 20:10:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:55:36.829771
• Title: Satisfiability of commutative vs. non-commutative CSPs
• Title（参考訳）: 可換性対非可換性CSPの満足度
• Authors: Andrei A. Bulatov, Stanislav Živný,
• Abstract要約: NP-ハード CSP は、有限次元および無限次元ヒルベルト空間上の作用素を通して古典的満足度と満足度を分離することを示す。 また,非有界幅のトラクタブル CSP は,いかなる種類の満足感ギャップも持たないことを示した。
• 参考スコア（独自算出の注目度）: 2.07180164747172
• License:
• Abstract: The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hilbert space of dimension four. A natural question is then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis, and Severini answered this question for all Boolean Constraint Satisfaction Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual Horn-SAT, classical satisfiability and operator satisfiability is the same and thus there is no gap; for all other Boolean CSPs, these notions differ as there are gaps, i.e., there are unsatisfiable instances that are satisfiable via operators on Hilbert spaces. We generalize their result to CSPs on arbitrary finite domains and give an almost complete classification: First, we show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show that tractable CSPs of unbounded width can simulate, in a satisfiability-gap-preserving fashion, linear equations over an Abelian group of prime order $p$; for such CSPs, we obtain a separation of classical satisfiability and satisfiability via operators on infinite-dimensional Hilbert spaces. Furthermore, if $p=2$, such CSPs also have gaps separating classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces.
• Abstract（参考訳）: マーミン・ペレスのマジック正方形は(古典的には)満足できないが、次元 4 のヒルベルト空間上の線型作用素によって満足できるブール線型方程式のシステムの有名な例である。 自然の疑問は、そのような現象がどんな問題を引き起こすのかということだ。 Atserias, Kolaitis, and Severini はこの質問に答えた: 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, Dual Horn-SAT に対して、古典的満足性と作用素の満足性は同じであり、ギャップがない。 まず、NP-ハードな CSP は、有限次元および無限次元ヒルベルト空間上の作用素を通して古典的満足性と満足性の間の分離を許すことを示す。 第2に,有界幅のトラクタブル CSP は任意の種類の充足性ギャップを持たないことを示す。 最後に、有界幅のトラクタブル CSP が、無限次元ヒルベルト空間上の作用素を通して古典的満足性と満足性の分離を得るため、アベリア群上の素数$p$の線形方程式を満足度-ギャップ保存形式でシミュレートできることを示す。 さらに、$p=2$ の場合、そのような CSP はまた、有限次元および無限次元ヒルベルト空間上の作用素を通して古典的満足性と満足性を分離するギャップを持つ。

関連論文リスト

• Applying the quantum approximate optimization algorithm to general constraint satisfaction problems [0.0]
  ランダム制約満足度問題(CSP)に適用した場合に量子近似最適化(QAOA)の性能を解析するための理論的手法を開発する。 提案手法により,ランダムに生成されたCSPのインスタンスに適用した場合に,各レイヤとパラメータを用いてQAOAの成功確率を計算することができる。 ランダムな$k$-SATは、QAOAを用いた量子古典的分離を示す上で、これらのCSPの中で最も有望であると考えられる。
  論文  参考訳（メタデータ） (2024-11-26T14:00:34Z)
• RE-completeness of entangled constraint satisfaction problems [0.0]
  シェーファーの定理は、CSP言語が効率的に決定可能であるかNP完全であることを示す。 CSP言語を非局所ゲームの公式性を用いて量子代入に拡張することは可能である。
  論文  参考訳（メタデータ） (2024-10-28T17:05:58Z)
• Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz [0.0]
  線形に制約された最適化問題のクラスを解く量子交互演算子アンサッツ(QAOA$+$)を提案する。 このクラスの問題に対して、回路層数が増加するにつれて、最適解に確実に収束する回路を考案する。 この分析はQAOA$+$の性能保証を線形に制約された問題のより一般的な集合に拡張し、将来の一般化のためのツールを提供する。
  論文  参考訳（メタデータ） (2024-09-27T15:23:47Z)
• Approximation algorithms for noncommutative CSPs [0.0]
  非可換制約満足問題(NC-CSP)は古典的CSPの高次元作用素拡張である。 量子情報においてその重要性にもかかわらず、その近似性はほとんど未解明のままである。 近似等長、相対分布、および$ast$-anticommutationという3つの主要な概念を導入する。
  論文  参考訳（メタデータ） (2023-12-28T01:22:27Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。 また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
  論文  参考訳（メタデータ） (2023-01-16T10:30:04Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
  パーコレーション遷移は無限クラスターの出現によって定義される。 ヒルベルト空間の指数的に増加する次元性は、有限サイズの超球面による被覆を非効率にすることを示す。 コンパクトな距離空間におけるパーコレーション遷移への我々のアプローチは、他の文脈での厳密な処理に有用である。
  論文  参考訳（メタデータ） (2022-10-15T13:53:21Z)
• The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for Two-Dimensional Systems [62.997667081978825]
  開量子系は、FGKLS(Franke-Gorini-Kossakowski-Lindblad-Sudarshan)方程式に従うことができる。 我々はヒルベルト空間次元が 2$ である場合を徹底的に研究する。
  論文  参考訳（メタデータ） (2022-04-16T07:03:54Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。 我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
  論文  参考訳（メタデータ） (2021-10-22T15:02:39Z)
• Bistochastic operators and quantum random variables [0.0]
  正の量子乱変数である可積分関数 $Xrightarrow Mathcal B(mathcal H)$ を考える。 そのような函数の空間上の半ノルムを定義し、商がバナッハ空間に導く。 古典的偏化理論と同様に、この文脈における偏化は、ある型のすべての可能な凸函数を含む不等式と関係する。
  論文  参考訳（メタデータ） (2020-04-30T12:45:54Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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