論文の概要: Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions

• arxiv url: http://arxiv.org/abs/2510.03385v1
• Date: Fri, 03 Oct 2025 17:40:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.011898
• Title: Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
• Title（参考訳）: 非凸関数の大域最適化における量子アドバンテージのメカニズム
• Authors: Dylan Herman, Guneykan Ozgul, Anuj Apte, Junhyung Lyle Kim, Anupam Prakash, Jiayu Shen, Shouvanik Chakrabarti,
• Abstract要約: 非同相関数の大域的最適化における量子スピードアップの新たな理論機構を示す。 我々は,実空間量子アルゴリズム (RsAA) が実時間実行を実現することを証明して,これらのアイデアを定式化する。
• 参考スコア（独自算出の注目度）: 6.135587835061064
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, expanding the scope of quantum advantage beyond traditional tunneling-based explanations. As our main building-block, we demonstrate a rigorous correspondence between the spectral properties of Schr\"{o}dinger operators and the mixing times of classical Langevin diffusion. This correspondence motivates a mechanism for separation on functions with unique global minimum: while quantum algorithms operate on the original potential, classical diffusions correspond to a Schr\"{o}dinger operators with a WKB potential having nearly degenerate global minima. We formalize these ideas by proving that a real-space adiabatic quantum algorithm (RsAA) achieves provably polynomial-time optimization for broad families of nonconvex functions. First, for block-separable functions, we show that RsAA maintains polynomial runtime while known off-the-shelf algorithms require exponential time and structure-aware algorithms exhibit arbitrarily large polynomial runtimes. These results leverage novel non-asymptotic results in semiclassical analysis. Second, we use recent advances in the theory of intrinsic hypercontractivity to demonstrate polynomial runtimes for RsAA on appropriately perturbed strongly convex functions that lack global structure, while off-the-shelf algorithms remain exponentially bottlenecked. In contrast to prior works based on quantum tunneling, these separations do not depend on the geometry of barriers between local minima. Our theoretical claims about classical algorithm runtimes are supported by rigorous analysis and comprehensive numerical benchmarking. These findings establish a rigorous theoretical foundation for quantum advantage in continuous optimization and open new research directions connecting quantum algorithms, stochastic processes, and semiclassical analysis.
• Abstract（参考訳）: 本稿では,非凸関数の大域的最適化における量子スピードアップの新たな理論機構を提案する。 主ビルディングブロックとして、Schr\"{o}dinger作用素のスペクトル特性と古典的ランゲヴィン拡散の混合時間の間の厳密な対応を示す。 量子アルゴリズムは元のポテンシャルで作用するが、古典的拡散は、ほとんど退化した大域最小値を持つ WKB ポテンシャルを持つ Schr\"{o}dinger 作用素に対応する。 我々は、実空間断熱量子アルゴリズム(RsAA)が、非凸関数の広い族に対して証明可能な多項式時間最適化を実現することを証明して、これらのアイデアを定式化する。 まず、ブロック分離可能な関数の場合、RsAAは多項式ランタイムを維持し、既知のオフザシェルフアルゴリズムは指数時間を必要とし、構造認識アルゴリズムは任意の大きさの多項式ランタイムを示す。 これらの結果は、半古典的分析において新しい非漸近的な結果を活用する。 第二に、本質的超収縮理論の最近の進歩を利用して、大域的な構造を欠いた強凸関数に対して RsAA の多項式ランタイムを実証する一方、オフザシェルフアルゴリズムは指数関数的にボトルネックを保ったままである。 量子トンネルに基づく以前の研究とは対照的に、これらの分離は局所的なミニマの間の障壁の幾何学に依存しない。 古典的アルゴリズムランタイムに関する理論的主張は厳密な解析と包括的な数値ベンチマークによって支持されている。 これらの発見は、連続最適化における量子優位の厳密な理論基盤を確立し、量子アルゴリズム、確率過程、半古典的解析を接続する新しい研究方向を開放する。

関連論文リスト

• Avoided-crossings, degeneracies and Berry phases in the spectrum of quantum noise through analytic Bloch-Messiah decomposition [49.1574468325115]
  解析的ブロッホ・メシア分解 (analytic Bloch-Messiah decomposition) は量子光学系の力学を特徴づけるためのアプローチを提供する。 単一パラメータが変化した場合,回避された交差は自然に発生し,特異ベクトルの過敏性をもたらすことを示す。 我々は,避けられた交差を意図的に設計することで,フォトニックシステムのスペクトル応答をプログラムできる可能性を強調した。
  論文  参考訳（メタデータ） (2025-04-29T13:14:15Z)
• Projective Quantum Eigensolver with Generalized Operators [0.0]
  PQEフレームワークにおける閉形式残留方程式の観点から一般化作用素を決定する手法を開発する。 いくつかの分子系への応用により、アンザッツは単体、二重体、三重体を含む(異方性)UCCと同様の精度を達成できることを実証した。
  論文  参考訳（メタデータ） (2024-10-21T15:40:22Z)
• Quantum Dissipative Search via Lindbladians [0.0]
  我々は、構造化されていない古典的な探索空間上の純粋に散逸した量子ランダムウォークを解析する。 ある種のジャンプ演算子は量子過程を古典的過程に複製させ、他方はオープン量子(OQRW)と古典的ランダムウォークの違いをもたらすことを示す。 また,従来観測されていた2次高速化も明らかにし,OQRWは古典的検索ほど効率的ではないことを示した。
  論文  参考訳（メタデータ） (2024-07-16T14:39:18Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
  本稿では,ギブス分割関数を線形時間で推定する新しい量子アルゴリズムを提案する。 これは、vStefankovivc, Vempala, Vigodaの半周期的なほぼ直線時間で得られる最初のスピードアップである。
  論文  参考訳（メタデータ） (2022-07-18T14:41:48Z)
• On constant-time quantum annealing and guaranteed approximations for graph optimization problems [0.0]
  量子アニーリング(Quantum Annealing, QA)は、量子系の連続的な進化が目的関数の最小値を見つけるために用いられる計算フレームワークである。 本稿では、理論物理学、リーブ・ロビンソン境界(LR)から借用した手法を用いて、短時間の量子アニールにより定数係数の近似比が保証されることを示す新しいツールを開発する。 我々の結果は、異なるが関連するQAOA(量子最適化アルゴリズム)フレームワークで得られたよく知られたものと類似している。
  論文  参考訳（メタデータ） (2022-02-03T15:23:18Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  平均場ランゲヴィン力学の収束速度解析について述べる。 ダイナミックスに付随する$p_q$により、凸最適化において古典的な結果と平行な収束理論を開発できる。
  論文  参考訳（メタデータ） (2022-01-25T17:13:56Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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