論文の概要: On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut

• arxiv url: http://arxiv.org/abs/2411.04124v1
• Date: Wed, 06 Nov 2024 18:58:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-07 19:22:03.240056
• Title: On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut
• Title（参考訳）: Log-Approximate CVP と Max-Cut の(古典的および量子的)ファイングラインド複素性について
• Authors: Jeremy Ahrens Huang, Young Kun Ko, Chunhao Wang,
• Abstract要約: 最大カット問題(Max-Cut)の1-varepsilon$と1-varepsilon1/2$から、任意の有限$ell_p$-normの下での$gamma$-Approximate Closest Vector Problemへの線形サイズの縮小を示す。 有限 $ell_p$-norm における $o(sqrtlog nfrac1p)$- Approximate Closest Vector Problem に対する部分指数時間(古典的あるいは量子的)アルゴリズムは、状態よりも高速であることを示す。
• 参考スコア（独自算出の注目度）: 2.2776283699063664
• License:
• Abstract: We show a linear sized reduction from the Maximum Cut Problem (Max-Cut) with completeness $1 - \varepsilon$ and soundness $1 - \varepsilon^{1/2}$ to the $\gamma$-Approximate Closest Vector Problem under any finite $\ell_p$-norm including $p = 2$. This reduction implies two headline results: (i) We show that any sub-exponential time (classical or quantum) algorithm for the $o(\sqrt{\log n}^{\frac{1}{p}})$-Approximate Closest Vector Problem in any finite $\ell_p$-norm implies a faster than the state-of-the-art (by Arora, Barak, and Steurer [\textit{Journal of the ACM}, 2015]) sub-exponential time (classical or quantum) algorithm for Max-Cut. This fills the gap between the results by Bennett, Golovnev, and Stephens-Davidowitz [\textit{FOCS} 2017] which had an almost optimal runtime lower bound but a very small approximation factor and the results by Dinur, Kindler, Raz, and Safra [\textit{Combinatorica}, 2003] which had an almost optimal approximation factor but small runtime lower bound, albeit using a different underlying hard problem; (ii) in combination with the classical results of Aggarwal and Kumar [\textit{FOCS} 2023] and our quantization of those results, there are no fine-grained reductions from $k$-SAT to Max-Cut with one-sided error, nor are there non-adaptive fine-grained (classical or quantum) reductions with two-sided error, unless the polynomial hierarchy collapses (or unless $\mathrm{NP} \subseteq \mathrm{pr} \text{-} \mathrm{QSZK}$ in the quantum case). The second result poses a significant barrier against proving the fine-grained complexity of Max-Cut using the Strong Exponential Time Hypothesis (or the Quantum Strong Exponential Time Hypothesis).
• Abstract（参考訳）: 最大カット問題 (Max-Cut) から完全性 $1 - \varepsilon$ および音性 $1 - \varepsilon^{1/2}$ から $\gamma$-Approximate Closest Vector Problem への線形縮小を、$p = 2$ を含む任意の有限の$\ell_p$-norm の下で示す。 この減少は2つの見出し結果を意味する。 i)$o(\sqrt{\log n}^{\frac{1}{p}})$-Approximate Closest Vector Problem in any finite $\ell_p$-norm は、Max-Cut の Sub-exponential time (classical or quantum) algorithm よりも高速であることを示す(Arora, Barak, and Steurer [\textit{Journal of the ACM}, 2015])。 これは、ほぼ最適なランタイムローバウンドを持つBennett, Golovnev, Stephens-Davidowitz [\textit{FOCS} 2017] の結果と、Dinur, Kindler, Raz, Safra [\textit{Combinatorica, 2003] の結果のギャップを埋める。 (ii)Aggarwal と Kumar [\textit{FOCS} 2023] の古典的な結果とこれらの結果の量子化と組み合わせて、一辺誤差で$k$-SAT から Max-Cut への微粒化や、多項式階層が崩壊しない限り、非適応的(古典的または量子的)な微粒化(古典的または古典的)の縮小は存在しない(あるいは、量子的ケースでは$\mathrm{NP} \subseteq \mathrm{pr} \text{-} \mathrm{QSZK}$)。 2つ目の結果は、強い指数時間仮説(または量子強い指数時間仮説)を用いてマックス・カットの微細な複雑さを証明するために大きな障壁となる。

関連論文リスト

• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。 ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。 有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
  論文  参考訳（メタデータ） (2024-06-06T11:33:29Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。 解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
  論文  参考訳（メタデータ） (2024-02-07T18:22:41Z)
• The classical limit of Quantum Max-Cut [0.18416014644193066]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45: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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms [0.0]
  我々は、Max $k$XORをおよそ解くための局所アルゴリズムのパワーを考える。 Max $k$XORでは、各制約は正確に$k$変数とパリティビットのXORである。 量子アルゴリズムがしきい値アルゴリズムを$k > 4$で上回ることを示す。
  論文  参考訳（メタデータ） (2021-09-22T16:50:45Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)

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

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