論文の概要: A counterexample to the quantum Hedetniemi conjecture

• arxiv url: http://arxiv.org/abs/2609.20690v1
• Date: Thu, 17 Sep 2026 16:57:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:54.389466
• Title: A counterexample to the quantum Hedetniemi conjecture
• Title（参考訳）: 量子ヘデトニエミ予想に対する反例
• Abstract要約: ゴドシル、ロバーソン、マル、セヴェリーニは、2つのグラフのカテゴリー積の量子色数はその因子の量子色数の最小値に等しいと推測した。 Gtimes H) leq 1538 1539 = min(_q(G),_q(H)] このグラフは、Zhuの反例からHedetniemiの予想まで、Lovszのゼータ数の基底グラフを用いて得られる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with \[ χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).\]The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.
• Abstract（参考訳）: ゴドシル、ロバーソン、シャマル、セヴェリーニは、2つのグラフのカテゴリー積の量子色数はその因子の量子色数の最小値に等しいと推測した。 明示的な有限グラフ $G, H$ を \[[(G\times H) \leq 1538 < 1539 = \min(\_q(G),\_q(H)) で構成する。 グラフは周の反例からヘデットニエミの予想まで、補体のロヴァース・テータ数(英語版)(Lovász theta number of the complement)が、分数的な色数だけでなく大きい基底グラフを用いて得られる。 第1因子の下位境界はテータ境界である。 第二の因子について、Zhu の議論は可換でない射影に適応する: クリッドの色を固定するステップは作用素間のIDに置き換えられる。 どちらの下界も、任意の非零単位元$C^*$-代数の射影による着色に対して成り立つ。 したがって、この予想は、空間的、近似的、可換な演算子と量子彩色数の$C^*$-代数的不変量に対しても失敗する。 また、正確な整数データによって証明された小さな反例を与える。 射影定式化におけるグラフ構成、証明書、および反例文は、Lean~4で形式化されている。

関連論文リスト

• Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography [1.529342790344802]
  King, Gosset, Kothari, Babbush の Conjecture 13 は、$B_(varrho)$ が任意の量子状態 $varrho$ において期待値が少なくとも$$ であるようなパウリ観測可能な集合であるなら、反可換グラフ $G$ は$B_(varrho)$ によって誘導される。 言い換えれば、$_f cdot 2 le であるような定数 $C$ が存在すると断言する。
  論文  参考訳（メタデータ） (2026-08-20T14:44:03Z)
• Tales of Hoffman: from a distance [2.2917707112773598]
  ホフマンは、隣接固有値を持つグラフ $G$ が$(G)geq 1+$ を満たすことを証明した。 我々は、この固有値を距離=k$設定に有界に拡張し、それに対応する量子距離グラフも下限であることを示すことによって、その強化を示す。
  論文  参考訳（メタデータ） (2025-12-15T10:51:22Z)
• Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph [11.495969551409729]
  直交グラフのいくつかの部分グラフの正確な量子色数を決定することによって結果を拡張する。 また、ハミング距離2の2進ベクトルからなるハミング距離2ハミンググラフの量子色数を決定する。
  論文  参考訳（メタデータ） (2025-12-01T02:21:25Z)
• 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)
• The exact quantum chromatic number of Hadamard graphs [0.0]
  我々は、位数$n=2N$ for $N$ a multiple of $4$のアダマールグラフの量子色数を計算する。 また、アダマールグラフのカテゴリー積の正確な量子色数を計算する。
  論文  参考訳（メタデータ） (2024-09-27T14:28:57Z)
• On a tracial version of Haemers bound [20.98023024846862]
  我々は、交換作用素モデルにおいて、グラフの量子独立数と量子シャノン容量の上限をそれらの値に拡張する。 私たちはこの境界を tracial Haemers bound と呼び、それが強い積に対して乗法的であることを証明します。
  論文  参考訳（メタデータ） (2021-07-06T12:09:33Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Counterexamples to the Low-Degree Conjecture [80.3668228845075]
  ホプキンスの予想は、ある高次元仮説テスト問題に対して、非時間アルゴリズムはいわゆる「単純な統計」よりも優れていると仮定する。 この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを囲む信念を定式化する。
  論文  参考訳（メタデータ） (2020-04-17T21:08:11Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。 レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
  論文  参考訳（メタデータ） (2019-09-04T11:46:26Z)

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

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