Exact bounds on quantum partial search algorithm and improving the parallel search

• URL: http://arxiv.org/abs/2603.01462v1
• Date: Mon, 02 Mar 2026 05:24:07 GMT
• Title: Exact bounds on quantum partial search algorithm and improving the parallel search
• Abstract summary: 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.
• Score: 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.

Related papers

• Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm [8.110154079694063]
  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.
  arXiv  Detail & Related papers  (2026-04-17T09:34:11Z)
• Search More, Think Less: Rethinking Long-Horizon Agentic Search for Efficiency and Generalization [64.61432234404276]
  emphSearch More, Think Less (SMTL) is a framework for long-horizon agentic search that targets both efficiency and generalization.<n>We train an end-to-end agent using supervised fine-tuning and reinforcement learning, achieving strong and often state of the art performance across benchmarks.
  arXiv  Detail & Related papers  (2026-02-26T06:46:41Z)
• 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)
• A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search [0.0]
  We present a quantum algorithm for solving perfect mazes by casting the pathfinding task as a structured search problem.<n>Building on Grover's amplitude amplification, the algorithm encodes all candidate paths in superposition and evaluates their proximity to the goal.<n>A Grover-compatible oracle marks high-fitness states, and an adaptive cutoff strategy refines the search iteratively.
  arXiv  Detail & Related papers  (2025-07-29T15:51:19Z)
• Deterministic Quantum Search via Recursive Oracle Expansion [0.0]
  We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches.<n>Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations.<n>We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits.
  arXiv  Detail & Related papers  (2025-07-21T16:57:15Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  We propose an efficient and scalable symbolic search framework for complex queries.<n>Our framework reduces the computational load of symbolic methods by 90% while maintaining nearly the same performance.
  arXiv  Detail & Related papers  (2025-05-13T01:24:09Z)
• Hybrid Search for Efficient Planning with Completeness Guarantees [63.02803974708516]
  We propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search.
  arXiv  Detail & Related papers  (2023-10-19T15:16:43Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Deterministic Grover search with a restricted oracle [2.976027966501599]
  Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms. We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.
  arXiv  Detail & Related papers  (2022-01-01T02:04:11Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• 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)
• Multi-layer quantum search and inclusion of NP into BQP [6.362434591714693]
  We present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. Our results show that the speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated.
  arXiv  Detail & Related papers  (2020-04-23T17:44:51Z)

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.