論文の概要: Quantum algorithms for escaping from saddle points
- arxiv url: http://arxiv.org/abs/2007.10253v3
- Date: Thu, 19 Aug 2021 06:14:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 14:51:14.805131
- Title: Quantum algorithms for escaping from saddle points
- Title（参考訳）: サドルポイントからの脱出のための量子アルゴリズム
- Authors: Chenyi Zhang, Jiaqi Leng, Tongyang Li
- Abstract要約: 本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
- 参考スコア（独自算出の注目度）: 7.191453718557392
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We initiate the study of quantum algorithms for escaping from saddle points
with provable guarantee. Given a function $f\colon\mathbb{R}^{n}\to\mathbb{R}$,
our quantum algorithm outputs an $\epsilon$-approximate second-order stationary
point using $\tilde{O}(\log^{2} (n)/\epsilon^{1.75})$ queries to the quantum
evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical
state-of-the-art algorithm by Jin et al. with $\tilde{O}(\log^{6}
(n)/\epsilon^{1.75})$ queries to the gradient oracle (i.e., the first-order
oracle), our quantum algorithm is polynomially better in terms of $\log n$ and
matches its complexity in terms of $1/\epsilon$. Technically, our main
contribution is the idea of replacing the classical perturbations in gradient
descent methods by simulating quantum wave equations, which constitutes the
improvement in the quantum query complexity with $\log n$ factors for escaping
from saddle points. We also show how to use a quantum gradient computation
algorithm due to Jordan to replace the classical gradient queries by quantum
evaluation queries with the same complexity. Finally, we also perform numerical
experiments that support our theoretical findings.
- Abstract（参考訳）: 我々は、証明可能な保証で鞍点から逃れる量子アルゴリズムの研究を開始する。
関数 $f\colon\mathbb{R}^{n}\to\mathbb{R}$ が与えられたとき、我々の量子アルゴリズムは$\tilde{O}(\log^{2} (n)/\epsilon^{1.75})$の量子評価オラクルへのクエリ(つまりゼロ階のオラクル)を用いて$\epsilon$-approximate 2階定常点を出力する。
jinらによる古典的なstate-of-the-artアルゴリズムと比較して、$\tilde{o}(\log^{6} (n)/\epsilon^{1.75})$クエリは勾配オラクル(すなわち一階オラクル)に対して、我々の量子アルゴリズムは$\log n$の点で多項式的に優れ、その複雑さは$/\epsilon$の点で一致する。
技術的に、我々の主な貢献は、量子波方程式をシミュレートすることで勾配降下法における古典的な摂動を置き換えることである。
また、ヨルダンによる量子勾配計算アルゴリズムを用いて、従来の勾配クエリを同じ複雑性で量子評価クエリに置き換える方法を示す。
最後に,理論的な知見を裏付ける数値実験を行う。
関連論文リスト
- 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) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。
我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。
我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文 参考訳（メタデータ） (2023-04-27T14:02:54Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。