Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm

• URL: http://arxiv.org/abs/2604.15886v1
• Date: Fri, 17 Apr 2026 09:34:11 GMT
• Title: Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm
• Abstract summary: The best known quantum algorithm for the partial search problem is the Grover-Radhakrishnan-Korepin (GRK) algorithm.<n>We prove the optimality of GRK in the large-block limit.
• Score: 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.

Related papers

• Exact bounds on quantum partial search algorithm and improving the parallel search [8.460141119038388]
  Grover's algorithm provides a quadratic speedup over classical algorithms for searching unstructured databases.<n>The Grover-Radhakrishnan-Korepin (GRK) algorithm is widely regarded as the optimal protocol for this task.
  arXiv  Detail & Related papers  (2026-03-02T05:24:07Z)
• Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
  We build upon previous work by Baertschi and Eidenbenz to construct a state preparation routine for the Traveling Salesperson Problem.<n>With our iterations, we aim to achieve a reasonable approximation ratio with only a number of iterations.
  arXiv  Detail & Related papers  (2026-02-09T09:21:04Z)
• Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization [3.3508820106803796]
  We analyze generalizations of algorithms based on the short-path framework first proposed by Hastings. Under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups. We conclude the paper with a numerical analysis that guides the choice of parameters for short path algorithms.
  arXiv  Detail & Related papers  (2024-10-30T17:52:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
  arXiv  Detail & Related papers  (2020-09-11T17:31:39Z)
• Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
  We study the multi-armed bandit problem with subgaussian rewards. We show that a variant of the explore-then-commit (ETC) algorithm can achieve the optimality for multi-armed bandit problems.
  arXiv  Detail & Related papers  (2020-02-21T08:07:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.