論文の概要: Existence and nonexistence of commutativity gadgets for entangled CSPs

• arxiv url: http://arxiv.org/abs/2509.07835v1
• Date: Tue, 09 Sep 2025 15:11:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-10 14:38:27.372159
• Title: Existence and nonexistence of commutativity gadgets for entangled CSPs
• Title（参考訳）: 絡み合ったCSP用可換ガジェットの存在と非存在
• Authors: Eric Culf, Josse van Dobben de Bruyn, Matthijs Vernooij, Peter Zeman,
• Abstract要約: 我々は、可換性ガジェットの存在に対する最初の既知の障害を証明した。 我々は,非ローカルゲームとして$k$-colouringを提示するための可換性ガジェットを構築した。 また, オーラキュラ可換性ガジェットの存在は, グラフの分類力の下で保存されていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSPs. This has been done, for instance, for NP-complete boolean CSPs and 3-colouring in the work of Culf and Mastel. For many CSPs over larger alphabets, including $k$-colouring when $k \geq 4$, it is not known whether or not commutativity gadgets exist, or if the entangled CSP is decidable. In this paper, we study commutativity gadgets and prove the first known obstruction to their existence. We do this by extending the definition of the quantum automorphism group of a graph to the quantum endomorphism monoid of a CSP, and showing that a CSP with non-classical quantum endomorphism monoid does not admit a commutativity gadget. In particular, this shows that no commutativity gadget exists for $k$-colouring when $k \geq 4$. However, we construct a commutativity gadget for an alternate way of presenting $k$-colouring as a nonlocal game, the oracular setting. Furthermore, we prove an easy to check sufficient condition for the quantum endomorphism monoid to be non-classical, extending a result of Schmidt for the quantum automorphism group of a graph, and use this to give examples of CSPs that do not admit a commutativity gadget. We also show that existence of oracular commutativity gadgets is preserved under categorical powers of graphs; existence of commutativity gadgets and oracular commutativity gadgets is equivalent for graphs with no four-cycle; and that the odd cycles and the odd graphs have a commutative quantum endomorphism monoid, leaving open the possibility that they might admit a commutativity gadget.
• Abstract（参考訳）: 通信機器は、古典的制約満足度問題(CSP)に対するNP硬度証明を、対応する絡み合ったCSPに対する不確定性証明に渡すことができる。 例えば、NP完全ブール CSP や、Culf と Mastel の業績における3色の色付けなどである。 例えば$k \geq 4$のときの$k$-colouringなど、大きなアルファベット上の多くのCSPでは、可換性ガジェットが存在するかどうか、あるいは絡み合ったCSPが決定可能であるかどうかは不明である。 本稿では,可換性ガジェットについて検討し,その存在を初めて実証する。 我々は、グラフの量子自己同型群の定義を CSP の量子自己同型モノイドに拡張し、非古典的量子自己同型モノイドを持つ CSP が可換ガジェットを含まないことを示す。 特に、$k \geq 4$ の場合、$k$-colouring の可換ガジェットは存在しない。 しかし,本研究では,非局所ゲームであるオラクレ設定として$k$-colouringを代替的に提示するための可換性ガジェットを構築した。 さらに、グラフの量子自己同型群に対するシュミットの結果を拡張して、量子自己同型モノイドが古典的でないことの十分な条件を証明し、これを用いて可換性ガジェットを含まないCSPの例を示す。 また, 4サイクルのないグラフに対して, 可換性ガジェットやオーラル可換性ガジェットの存在は等価であり, 奇数サイクルと奇数グラフは可換性量子自己準同型モノイドを有しており, 可換性ガジェットを許容する可能性を秘めていることを示す。

関連論文リスト

• Homomorphism Indistinguishability Relations induced by Quantum Groups [0.23020018305241333]
  準同型不変性(英:homomorphism indistinguishability)は、グラフ上の多くの自然同値関係を特徴づける方法である。 我々は、Manvcinska と Roberson の結果をすべての簡単な量子群に一般化する。
  論文  参考訳（メタデータ） (2025-05-12T16:58:51Z)
• On the Quantum Chromatic Gap [1.90365714903665]
  我々は、Khotの$d$-to-$1$ Games Conjectureの量子擬似テレパシーバージョンを作成した。 ある種の擬テレパシーXORゲームの存在は、この予想を暗示することを示している。 Dinur-Khot--Kindler--Minzer--Safraは、最近2ドルから2ドルというゲーム定理が量子完備であることを証明した。
  論文  参考訳（メタデータ） (2025-03-29T20:10:34Z)
• A Criterion for Quantum Advantage [0.0]
  非ユニバーサルゲート集合上の均一かつ大きさの量子回路が効率よくシミュレートできないことを証明した。 我々の結果は、(Udagger otimes Udagger) MathrmU(2)$以上の回路は量子的に有利であることを示している。
  論文  参考訳（メタデータ） (2024-11-04T18:38:43Z)
• Quantum Current and Holographic Categorical Symmetry [62.07387569558919]
  量子電流は、任意の長距離にわたって対称性電荷を輸送できる対称作用素として定義される。 超伝導である量子電流の条件も規定されており、これは1つの高次元のエノンの凝縮に対応する。
  論文  参考訳（メタデータ） (2023-05-22T11:00:25Z)
• Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint [0.0]
  グラフ準同型(Graph homomorphism)は、$mathcalF$ と $mathcalF'$ のそれぞれが 1 つの対称な 0-1 値のバイナリ制約関数を含む特別な場合である。 任意のペアの集合 $mathcalF$ と $mathcalF'$ は、任意の平面#CSPインスタンスに同じ値を与える実数値で任意のアリティ制約関数を示す。
  論文  参考訳（メタデータ） (2022-12-06T21:38:40Z)
• Non-Abelian symmetry can increase entanglement entropy [62.997667081978825]
  代用電荷の非可換化がページ曲線に及ぼす影響を定量化する。 非可換電荷の場合の方が絡み合いが大きいことを解析的および数値的に示す。
  論文  参考訳（メタデータ） (2022-09-28T18:00:00Z)
• A New Look at the $C^{0}$-formulation of the Strong Cosmic Censorship Conjecture [68.8204255655161]
  我々は、アインシュタイン方程式の初期条件としての一般ブラックホールパラメータに対して、計量はより大きなローレンツ多様体に対して$C0$-extendableであると主張する。 我々は、温度の低い双曲型AdS$_d+1$ブラックホールと、(d-1$)次元の双曲型H_d-1$のCFTとの「複雑=体積」予想に反することを示した。
  論文  参考訳（メタデータ） (2022-06-17T12:14:33Z)
• Sub-bosonic (deformed) ladder operators [62.997667081978825]
  ファジィネスという厳密な概念から派生した変形生成および消滅作用素のクラスを提示する。 これにより変形し、ボゾン準可換関係は、修正された退化エネルギーとフォック状態を持つ単純な代数構造を誘導する。 さらに、量子論において導入された形式論がもたらす可能性について、例えば、自由準ボソンの分散関係における線型性からの偏差について検討する。
  論文  参考訳（メタデータ） (2020-09-10T20:53:58Z)

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

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