Adversary progress at initial and bounded-error final states

If Γ=0, then W_0=W_T=0 and both endpoint bounds hold. Assume Γ≠0. By [F6], choose a real orthonormal eigenbasis; the induced norm [F11] then gives a real unit eigenvector α of Γ with eigenvalue λ satisfying |λ|=||Γ||. Since Γ has only cross-output blocks, write Γ=[[0,B],[B^T,0]] with respect to the two nonempty output classes. The SVD [F8] and largest-singular-value characterization [F9] show ||Γ||=||B||: for any (a,b), ||Γ(a,b)||²=||Bb||²+||B^Ta||²≤||B||²(||a||²+||b||²), and a top right singular vector of B attains equality. The eigenvector equations imply α_0^{\mathsf T}Bα_1=λ||α_0||²=λ||α_1||²; because λ≠0, the class norms are equal, hence each is 1/√2. Initially all x-dependent states are identical, so W_0=Σ_xyΓ_xyα_xα_y=α^TΓα=λ.

By [F5], represent the terminal computation by unit vectors ψ_x and an output-one projection P. For x with f(x)=0 put a_x=Pψ_x, b_x=(I−P)ψ_x; for y with f(y)=1 put c_y=Pψ_y, d_y=(I−P)ψ_y. The per-input error hypothesis gives p_x=||a_x||²≤ε and q_y=||c_y||²≥1−ε. Orthogonality of the two measurement subspaces gives ⟨ψ_x|ψ_y⟩=⟨a_x|c_y⟩+⟨b_x|d_y⟩.

If ε=0, then a_x=d_y=0 for every opposite-output pair, so all such overlaps vanish and W_T=0. Suppose 0<ε<1/2. Set r=(1−ε)/ε, b=√(ε/(1−ε)), and a=rb=√((1−ε)/ε). Define u_x=(√a,a_x,√b,b_x) and v_y=(a^{-1/2}c_y,b^{-1/2}d_y). Then ⟨u_x|v_y⟩=⟨ψ_x|ψ_y⟩. Since a≥b, the bounds p_x≤ε and q_y≥1−ε give ||u_x||²≤aε+b(1−ε)=2√(ε(1−ε)), ||v_y||²≤(1−ε)/a+ε/b=2√(ε(1−ε)). Thus the cross-overlap matrix has a factorization with both squared vector norms at most c:=2√(ε(1−ε)).

Choose an orthonormal basis $(e_r)$ of the finite state space by [F7], and write $u_x={\sum }_r{u}_{xr}{e}_r$, $v_y={\sum }_r{v}_{yr}{e}_r$. For each r set $a_r=({\alpha }_x{u}_{xr}{)}_{x\in D_0}$ and $b_r=({\alpha }_y{v}_{yr}{)}_{y\in D_1}$. The cross-output contribution is ${\sum }_r{a}_r^{\ast }B{b}_r$. By Cauchy–Schwarz [F10] and the induced norm definition [F11], each term is bounded by $\mathrm{\parallel }B\mathrm{\parallel }\mathrm{\parallel }{a}_r\mathrm{\parallel }\mathrm{\parallel }{b}_r\mathrm{\parallel }$: the real SVD $B=U\mathrm{\Sigma }{V}^{\mathsf{T}}$ in [F8] also acts unitarily on complex coordinates, so [F9] gives $\mathrm{\parallel }B{b}_r\mathrm{\parallel }\le \mathrm{\parallel }B\mathrm{\parallel }\mathrm{\parallel }{b}_r\mathrm{\parallel }$. Summing and applying real Cauchy–Schwarz to the nonnegative norms gives $\mathrm{\parallel }B\mathrm{\parallel }{\sum }_r\mathrm{\parallel }{a}_r\mathrm{\parallel }\mathrm{\parallel }{b}_r\mathrm{\parallel }\le \mathrm{\parallel }B\mathrm{\parallel }({\sum }_x{\alpha }_x^2\mathrm{\parallel }{u}_x{\mathrm{\parallel }}^2{)}^{1\mathrm{/}2}({\sum }_y{\alpha }_y^2\mathrm{\parallel }{v}_y{\mathrm{\parallel }}^2{)}^{1\mathrm{/}2}$. By step 2.1 this is at most $c\mathrm{\parallel }B\mathrm{\parallel }\mathrm{\parallel }{\alpha }_0\mathrm{\parallel }\mathrm{\parallel }{\alpha }_1\mathrm{\parallel }=c\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }\mathrm{/}2$. The reverse-output block contributes the complex conjugate, hence $\mathrm{\mid }{W}_T\mathrm{\mid }\le c\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }=2\sqrt{ϵ(1-ϵ)}\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }$. Together with the $ϵ=0$ case this proves the endpoint bound.