論文の概要: Quantum spectral method for gradient and Hessian estimation
- arxiv url: http://arxiv.org/abs/2407.03833v1
- Date: Thu, 4 Jul 2024 11:03:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-08 18:22:43.893238
- Title: Quantum spectral method for gradient and Hessian estimation
- Title（参考訳）: 勾配とヘッセン推定のための量子スペクトル法
- Authors: Yuxin Zhang, Changpeng Shao,
- Abstract要約: 勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.193480001271463
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient descent is one of the most basic algorithms for solving continuous optimization problems. In [Jordan, PRL, 95(5):050501, 2005], Jordan proposed the first quantum algorithm for estimating gradients of functions close to linear, with exponential speedup in the black-box model. This quantum algorithm was greatly enhanced and developed by [Gily\'en, Arunachalam, and Wiebe, SODA, pp. 1425-1444, 2019], providing a quantum algorithm with optimal query complexity $\widetilde{\Theta}(\sqrt{d}/\varepsilon)$ for a class of smooth functions of $d$ variables, where $\varepsilon$ is the accuracy. This is quadratically faster than classical algorithms for the same problem. In this work, we continue this research by proposing a new quantum algorithm for another class of functions, namely, analytic functions $f(\boldsymbol{x})$ which are well-defined over the complex field. Given phase oracles to query the real and imaginary parts of $f(\boldsymbol{x})$ respectively, we propose a quantum algorithm that returns an $\varepsilon$-approximation of its gradient with query complexity $\widetilde{O}(1/\varepsilon)$. This achieves exponential speedup over classical algorithms in terms of the dimension $d$. As an extension, we also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method. The two algorithms have query complexity $\widetilde{O}(d/\varepsilon)$ and $\widetilde{O}(d^{1.5}/\varepsilon)$, respectively, under different assumptions. Moreover, if the Hessian is promised to be $s$-sparse, we then have two new quantum algorithms with query complexity $\widetilde{O}(s/\varepsilon)$ and $\widetilde{O}(sd/\varepsilon)$, respectively. The former achieves exponential speedup over classical algorithms. We also prove a lower bound of $\widetilde{\Omega}(d)$ for Hessian estimation in the general case.
- Abstract（参考訳）: 勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
ヨルダンは[Jordan, PRL, 95(5):050501, 2005] において、線形に近い関数の勾配を推定するための最初の量子アルゴリズムを提案し、ブラックボックスモデルでは指数的なスピードアップを行った。
この量子アルゴリズムは[Gily\'en, Arunachalam, and Wiebe, SODA, pp. 1425-1444, 2019]によって大幅に拡張され、$d$変数の滑らかな関数のクラスに対して、最適なクエリ複雑性を持つ量子アルゴリズムを提供する。
これは、同じ問題に対して古典的なアルゴリズムよりも2倍高速である。
この研究では、複素体上で十分に定義された解析関数 $f(\boldsymbol{x})$ という別の種類の函数に対して、新しい量子アルゴリズムを提案することで、この研究を継続する。
実部と虚部をそれぞれ$f(\boldsymbol{x})$で問うための位相オラクルが与えられたとき、クエリ複雑性$\widetilde{O}(1/\varepsilon)$で勾配の$\varepsilon$-approximationを返す量子アルゴリズムを提案する。
これにより、古典的アルゴリズムの次元$d$の指数的なスピードアップが達成される。
拡張として、ニュートン法の量子アナログを改善することを目的とした、ヘッセン推定のための2つの量子アルゴリズムを提案する。
2つのアルゴリズムはそれぞれ異なる仮定の下で、クエリ複雑性$\widetilde{O}(d/\varepsilon)$と$\widetilde{O}(d^{1.5}/\varepsilon)$を持つ。
さらに、ヘシアンが$s$スパースであると約束されている場合、クエリ複雑性を持つ2つの新しい量子アルゴリズムがそれぞれ$\widetilde{O}(s/\varepsilon)$と$\widetilde{O}(sd/\varepsilon)$である。
前者は古典的アルゴリズムよりも指数的なスピードアップを達成する。
また、一般の場合におけるヘッセン推定に対して、$\widetilde{\Omega}(d)$の低い境界も証明する。
関連論文リスト
- Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - 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 Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。