論文の概要: Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search

• arxiv url: http://arxiv.org/abs/2603.26039v2
• Date: Fri, 03 Apr 2026 03:09:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-06 12:42:34.065066
• Title: Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search
• Title（参考訳）: 最適化に基づく量子非構造探索における二重対数精度依存性の実現
• Abstract要約: RMN法は誤差$varepsilon$に対して2次収束率を数値的に達成し,O(sqrtN/M loglog (1/varepsilon)$の複雑さを示唆する。
• 参考スコア（独自算出の注目度）: 17.013842168748127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grover's algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems of size $N$. Recent studies have reformulated this task as a maximization problem on the unitary manifold and solved it via linearly convergent Riemannian gradient ascent (RGA) methods, resulting in a complexity of $O(\sqrt{N/M} \log (1/\varepsilon))$, where $M$ denotes the number of target items. In this work, we adopt the Riemannian modified Newton (RMN) method to solve the quantum search problem, under the assumption that the ratio $ M/N$ is known. We show that, in this setting, the Riemannian Newton direction is collinear with the Riemannian gradient in the sense that the Riemannian gradient is always an eigenvector of the corresponding Riemannian Hessian. As a result, without additional overhead, the proposed RMN method numerically achieves a quadratic convergence rate with respect to the error $\varepsilon$, implying a complexity of $O(\sqrt{N/M} \log\log (1/\varepsilon))$. Furthermore, our approach remains Grover-compatible, namely, it relies exclusively on the standard Grover diffusion and oracle operators to ensure algorithmic implementability, and its parameter update process can be efficiently precomputed on classical computers.
• Abstract（参考訳）: Groverのアルゴリズムは、N$の未構造化探索問題の2次高速化を実現する基本量子アルゴリズムである。 最近の研究は、この問題をユニタリ多様体上の最大化問題として再定義し、線型収束リーマン勾配上昇(RGA)法で解いた結果、$O(\sqrt{N/M} \log (1/\varepsilon))$が複雑になる。 本研究では、M/N$の比が知られているという仮定のもと、量子探索問題を解くためにリーマン修正ニュートン法(RMN)を採用する。 この設定では、リーマンのニュートン方向がリーマン勾配と余線型であることを示し、リーマン勾配は常に対応するリーマン・ヘッセンの固有ベクトルである。 その結果、追加オーバーヘッドを伴わずに、提案したRMN法は誤差$\varepsilon$に対して2次収束率を数値的に達成し、複雑さは$O(\sqrt{N/M} \log\log (1/\varepsilon)$となる。 さらに,提案手法はGrover互換であり,アルゴリズム実装性を確保するため,標準のGrover拡散演算子とオラクル演算子にのみ依存しており,パラメータ更新プロセスは従来のコンピュータで効率的にプリ計算可能である。

関連論文リスト

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• A Grover-compatible manifold optimization algorithm for quantum search [17.013842168748127]
  グロバーのアルゴリズムは、非構造化探索問題に対して2次高速化を提供する基本量子アルゴリズムである。 我々はGroverのアルゴリズムがGroverのアルゴリズムによって達成された$O(qrstN)$のスピードアップと一致することを示す。
  論文  参考訳（メタデータ） (2025-12-09T10:01:55Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Riemannian Bilevel Optimization [35.42472057648458]
  特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。 本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。 様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
  論文  参考訳（メタデータ） (2024-05-22T20:49:01Z)
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
  tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。 軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
  論文  参考訳（メタデータ） (2024-05-05T22:53:14Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximation [11.925232472331494]
  非線形関数近似を用いたQラーニング問題を解くため,ガウスニュートン時間差分法(GNTD)学習法を提案する。 各イテレーションにおいて、我々の手法は1つのガウスニュートン(GN)ステップを踏んで平均二乗ベルマン誤差(MSBE)の変種を最適化する。 いくつかのRLベンチマークにおいて、GNTDはTD型よりも高い報酬と高速な収束を示す。
  論文  参考訳（メタデータ） (2023-02-25T14:14:01Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• On Riemannian Gradient-Based Methods for Minimax Problems [24.199289678553896]
  ミニマックス問題を解くためのリーマン的手法のクラスを提案する。 我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。 また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
  論文  参考訳（メタデータ） (2020-10-13T00:54:00Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold [7.257751371276488]
  R-ProxSGDとR-ProxSPBは、近位SGDと近位SpiderBoostの一般化である。 R-ProxSPBアルゴリズムは、オンラインの場合で$O(epsilon-3)$ IFOs、有限サムの場合は$O(n+sqrtnepsilon-3)$ IFOsである。
  論文  参考訳（メタデータ） (2020-05-03T23:41:35Z)

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

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