arXiv · 19 Nov 2026
Query-Optimal Quantum Minimum Finding from Numerical Estimators
Egil Bae
Citations by database
Each database indexes a different set of journals, preprints and books, so they are shown side by side rather than blended.
- OpenCitations0
Citations per year
The current year is still counting.
- 2026 so far0
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/3$ on each of $N$ labels suffices to find a $2\varepsilon$-optimal label using $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 $p$ to objective values at most $a$. Without knowing $a$ or the prepared distribution, our algorithm returns a candidate and an estimate $v$ such that, jointly with constant probability, $v$ is $\varepsilon$-accurate for the candidate and $v\le a+\varepsilon$. The algorithm uses $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 $s_P$ and estimator workspace width $w$, it requires $O(s_P+w+\log\log(4/p))$ qubits, independently of the requested confidence. Applications give worst-case optimal $Θ(\sqrt N/η)$ queries for selecting an $η$-optimal bounded expectation, and guided ground-energy estimation using $O(ω^{-1})$ preparations and $O((ωη)^{-1})$ elementary controlled-evolution queries at constant confidence, where $ω$ is a lower bound on the guiding state's ground-space amplitude overlap.
What the data shows
- No database records a citation yet, as is usual for a paper this new.
Graph
This paper in the middle, its authors and their most-cited papers below, the papers it cites to the left and the papers citing it to the right. The timeline lays every paper out by year.
Select a node for its details. Drag to pan, scroll to zoom, drag a node to move it.
Start with
Cited by 0 papers
Who cites this paper, from open citation data, with Crossref's record of each; the 100 newest when there are more.
References (0)
What it cites, from open citation data, with Crossref's record of each.