betaFeedback

WorksPhysics and Astronomy

Query-Optimal Quantum Minimum Finding from Numerical Estimators

Abstract

We propose a quantum minimum-finding algorithm for objectives accessed via numerical estimators that avoids the logarithmic query overhead of amplifying the confidence of estimates before the search. A coherent estimator that is ε\varepsilon-accurate with probability at least 2/32/3 on each of NN labels suffices to find a 2ε2\varepsilon-optimal label using O(N)O(\sqrt N) base-estimator queries at constant confidence. The query bound and the additive-error constant are separately worst-case optimal. More generally, suppose a preparation assigns probability mass at least a known pp to objective values at most aa. Without knowing aa or the prepared distribution, our algorithm returns a candidate and an estimate vv such that, jointly with constant probability, vv is ε\varepsilon-accurate for the candidate and v≤a+εv\le a+\varepsilon. The algorithm uses O(p−1/2)O(p^{-1/2}) queries to each of the preparation and estimator oracles in the worst case, and the selected candidate can be retained as a quantum state. For preparation width sPs_P and estimator workspace width ww, it requires O(sP+w+log⁡log⁡(4/p))O(s_P+w+\log\log(4/p)) qubits, independently of the requested confidence. Applications give worst-case optimal Θ(N/η)Θ(\sqrt N/η) queries for selecting an ηη-optimal bounded expectation, and guided ground-energy estimation using O(ω−1)O(ω^{-1}) preparations and O((ωη)−1)O((ωη)^{-1}) elementary controlled-evolution queries at constant confidence, where ωω is a lower bound on the guiding state's ground-space amplitude overlap.

Introduction

Quantum minimum finding extends the quadratic advantage of quantum search [1, 2, 3] to finding the smallest of NN arbitrary values using O(N)O(\sqrt{N}) evaluations [4]. In numerical applications, the objective value may not be available directly, and each evaluation may itself involve an estimation procedure. For example, coherent simulation can be used to estimate an expected loss, while phase estimation can be used to estimate the energy of a quantum state. In this work, we consider estimators that, for every candidate, return a value within additive error ε\varepsilon of the objective with probability at least 2/3.

To avoid biasing the search towards poor candidates with low estimated values, a standard approach applies the estimator several times and takes the median of the outputs. Implemented coherently, this procedure can reduce the estimator’s failure probability to O(1/N)O(1/N) using O(log⁡N)O(\log N) repetitions. For bounded-error Boolean search, Høyer, Mosca, and de Wolf [5] showed that this logarithmic overhead can be avoided by interleaving amplitude amplification with error reduction. In case of numerical estimation, however, the probability of obtaining an accurate estimate may be distributed among many accurate output values, such that no individual value has probability greater than 1/21/2. Moreover, accurate estimates may give different orderings of candidates with similar objective values, or place the same candidate on opposite sides of a threshold. The probability that a candidate passes a threshold comparison depends on how often its estimates fall below the threshold. Lowering the threshold can reduce the acceptance probability by different amounts for different candidates and consequently change their relative probabilities of being selected.

Generalized minimum finding considers the problem of selecting a candidate with a low encoded score from an arbitrary prepared distribution, without requiring knowledge of the qualifying threshold [6]. The procedure requires O(p−1/2)O(p^{-1/2}) queries to the score-preparation unitary and its inverse to succeed with constant confidence, where pp is a known lower bound on the prepared probability mass of scores at most this threshold. When objective values are available only through numerical estimators, a standard approach is to first amplify the confidence of the estimator. More specifically, its failure probability is reduced to a sufficiently small constant multiple of pp, resulting in a total cost of O(p−1/2log⁡(2/p))O(p^{-1/2}\log(2/p)) base-estimator queries. Chen and de Wolf [7] use this approach to derive their approximate-unitary minimum-finding theorem from the generalized procedure, with a uniform preparation over NN labels and p=1/Np = 1/N. The same reduction is also used in the k=1k = 1 special case of Gao, Ji, and Wang [8]. With confidence amplification, both these approaches therefore use O(Nlog⁡(2N))O(\sqrt{N}\log(2N)) base-estimator queries and give an additive selection error of 2ε2\varepsilon. The factor 22 in this error bound cannot in general be improved, as we prove in Proposition 2.4.

We propose a quantum minimum-finding algorithm for general objectives accessed through numerical estimators that avoids the logarithmic overhead and attains the optimal additive selection error of 2ε2\varepsilon. For arbitrary prepared distributions, the algorithm achieves simultaneous O(p−1/2)O(p^{-1/2}) bounds on preparation and base-estimator queries at constant confidence. It returns a candidate together with an accurate estimate of its objective value. The selected candidate can be returned as a classical label or as a quantum state.

Main results

Consider first the special case of NN classical labels and a coherent estimator that is ε\varepsilon-accurate with probability at least 2/32/3 on every label. The objective values can be arbitrarily close and there can be arbitrarily many ties. We propose an algorithm that with constant confidence returns a label ss such that

f(s)≤min⁡if(i)+2ε.f(s) \le\min_i f(i) + 2\varepsilon.

The algorithm requires O(N)O(\sqrt{N}) queries to the base estimator and its inverse. The query scaling and the additive-error constant are individually worst-case optimal for 0<ε<1/20 < \varepsilon< 1/2.

In the general setting, assume that the estimator has the full unitary form A=∑iΠi⊗AiA = \sum_i \Pi_i \otimes A_i, where Πi\Pi_i are projectors onto objective sectors with corresponding objective values fif_i. Within each sector, all input states give the same distribution of estimates, including states entangled with other registers. This form of AA is stronger than preserving sector probabilities alone, as explained in § 2.

Let PP be a state preparation unitary and assume access to PP, AA, and their inverses. Write μ{f≤a}\mu\{f \le a\} for the probability that a measurement of the prepared state would yield an objective value at most aa. Assume that p∈(0,1]p \in(0,1] is known, and define

ap=min⁡{a:μ{f≤a}≥p}.a_p = \min\{a : \mu\{f \le a\} \ge p\}.

The value of apa_p is used only in the analysis and is not needed by the algorithm. Theorem 2.2 shows that, with probability at least 1−δ1-\delta, the algorithm returns a candidate together with an estimate vv of its objective value such that

∣v−Xout∣≤ε,v≤ap+ε,\lvert v-X_{\mathrm{out}}\rvert\le\varepsilon,\qquad v\le a_p+\varepsilon,

for any fixed 0<δ<1/20<\delta<1/2. Here XoutX_{\mathrm{out}} denotes the objective value that would be obtained if the returned candidate had been measured. Writing u=log⁡(2/δ)u=\log(2/\delta), the worst-case bounds on the preparation query count QPQ_P, estimator query count QAQ_A, and number of qubits SQS_Q are

QP=O(p−1/2u),QA=O(p−1/2u+u2),SQ=O(sP+w+log⁡log⁡(4/p)),Q_P=O(p^{-1/2}u),\qquad Q_A=O(p^{-1/2}u+u^2),\qquad S_Q=O(s_P+w+\log\log(4/p)),

where sPs_P and ww are the number of qubits used for preparation and for the estimator workspace, respectively. The result applies to both classical labels and unknown energy eigenspaces.

The algorithm is applied to bounded-expectation selection and ground-energy estimation. Combined with amplitude estimation, it gives the worst-case optimal bound of Θ(N/η)\Theta(\sqrt{N}/\eta) queries to the underlying coherent sampling oracle for selecting an η\eta-optimal bounded expectation at constant confidence. For ground-energy estimation, the algorithm uses phase estimation and a guiding state with ground-space amplitude overlap at least ω\omega. An additive-η\eta estimate can then be obtained using O(ω−1u)O(\omega^{-1}u) preparation queries and O((ωη)−1u)O((\omega\eta)^{-1}u) elementary controlled-evolution queries. No initial energy estimate is needed, and neither application requires a gap assumption.

Proof overview

The algorithm runs a sequence of trials to improve a current candidate (incumbent). Each trial seeks a new candidate with estimated value yy below the estimate τ\tau of the incumbent. The new candidate is accepted if additional estimates of its value pass validation, otherwise it is rejected. The same estimate yy can pass validation more often in one sector than in another. We therefore analyze the probability that a trial proposes a candidate from sector ii with estimate yy.

Let YiY_i be a new estimate in sector ii, and write qi−(y)=Pr⁡{Yi≤y}q_i^{-}(y)=\Pr\{Y_i\le y\} and qi+(y)=Pr⁡{Yi≥y}q_i^{+}(y)=\Pr\{Y_i\ge y\}. Let α\alpha and β\beta be constants satisfying 1/3<α<β<1/21/3<\alpha<\beta<1/2. If both the probabilities exceed α\alpha for a pair (i,y)(i,y), then yy must differ from the objective value in sector ii by at most ε\varepsilon. Such a pair (i,y)(i,y) is called acceptable. A pair is called good if both probabilities are at least β\beta. In every sector, an estimate gives a good pair with probability at least 1−2β1-2\beta.

The recursion follows Høyer et al. [5] by interleaving amplitude amplification with error reduction. In our construction, error reduction is performed by two coherent polynomial filters that suppress unacceptable pairs while preserving the weight of good pairs. The filters are constructed using linear-combination block encodings and singular value transformation with real polynomials [9]. If πi,y\pi_{i,y} is the initial probability of (i,y)(i,y) and eℓ(i,y)e_\ell(i,y) its probability of passing the filters at level ℓ\ell, the probability that a depth-jj trial produces the pair (i,y)(i,y) without recording a rejection is

cj(τ)2ωj(i,y)1{y<τ},ωj(i,y)=πi,y∏ℓ=0j−1eℓ(i,y).c_j(\tau)^2\omega_j(i,y)\mathbf{1}_{\{y<\tau\}},\qquad\omega_j(i,y)=\pi_{i,y}\prod_{\ell=0}^{j-1}e_\ell(i,y).

Since the weights ωj(i,y)\omega_j(i,y) are independent of τ\tau, and the amplification factor cj(τ)c_j(\tau) is common to all pairs, the relative proposal probabilities of the pairs with estimates below the threshold τ\tau are preserved when it is lowered. This allows us to analyze the progress of the algorithm using weights that do not depend on the previously accepted estimates.

At depth jj, we define the rank Rj(τ)R_j(\tau) as the total ωj\omega_j-weight of acceptable pairs with y<τy < \tau, and aim to reduce it below a prescribed upper bound, called the rank cap. Rank bounds established at earlier depths, together with the suppression of unacceptable pairs, give a lower bound on the amplification factor. If the current rank exceeds its cap, there is a smallest estimated value y∗y_* such that the total weight of acceptable pairs with estimates at most y∗y_* reaches the cap. Accepting a proposal with estimate y≤y∗y \le y_* lowers the threshold to yy, bringing the rank below the cap since only pairs with strictly smaller estimates are counted. The acceptable pairs with estimates at most y∗y_* have total weight at least the cap, so the proposal formula and validation completeness give a lower bound on the probability of such an update in every trial. Repetition therefore brings the rank below each cap with high probability, even when thresholds depend on previous trials or estimated values have ties.

Since the filters retain a fixed proportion of the initial weight of good pairs from sectors with objective value at most apa_p, a threshold τ>ap+ε\tau> a_p + \varepsilon gives a final rank of at least a constant times pp. Choosing the final rank cap below this amount therefore implies τ≤ap+ε\tau\le a_p + \varepsilon. With high probability, validation also ensures that the stored estimate differs from the objective value by at most ε\varepsilon, giving a final objective value of at most ap+2εa_p + 2\varepsilon.

The filters require O(j+1)O(j+1) estimator queries at level jj. Each recursive amplification step applies the preceding circuit twice and its inverse once, followed by a new filter. Consequently, the query cost of a depth-jj trial is O(3j−1)O(3^{j-1}). We choose the maximum depth KK such that 9K−1=Θ(1/p)9^{K-1} = \Theta(1/p), giving a maximum trial cost of O(3K−1)=O(p−1/2)O(3^{K-1}) = O(p^{-1/2}). The number of repetitions increases geometrically toward the cheaper lower depths, but at a rate that keeps the total query cost within the same bound. The query cost of validation is of lower order.

A reversible counter records the level of the first rejection, requiring only O(log⁡(K+1))O(\log(K+1)) qubits. On branches where no rejection has been recorded, the filter workspace is zero and can be reused. Since K=O(log⁡(2/p))K = O(\log(2/p)), this gives a total space bound of O(sP+w+log⁡log⁡(4/p))O(s_P + w + \log\log(4/p)).

Related work

Table 1 compares our algorithm with the previously discussed constructions of AGGW [6] and Chen and de Wolf [7]. Gao et al. [8] extend approximate minimum finding to the selection of kk distinct labels. In the special case k=1k = 1, their Algorithm 1 reduces to a single call to AGGW’s generalized minimum finder, using uniform preparation over labels followed by the numerical estimator. Appendix § 10 derives their query bounds under our oracle assumptions (Definition 2.1), using confidence amplification before search.

Optimal minimum finding with bounded-error comparisons was obtained by Wang and Ying [11]. Allcock et al. [12] give query and time bounds for search and minimization with subroutines that return a specified integer answer for each input with bounded error. The non-Boolean purification result of Belovs and Jeffery [13 Section 7] also assumes that one particular output occurs with probability greater than 1/21/2. A numerical estimator may instead distribute its success probability among several values within ε\varepsilon of the objective, with no individual value occurring with probability greater than 1/21/2. Quek et al. [14] consider comparisons that may be unreliable when the values being compared are close. Their result requires a local-density assumption, while our result allows arbitrarily close objective values and arbitrary ties.

Search with neutral inputs [15 Section 3.2] allows threshold decisions to be ambiguous. Its witness guarantee, however, does not specify how the probability of success is distributed among valid witnesses. For example, an algorithm satisfying this guarantee could always return the largest score below the incumbent. Each update would then reduce the rank only by the weight assigned to that score.

Comparisons with related work on bounded-expectation selection [16, 17] and ground-energy estimation [18, 19, 20] are given in § 6.

Organization

§ 2 formalizes the oracle model and the main results. The proof is developed in § 3–§ 5 through validation tests, coherent trials and the adaptive selection procedure. § 6 presents the applications and comparisons with existing methods. § 7 concludes the paper. The appendices contain supplementary proofs, implementation details and query comparisons for concrete constants.

Model and main results

We give a more formal statement of the oracle model and main results, and prove lower bounds on the number of estimator queries and the additive selection error. All systems are assumed to be finite-dimensional. We use the Euclidean norm for vectors and the spectral norm for operators. Logarithms are assumed to be natural unless a base is specified. The main parameters used throughout the paper are listed in Table 2.

SymbolMeaning
p,app, a_pKnown probability level pp and corresponding quantile apa_p, which is used only in the analysis
ε\varepsilonAdditive accuracy of the numerical estimator
δ,u\delta, uUpper bound δ\delta on the overall failure probability and u=log⁡(2/δ)u = \log(2/\delta)
sP,ws_P, wNumbers of qubits used for preparation and in the estimator workspace, respectively
v,L,Uv, L, UReturned estimate vv and endpoints L=v−εL = v - \varepsilon and U=v+εU = v + \varepsilon of the reported interval
τ,Rj(τ),K\tau, R_j(\tau), KCurrent estimate τ\tau, total weight Rj(τ)R_j(\tau) of acceptable pairs with estimates below τ\tau at depth jj, and maximum recursion depth KK
η\etaRequired additive accuracy in the applications
ω\omegaLower bound on the amplitude overlap of the guiding state with the ground space, giving p=ω2p = \omega^2

Table 2. Parameters used throughout the paper.

Oracle model

Let C\mathcal{C} be the candidate register and R\mathcal{R} the auxiliary registers of the preparation unitary PP. We consider a target of the form

F=∑i∈IfiΠi,0≤fi≤1,F = \sum_{i \in I} f_i \Pi_i, \qquad0 \leq f_i \leq1,

where II is finite and {Πi}\{\Pi_i\} is a family of mutually orthogonal projectors summing to the identity on C\mathcal{C}. Projectors can have rank greater than one. Classical labels correspond to the special case where Πi=∣i⟩⟨i∣\Pi_i = |i\rangle\langle i|. We assume access to the objective via the estimator below. We are not given the projectors, a method for preparation of states in different sectors, or an independent oracle for evaluation or measurement of FF.

Let PP be a unitary that prepares the state

∣Ω⟩CR=P∣0⟩.|\Omega\rangle_{CR} = P|0\rangle.

We denote by μi\mu_i the probability of obtaining sector ii in a hypothetical measurement of this state with the projectors {Πi}\{\Pi_i\}, so that

μi=∥(Πi⊗IR)∣Ω⟩∥2.\mu_i = \lVert(\Pi_i \otimes I_R)|\Omega\rangle\rVert^2.

For a set EE of objective values, we write μ{f∈E}=∑i:fi∈Eμi\mu\{f \in E\} = \sum_{i:f_i\in E}\mu_i for the probability that the measured value belongs to EE.

References

  1. [1]L. K. Grover. “A fast quantum mechanical algorithm for database search”. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC 1996). Pages 212–219. (1996). arXiv:quant-ph/9605043.arxiv.org/abs/quant-ph/9605043
  2. [2]C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. “Strengths and weaknesses of quantum computing”. SIAM Journal on Computing 26, 1510–1523 (1997). arXiv:quant-ph/9701001.DOI
  3. [3]M. Boyer, G. Brassard, P. Høyer, and A. Tapp. “Tight bounds on quantum searching”. Fortschritte der Physik 46, 493–505 (1998). arXiv:quant-ph/9605034.arxiv.org/abs/quant-ph/9605034
  4. [4]C. Dürr and P. Høyer. “A quantum algorithm for finding the minimum” (1996). arXiv:quant-ph/9607014.arxiv.org/abs/quant-ph/9607014
  5. [5]P. Høyer, M. Mosca, and R. de Wolf. “Quantum search on bounded-error inputs”. In Automata, Languages and Programming (ICALP 2003). Volume 2719 of Lecture Notes in Computer Science, pages 291–299. (2003). arXiv:quant-ph/0304052.DOI
  6. [6]J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf. “Quantum SDP-solvers: Better upper and lower bounds”. Quantum 4, 230 (2020). arXiv:1705.01843v4.DOI
  7. [7]Y. Chen and R. de Wolf. “Quantum algorithms and lower bounds for linear regression with norm constraints”. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:21. (2023). arXiv:2110.13886v2.
  8. [8]M. Gao, Z. Ji, and Q. Wang. “Quantum approximate k-minimum finding”. In 33rd Annual European Symposium on Algorithms (ESA 2025). Volume 351 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1–51:15. (2025). arXiv:2412.16586v1.DOI
  9. [9]A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). Pages 193–204. (2019). arXiv:1806.01838v1.DOI
  10. [11]Q. Wang and M. Ying. “Quantum algorithm for lexicographically minimal string rotation”. Theory of Computing Systems 68, 29–74 (2024).DOI
  11. [12]J. Allcock, J. Bao, A. Belovs, T. Lee, and M. Santha. “On the quantum time complexity of divide and conquer”. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:20. (2025). arXiv:2311.16401.DOI
  12. [13]A. Belovs and S. Jeffery. “Space-efficient quantum error reduction without log factors”. Quantum 10, 2039 (2026). arXiv:2502.09249v2.arxiv.org/abs/2502.09249
  13. [14]Y. Quek, C. L. Cannone, and P. Rebentrost. “Robust quantum minimum finding with an application to hypothesis selection” (2020). arXiv:2003.11777.arxiv.org/abs/2003.11777
  14. [15]T. Kociumaka, J. Nogler, and P. Wellnitz. “Near-optimal-time quantum algorithms for approximate pattern matching”. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 517–534. (2025). arXiv:2410.06808v1.arxiv.org/abs/2410.06808
  15. [16]D. Wang, X. You, T. Li, and A. M. Childs. “Quantum exploration algorithms for multi-armed bandits”. Proceedings of the AAAI Conference on Artificial Intelligence 35, 10102–10110 (2021). arXiv:2007.07449.
  16. [17]M. Hu, J.-q. Hu, and E. Zhou. “Quantum Grover adaptive search for discrete simulation optimization” (2026). arXiv:2604.26277v1.arxiv.org/abs/2604.26277
  17. [18]S. Jeffery and F. Witteveen. “Optimal quantum algorithm for ground-state energy estimation with a guiding state” (2026). arXiv:2608.24494v1.arxiv.org/abs/2608.24494
  18. [19]N. S. Mande and R. de Wolf. “Tight bounds for quantum phase estimation and related problems”. Quantum 10, 2140 (2026).DOI
  19. [20]R. D. Somma and R. de Wolf. “Optimal lower bound for ground-state energy estimation with a guiding state” (2026). arXiv:2608.24493v2.arxiv.org/abs/2608.24493
  20. [21]G. Brassard, P. Høyer, M. Mosca, and A. Tapp. “Quantum amplitude amplification and estimation”. In Quantum Computation and Information. Volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society (2002). arXiv:quant-ph/0005055.
  21. [22]E. Even-Dar, S. Mannor, and Y. Mansour. “Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems”. Journal of Machine Learning Research 7, 1079–1105 (2006). url: https://jmlr.org/papers/v7/evendar06a.html.DOI
  22. [23]A. Yu. Kitaev. “Quantum measurements and the Abelian Stabilizer Problem” (1995). arXiv:quant-ph/9511026.
  23. [24]S. Jeffery, R. D. Somma, F. Witteveen, and R. de Wolf. “Optimal ground-state preparation with a guiding state” (2026). arXiv:2609.38091v2.arxiv.org/abs/2609.38091
  24. [25]B. Chen, M. Gao, X. Wang, and S. Zhou. “Optimal query complexity for ground-state preparation” (2026). arXiv:2609.35668.arxiv.org/abs/2609.35668
  25. [26]A. Ambainis. “Quantum lower bounds by quantum arguments”. Journal of Computer and System Sciences 64, 750–767 (2002). arXiv:quant-ph/0002066.DOI
  26. [27]P. Høyer, T. Lee, and R. Špalek. “Negative weights make adversaries stronger”. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC 2007). Pages 526–535. (2007). arXiv:quant-ph/0611054.DOI

Paper details

vlnc:W_s68zs2ux
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

OpenAI’s ChatGPT

View statement
Looking for related papers…
Contents