Explicit median confidence guarantee for amplitude estimation

The threshold $88\mathrm{/}(7ϵ)$ is rational and exceeds $4\pi \mathrm{/}ϵ$ by [F22]. By [F26], powers of two are unbounded: choose a natural $q$ above any fixed real threshold by the Archimedean property and use induction to get $2^q\ge q+1$. Thus the doubling loop for $M$ terminates, and its first value above the threshold is the least such power; since $ϵ\le 1$ and $88\mathrm{/}7>8$, this value is at least $16$, so it is an admissible phase-register size and satisfies the one-run precision requirement. The rational target $(2\mathrm{/}\delta {)}^8$ is finite. Choose a natural $q>(2\mathrm{/}\delta {)}^8$ by [F26]; if $q$ is odd take $r=q$, and if $q$ is even take $r=q+1$. Then $r$ is positive odd and $2^r\ge 2^q\ge q+1>(2\mathrm{/}\delta {)}^8$, so the odd-increment loop for $r$ terminates at the least positive odd solution. Each comparison is exact rational arithmetic after clearing denominators.

Each run returns an algebraic estimate in the same real cyclotomic field $\mathbb{Q}({\zeta }_M+{\zeta }_M^{-1})$. Exact finite comparisons determine the middle order statistic; repetitions use independent fresh preparations and readouts by [F24].

From [F1]–[F2] and $ϵ\le 1$, a good run has error at most $ϵ\mathrm{/}4+{ϵ}^2\mathrm{/}16\le 5ϵ\mathrm{/}16<ϵ$. Its success probability is at least $p=8\mathrm{/}{\pi }^2>p_0:=98\mathrm{/}121$, so each failure indicator has mean at most $1-p_0$.

The output is one of the $r$ finite run estimates, and the odd sample size makes its middle index unique. Thus the procedure is defined for all stated rational inputs, with query and classical comparison costs remaining separate under [F23].

If the median lies outside $[a-ϵ,a+ϵ]$, at least $(r+1)\mathrm{/}2$ runs are failures. For their sum $S$, this entails $S-\mathbb{E}S\ge r(p_0-1\mathrm{/}2)$. Applying the two-sided additive bound [F3] to this containing event gives probability at most $2\exp (-2r(p_0-1\mathrm{/}2{)}^2)$.

Here $p_0-1\mathrm{/}2=75\mathrm{/}242$ and $c=2(75\mathrm{/}242{)}^2=5625\mathrm{/}29282$, so $8c>1$. By [F6], monotonicity and the logarithm product law turn $2^r\ge (2\mathrm{/}\delta {)}^8$ into $r\ln 2\ge 8\ln (2\mathrm{/}\delta )$. Put $L=\ln (2\mathrm{/}\delta )>0$. By [F5], $0<\ln 2<1$, so $r>8L$ and hence $cr>8cL>L$. The reciprocal law in [F6] gives $\ln (\delta \mathrm{/}2)=-L$, while the inverse identity gives $\ln (e^{-cr})=-cr<\ln (\delta \mathrm{/}2)$. Strict increase of $\ln$ therefore implies $2e^{-cr}<\delta$. Step 2.2 bounds median failure by this quantity, proving success at least $1-\delta$.