論文の概要: k-partite quantum homomorphisms
- arxiv url: http://arxiv.org/abs/2611.15839v1
- Date: Wed, 11 Nov 2026 18:50:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.254394
- Title: k-partite quantum homomorphisms
- Title(参考訳): k-パーティト量子準同型
- Abstract要約: 我々は$k$-partite準同型ゲームを導入し、$k$-XORのゲームを線形システムから任意のリレーショナル構造へ拡張する。
我々は、完全古典的戦略を持たない完全量子戦略の存在という、擬テレパシー的な意味での量子優位性について研究する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: $k$-partite XOR games and linear binary constraint system (BCS) games arise from systems of linear equations over $\mathbb{Z}_2$, providing distinct quantum relaxations of the same classical constraint satisfaction problem (CSP). Linear BCS games have been generalised to synchronous homomorphism games on arbitrary relational structures, with compositional semantics provided by the quantum monad. We introduce $k$-partite homomorphism games, extending $k$-XOR games from linear systems to arbitrary relational structures. This yields a framework for studying multipartite quantum CSPs and quantum homomorphisms. We characterise perfect strategies in both the tensor-product and commuting-operator models as Kleisli morphisms of suitable state-dependent graded quantum monads on a category of $k$-partite relational structures. We then study quantum advantage in the pseudotelepathic sense: the existence of a perfect quantum strategy without a perfect classical strategy. We show that synchronous and $k$-partite quantum advantage are incomparable at the level of CSP instances. The GHZ instance admits three-player quantum advantage but no synchronous commuting-operator advantage, whereas the magic-square instance admits synchronous quantum advantage but no $k$-partite commuting-operator advantage for any number of players or proper colouring. We also exhibit an explicit six-element template whose CSP is NP-complete and admits two-player quantum advantage. Finally, we prove that no bounded-width CSP template admits $k$-partite quantum advantage, even in the commuting-operator model.
- Abstract(参考訳): $k$-partite XOR ゲームと線形二項制約系 (BCS) ゲームは$\mathbb{Z}_2$ 上の線形方程式の系から生じ、同じ古典的制約満足問題 (CSP) の量子緩和を与える。
線形BCSゲームは、任意の関係構造上の同期準同型ゲームに一般化され、量子モナドによって構成的意味論が提供される。
我々は$k$-partite準同型ゲームを導入し、$k$-XORのゲームを線形システムから任意のリレーショナル構造へ拡張する。
これは多部量子 CSP と量子準同型を研究するための枠組みをもたらす。
テンソル積および可換作用素モデルの両方において完全戦略を、$k$-パーティイト関係構造の圏上の適切な状態依存次数量子モナドのKleisli準同型として特徴づける。
次に、擬テレパシー的な意味での量子優位性(完全古典的戦略を持たない完全量子戦略の存在)について研究する。
同期および$k$-partite量子アドバンテージは、CSPインスタンスのレベルでは比較不可能であることを示す。
GHZインスタンスは3つのプレイヤーの量子アドバンテージを認めるが、同期型通勤演算のアドバンテージはないが、マジックスクエアインスタンスは同期型量子アドバンテージを認めるが、任意の数のプレイヤーや適切な色付けに対して$k$パーティト通勤演算のアドバンテージは認めない。
また,CSPがNP完全で2プレーヤの量子優位性を有する明示的な6要素テンプレートも提示した。
最後に、有界幅CSPテンプレートが、通勤演算モデルにおいても、$k$-partite量子優位性を認めないことを証明する。
関連論文リスト
- Quantum non-local games: Quantum relations, projection lattices and rule operators [51.56484100374058]
(mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。
(mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。
(mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。
(mathcal R)-射影テスト 有限次元入力とノイマン代数の出力を持つ量子ゲーム。
論文 参考訳(メタデータ) (2026-08-31T09:41:14Z) - Quantum Polymorphisms and Commutativity Gadgets [2.8726155411976535]
我々は,リレーショナル構造のための可換性ガジェットの存在の完全な特徴付けを行う。
奇数サイクルによってパラメータ化される絡み合ったCSPは決定不可能であることを示す。
非分子量子準同型の場合、絡み合ったCSPに対するガロア接続の量子バージョンを確立する。
論文 参考訳(メタデータ) (2025-11-28T18:37:36Z) - Bounding the asymptotic quantum value of all multipartite compiled non-local games [0.27998963147546146]
非局所ゲームは、古典的な世界と量子世界の相関関係を区別するための強力なツールである。
Kalai et al. (STOC'23) は、マルチパート非ローカルなゲームを1つの証明子でインタラクティブなプロトコルに変換するコンパイラを提案した。
我々は、Kalai et al. のコンパイラが、実際にはすべてのマルチパーティライト非局所ゲームに対して量子音性を達成することを証明した。
論文 参考訳(メタデータ) (2025-07-16T16:58:39Z) - A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
暗号コンパイラは、任意の非ローカルゲームを単一の計算バウンド証明器で対話的プロトコルに変換する。
我々は、コンパイルされた2人プレイヤの非ローカルゲームに対して量子音響結果を確立する。
論文 参考訳(メタデータ) (2024-08-13T08:11:56Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳(メタデータ) (2023-11-17T20:38:38Z) - Synchronicity for quantum non-local games [0.7646713951724009]
量子グラフの量子準同型(quantum homomorphisms of quantum graphs)は、そのグラフの古典的準同型(classical homomorphisms of the graphs)とみなすことができる。
量子グラフ準同型ゲームにおける完全量子交換と完全近似量子戦略について記述する。
論文 参考訳(メタデータ) (2021-06-22T02:40:41Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳(メタデータ) (2021-06-11T18:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。