Estimated SDP polytopes and sound bounded-dual threshold exclusion

For every nonnegative $y$ with $\mathrm{\parallel }y{\mathrm{\parallel }}_1\le r$, the estimate discrepancy is bounded by $\mathrm{\mid }(\tilde{a}-a)\cdot y-(\tilde{c}-c)\mathrm{\mid }\le \theta \mathrm{\parallel }y{\mathrm{\parallel }}_1+\theta \le w\theta$. Hence an exact nonnegative trace slack implies $\tilde{a}\cdot y-\tilde{c}\ge -w\theta$, proving the first inclusion. Conversely an estimated slack at least $-w\theta$ implies $a\cdot y-c\ge -2w\theta$, proving the second. Multiplication by $R$ gives the statement for $X$, and $w=r+1\le 2r$ gives $2Rw\theta \le 4Rr\theta$. All objective, sign and norm constraints are retained exactly.

Index all actually invoked blocks in execution order by $i=1,2,\dots$ and let ${\mathcal{H}}_{i-1}$ record their prior classical history and the event that block $i$ is reached. Its input may depend on that history. Suppose its bad-output event $B_i$ satisfies $\mathrm{Pr}(B_i\mid {\mathcal{H}}_{i-1},i\text{ reached})\le {\delta }_i({\mathcal{H}}_{i-1})$ for every admissible history. Then $\mathrm{Pr}(i\text{ reached and }{B}_i)\le \mathbb{E}[{\mathbf{1}}_{i\text{ reached}}{\delta }_i]$ by conditioning. A union bound and nonnegative sums give $\mathrm{Pr}({\bigcup }_i\{i\text{ reached and }{B}_i\})\le \mathbb{E}{\sum }_i{\mathbf{1}}_{i\text{ reached}}{\delta }_i\le \delta$. For a known cap $B$ one may allocate ${\delta }_i=\delta \mathrm{/}B$; without a known cap use ${\delta }_i=\delta 2^{-i}$. This covers adaptive threshold/refinement paths without multiplying independent probabilities or union-bounding unmeasured quantum branches as if they were classical samples. Deterministic operator/numerical approximation errors must already have been included in each block's guarantee.

The dual slack $D^{\ast }={\sum }_j{y}_j^{\ast }{A}_j-C$ is positive semidefinite. The positive-product trace lemma [F2] gives $a\cdot y^{\ast }-c=\mathrm{tr}(D^{\ast }\rho )\ge 0$. Thus if $\alpha \ge v_D$, then $y^{\ast }\in P_0(\rho )$ and $\mathrm{\parallel }{y}^{\ast }{\mathrm{\parallel }}_1\le r$; step 1.1 implies $y^{\ast }\in \tilde{P}$. Taking the contrapositive proves $\tilde{P}=\mathrm{\varnothing }\Rightarrow \alpha <v_D$, including the equality endpoint. This argument works for every density matrix and therefore for a state selected adaptively from earlier rounds. It uses the bounded attained optimal dual itself; it does not assert that every unbounded-polytope feasible vector has bounded norm.

On the good event a returned multiplier has all the finite hypotheses of [F3]: nonnegative coordinates, norm at most $r$, objective at most $\alpha$, the shifted estimated-trace inequality, and the exact MMW states and losses specified in the Statement. That lemma therefore gives a feasible averaged dual vector with objective at most $\alpha +\gamma R$ if all $T$ rounds return multipliers. If an oracle instead returns its sound EMPTY outcome, step 2.1 gives $\alpha <v_D$. These are precisely the threshold alternatives needed for binary search on the dual optimum. Statistical failures outside the good event may produce either outcome incorrectly; their probability is budgeted rather than declared impossible.

On the complement of that union, every invoked oracle has its stated complete/sound contract and step 1.1 and step 2.1 and step 3.1 apply to every reached threshold. In particular a cap/search miss is permitted to generate the probabilistic HIGHER outcome only after proving that the complete round oracle's bad-output probability is included in the conditional budget. A low-level timeout or unresolved numerical comparison for which no such guarantee has been established remains a separate failure, not an emptiness certificate. This distinguishes a legitimate bounded-error threshold algorithm from either an unconditional emptiness assertion or an always-aborting threshold search.