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

• arxiv url: http://arxiv.org/abs/2603.26039v1
• Date: Fri, 27 Mar 2026 03:19:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-30 21:49:48.340522
• Title: Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search
• Title（参考訳）: 最適化に基づく量子非構造探索における二重対数精度依存性の実現
• Authors: Zhijian Lai, Dong An, Jiang Hu, Zaiwen Wen,
• Abstract要約: 提案手法は,誤差$varepsilon$に対して2次収束率を達成し,精度で二重対数的な$O(sqrtNloglog (1/varepsilon)$を意味することを示す。 我々のアプローチはGrover互換であり、アルゴリズムの実装性を保証するため、Groverの標準的なオラクルと演算子にのみ依存している。
• 参考スコア（独自算出の注目度）: 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}\log (1/\varepsilon))$. In this work, we adopt the Riemannian modified Newton (RMN) method to solve the quantum search problem. We show that, in the setting of quantum search, 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 error $\varepsilon$, implying a complexity of $O(\sqrt{N}\log\log (1/\varepsilon))$, which is double-logarithmic in precision. Furthermore, our approach remains Grover-compatible, namely, it relies exclusively on the standard Grover oracle and diffusion 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}\log (1/\varepsilon))$の複雑性をもたらす。 本研究では,量子探索問題の解法として,リーマン修正ニュートン法(RMN)を用いる。 量子探索の設定において、リーマンのニュートン方向はリーマン勾配と共線型であることを示し、リーマン勾配は対応するリーマン・ヘッセンの固有ベクトルである。 その結果、追加オーバーヘッドを伴わずに、提案したRMN法は誤差$\varepsilon$に対する二次収束率を数値的に達成し、O(\sqrt{N}\log\log (1/\varepsilon))$の複雑さを示唆する。 さらに,提案手法はGrover互換であり,アルゴリズム実装性を確保するため,標準のGroverオラクルと拡散演算子のみに依存しており,パラメータ更新プロセスは従来のコンピュータで効率的にプリ計算可能である。

関連論文リスト

• 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)
• 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)
• 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)
• 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)

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

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