論文の概要: Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

• arxiv url: http://arxiv.org/abs/2604.15886v1
• Date: Fri, 17 Apr 2026 09:34:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-20 22:00:19.863615
• Title: Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm
• Title（参考訳）: Grover-Radhakrishnan-Korepinアルゴリズムの漸近最適性
• Authors: Kun Zhang, Kang-Yuan Chen, Xiao-Hui Wang, Vladimir Korepin,
• Abstract要約: 部分探索問題に対する最もよく知られた量子アルゴリズムは、Grover-Radhakrishnan-Korepin (GRK)アルゴリズムである。 大ブロック極限におけるGRKの最適性を証明する。
• 参考スコア（独自算出の注目度）: 8.110154079694063
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grover's algorithm is a cornerstone of quantum algorithms and is strictly optimal in oracle-query complexity. While the full search problem admits no further improvement, one may trade accuracy for speed in the partial search problem, where the task is to identify only the block containing the target item. The best known quantum algorithm for the partial search problem is the Grover-Radhakrishnan-Korepin (GRK) algorithm, whose optimality has long been conjectured but not proved. In this work, we prove the optimality of GRK in the large-block limit. We formulate partial search as a time-optimal control problem and apply the Pontryagin maximum principle to derive the switching-function dynamics, establish the bang-bang structure of regular extremals, and exclude non-optimal switching patterns. As a result, we show that the optimal regular extremal has the global-local-global form, which yields a control-theoretic proof of the asymptotic optimality of the GRK algorithm in oracle-query complexity.
• Abstract（参考訳）: グローバーのアルゴリズムは量子アルゴリズムの基礎であり、オラクル・クエリの複雑さにおいて厳密に最適である。 完全探索問題は更なる改善は認めないが、対象項目を含むブロックのみを特定するタスクである部分探索問題において、速度のトレードオフ精度を取引することができる。 部分探索問題の最もよく知られている量子アルゴリズムはGrover-Radhakrishnan-Korepin (GRK) アルゴリズムである。 本研究では,大ブロック極限におけるGRKの最適性を証明する。 時間-最適制御問題として部分探索を定式化し、ポントリャーギン最大原理を適用してスイッチング関数のダイナミクスを導出し、正規極小のバンバン構造を確立し、非最適スイッチングパターンを除外する。 その結果、最適正則極値が大域的-局所的-グローバルな形式であることを示し、これはオラクル-クエリの複雑性におけるGRKアルゴリズムの漸近的最適性の制御理論的証明をもたらす。

関連論文リスト

• Exact bounds on quantum partial search algorithm and improving the parallel search [8.460141119038388]
  グロバーのアルゴリズムは、非構造化データベースを探索する古典的なアルゴリズムを2次的に高速化する。 Grover-Radhakrishnan-Korepin (GRK)アルゴリズムは、このタスクの最適なプロトコルとして広く見なされている。
  論文  参考訳（メタデータ） (2026-03-02T05:24:07Z)
• Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
  我々は,バッテッチとエーデンベンツの以前の研究に基づいて,旅行販売問題のための国家準備ルーチンを構築した。 イテレーションでは、数回のイテレーションだけで妥当な近似比を達成することを目指しています。
  論文  参考訳（メタデータ） (2026-02-09T09:21:04Z)
• Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
  本稿ではHastingsが最初に提案したショートパスフレームワークに基づいてアルゴリズムの一般化を分析する。 一般的に満たされているいくつかの技術的条件の下では、適切な一般化は超4次スピードアップを達成することができる。 本論文は,短経路アルゴリズムのパラメータ選択を導く数値解析で締めくくった。
  論文  参考訳（メタデータ） (2024-10-30T17:52:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。 各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
  論文  参考訳（メタデータ） (2020-09-11T17:31:39Z)
• Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
  ガウス級報酬を用いたマルチアームバンディット問題について検討する。 本研究では,探索-then-commit (ETC) アルゴリズムの変種により,マルチアームバンディット問題に対する最適性が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-21T08:07:56Z)

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

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