論文の概要: A Grover-compatible manifold optimization algorithm for quantum search

• arxiv url: http://arxiv.org/abs/2512.08432v1
• Date: Tue, 09 Dec 2025 10:01:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-10 22:28:07.906786
• Title: A Grover-compatible manifold optimization algorithm for quantum search
• Title（参考訳）: 量子探索のためのGrover互換多様体最適化アルゴリズム
• Authors: Zhijian Lai, Dong An, Jiang Hu, Zaiwen Wen,
• Abstract要約: グロバーのアルゴリズムは、非構造化探索問題に対して2次高速化を提供する基本量子アルゴリズムである。 我々はGroverのアルゴリズムがGroverのアルゴリズムによって達成された$O(qrstN)$のスピードアップと一致することを示す。
• 参考スコア（独自算出の注目度）: 17.013842168748127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem by alternately applying physically implementable oracle and diffusion operators. In this paper, we reformulate the unstructured search as a maximization problem on the unitary manifold and solve it via the Riemannian gradient ascent (RGA) method. To overcome the difficulty that generic RGA updates do not, in general, correspond to physically implementable quantum operators, we introduce Grover-compatible retractions to restrict RGA updates to valid oracle and diffusion operators. Theoretically, we establish a local Riemannian $μ$-Polyak-Łojasiewicz (PL) inequality with $μ= \tfrac{1}{2}$, which yields a linear convergence rate of $1 - κ^{-1}$ toward the global solution. Here, the condition number $κ= L_{\mathrm{Rie}} / μ$, where $L_{\mathrm{Rie}}$ denotes the Riemannian Lipschitz constant of the gradient. Taking into account both the geometry of the unitary manifold and the special structure of the cost function, we show that $L_{\mathrm{Rie}} = O(\sqrt{N})$ for problem size $N = 2^n$. Consequently, the resulting iteration complexity is $O(\sqrt{N} \log(1/\varepsilon))$ for attaining an $\varepsilon$-accurate solution, which matches the quadratic speedup of $O(\sqrt{N})$ achieved by Grover's algorithm. These results demonstrate that an optimization-based viewpoint can offer fresh conceptual insights and lead to new advances in the design of quantum algorithms.
• Abstract（参考訳）: Groverのアルゴリズムは、物理的に実装可能なオラクルと拡散演算子を交互に適用することにより、非構造化探索問題に対する2次高速化を提供する基本量子アルゴリズムである。 本稿では、ユニタリ多様体上の最大化問題として非構造探索を再構成し、リーマン勾配上昇法(RGA)を用いて解く。 一般のRGA更新が物理的に実装可能な量子演算子に対応しない難しさを克服するために、有効なオラクルや拡散演算子にRGA更新を制限するためにGrover互換のリトラクションを導入する。 理論的には、局所リーマン的$μ$-ポリアック-ジョジャシエヴィチ(PL)不等式を$μ= \tfrac{1}{2}$で定め、これは大域的な解に対して1-κ^{-1}$の線型収束率をもたらす。 ここで、条件番号 $κ = L_{\mathrm{Rie}} / μ$, ここで、$L_{\mathrm{Rie}}$ は勾配のリーマンリプシッツ定数を表す。 ユニタリ多様体の幾何学とコスト関数の特殊構造の両方を考慮すると、問題サイズ$N = 2^n$に対して$L_{\mathrm{Rie}} = O(\sqrt{N})$であることが分かる。 したがって、結果として生じる反復複雑性は$O(\sqrt{N} \log(1/\varepsilon)$で、Groverのアルゴリズムによって達成された$O(\sqrt{N})$の二次的なスピードアップと一致する$\varepsilon$-accurate解を得る。 これらの結果は、最適化に基づく視点が新しい概念的洞察を与え、量子アルゴリズムの設計に新たな進歩をもたらすことを示している。

関連論文リスト

• Quantum Algorithm for the Fixed-Radius Neighbor Search [39.58317527488534]
  本稿では,Grover アルゴリズムの固定点バージョンに基づく固定 RAdius Neighbor Search problem (FRANS) の量子アルゴリズムを提案する。 我々は,FRANSを,粒子数$N$の線形クエリ複雑性で解くための効率的な回路を導出する。 読み出し誤差に対するモデルのレジリエンスを評価し,結果の精度を確認するための誤り訂正フリー戦略を提案する。
  論文  参考訳（メタデータ） (2025-07-04T10:01:10Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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 Ground-State Preparation and Green's Function Calculation [5.28670135448572]
  周波数領域における多体グリーン関数の基底状態準備と計算のための射影量子アルゴリズムを提案する。 アルゴリズムはユニタリ演算(LCU)の線形結合に基づいており、基本的には量子資源のみを使用する。
  論文  参考訳（メタデータ） (2021-12-10T18:39:55Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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