paper

Query-Optimal Quantum Minimum Finding from Numerical Estimators

arXiv:2611.26606

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 -accurate with probability at least on each of labels suffices to find a -optimal label using 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 to objective values at most . Without knowing or the prepared distribution, our algorithm returns a candidate and an estimate such that, jointly with constant probability, is -accurate for the candidate and . The algorithm uses 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 and estimator workspace width , it requires qubits, independently of the requested confidence. Applications give worst-case optimal queries for selecting an -optimal bounded expectation, and guided ground-energy estimation using preparations and elementary controlled-evolution queries at constant confidence, where is a lower bound on the guiding state's ground-space amplitude overlap.