論文の概要: Universality of graph homomorphism games and the quantum coloring
problem
- arxiv url: http://arxiv.org/abs/2305.18116v2
- Date: Mon, 10 Jul 2023 18:10:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-12 18:22:08.134880
- Title: Universality of graph homomorphism games and the quantum coloring
problem
- Title（参考訳）: グラフ準同型ゲームの普遍性と量子彩色問題
- Authors: Samuel J. Harris
- Abstract要約: 量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。
同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that quantum graph parameters for finite, simple, undirected graphs
encode winning strategies for all possible synchronous non-local games. Given a
synchronous game $\mathcal{G}=(I,O,\lambda)$ with $|I|=n$ and $|O|=k$, we
demonstrate what we call a weak $*$-equivalence between $\mathcal{G}$ and a
$3$-coloring game on a graph with at most $3+n+9n(k-2)+6|\lambda^{-1}(\{0\})|$
vertices, strengthening and simplifying work implied by Z. Ji (arXiv:1310.3794)
for winning quantum strategies for synchronous non-local games. As an
application, we obtain a quantum version of L. Lov\'{a}sz's reduction (Proc.
4th SE Conf. on Comb., Graph Theory & Computing, 1973) of the $k$-coloring
problem for a graph $G$ with $n$ vertices and $m$ edges to the $3$-coloring
problem for a graph with $3+n+9n(k-2)+6mk$ vertices. Moreover, winning
strategies for a synchronous game $\mathcal{G}$ can be transformed into winning
strategies for an associated graph coloring game, where the strategies exhibit
perfect zero knowledge for an honest verifier. We also show that, for ``graph
of the game" $X(\mathcal{G})$ associated to $\mathcal{G}$ from A. Atserias et
al (J. Comb. Theory Series B, Vol. 136, 2019), the independence number game
$\text{Hom}(K_{|I|},\overline{X(\mathcal{G})})$ is hereditarily $*$-equivalent
to $\mathcal{G}$, so that the possibility of winning strategies is the same in
both games for all models, except the game algebra. Thus, the quantum versions
of the chromatic number, independence number and clique number encode winning
strategies for all synchronous games in all quantum models.
- Abstract（参考訳）: 有限、単純、無向グラフに対する量子グラフパラメータは、すべての同期非局所ゲームに対する勝利戦略を符号化する。
同期ゲーム $\mathcal{G}=(I,O,\lambda)$ with $|I|=n$ and $|O|=k$ が与えられたとき、Z. Ji (arXiv:1310.3794) による同期型非局所ゲームに対する量子戦略の勝利のために、Z. Ji (arXiv:1310.3794) が入力した作業を強化し単純化し、最大で3+n+9n(k-2)+6|\lambda^{-1}(\{0\})| のグラフ上の3ドルカラーゲームと$*$-equivalence と呼ぶものを実証する。
応用として、L. Lov\'{a}sz's reduction の量子バージョン (Comb. on 4th SE Conf. on Graph Theory & Computing, 1973) のグラフの$k$彩色問題である$G$と$n$頂点を持つ$m$エッジを、3+n+9n(k-2)+6mk$頂点を持つグラフの$3$彩色問題に適用する。
さらに、同期ゲーム $\mathcal{G}$ の勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換できる。
a. atserias et al (j. comb. theory series b, vol. 136, 2019) ``graph of the game" $x(\mathcal{g})$ associated to $\mathcal{g}$ from a. atserias et al (j. comb. theory series b, vol. 136, 2019) 独立数ゲーム $\text{hom}(k_{|i|},\overline{x(\mathcal{g})})$ はここでは$*$-equivalent to $\mathcal{g}$ であるので、ゲーム代数を除く全てのゲームで勝利戦略の可能性は同じである。
したがって、色数、独立数、クランク数の量子バージョンは、すべての量子モデルにおける全ての同期ゲームに対する勝利戦略をエンコードする。
関連論文リスト
- Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文 参考訳（メタデータ） (2024-08-20T05:20:55Z) - Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions [0.0]
我々は遺伝モデルと$C*$モデルの等価性を証明している(Hlton et al., New York J. Math)。
また、量子変換NP硬度低減$texttt3-SAT* leq_p textttClique*$ も拡張し、この還元の別の例を示す。
論文 参考訳（メタデータ） (2024-08-19T16:01:21Z) - Complexity of graph-state preparation by Clifford circuits [2.7010154811483167]
グラフ状態の CZ-複素性は、|Grangle$ とグラフのランク幅 $G$ との接続を示す。
我々は、グラフの特殊クラスに$G$が含まれているとき、$|Grangle$を$O(n)$ CZ-複雑度で作成する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-08T18:08:09Z) - Quantum walks on blow-up graphs [0.0]
グラフ$G$の$n$コピーは、グラフ$oversetnuplusG$である。
ブローアップグラフ $oversetnuplusG$ 上の量子状態移動の存在について検討する。
論文 参考訳（メタデータ） (2023-08-26T14:07:25Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs [6.305950347749109]
本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。
我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
論文 参考訳（メタデータ） (2021-10-08T15:24:31Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。