論文の概要: Satisfiability of commutative vs. non-commutative CSPs
- arxiv url: http://arxiv.org/abs/2404.11709v1
- Date: Wed, 17 Apr 2024 19:26:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-19 13:40:17.435360
- Title: Satisfiability of commutative vs. non-commutative CSPs
- Title(参考訳): 可換性対非可換性CSPの満足度
- Authors: Andrei A. Bulatov, Stanislav Živný,
- Abstract要約: マーミン・ペレスのマジック正方形は(古典的には)満足できないが、次元 4 のヒルベルト空間上の線型作用素によって満足できるブール線型方程式のシステムの有名な例である。
2-SAT, Horn-SAT, Dual Horn-SAT の場合、古典的満足度と演算子満足度は同じであり、ギャップがないことを示す。
それらの結果を任意の有限領域上の CSP に一般化する。
- 参考スコア(独自算出の注目度): 2.07180164747172
- License: http://creativecommons.org/licenses/by/4.0/
- 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 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, the two notions differ as there is a gap, i.e., there are unsatisfiable instances that are satisfied via operators on a finite-dimensional Hilbert space. We generalize their result to CSPs on arbitrary finite domains: CSPs of so-called bounded-width have no satisfiability gap, whereas all other CSPs have a satisfiability gap.
- Abstract(参考訳): マーミン・ペレスのマジック正方形は(古典的には)満足できないが、次元 4 のヒルベルト空間上の線型作用素によって満足できるブール線型方程式のシステムの有名な例である。
自然の疑問は、そのような現象がどんな問題を引き起こすのかということだ。
Atserias, Kolaitis, and Severini はすべてのブール制約満足問題 (CSPs): 2-SAT, Horn-SAT, Dual Horn-SAT に対し、古典的満足度と作用素の満足度は同じであり、ギャップがない。
これらの結果を任意の有限領域上の CSP に一般化する: いわゆる有界幅の CSP は満足性ギャップを持たないが、他のすべての CSP は満足性ギャップを持つ。
関連論文リスト
- Some consequences of Sica's approach to Bell's inequalities [65.268245109828]
ルイ・シカ(Louis Sica)は、ベルの不等式を、あるステーションで観測された結果の時系列が、他のステーションの設定が変更された場合に変化しないという単純な仮説から導いた。
この導出は算術的性質のみに基づいている。
局所性とリアリズムの議論を巻き起こす定義は含まないが、確率の定義は必要とせず、任意の長さの連続に対して有効である。
論文 参考訳(メタデータ) (2024-03-05T13:59:52Z) - Approximation algorithms for noncommutative constraint satisfaction
problems [0.0]
我々は制約満足度問題(CSP)の作用素、あるいは非可換変量について研究する。
非可換なCSPに対する近似アルゴリズムを設計するためのフレームワークを提案する。
この研究は、より広い非可換 CSP のクラスに対する近似比を確立する最初のものである。
論文 参考訳(メタデータ) (2023-12-28T01:22:27Z) - Approximation of optimization problems with constraints through kernel
Sum-Of-Squares [77.27820145069515]
我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。
また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
論文 参考訳(メタデータ) (2023-01-16T10:30:04Z) - 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) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳(メタデータ) (2022-03-11T17:19:26Z) - Many-Qudit representation for the Travelling Salesman Problem
Optimisation [0.0]
本稿では、旅行セールスマン問題(TSP)から、多くのクイディットのシステムに関連する基底状態へのマップを提案する。
提案手法はヒルベルト空間が2NlogN$の多量子系を提供するが、これはQUBO写像から得られる系の寸法よりもかなり小さい。
この削減は量子コンピュータや古典コンピュータにおいて大きなスピードアップをもたらす可能性がある。
論文 参考訳(メタデータ) (2021-02-26T04:14:27Z) - A gauge redundancy-free formulation of compact QED with dynamical matter
for quantum and classical computations [0.0]
本稿では,2次元および3次元空間格子上での動的物質を用いたコンパクト量子電磁力学の表現法を紹介する。
物体がゲージ制約から切り離された回転フレームに変換することで、双対作用素の観点でゲージ場作用素を表現できる。
論文 参考訳(メタデータ) (2020-08-04T06:04:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。