論文の概要: Quantum Max-Cut is NP hard to approximate

• arxiv url: http://arxiv.org/abs/2510.07995v1
• Date: Thu, 09 Oct 2025 09:32:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:14.987798
• Title: Quantum Max-Cut is NP hard to approximate
• Title（参考訳）: 量子マックスカットはNPの近似が難しい
• Authors: Stephen Piddock,
• Abstract要約: 我々は、定数有界グラフ上の QUANTUM MAX-CUT 問題に対する定数乗法近似を計算するのがNPハードであることを証明する。
• 参考スコア（独自算出の注目度）: 0.06768558752130309
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We unconditionally prove that it is NP-hard to compute a constant multiplicative approximation to the QUANTUM MAX-CUT problem on an unweighted graph of constant bounded degree. The proof works in two stages: first we demonstrate a generic reduction to computing the optimal value of a quantum problem, from the optimal value over product states. Then we prove an approximation preserving reduction from MAX-CUT to PRODUCT-QMC the product state version of QUANTUM MAX-CUT. More precisely, in the second part, we construct a PTAS reduction from MAX-CUT$_k$ (the rank-k constrained version of MAX-CUT) to MAX-CUT$_{k+1}$, where MAX-CUT and PRODUCT-QMC coincide with MAX-CUT$_1$ and MAX-CUT$_3$ respectively. We thus prove that Max-Cut$_k$ is APX-complete for all constant $k$.
• Abstract（参考訳）: 非条件で、定数有界グラフ上の QUANTUM MAX-CUT 問題に対する定数乗法近似を計算するのがNPハードであることを証明する。 証明は2つの段階で成り立つ: まず、積状態に対する最適値から量子問題の最適値を計算するための一般的な還元を実証する。 次に MAX-CUT から PRODUCT-QMC への還元を QUANTUM MAX-CUT の製品状態バージョンとして近似した。 より正確には、第2部では、MAX-CUT$_k$(MAX-CUTのランク-k制約版)からMAX-CUT$_{k+1}$(MAX-CUTとProductCT-QMCがそれぞれMAX-CUT$_1$とMAX-CUT$_3$と一致する)へのPTASの削減を構築する。 したがって、Max-Cut$_k$ がすべての定数 $k$ に対して APX-完全であることを証明する。

関連論文リスト

• Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory [3.359365297148466]
  効率的なアルゴリズムの既知の限界を改善する新しい構造を見つけるのにAIのテクニックが役立つかどうかを探索する。 具体的には、AlphaEvolveを使って、a)MAX-CUTの平均ケース硬度とMAX-Independent Setの2つの設定を研究します。 改良された下界は、最大163$のノード上にほぼ極端ラマヌジャングラフを構築することで得られる。
  論文  参考訳（メタデータ） (2025-09-22T17:30:33Z)
• Self-Adjust Softmax [62.267367768385434]
  ソフトマックス関数はトランスフォーマーアテンションにおいて重要であり、アテンションスコアの各行を1にまとめて正規化する。 この問題に対処するために、$softmax(x)$を$x cdot Softmax(x)$に修正し、その正規化された変種である$frac(x - min(x_min,0))max(0,x_max)-min(x_min,0)cdot softmax(x)$を変更することを提案する。
  論文  参考訳（メタデータ） (2025-02-25T15:07:40Z)
• A maximum concurrence criterion to investigate absolutely maximally entangled states [0.7373617024876725]
  我々は、純状態の最大絡み付けを決定するために、絡み合いの尺度である最大I-コンカレンスの基準を用いる。 我々は、可能なすべての二分割にまたがる最大の絡み合いを示す、絶対的に極大な純粋状態(AME)を多数同定する。
  論文  参考訳（メタデータ） (2025-01-26T10:46:03Z)
• Convex Bounds on the Softmax Function with Applications to Robustness Verification [69.09991317119679]
  ソフトマックス関数は、ニューラルネットワークの出力においてユビキタスなコンポーネントであり、中間層もますます多くなっている。 本稿では,ニューラルネットワークや他のMLモデルのキャラクタリゼーションのための凸最適化式と互換性のある,ソフトマックス関数上の凸下界と凹上界を提供する。
  論文  参考訳（メタデータ） (2023-03-03T05:07:02Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。 我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。 マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2020-07-02T10:48:42Z)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。 Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
  論文  参考訳（メタデータ） (2020-02-13T02:16:57Z)

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

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