論文の概要: Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition
- arxiv url: http://arxiv.org/abs/2608.23002v1
- Date: Mon, 24 Aug 2026 09:05:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-25 13:29:44.00515
- Title: Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition
- Title（参考訳）: ヒルベルト空間分解によるエクササイズと最適再帰量子探索
- Abstract要約: 量子探索への現在のアプローチは、根底にあるヒルベルト空間の既存の構造を深く活用することができない。
この構造に直接作用する新しい分解手法を提案する。
初期状態と目標状態がこの分割に分解されると、ダイナミクスは2次元平面の1つの回転に還元される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal $Θ(\sqrt{N})$ oracle and non-oracle gate counts. For spatial search on $d$-dimension grids, it recovers the $O(\sqrt{N})$ time for $d\geq3$ and the $O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$ bound of Aaronson and Ambainis for $d=2$. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.
- Abstract（参考訳）: 量子探索への現在のアプローチは、根底にあるヒルベルト空間の既存の構造を深く活用することができない。
この構造によって探索を分解することで、量子探索とアルゴリズム設計のための新しい戦略と定式化が実現される。
本稿では、ヒルベルト空間を再帰的に分解し、結果として生じる分割の反射から探索演算子を構成することにより、この構造に直接作用する新しい分解手法を提案する。
初期状態と目標状態がこの分割に分解されると、ダイナミクスはスカラー再帰によって与えられる角度で、各レベルで2次元平面の1つの回転に還元される。
この再帰は、各レベルの成功確率を分離して有界化することからエラーの蓄積を回避し、再帰を全体として扱える正確な状態記述を与える。
対象状態は決定論的に取得し,探索条件とは無関係にオラクルと非オラクルのコストを導出する。
非構造化探索に対して、我々の手法は同時に最適な $ s(\sqrt{N})$ oracle と non-oracle gate count を得る。
d$次元グリッド上の空間探索では、$O(\sqrt{N})$time for $d\geq3$と$O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$bound of Aaronson and Ambainis for $d=2$を回復する。
再帰の正確な記述は、我々の分解から新しい部分分割構造へと拡張され、量子アルゴリズム設計における再帰の適用と解析のための新しいアプローチを提供する。
関連論文リスト
- Ancilla-mediated fixed-point quantum search using Grover iterations [0.0]
グロバーの量子探索アルゴリズムは、非構造化データセットの基本的な二次的スピードアップを提供する。
本稿では,ロバスト収束を実現するアンシラを用いた固定点量子探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-08-30T15:13:14Z) - SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
データセットに対する経験的リスクは、自然に$N=nm$全サンプルに類似性を示す。
我々は悲観的な収束分析を避ける分析を提供する。
我々の成果は、既存の最先端の体制を改善した。
論文 参考訳（メタデータ） (2026-06-14T14:11:07Z) - Quantum Search without Global Diffusion [0.0]
量子探索は量子コンピューティングにおいて最も重要なアルゴリズムの一つである。
中心となるのは量子振幅増幅であり、古典的な探索よりも二次的なスピードアップを達成する技術である。
オラクルが唯一の大域演算子であるときに、このスピードアップを保存できることが示される。
論文 参考訳（メタデータ） (2026-04-16T18:00:27Z) - Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search [17.013842168748127]
RMN法は誤差$varepsilon$に対して2次収束率を数値的に達成し,O(sqrtN/M loglog (1/varepsilon)$の複雑さを示唆する。
論文 参考訳（メタデータ） (2026-03-27T03:19:27Z) - A Grover-compatible manifold optimization algorithm for quantum search [17.013842168748127]
グロバーのアルゴリズムは、非構造化探索問題に対して2次高速化を提供する基本量子アルゴリズムである。
我々はGroverのアルゴリズムがGroverのアルゴリズムによって達成された$O(qrstN)$のスピードアップと一致することを示す。
論文 参考訳（メタデータ） (2025-12-09T10:01:55Z) - Deterministic Quantum Search via Recursive Oracle Expansion [0.0]
本稿では,従来の確率論的探索手法の代替となる新しい決定論的量子探索アルゴリズムを提案する。
提案手法は,任意の位相回転に依存することなく,量子探索の本質的な不確実性を排除している。
クエリの複雑さが増大しているにもかかわらず、この設計は、少なくとも18キュービットまでの探索空間において、拡散に必要な2キュービットゲートの総数を1桁以上削減することを示した。
論文 参考訳（メタデータ） (2025-07-21T16:57:15Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。