論文の概要: Exact bounds on quantum partial search algorithm and improving the parallel search
- arxiv url: http://arxiv.org/abs/2603.01462v1
- Date: Mon, 02 Mar 2026 05:24:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-03 19:50:56.694026
- Title: Exact bounds on quantum partial search algorithm and improving the parallel search
- Title（参考訳）: 量子部分探索アルゴリズムの厳密な境界と並列探索の改善
- Authors: Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang, Vladimir Korepin,
- Abstract要約: グロバーのアルゴリズムは、非構造化データベースを探索する古典的なアルゴリズムを2次的に高速化する。
Grover-Radhakrishnan-Korepin (GRK)アルゴリズムは、このタスクの最適なプロトコルとして広く見なされている。
- 参考スコア（独自算出の注目度）: 8.460141119038388
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm provides a quadratic speedup over classical algorithms for searching unstructured databases and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is widely regarded as the optimal protocol for this task. In this work, we provide strong evidence for the strict optimality of the GRK operator sequence among all admissible compositions of global and local Grover operators. By exhaustively examining all operator sequences with a fixed number of oracle queries, we show that the GRK structure universally maximizes the success probability. Building on this result, we derive an asymptotically tight upper bound on the maximal success probability for partial search and establish a matching lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols achieves a strictly improved parallel efficiency. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.
- Abstract（参考訳）: グロバーのアルゴリズムは、構造化されていないデータベースを探索するための古典的なアルゴリズムを2次的に高速化し、その成功確率に厳密な制限があるオラクルクエリの複雑さにおいて厳密に最適であることが知られている。
通常のGrover検索は全検索設定ではさらに高速化できないが、精度とクエリの複雑さのトレードオフが部分探索問題を引き起こす。
Grover-Radhakrishnan-Korepin (GRK)アルゴリズムは、このタスクの最適なプロトコルとして広く見なされている。
本研究では、グローバルおよび局所グロバー作用素の許容可能なすべての構成のうち、GRK作用素列の厳密な最適性を示す強い証拠を提供する。
固定数のオラクルクエリで全演算子列を網羅的に調べることで、GRK構造が成功確率を普遍的に最大化することを示す。
この結果に基づいて,部分探索における最大成功確率の漸近的に厳密な上界を導出し,最小数のオラクルクエリに基づいて一致した下界を確立する。
さらに,部分探索フレームワーク内での並列量子探索について検討する。
GRKに基づく直接並列化は、確立された並列Groverスキームよりも優れているわけではないが、部分探索プロトコルと完全探索プロトコルを組み合わせたハイブリッド戦略は、厳密に改良された並列効率を実現することを実証する。
本研究では,量子部分探索の基本的限界と並列量子探索アルゴリズムの最適化におけるその役割を明らかにする。
関連論文リスト
- Search More, Think Less: Rethinking Long-Horizon Agentic Search for Efficiency and Generalization [64.61432234404276]
emphSearch More, Think Less (SMTL) は、効率性と一般化の両方をターゲットとした長期エージェント検索のためのフレームワークである。
我々は、教師付き微調整と強化学習を用いてエンドツーエンドエージェントを訓練し、ベンチマーク全体にわたって、強固で頻繁なパフォーマンスを実現する。
論文 参考訳（メタデータ） (2026-02-26T06:46:41Z) - Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
我々は,バッテッチとエーデンベンツの以前の研究に基づいて,旅行販売問題のための国家準備ルーチンを構築した。
イテレーションでは、数回のイテレーションだけで妥当な近似比を達成することを目指しています。
論文 参考訳（メタデータ） (2026-02-09T09:21:04Z) - A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search [0.0]
本稿では、パスフィニングタスクを構造化探索問題としてキャストすることで、完璧な迷路を解くための量子アルゴリズムを提案する。
グロバーの振幅増幅に基づいて、アルゴリズムは重ね合わせ中の全ての候補経路を符号化し、その目標に近接することを評価する。
グロバー互換のオラクルは、高い適合状態を示し、適応的なカットオフ戦略は、探索を反復的に洗練する。
論文 参考訳（メタデータ） (2025-07-29T15:51:19Z) - Deterministic Quantum Search via Recursive Oracle Expansion [0.0]
本稿では,従来の確率論的探索手法の代替となる新しい決定論的量子探索アルゴリズムを提案する。
提案手法は,任意の位相回転に依存することなく,量子探索の本質的な不確実性を排除している。
クエリの複雑さが増大しているにもかかわらず、この設計は、少なくとも18キュービットまでの探索空間において、拡散に必要な2キュービットゲートの総数を1桁以上削減することを示した。
論文 参考訳（メタデータ） (2025-07-21T16:57:15Z) - Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。
我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
論文 参考訳（メタデータ） (2025-05-13T01:24:09Z) - Hybrid Search for Efficient Planning with Completeness Guarantees [63.02803974708516]
本稿では,離散的な行動空間における完全性を実現するために,部分ゴール探索法を効果的に拡張する手法を提案する。
このソリューションは、高レベルの探索の実践的効率と低レベルの探索の完全性という、両方の世界のベストを達成している。
論文 参考訳（メタデータ） (2023-10-19T15:16:43Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Deterministic Grover search with a restricted oracle [2.976027966501599]
グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。
量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
論文 参考訳（メタデータ） (2022-01-01T02:04:11Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳（メタデータ） (2021-12-05T06:42:48Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Multi-layer quantum search and inclusion of NP into BQP [6.362434591714693]
本稿では,Groverのアルゴリズムを指数的に高速化する多層量子探索法を提案する。
その結果、量子回路の高速化はユビキタスであり、Groverの探索は実証されたよりもはるかに強力であることがわかった。
論文 参考訳（メタデータ） (2020-04-23T17:44:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。