論文の概要: Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT

• arxiv url: http://arxiv.org/abs/2608.00333v1
• Date: Fri, 31 Jul 2026 22:53:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-17 01:32:04.542439
• Title: Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT
• Title（参考訳）: MAX-3-CUTと量子MAX-CUTのシャープ硬度
• Abstract要約: ここでは、すべての$>0$に対して$_3+$の乗算係数で MAX-3-CUT を近似することがNPハードであることが示される。 同様の戦略で、$>0$ごとに$_rm BOV+$の乗算係数でQuantum-CUTの積状態値を近似することがNPハードであることが証明できる。
• 参考スコア（独自算出の注目度）: 2.538209532048867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $α_3+ε$ for every $ε>0$, where $α_3\approx.83600811464$ is the approximation ratio of Frieze-Jerrum's polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O'Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in $[-1/2,2/5]$ and generalizes the Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math, 2010]. With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of $α_{\rm BOV}+ε$ for every $ε>0$, where $α_{\rm BOV}\approx 0.9563372685$ is the approximation ratio of the Briët-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their $S^{k-1}$-valued Borell inequality for correlations in $[-.5843,.5843]$ for all $k\geq3$.
• Abstract（参考訳）: Unique Games Conjecture を仮定すると、任意の$ε>0$に対して$α_3+ε$の乗算係数で MAX-3-CUT を近似することはNPハードであることが示され、ここでは$α_3\approx.83600811464$ はフリーゼ・ジェラムの多項式時間アルゴリズムの1995年の近似比である。 すなわち,MAX-3-CUT に対する近似の急激な硬さを証明した。 この結果は、2004年にKhot-Kindler-Mossel-O'Donnell の予想を解決し、3つの候補 Plurality が $[-1/2,2/5]$ の相関に対して安定な導出であることを証明することによって証明し、Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math, 2010] を一般化する。 類似の戦略を仮定すると、$α_{\rm BOV}+ε$ for every $ε>0$, where $α_{\rm BOV}\approx 0.9563372685$ は Briët-de Oliveira Filho-Vallentin アルゴリズムの近似比である。 このシャープな硬さの結果、2021年より Hwang-Neeman-Parekh-Thompson-Wright の予想された硬さは、すべての$k\geq3$に対して$[-.5843,.5843]$の相関に対して $S^{k-1}$-値のボレル不等式を証明することによって完結する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Semidefinite extension complexity of the separable set, with applications to approximate disentanglers [0.6117371161379209]
  分離可能な状態における測定値の最大受容確率を近似する半定値プログラムを考える。 我々の証明は、Lee, Raghavendra, Steurer の量的擬似密度定理と明示的なブロック陽性作用素とチェビシェフ増幅を組み合わせたものである。
  論文  参考訳（メタデータ） (2026-09-08T17:00:11Z)
• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。 私たちの指導原則は、最大値が丸みを帯びた候補であることです。
  論文  参考訳（メタデータ） (2026-08-03T17:58:00Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Sphere Valued Noise Stability and Quantum MAX-CUT Hardness [0.0]
  この不等式は、Hwang, Neeman, Parekh, Thompson and Wright によって予想された。 量子MAX-CUTの積状態は、乗法係数$.9859$で近似するNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-06-06T17:54:22Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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