論文の概要: Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation

• arxiv url: http://arxiv.org/abs/2502.04285v1
• Date: Thu, 06 Feb 2025 18:32:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-07 14:32:13.750623
• Title: Exponentially Better Bounds for Quantum Optimization via Dynamical Simulation
• Title（参考訳）: 動的シミュレーションによる量子最適化のための指数的に優れた境界
• Authors: Ahmet Burak Catli, Sophia Simon, Nathan Wiebe,
• Abstract要約: 我々は、勾配推定を必要としない連続的な最適化のために、いくつかの量子アルゴリズムを提供する。 我々は、最適化問題を物理系の力学にエンコードし、時間進化をコヒーレントにシミュレートする。
• 参考スコア（独自算出の注目度）: 0.5097809301149342
• License:
• Abstract: We provide several quantum algorithms for continuous optimization that do not require any gradient estimation. Instead, we encode the optimization problem into the dynamics of a physical system and coherently simulate the time evolution. This allows us, in certain cases, to obtain exponentially better query upper bounds relative to the best known upper bounds for gradient-based optimization schemes which utilize quantum computers only for the evaluation of gradients. Our first two algorithms can find local optima of a differentiable function $f: \mathbb{R}^N \rightarrow \mathbb{R}$ by simulating either classical or quantum dynamics with friction via a time-dependent Hamiltonian. We show that these methods require $O(N\kappa^2/h_x^2\epsilon)$ queries to a phase oracle to find an $\epsilon$-approximate local optimum of a locally quadratic objective function, where $\kappa$ is the condition number of the Hessian matrix and $h_x$ is the discretization spacing. In contrast, we show that gradient-based methods require $O(N(1/\epsilon)^{\kappa \log(3)/4})$ queries. Our third algorithm can find the global optimum of $f$ by preparing a classical low-temperature thermal state via simulation of the classical Liouvillian operator associated with the Nos\'e Hamiltonian. We use results from the quantum thermodynamics literature to bound the thermalization time for the discrete system. Additionally, we analyze barren plateau effects that commonly plague quantum optimization algorithms and observe that our approach is vastly less sensitive to this problem than standard gradient-based optimization. Our results suggests that these dynamical optimization approaches may be far more scalable for future quantum machine learning, optimization and variational experiments than was widely believed.
• Abstract（参考訳）: 我々は、勾配推定を必要としない連続的な最適化のために、いくつかの量子アルゴリズムを提供する。 代わりに、最適化問題を物理系の力学にエンコードし、時間進化をコヒーレントにシミュレートする。 これにより、ある場合において、勾配の評価のみに量子コンピュータを利用する勾配に基づく最適化スキームにおいて、最もよく知られた上限に対して指数関数的に優れたクエリ上界が得られる。 最初の2つのアルゴリズムは微分可能関数 $f: \mathbb{R}^N \rightarrow \mathbb{R}$ の局所最適性を見つけることができる。 これらの手法は位相オラクルへの$O(N\kappa^2/h_x^2\epsilon)$クエリを必要とし、局所二次目的関数の$\epsilon$-approximate局所最適化を求める。 対照的に、勾配に基づく手法は$O(N(1/\epsilon)^{\kappa \log(3)/4})$クエリを必要とする。 第3のアルゴリズムは、古典的リウィリア作用素とNos\e Hamiltonianのシミュレーションにより、古典的な低温熱状態を作成することで、大域的な$f$の最適値を見つけることができる。 我々は、離散系の熱化時間を制限するために、量子熱力学の文献による結果を使用する。 さらに、量子最適化アルゴリズムをよく悩ませるバレンプラトー効果を分析し、我々のアプローチが標準勾配に基づく最適化よりもこの問題に非常に敏感でないことを観察する。 我々の結果は、これらの動的最適化アプローチは、広く信じられていたよりも、将来の量子機械学習、最適化、変分実験においてはるかにスケーラブルである可能性を示唆している。

関連論文リスト

• 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)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。 最初の設定について、Omegabig(frac-1+ppp)$。 第二設定については、おめがの()$。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。
  論文  参考訳（メタデータ） (2022-12-07T19:02:36Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth [0.0]
  変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。 最適化問題の解法における絡み合いの役割について検討する。 ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
  論文  参考訳（メタデータ） (2022-07-07T16:21:36Z)
• 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)
• Progress towards analytically optimal angles in quantum approximate optimisation [0.0]
  量子近似最適化アルゴリズム(Quantum Approximate optimization algorithm)は、量子プロセッサ上で実行される時間可変分割演算子である。 p=1$層の最適パラメータが1自由変数に減少し、熱力学の極限で最適角度を回復することが証明された。 さらに、重なり関数の勾配の消失条件は、回路パラメータ間の線形関係を導出し、キュービット数に依存しない類似の形式を持つことを示した。
  論文  参考訳（メタデータ） (2021-09-23T18:00:13Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Approximate optimization of MAXCUT with a local spin algorithm [0.0]
  局所テンソル法は[Hastings,arXiv: 1905.07047v2]で導入された最適化アルゴリズムのクラスである。 MAXCUT問題のインスタンス上でのベンチマーク実験により,実際の性能について検討する。 局所テンソル法による解法は,広く使用されている商用最適化パッケージの解法とは全く関係がない。
  論文  参考訳（メタデータ） (2020-08-13T18:00:00Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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