論文の概要: On Speedups for Convex Optimization via Quantum Dynamics

• arxiv url: http://arxiv.org/abs/2503.24332v1
• Date: Mon, 31 Mar 2025 17:21:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-01 14:32:48.730134
• Title: On Speedups for Convex Optimization via Quantum Dynamics
• Title（参考訳）: 量子力学による凸最適化の高速化について
• Authors: Shouvanik Chakrabarti, Dylan Herman, Jacob Watkins, Enrico Fontana, Brandon Augustino, Junhyung Lyle Kim, Marco Pistoia,
• Abstract要約: 量子ハミルトニアンDescentフレームワークの離散シミュレーションを用いて凸最適化における量子速度の可能性を探る。 連続時間において、適切なパラメータを持つQHDは、任意に高速な収束率が得られることを示す。 QHDは、この評価ノイズのレベルを許容する既知の全ての古典的アルゴリズムに対して、超クアドラルなクエリの利点を提供することを示す。
• 参考スコア（独自算出の注目度）: 2.5094874597551913
• License:
• Abstract: We explore the potential for quantum speedups in convex optimization using discrete simulations of the Quantum Hamiltonian Descent (QHD) framework, as proposed by Leng et al., and establish the first rigorous query complexity bounds. We develop enhanced analyses for quantum simulation of Schr\"odinger operators with black-box potential via the pseudo-spectral method, providing explicit resource estimates independent of wavefunction assumptions. These bounds are applied to assess the complexity of optimization through QHD. Our findings pertain to unconstrained convex optimization in $d$ dimensions. In continuous time, we demonstrate that QHD, with suitable parameters, can achieve arbitrarily fast convergence rates. The optimization speed limit arises solely from the discretization of the dynamics, mirroring a property of the classical dynamics underlying QHD. Considering this cost, we show that a $G$-Lipschitz convex function can be optimized to an error of $\epsilon$ with $\widetilde{\mathcal{O}}(d^{1.5}G^2 R^2/\epsilon^2)$ queries. Moreover, under reasonable assumptions on the complexity of Hamiltonian simulation, $\widetilde{\Omega}(d/\epsilon^2)$ queries are necessary. Thus, QHD does not offer a speedup over classical zeroth order methods with exact oracles. However, we demonstrate that the QHD algorithm tolerates $\widetilde{\mathcal{O}}(\epsilon^3/d^{1.5}G^2 R^2)$ noise in function evaluation. We show that QHD offers a super-quadratic query advantage over all known classical algorithms tolerating this level of evaluation noise in the high-dimension regime. Additionally, we design a quantum algorithm for stochastic convex optimization that provides a super-quadratic speedup over all known classical algorithms in the high-dimension regime. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization achieved through a dynamical algorithm.
• Abstract（参考訳）: コンベックス最適化における量子スピードアップの可能性について,Lengらによって提案された量子ハミルトン Descent (QHD) フレームワークの離散シミュレーションを用いて検討し,最初の厳密なクエリ複雑性境界を確立する。 我々は、疑似スペクトル法によりブラックボックスポテンシャルを持つシュリンガー作用素の量子シミュレーションのための拡張解析を開発し、波動関数の仮定とは無関係に明確な資源推定を提供する。 これらの境界は、QHDによる最適化の複雑さを評価するために適用される。 この結果は,$d$次元における非拘束凸最適化に関係している。 連続時間において、適切なパラメータを持つQHDは、任意に高速な収束率が得られることを示す。 最適化速度制限は、力学の離散化によってのみ生じ、QHDの基礎となる古典力学の特性を反映している。 このコストを考慮すると、$G$-Lipschitz convex関数は$\epsilon$ with $\widetilde{\mathcal{O}}(d^{1.5}G^2 R^2/\epsilon^2)$クエリのエラーに最適化できる。 さらに、ハミルトンシミュレーションの複雑さに関する合理的な仮定の下では、$\widetilde{\Omega}(d/\epsilon^2)$クエリが必要である。 したがって、QHDは正確なオラクルを持つ古典的なゼロ階法の高速化を提供していない。 しかし、QHDアルゴリズムは関数評価において$\widetilde{\mathcal{O}}(\epsilon^3/d^{1.5}G^2 R^2)$ノイズを許容することを示した。 我々はQHDが、高次元構造におけるこのレベルの評価ノイズを許容する既知の全ての古典的アルゴリズムに対して、超2次クエリの利点を提供することを示す。 さらに,高次元の古典的アルゴリズムを超4次高速化する確率凸最適化のための量子アルゴリズムを設計する。 我々の知る限り、これらの結果は動的アルゴリズムによって達成された凸最適化のための最初の厳密な量子スピードアップを表している。

関連論文リスト

• Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation [0.5097809301149342]
  我々は、勾配推定を必要としない連続的な最適化のために、いくつかの量子アルゴリズムを提供する。 我々は、最適化問題を物理系の力学にエンコードし、時間進化をコヒーレントにシミュレートする。
  論文  参考訳（メタデータ） (2025-02-06T18:32:26Z)
• Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
  2次元の$(gamma, beta)$サーチを$gamma$より1次元の検索に還元する方法を示し、$beta*$を解析的に計算する。 このアプローチはRecursive QAOA (RQAOA) を用いて検証され、粗い最適化RQAOAと半定値プログラムを一貫して上回る。
  論文  参考訳（メタデータ） (2025-01-27T19:00:00Z)
• Optimizing Unitary Coupled Cluster Wave Functions on Quantum Hardware: Error Bound and Resource-Efficient Optimizer [0.0]
  本稿では、量子ハードウェア上でのユニタリ結合クラスタ波関数の最適化のための射影量子固有解法(PQE)アプローチについて検討する。 このアルゴリズムはシュル・オーディンガー方程式の射影を用いて、試行状態をハミルトニアンの固有状態に効率的に近づける。 我々は,BFGS法を用いて最適化されたarXiv:2102.00345とVQEの両方で導入された最適化よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-19T15:03:59Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。 一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
  論文  参考訳（メタデータ） (2023-11-01T19:51:00Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Quantum algorithms for approximate function loading [0.0]
  我々は,Grover-RudolphアルゴリズムにインスパイアされたNISQ時代の量子状態生成法を2つ導入した。 上述の滑らかさ条件を超えて関数をロードできる変分アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-15T17:36:13Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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