論文の概要: Quantum n-coloring is undecidable for every n $\ge$ 3

• arxiv url: http://arxiv.org/abs/2610.05280v1
• Date: Sun, 04 Oct 2026 14:59:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 22:03:08.341351
• Title: Quantum n-coloring is undecidable for every n $\ge$ 3
• Title（参考訳）: 量子n-色付けは n$\ge$ 3 ごとに決定できない
• Abstract要約: 我々は、$G'=(G square K_3)lor K_n-3$、$G'$が量子$$3$-colorableであることと、$G'$が量子$n$-colorableであることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum $n$-coloring problem, given graph $G$, asks whether there exists a perfect quantum strategy for the $n$-coloring game of $G$. Previously it was known that quantum $n$-coloring is undecidable only for $n=3$. We extend this to all $n\geq 3$ with one elementary reduction. Letting $G'=(G\square K_3)\lor K_{n-3}$, we show that $G$ is quantum $3$-colorable if and only if $G'$ is quantum $n$-colorable.
• Abstract（参考訳）: グラフ$G$が与えられた量子$$カラー化問題は、$n$カラー化ゲームが$G$の完全量子戦略が存在するかどうかを問うものである。 以前は、量子$n$-彩色は$n=3$でしか決定できないことが知られていた。 これをすべての$n\geq 3$に拡張する。 G'=(G\square K_3)\lor K_{n-3}$とすると、$G$が量子$$3$-彩度であることと、$G'$が量子$n$-彩度であることは同値である。

関連論文リスト

• Quantum Colorings of Spheres [0.0]
  Sn-1$ が量子的に $n$-colorable であれば、$n=2$ または $n$ が 4 の倍数であることを示し、次数 $n$ のアダマール行列が存在するたびに逆が成り立つことを示す。 Sn-1$ が階数 1 の量子 $n$-色付けを認め、かつ、$n が 2,4,8$ である場合に限り、Zeng と Zhang の予想を定めている。
  論文  参考訳（メタデータ） (2026-06-09T13:49:08Z)
• Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem [0.0]
  各同期非局所ゲーム $mathcalG=(I,O,lambda)$ with $|I|=n$ and $O=m geq 3$ に対して、関連するグラフ $G_lambda$ が存在することを証明している。 また、グラフの非可換Max-$3$-Cutが$E|$か$E|$以下の$alpha |E|$がRE-hardかどうかを判定する$alpha in (0,1)$が存在することを証明している。
  論文  参考訳（メタデータ） (2024-12-27T02:05:37Z)
• Learning low-degree quantum objects [5.2373060530454625]
  低次量子オブジェクトを、$ell$-distanceで$varepsilon$-errorまで学習する方法を示す。 我々の主な技術的貢献は、量子チャネルと完全有界ポリリノミアルに対する新しいボネンブラスト・ヒル不等式である。
  論文  参考訳（メタデータ） (2024-05-17T17:36:44Z)
• Quantum connection, charges and virtual particles [65.268245109828]
  量子バンドル $L_hbar$ には接続 $A_hbar$ が与えられ、そのセクションは標準波動関数 $psi$ がシュリンガー方程式に従う。 L_Cpm$ と接続 $A_hbar$ を相対論的位相空間 $T*R3,1$ に持ち上げ、粒子と反粒子の両方を記述する Dirac スピノルバンドルに結合する。
  論文  参考訳（メタデータ） (2023-10-10T10:27:09Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。 同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
  論文  参考訳（メタデータ） (2023-05-29T14:28:28Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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