Ancilla-mediated fixed-point quantum search using Grover iterations

• URL: http://arxiv.org/abs/2608.29839v1
• Date: Sun, 30 Aug 2026 15:13:14 GMT
• Title: Ancilla-mediated fixed-point quantum search using Grover iterations
• Abstract summary: Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets.<n>We present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence.
• Score: 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.

Related papers

• Quantum iterative approach to the Traveling Salesman Problem [0.6741942263052466]
  The Traveling Salesman Problem (TSP) is a classical NP-hard problem in optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases.<n>This work explores quantum computing as an alternative approach to address this complexity.<n>Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route.
  arXiv  Detail & Related papers  (2026-06-10T09:21:15Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search [17.013842168748127]
  We show that the RMN method numerically achieves a quadratic convergence rate with respect to the error $varepsilon$, implying a complexity of $O(sqrtN/M loglog (1/varepsilon)$.
  arXiv  Detail & Related papers  (2026-03-27T03:19:27Z)
• A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization [39.146761527401424]
  This work presents a rigorous worst-case runtime analysis of a measurement-driven quantum SAT solver.<n>We show that this quantum algorithm does not exclusively rely on Grover-type methods and shows promising numerical performance.<n>We also develop a new readout routine that efficiently finds a solution even for instances with multiple satisfying assignments.
  arXiv  Detail & Related papers  (2025-11-12T19:00:13Z)
• 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)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.