論文の概要: Ancilla-mediated fixed-point quantum search using Grover iterations
- arxiv url: http://arxiv.org/abs/2608.29839v1
- Date: Sun, 30 Aug 2026 15:13:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.087724
- Title: Ancilla-mediated fixed-point quantum search using Grover iterations
- Title（参考訳）: グローバー反復を用いたアンシラによる不動点量子探索
- Abstract要約: グロバーの量子探索アルゴリズムは、非構造化データセットの基本的な二次的スピードアップを提供する。
本稿では,ロバスト収束を実現するアンシラを用いた固定点量子探索アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from $\mathcal{O}(N)$ to $\mathcal{O}(\sqrt{N})$. However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, $M$, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least $92.6\%$ with a query complexity of approximately $\mathcal{O}(\sqrt{N/M})$, effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.
- Abstract（参考訳）: グロバーの量子探索アルゴリズムは、非構造化データセットの基本的な二次的スピードアップを提供し、クエリの複雑さを$\mathcal{O}(N)$から$\mathcal{O}(\sqrt{N})$に還元する。
しかし、アルゴリズムの正確な反復数への依存は、過剰回転が成功確率の急激な低下をもたらす 'soufflé problem'' に繋がる。
この制限は、解状態数$M$が未知の場合、特に制限的である。
本研究では,解振幅を専用アンシラ量子ビットにマッピングすることで,ロバスト収束を実現するアンシラを介する固定点量子探索アルゴリズムを提案する。
既存の位相マッチング固定点法とは異なり、我々の手法はグロバーの実平面反射を利用して、元のアルゴリズムの直感的な幾何学的構造を維持する。
この手法は,約$\mathcal{O}(\sqrt{N/M})$のクエリ複雑度で少なくとも9,2.6 %$の成功確率を達成し,標準振幅増幅とロバストな固定点収束のギャップを効果的に埋めることを示した。
関連論文リスト
- Quantum iterative approach to the Traveling Salesman Problem [0.6741942263052466]
トラベリングセールスマン問題(TSP)は、最適化における古典的なNPハード問題であり、問題の規模が大きくなるにつれて、一組の都市で最短ルートを決定することは、計算的に禁止される。
この研究は、この複雑さに対処するための代替アプローチとして量子コンピューティングを探求する。
経路コストは量子位相として符号化され、QPEはそれらを効率的に評価できる一方、振幅増幅はGrover-Longアルゴリズムによって実装され、最適経路に向けた解空間を反復的に洗練する。
論文 参考訳（メタデータ） (2026-06-10T09:21:15Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - 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 measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization [39.146761527401424]
この研究は、測定駆動量子SATソルバの厳密な最悪の実行時解析を示す。
この量子アルゴリズムはGrover型法にのみ依存せず,有望な数値性能を示す。
また,複数のタスクを満足するインスタンスに対しても,効率的に解を見つける新しい読み出しルーチンを開発した。
論文 参考訳（メタデータ） (2025-11-12T19:00:13Z) - 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) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。