論文の概要: On the Quantum Chromatic Gap II

• arxiv url: http://arxiv.org/abs/2610.40571v1
• Date: Thu, 29 Oct 2026 17:44:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 06:40:41.213042
• Title: On the Quantum Chromatic Gap II
• Title（参考訳）: 量子クロマティックギャップIIについて
• Abstract要約: 我々は、ホートの$d$-to-$1$のゲームに対して、最初の著者(SODA'26)の強い擬テレパシーの形の予想を証明した。 すべての$dgeq 4$, every $>0$, every $kinmathbb N$に対して、$d$-to-1$という古典的な値のラベルカバーゲームがある。
• 参考スコア（独自算出の注目度）: 3.22853198951198
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's $d$-to-$1$ games: for every $d\geq 4$, every $ε>0$, and every $k\in\mathbb N$, there is a $d$-to-$1$ label-cover game of classical value less than $ε$ that admits a perfect quantum strategy using finite-dimensional shared entanglement with measurement contexts of radius at least $k$. As a consequence, there exist graphs whose quantum chromatic number $χ_q$ is $3$ and whose classical chromatic number $χ$ is arbitrarily large. This is the first improvement on the quantum chromatic gap since the work of Brassard, Cleve, and Tapp [Phys. Rev. Lett.'99], which produced graphs for which $χ$ grows exponentially in $χ_q$. To prove the conjecture, we proceed as follows. We start with a ``stretched'' version of the Mermin--Peres magic square, obtained by spacing out its equations and linking them with additional long equation wires. This operation increases the radius of the initial measurement contexts of a perfect quantum strategy for the game, while preserving classical unsatisfiability. We then apply parallel repetition to make the classical value small, and we turn the system into a pseudo-telepathic multi-layered Kneser hypergraph via a PCP construction of Dinur, Guruswami, Khot, and Regev [STOC'03]. Finally, we feed the resulting hypergraph into the reduction of Fei, Minzer, and Wang from hypergraph colouring to $4$-to-$1$ games, we establish quantum completeness of this reduction, and we show that it preserves context radius.
• Abstract（参考訳）: 我々は、Khotの$d$-to-$1$ゲームに対して、最初の著者 [SODA'26] の強い擬テレパシーの形の予想を裏付ける:すべての$d\geq 4$, every $ε>0$, every $k\in\mathbb N$ に対して、古典的な値を持つ$d$-to-$1$のラベル付きゲームが存在する。 結果として、量子クロマティック数 $ ==q$ が 3$ で、古典的なクロマティック数 $ =$ が任意に大きいグラフが存在する。 これはBrassard, Cleve, and Tapp [Phys. Rev. Lett.'99] の業績以来の量子色差における最初の改善である。 その予想を証明するため、我々は次のように進める。 まず、Mermin-Peres のマジックスクエアの ``stretched' バージョンから始めます。 この操作は、古典的な不満足性を保ちながら、ゲームの完全な量子戦略の初期測定コンテキストの半径を増大させる。 次に、古典的な値を小さくするために並列繰り返しを適用し、Dinur, Guruswami, Khot, Regev [STOC'03] のPCP構築を通して擬似テレパシー多層Kneserハイパーグラフに変換する。 最後に、結果のハイパーグラフをFei, Minzer, Wangの減色から4ドルから1ドルゲームの減色に投入し、この減色を量子完全性(quantum completeness)を確立し、文脈半径を保存することを示す。

関連論文リスト

• Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points [31.45779401617503]
  タルスキの不動点問題は、幅$n$の$k$次元格子上の単調写像の固定点を求め、ゲーム理論、経済学、検証に応用できる。 量子下界に対する2つのブートストラッピング定理を証明する。
  論文  参考訳（メタデータ） (2026-10-12T05:39:35Z)
• Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders [39.564326983693704]
  量子マックス・カット(英: Quantum Max-Cut)は、二部体の場合の古典的複雑性が依然として開であるような、よく研究された局所ハミルトン問題である。 スピン磁性12$反強磁性ハイゼンベルクモデルに対する時空の古典的ランダム化アルゴリズム、すなわち量子マックスキュート(Quantum Max-Cut)を高密度に平衡したバイパルタイト展開器に与える。
  論文  参考訳（メタデータ） (2026-10-02T17:40:52Z)
• Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
  クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。 非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
  論文  参考訳（メタデータ） (2026-09-03T13:06:12Z)
• Perfect Games in Dimension-Bounded Communication [0.0]
  完璧な準備と測定のゲームは、オール・オ・ナッシングな量子優位性を示す。 量子システム次元$d$は、所定の入賞制約を全て満たすが、古典的な$d$レベルメッセージは満たせない。
  論文  参考訳（メタデータ） (2026-08-05T17:28:44Z)
• The Kikuchi Hierarchy is Sharp for $k$XOR [46.26532142699448]
  菊池階層の正規化された変種は、対数損失のない鋭い予想されたトレードオフを、全てのアーティ$kge3$で達成することを示す。 また、同じモデルで一致した下界を証明し、推論と難解な上界はより一般的な植林法や述語に遷移する。
  論文  参考訳（メタデータ） (2026-07-31T17:54:11Z)
• A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
  ハイパーグラフムーア境界に関するファイゲの2008年の予想を証明する。 すべての$kge3$と$1leellle n$に対して、$n$ vertices 上の任意の $k$-uniform hypergraph は、$C,nk/2/ellk/2-1$ hyperedges は、最大$A,elllog(en/ell)$で偶数被覆を含む。
  論文  参考訳（メタデータ） (2026-07-28T17:38:31Z)
• 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)
• Perfect quantum strategies with small input cardinality [0.0]
  少数の設定でqudit-qudit完全量子戦略を生成する方法を示す。 任意の$(2,d-1,d)$ Bell シナリオで完全量子戦略の族を示す。
  論文  参考訳（メタデータ） (2024-07-31T09:33:52Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。 同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
  論文  参考訳（メタデータ） (2023-05-29T14:28:28Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)

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

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