Quantile minimum and coherent-score nondomination guarantee

Write $p=\mathrm{Pr}(\text{score}<v)$ for an incumbent. By the good/bad decomposition in [F2], after $q$ Grover iterations the success probability is $\mathrm{\mid }\mathrm{Im}(z^{2q+1}){\mathrm{\mid }}^2$ for $z=\sqrt{1-p}+i\sqrt{p}$; the same exact two-coordinate recurrence as in that lemma applies. The flag-only good branch has the normalized good projection, whose score/label measurement is therefore distributed as the original sampler conditioned on score $<v$. Direct successes have this same conditional distribution. Thus every verified improvement has that conditional distribution, with probability zero of improvement when $p=0$. For $0<p<1$, the finite geometric sum in [F2] also gives the random-iteration average $\frac{1}{2}-\mathrm{Im}(z^{4K})\mathrm{/}(4K\beta )$, where $\beta =2\sqrt{p(1-p)}$ and $K$ is the current stage cap.

Suppose the sampler preserves a uniform input index $j\in [m]$ and has bad-estimate probability at most $\nu$ for each $j$. In analysis only, replace its per-index output by the normalized good projection. The good subspace can depend on the true value; no implementation of that projector is assumed. For each $j$, a two-dimensional rotation takes the actual unit output to its good normalization with operator distance at most $2\sqrt{\nu }$: its angle has cosine $\sqrt{1-p_{bad}}$, so $2\sin (\gamma \mathrm{/}2)\le 2\sqrt{\nu }$. The direct sum of these rotations over the preserved index gives a unitary sampler replacement with the same operator bound. Inverses and controlled versions have the same bound. For at most $Q$ sampler calls, telescoping products gives output-vector error at most $2Q\sqrt{\nu }$, and any measured event changes by at most $4Q\sqrt{\nu }$. This also covers adaptive classical branches by retaining measurement results as orthogonal history registers.

If $p=0$, no improvement is possible and the incumbent already has strict-lower mass zero. For $0<p\le 1\mathrm{/}2$, put $\beta =2\sqrt{p(1-p)}\ge \sqrt{2p}$, $t=5\mathrm{/}(2\beta )\ge 5\mathrm{/}2$, and let $J$ be the first stage with $K_J\ge t$. For every subsequent stage, step 1.1 gives conditional Grover success at least $2\mathrm{/}5$; five bounded bit attempts make the random part accepted with probability at least $31\mathrm{/}32$, so stage survival is at most $49\mathrm{/}80$. The pre-threshold charge is at most $42t$: use ${\sum }_{j\le J}(4K_j+4)\le 12(3\mathrm{/}2{)}^J+8(J+1)$, $(3\mathrm{/}2{)}^J<(3\mathrm{/}2)t$, and $J+1\le 3t$. The remaining expected charge is at most ${\sum }_{h\ge 0}(49\mathrm{/}80{)}^h(6t(3\mathrm{/}2{)}^h+8)=960t\mathrm{/}13+640\mathrm{/}31$. Together these are below $128t$, hence below $256\mathrm{/}\sqrt{p}$. If $p>1\mathrm{/}2$, the direct sample alone makes stage survival at most $1\mathrm{/}2$, and total expected charge is at most ${\sum }_{j\ge 0}{2}^{-j}(4(3\mathrm{/}2{)}^j+8)=32\le 256\mathrm{/}\sqrt{p}$. Thus every verified improvement has expected charge at most $256\mathrm{/}\sqrt{p}$.

For clarity choose dyadic rank bands $[a,2a)$, $a=2^{\mathrm{\ell }}\mathrm{/}N$, truncated at one. If an incumbent lies in such a band, the next improvement has probability at least $1\mathrm{/}2$ of having rank below $a$. Indeed, under the distribution conditioned below the incumbent, the total mass of scores whose strict lower cumulative mass is less than $a$ is at least $a$; an atom crossing that cumulative threshold is included, so discreteness cannot reduce that mass. The conditional mass is at least $a\mathrm{/}q(v)\ge 1\mathrm{/}2$. Ranks decrease, so each band is entered at most once and has at most two visits in expectation. The expected charge until rank is below $1\mathrm{/}N$ is therefore at most $1+512\sqrt{N}{\sum }_{\mathrm{\ell }\ge 0}{2}^{-\mathrm{\ell }\mathrm{/}2}<2048\sqrt{N}$. Markov's inequality at the declared finite cap $100000\lceil \sqrt{N}\rceil$ gives trial failure below $1\mathrm{/}8$. Truncation is coupled to the precharged unbounded procedure: on paths whose hitting charge is within the cap, no precharge check stops the trial before its successful incumbent.

Independent trials each succeed with probability at least $7\mathrm{/}8$. Returning their smallest score preserves success whenever one trial succeeds, so the all-failure probability is at most $8^{-R}\le \delta$ by the exact rational cap test in [F1]. If $R>1$, minimality gives $8^{-(R-1)}>\delta$; applying the increasing logarithm and using $\ln (8^{R-1})=(R-1)\ln 8$ yields $R-1<\ln (1\mathrm{/}\delta )\mathrm{/}\ln 8$, with $\ln 8>0$ since $8>1$. This also gives $R=O(1+\ln (1\mathrm{/}\delta ))$ when $R=1$. A cutoff with $q(v)<1\mathrm{/}N$ is at or below any score whose cumulative mass is at least $1\mathrm{/}N$; this proves the minimum specialization. No probability of an exact score atom is assumed beyond the stated quantile/minimum promise.

Run the quantile algorithm with $N=m$ and confidence $\delta \mathrm{/}2$ on that ideal cleaned sampler, and choose $\nu \le (\delta \mathrm{/}(16Q){)}^2$. The ideal output is good and has less than $1\mathrm{/}m$ strict-lower score mass. Thus no index can have every good output score strictly below the returned score: that one index alone would contribute probability $1\mathrm{/}m$. The hybrid bound transfers this good-output/nondomination property to the implemented sampler with failure at most $\delta$. It does not require the selected score atom to have probability $1\mathrm{/}m$, does not union-bound unmeasured branches as classical samples, and does not infer a simultaneous deterministic table of all estimates. The separate planar oracle proof handles compatible completion of its two score orders.