論文の概要: Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem

• arxiv url: http://arxiv.org/abs/2412.19405v1
• Date: Fri, 27 Dec 2024 02:05:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-30 17:24:59.340010
• Title: Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem
• Title（参考訳）: グラフの近似量子3色化と量子Max 3-Cut問題
• Authors: Samuel J. Harris,
• Abstract要約: 各同期非局所ゲーム $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)$が存在することを証明している。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We prove that, to each synchronous non-local game $\mathcal{G}=(I,O,\lambda)$ with $|I|=n$ and $|O|=m \geq 3$, there is an associated graph $G_{\lambda}$ for which approximate winning strategies for the game $\mathcal{G}$ and the $3$-coloring game for $G_{\lambda}$ are preserved. That is, using a similar graph to previous work of the author (Ann. Henri Poincar\'{e}, 2024), any synchronous strategy for $\text{Hom}(G_{\lambda},K_3)$ that wins the game with probability $1-\varepsilon$ with respect to the uniform probability distribution on the edges, yields a strategy in the same model that wins the game $\mathcal{G}$ with respect to the uniform distribution with probability at least $1-h(n,m)\varepsilon^{\frac{1}{2}}$, where $h$ is a polynomial in $n$ and $2^m$. As an application, we prove that the gapped promise problem for quantum $3$-coloring is undecidable. Moreover, we prove that there exists an $\alpha \in (0,1)$ for which determining whether the non-commutative Max-$3$-Cut of a graph is $|E|$ or less than $\alpha |E|$ is RE-hard, thus giving a positive answer to a problem posed by Culf, Mousavi and Spirig (arXiv:2312.16765), along with evidence for a sharp computability gap in the non-commutative Max-$3$-Cut problem. We also prove that there is some $\alpha \in (0,1)$ such that determining the non-commutative (respectively, commuting operator framework) versions of the Max-$3$-Cut of a graph within a factor of $\alpha$ is uncomputable. All of these results avoid use of the unique games conjecture.
• Abstract（参考訳）: 各同期非局所ゲーム $\mathcal{G}=(I,O,\lambda)$ with $|I|=n$ and $|O|=m \geq 3$ に対して、ゲーム $\mathcal{G}$ と $G_{\lambda}$ に対する近似的な勝利戦略が保存されているグラフ $G_{\lambda}$ が存在することを証明している。 つまり、著者(Ann)の以前の作業と同様のグラフを使用する。 Henri Poincar\'{e}, 2024) の任意の同期戦略である$\text{Hom}(G_{\lambda}, K_3)$ は、エッジ上の一様確率分布に関して確率 1-\varepsilon$ でゲームに勝利し、その確率が少なくとも 1-h(n,m)\varepsilon^{\frac{1}{2}}$ で確率が 1-h(n,m)\varepsilon^{\frac{1}{2}}$ で、$h$ は$n$ と $2^m$ の多項式である。 応用として、量子3$カラー化におけるギャップ付き約束問題は決定不可能であることを示す。 さらに、グラフの非可換な Max-3$-Cut が $|E|$ か $\alpha |E|$ 以下であるかどうかを判定する $\alpha \in (0,1)$ が存在することを証明し、Culf, Mousavi and Spirig (arXiv:2312.16765) が主張する問題に対する正の答えを与える。 さらに、$\alpha \in (0,1)$ が存在して、$\alpha$ の係数内のグラフの Max-$3$-Cut の非可換(可換作用素フレームワーク)バージョンが計算不可能であることを示す。 これらの結果はすべて、ユニークなゲーム予想の使用を避ける。

関連論文リスト

• Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
  我々はKarpとKleinbergのノイズの多いバイナリ検索モデルを再検討する。 我々は[ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta)右から1-delta$の確率で成功するアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2023-11-01T20:45:13Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  量子グラフパラメータは、任意の同期非局所ゲームに対する勝利戦略をエンコードすることを示す。 同期ゲームにおける勝利戦略は、関連するグラフカラーゲームに対する勝利戦略に変換することができる。
  論文  参考訳（メタデータ） (2023-05-29T14:28:28Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01:34Z)
• Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
  本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。 近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。 副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
  論文  参考訳（メタデータ） (2022-02-22T04:14:45Z)
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
  関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。 我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
  論文  参考訳（メタデータ） (2021-11-01T20:45:42Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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