arXiv:2610.06364
Adaptive complete quantum search with unknown number of solutions
Raj Alexandru Guţoiu, Bogdan-Călin Ciobanu, Pantelimon George Popescu
Abstract
Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.
AI Summary
The paper studies finding all marked elements in an unstructured database when their number is unknown, accounting for candidate-verification time relative to amplitude amplification. It maintains a Bayesian posterior over the remaining solution count, removes each tested candidate, and greedily chooses classical sampling, Grover search, or Yoder–Low–Chuang (YLC) fixed-point search to maximize predictive success probability per cost. An instance with $m$ amplification iterations costs $m+r$, where $r$ is the verification-to-iteration time ratio; stopping uses a posterior tolerance. For known $M=o(N)$, Bellman and greedy analyses give asymptotically equal expected costs within this model, with per-attempt success approaching $0.84458$. When additionally $M\to\infty$, runtime approaches $1.38005\sqrt{NM}$, versus $1.57080\sqrt{NM}$ for exact search at every stage. A Fourier-coefficient argument proves that, for every posterior and $r\leq1/4$, YLC cannot improve the best classical/Grover greedy score. For larger $r$, depth-dependent bounds constrain its possible advantage and tolerable implementation overhead. Under a uniform-prior continuum approximation, the first quantum score crossing occurs at depth one for $r>1/4$; for fixed observed-success count and $r\to0$, preceding classical queries scale as $C_s^2/r^2-2B_s/r+O_s(1)$. Decision-tree calculations and paired Monte Carlo simulations support these results. Limitations include neglected active-space state-preparation overhead, ideal noiseless probabilities, and no general total-runtime optimality guarantee for unknown $M$. Fixed-point score bounds do not imply policy-runtime bounds, and simulated improvements are not uniform. Posterior stopping can leave solutions undiscovered; relaxing its tolerance increases this frequency.
Central claim may not hold: The proof of asymptotic optimality for known sparse solution counts drops a Bellman runtime finite difference inside a probability-normalized minimization without establishing the stronger control needed for actions with vanishing success probability.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages, 8 figures