論文の概要: Fast Convex Optimization with Quantum Gradient Methods

• arxiv url: http://arxiv.org/abs/2503.17356v1
• Date: Fri, 21 Mar 2025 17:58:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-24 15:40:10.562469
• Title: Fast Convex Optimization with Quantum Gradient Methods
• Title（参考訳）: 量子勾配法による高速凸最適化
• Authors: Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, Marco Pistoia,
• Abstract要約: 雑音評価オラクルを用いた量子(サブ)次次推定に基づく量子アルゴリズムについて検討する。 古典的勾配勾配の1次クエリ複雑度は,雑音評価オラクルのみを用いて一致した。 我々は、これらのアルゴリズムをユークリッド以外の設定で動作させるように一般化する。
• 参考スコア（独自算出の注目度）: 2.5094874597551913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum algorithms based on quantum (sub)gradient estimation using noisy evaluation oracles, and demonstrate the first dimension independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. We match the first-order query complexities of classical gradient descent, using only noisy evaluation oracles, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. Specifically, for the smooth case, zeroth-order quantum gradient descent achieves $\widetilde{\mathcal{O}}(LR^2/\varepsilon)$ and $\widetilde{\mathcal{O}} \left( \kappa \log(1/\varepsilon \right))$ query complexities, for the convex and strongly convex case respectively; for the nonsmooth case, the zeroth-order quantum subgradient method attains a query complexity of $\widetilde{\mathcal{O}}((GR/\varepsilon)^2 )$. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent, dual averaging and mirror prox. We demonstrate how our algorithm for nonsmooth optimization can be applied to solve an SDP involving $m$ constraints and $n \times n$ matrices to additive error $\varepsilon$ using $\widetilde{\mathcal{O}} ((mn^2+n^{\omega})(Rr/\varepsilon)^2)$ gates, where $\omega \in [2,2.38)$ is the exponent of matrix-multiplication time and $R$ and $r$ are bounds on the primal and dual optimal solutions, respectively. Specializing to linear programs, we obtain a quantum LP solver with complexity $ \widetilde{\mathcal{O}}((m+\sqrt{n}) (Rr/\varepsilon)^2).$ For zero-sum games we achieve the best quantum runtimes for any $\varepsilon > 0$ when $m = \mathcal{O}(\sqrt{n})$. We obtain the best algorithm overall (quantum or classical) whenever we further impose $\varepsilon=\Omega((m+n)^{-1/4})$.
• Abstract（参考訳）: 雑音評価オラクルを用いた量子(サブ)勾配推定に基づく量子アルゴリズムについて検討し、滑らかかつ非滑らかな設定でゼロ階凸最適化のための1次元独立なクエリ複雑度(多対数因子まで)を実証する。 古典的勾配勾配の1次クエリ複雑度をノイズ評価オラクルのみを用いてマッチングし、量子と古典的ゼロ階最適化の指数関数的分離を示す。 具体的には、滑らかな場合において、ゼロ階量子勾配勾配は$\widetilde{\mathcal{O}}(LR^2/\varepsilon)$および$\widetilde{\mathcal{O}} \left( \kappa \log(1/\varepsilon \right))$クエリ複雑さをそれぞれ、凸と強凸のそれぞれに対して達成する。 次に、量子(サブ)勾配推定を用いて、これらのアルゴリズムを非ユークリッド環境での動作に一般化し、ミラー降下、双対平均化、ミラープロキシをインスタンス化する。 我々は、m$制約を含むSDPと$n \times n$行列を加算誤差に$\varepsilon$ using $\widetilde{\mathcal{O}} ((mn^2+n^{\omega})(Rr/\varepsilon)^2)$ gates, where $\omega \in [2,2.38)$は行列乗算時間の指数であり、$R$と$r$はそれぞれ原始最適解と双対最適解に有界であることを示す。 線形プログラムに特化して、複雑性 $ \widetilde{\mathcal{O}}((m+\sqrt{n}) (Rr/\varepsilon)^2) を持つ量子LPソルバを得る。 ゼロサムゲームに対しては、$m = \mathcal{O}(\sqrt{n})$ が任意の$\varepsilon > 0$に対して最高の量子ランタイムを達成する。 さらに$\varepsilon=\Omega((m+n)^{-1/4})$を課すと、全体的なアルゴリズム(量子または古典)を得る。

関連論文リスト

• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  本稿では,LCU演算子の線形結合として表現できる演算子の期待値を計算するための新しい手法を提案する。 この方法は任意の量子アルゴリズムに対して一般的であり、変分量子アルゴリズムの加速に特に関心がある。
  論文  参考訳（メタデータ） (2025-03-03T17:15:23Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。 代理オラクル関数に対するゼロ階量子推定器を構築する。
  論文  参考訳（メタデータ） (2024-10-21T16:52:26Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  Decoded Quantum Interferometry (DQI) という量子アルゴリズムを導入する。 有限体上のデータに近似するために、DQIは我々の知るどの時間よりも良い近似比を達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。 また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-04T11:03:48Z)
• Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
  我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。 我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
  論文  参考訳（メタデータ） (2024-02-20T06:23:36Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  本稿では,デジタルカウンセバティック量子最適化(DCQO)パラダイムを用いて,ポートフォリオ最適化のための高速なディジタル量子アルゴリズムを提案する。 提案手法は,アルゴリズムの回路深度要件を特に低減し,解の精度を向上し,現在の量子プロセッサに適している。 我々は,IonQトラップイオン量子コンピュータ上で最大20量子ビットを使用するプロトコルの利点を実験的に実証した。
  論文  参考訳（メタデータ） (2023-08-29T17:53:08Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
  量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。 また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
  論文  参考訳（メタデータ） (2022-12-05T19:10:32Z)
• 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)
• 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)
• Stochastic optimization algorithms for quantum applications [0.0]
  本稿では、一階法、二階法、量子自然勾配最適化法の使用法を概観し、複素数体で定義される新しいアルゴリズムを提案する。 全ての手法の性能は、変分量子固有解法、量子状態の量子制御、および量子状態推定に応用して評価される。
  論文  参考訳（メタデータ） (2022-03-11T16:17:05Z)
• Quantum Interior Point Methods for Semidefinite Optimization [0.16874375111244327]
  半定値最適化問題に対する2つの量子内点法を提案する。 第1のスキームは、不正確な探索方向を計算し、実現可能な点のみを探索することが保証されない。 第二のスキームはニュートン線形系のヌルスペース表現を用いて、不正確な探索方向であっても実現可能であることを保証する。
  論文  参考訳（メタデータ） (2021-12-11T16:52:25Z)
• Progress towards analytically optimal angles in quantum approximate optimisation [0.0]
  量子近似最適化アルゴリズム(Quantum Approximate optimization algorithm)は、量子プロセッサ上で実行される時間可変分割演算子である。 p=1$層の最適パラメータが1自由変数に減少し、熱力学の極限で最適角度を回復することが証明された。 さらに、重なり関数の勾配の消失条件は、回路パラメータ間の線形関係を導出し、キュービット数に依存しない類似の形式を持つことを示した。
  論文  参考訳（メタデータ） (2021-09-23T18:00:13Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• Warm-starting quantum optimization [6.832341432995627]
  最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。 これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。 同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
  論文  参考訳（メタデータ） (2020-09-21T18:00:09Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Measuring Analytic Gradients of General Quantum Evolution with the Stochastic Parameter Shift Rule [0.0]
  本研究では,量子計測から直接最適化される関数の勾配を推定する問題について検討する。 マルチキュービットパラメトリック量子進化の勾配を推定するアルゴリズムを提供する数学的に正確な公式を導出する。 私たちのアルゴリズムは、利用可能な全ての量子ゲートがノイズである場合でも、いくつかの近似で機能し続けています。
  論文  参考訳（メタデータ） (2020-05-20T18:24:11Z)

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

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