Adversary Methods and Quantum Query Complexity

The cone $K=\{X\in {\mathbb{S}}^n:X⪰0\}$ is convex and closed because it is the intersection, over $v\in {\mathbb{R}}^n$, of the closed half-spaces $v^{T}Xv\ge 0$. It is self-dual for $⟨\cdot ,\cdot {⟩}_F$: if $X,Y⪰0$, diagonalize $X={\sum }_j{\lambda }_j{u}_j{u}_j^T$ by [F2], with ${\lambda }_j\ge 0$, to get $⟨X,Y{⟩}_F={\sum }_j{\lambda }_j{u}_j^{T}Y{u}_j\ge 0$; conversely, $⟨X,v{v}^T{⟩}_F=v^{T}Xv\ge 0$ for every $v$ implies $X⪰0$.

If $X$ is primal feasible and $y$ dual feasible, then $b^{T}y-⟨C,X{⟩}_F=⟨A^{\ast }y-C,X{⟩}_F\ge 0$ by self-duality in step 1.1. Thus weak duality gives $p^{\ast }\le d^{\ast }$.

Define $S=\{(A(X),⟨C,X{⟩}_F-r):X\in K,r\ge 0\}\subseteq {\mathbb{R}}^m\times \mathbb{R}$. This set is nonempty and convex by linearity and convexity of $K$. To prove it closed without making countably many witness choices, take any $z=(u,t)$ in the closure of $S$ and let $V=\{(u^{\mathrm{\prime }},t^{\mathrm{\prime }}):\mathrm{\parallel }{u}^{\mathrm{\prime }}-u\mathrm{\parallel }<1,\mathrm{\mid }{t}^{\mathrm{\prime }}-t\mathrm{\mid }<1\}$, an open neighborhood of $z$. For any point $(u^{\mathrm{\prime }},t^{\mathrm{\prime }})\in S\cap V$, a witness $X⪰0,r\ge 0$ satisfies $A(X)=u^{\mathrm{\prime }}$ and $t^{\mathrm{\prime }}=⟨C,X{⟩}_F-r$. Let $S_0=A^{\ast }{y}_0-C\succ 0$ be the strict dual slack and choose $\delta >0$ with $S_0⪰\delta I$ by [F2]. Self-duality from step 1.1 and $r\ge 0$ give $\delta \mathrm{tr}(X)\le ⟨S_0,X{⟩}_F=y_0^T{u}^{\mathrm{\prime }}-⟨C,X{⟩}_F\le y_0^T{u}^{\mathrm{\prime }}-t^{\mathrm{\prime }}$. Since $(u^{\mathrm{\prime }},t^{\mathrm{\prime }})\in V$, [F12] bounds the right side above by $\mathrm{\mid }{y}_0^{T}u\mathrm{\mid }+\mathrm{\parallel }{y}_0\mathrm{\parallel }+\mathrm{\mid }t\mathrm{\mid }+1$. Choose $B>0$ larger than this bound divided by $\delta$. Writing the nonnegative eigenvalues of $X$ as ${\lambda }_j$, [F2,F6] give $\mathrm{tr}(X)={\sum }_j{\lambda }_j$ and $\mathrm{\parallel }X{\mathrm{\parallel }}_F=({\sum }_j{\lambda }_j^2{)}^{1\mathrm{/}2}\le {\sum }_j{\lambda }_j$, so by [F2,F6], $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le \mathrm{tr}(X)\le B$; [F12] applied to the Frobenius pairing then gives $0\le r=⟨C,X{⟩}_F-t^{\mathrm{\prime }}\le \mathrm{\parallel }C{\mathrm{\parallel }}_{F}B+\mathrm{\mid }t\mathrm{\mid }+1$. Thus $S\cap V$ lies in the image under the continuous map $\mathrm{\Phi }(X,r)=(A(X),⟨C,X{⟩}_F-r)$ of the closed bounded set $\{(X,r):X⪰0,\mathrm{tr}(X)\le B,0\le r\le R\}$ for $R=\mathrm{\parallel }C{\mathrm{\parallel }}_{F}B+\mathrm{\mid }t\mathrm{\mid }+1$. This set is compact by [F5], so its image is compact by [F7] and closed by [F8]. Because that image is contained in $S$, and [F11] gives $z$ in the closure of $S\cap V$ (as $V$ is a neighborhood of $z$), it follows that $z\in S$. Hence $S$ is closed.

Fix any $\gamma >p^{\ast }$. The point $(b,\gamma )$ lies outside $S$, since $A(X)=b$ implies $⟨C,X{⟩}_F\le p^{\ast }<\gamma$ and subtracting $r\ge 0$ cannot increase it. By closedness in step 2.2 and [F3], there are $y\in {\mathbb{R}}^m$, $\alpha \in \mathbb{R}$, and $\beta \in \mathbb{R}$ such that $y^{T}u+\alpha t\le \beta <y^{T}b+\alpha \gamma$ for every $(u,t)\in S$. Taking $X=0$ and arbitrarily large $r$ shows $\alpha \ge 0$. If $\alpha =0$, the strict primal point $X_0$ has $A(X_0)=b$, contradicting $y^{T}b\le \beta <y^{T}b$; hence $\alpha >0$. Taking $(u,t)=(A(sX),⟨C,sX{⟩}_F)$ for arbitrary $X\in K,s\ge 0$ shows $⟨A^{\ast }y+\alpha C,X{⟩}_F\le 0$ for all $X\in K$. By the defining adjoint identity [F4] and self-duality, $y^{\mathrm{\prime }}=-y\mathrm{/}\alpha$ satisfies $A^{\ast }{y}^{\mathrm{\prime }}-C⪰0$. Since $(0,0)\in S$, $0\le \beta <y^{T}b+\alpha \gamma$, so $b^T{y}^{\mathrm{\prime }}=-y^{T}b\mathrm{/}\alpha <\gamma$.

Step 3.1 gives dual feasible values below every $\gamma >p^{\ast }$, hence $d^{\ast }\le p^{\ast }$; weak duality in step 2.1 gives equality. For primal attainment, let $c_0=⟨C,X_0{⟩}_F$ and consider $P=\{X⪰0:A(X)=b,⟨C,X{⟩}_F\ge c_0\}$. It is nonempty because $X_0\in P$, and closed by step 1.1 and continuity. For $S_0=A^{\ast }{y}_0-C\succ 0$, choose $\delta >0$ with $S_0⪰\delta I$. Every $X\in P$ satisfies $\delta \mathrm{tr}(X)\le ⟨S_0,X{⟩}_F=y_0^{T}b-⟨C,X{⟩}_F\le y_0^{T}b-c_0$, and the same eigenvalue calculation as in step 2.2 gives $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le \mathrm{tr}(X)$, so $P$ is bounded. By [F5], $P$ is compact, and [F9] makes the continuous objective attain a maximum there. Since the attained maximum is at least $c_0$, no feasible point outside $P$ can improve it; it equals $p^{\ast }$. For dual attainment, if $m=0$, the only dual variable is the given feasible $y_0=0$ and it attains $d^{\ast }$. Assume $m\ge 1$, let $K=(\ker A^{\ast }{)}^{\perp }$, and use [F10] to decompose each $y\in {\mathbb{R}}^m$ uniquely as $y=z+k$ with $z\in K$ and $k\in \ker A^{\ast }$. Since $b=A(X_0)$, $b^{T}k=k^{T}A(X_0)=⟨A^{\ast }k,X_0{⟩}_F=0$; thus projection to $z$ preserves both $A^{\ast }y$ and $b^{T}y$. The set $D=\{z\in K:A^{\ast }z-C⪰0,b^{T}z\le b^T{y}_0\}$ is nonempty (it contains the projection of $y_0$) and closed: $K$ is the intersection of the closed hyperplanes perpendicular to vectors in $\ker A^{\ast }$, and the PSD cone is closed by step 1.1. Put $T=A^{\ast }z-C$. Since $X_0\succ 0$, choose $\eta >0$ with $X_0⪰\eta I$; for $z\in D$, $\eta \mathrm{tr}(T)\le ⟨T,X_0{⟩}_F=b^{T}z-c_0\le b^T{y}_0-c_0$. The same eigenvalue calculation as in step 2.2 gives $\mathrm{\parallel }T{\mathrm{\parallel }}_F\le \mathrm{tr}(T)$, so $T$ is bounded and hence so is $A^{\ast }z=T+C$. On the unit sphere of $K$, the continuous function $z\mapsto \mathrm{\parallel }{A}^{\ast }z\mathrm{\parallel }$ is strictly positive because $K\cap \ker A^{\ast }=\{0\}$. The sphere is compact by [F5], so [F9] gives a positive minimum $\mu$; therefore $\mathrm{\parallel }{A}^{\ast }z\mathrm{\parallel }\ge \mu \mathrm{\parallel }z\mathrm{\parallel }$ for all $z\in K$, and $D$ is bounded. (If $K=\{0\}$, boundedness is immediate.) Thus $D$ is compact by [F5], and [F9] makes $b^{T}z$ attain its minimum on $D$. Any dual feasible point with objective above $b^T{y}_0$ cannot lower this minimum, while every other dual feasible point projects into $D$ without changing its objective. Hence this minimum equals $d^{\ast }$ and is attained.

By [F2], choose real vectors $a_1,\dots ,a_n$ with $A_{jk}=a_j^T{a}_k$ and real vectors $b_1,\dots ,b_n$ with $B_{jk}=b_j^T{b}_k$: diagonalize each matrix orthogonally and multiply each eigenvector coordinate by the square root of its nonnegative eigenvalue.

For each $j$, let $c_j\in {\mathbb{R}}^{n^2}$ have $(p,q)$-coordinate $(a_j{)}_p(b_j{)}_q$, and give ${\mathbb{R}}^{n^2}$ its standard dot product. Then $c_j^T{c}_k={\sum }_{p,q}(a_j{)}_p(b_j{)}_q(a_k{)}_p(b_k{)}_q=(a_j^T{a}_k)(b_j^T{b}_k)=A_{jk}{B}_{jk}$. Thus $A\circ B$ is the Gram matrix of the $c_j$. For every real vector $z$, $z^T(A\circ B)z={\parallel {\sum }_j{z}_j{c}_j\parallel }^2\ge 0$, so $A\circ B$ is positive semidefinite.

Put R_P=2P-I and R_D=2D-I. Since D w=0, R_D w=-w; hence U w=R_P R_Dw=-R_Pw and therefore P w=(w+R_Pw)/2=(I-U)w/2.

Let E_ω be the orthogonal spectral projection of U onto eigenvectors with eigenvalue e^{iφ} for a principal phase φ∈[-π,π] satisfying |φ|≤ω. By [F2], both reflections are unitary, so U is unitary. By [F3], E_ω commutes with U and has an orthonormal eigenbasis. Thus E_ω P w=(I-U)E_ωw/2, and on each selected eigenvector |1-e^{iφ}|≤|φ|≤ω. The squared norm in that basis is at most (ω/2)^2||E_ωw||²≤(ω/2)^2||w||².

Taking square roots proves ||E_ωP w||≤ω||w||/2, including zero- and full-rank projections because step 1.1 used only the projection identities.

The root state and all nonoracle instruments are input-independent by [F1]. Apply [F2] to those instruments only, retaining their observed outcomes and hidden dilation registers. Each dilation and each block control of a known nonoracle operation is then an input-independent unitary on finitely enlarged registers, allowed as a nonoracle operation in this query model; their gate and preparation costs are separate from oracle count. Retaining the orthogonal histories [F5] and using [F2] with the remaining registers as reference preserves the original branch output law. No oracle operation is dilated or replaced by an assumed controlled oracle.

Synchronize the finite execution tree by query number: before slot q, run each retained history's nonoracle segment until its qth query or termination, keeping terminated histories unchanged. These finite controlled segments are input-independent unitaries by step 1.1. At the slot, an active history presents its address and response to the query wires. On an inactive history, controlled swaps instead present a scratch address i_0 chosen as the first computational-basis label (the empty word for a zero-qubit address register) and a scratch target |+⟩=(|0⟩+|1⟩)/√2, preserving the algorithm registers. This address exists because the address register has positive dimension by [F4]. Apply one unconditional O_x and undo the routing swaps. Since X^{x_i}|+⟩=|+⟩ for every i, this acts identically on inactive histories and as the prescribed query on active ones, including their coherent superpositions.

Use slots q=1,…,T, then execute the final nonoracle segments and read the retained output records. Each slot contains exactly one unconditional oracle call by step 2.1, and step 1.1 adds none, so the total is exactly T, including zero when T=0. Histories with fewer queries are padded by inactive slots. Induction over the slots preserves each branch map and hence the final output law. All remaining operations and the initial state are input-independent; no controlled access to an unknown O_x or gate-efficiency bound is assumed.

The declared finite set D and map f give the promised decision problem. The extension $\tilde{x}$ is defined on every $a$-bit address, so [F2] gives its total XOR unitary. The span of the first $N$ address basis states is invariant, and identifying its word for $i-1$ with $\mathrm{\mid }i⟩$ gives exactly the displayed $O_x$; unused codewords are fixed because their extension bit is zero. Thus the local oracle is total on its $N$-address register, including when $N=1$ and $a=0$. The promise restricts x, not which address in $[N]$ may be queried.

The local Q_ε clause in the Definition counts the least worst-case number of designated calls to this oracle among algorithms correct with probability at least 1−ε on every promised input; [F3] supplies the general worst-case query-cost convention and excludes nonoracle gates. Equation (F4)'s ket convention fixes all later matrix and state formulas.

For every i∈[N], set (Δ_i){xy}=1 when x_i≠y_i and 0 otherwise; then Δ_i is a real symmetric Boolean matrix indexed by D×D. Define (A∘B){xy}=A_{xy}B_{xy} for matrices with the same row and column labels.

Set F_{xy}=1[f(x)=f(y)] and J_{xy}=1 for all x,y∈D. If x=y, every Δ_i(x,x)=0; if x≠y, then x and y differ in at least one coordinate, so at least one Δ_i(x,y)=1. Hence J−F is supported exactly on pairs with opposite outputs, and every diagonal entry is excluded by every query mask.

On H=C^N⊗H_response⊗H_work define Π_i=|i⟩⟨i|⊗I_response⊗I_work. Since ⟨i|j⟩=δ_{ij}, Π_iΠ_j=0 for i≠j and Π_i²=Π_i=Π_i*.

The ordered address basis resolves identity: Σ_i|i⟩⟨i|=I_{C^N}. Tensoring with the two identity factors gives Σ_iΠ_i=I_H. This includes every response and work state and proves the asserted resolution.

For each i, encode two finite vector families u_{x,i},v_{y,i} in a common finite-dimensional complex inner-product space. Their filtered factorization represents A exactly when A_{xy}=Σ_i(Δ_i){xy}⟨u{x,i}|v_{y,i}⟩_D for every ordered pair (x,y). The Dirac convention [F3] makes this expression conjugate-linear in each u factor and linear in each v factor.

The cost of a representation is max{max_xΣ_i||u_{x,i}||²,max_yΣ_i||v_{y,i}||²}; take the infimum over all finite-dimensional representations. If A_{xx}≠0 for some x, all Δ_i(x,x)=0 and no representation exists. If A has zero diagonal, each off-diagonal pair differs in some coordinate; assigning its entry to the first differing mask and writing $A^{(i)}$ for each resulting matrix, take $u_{x,i}=(\overline{A_{xy}^{(i)}}{)}_{y\in D}$ and $v_{y,i}=e_y$ in ${\mathbb{C}}^{\mathrm{\mid }D\mathrm{\mid }}$. Then $⟨u_{x,i}\mathrm{\mid }{v}_{y,i}{⟩}_D=A_{xy}^{(i)}$, so this is a feasible representation.

Thus the value is +∞ exactly when the diagonal support obstruction occurs, and otherwise the infimum ranges over a nonempty finite-dimensional class with a finite nonnegative cost. For any feasible family, restricting the ambient space for each i to the span of its 2|D| vectors preserves all inner products and norms and gives dimension at most 2|D|. Nonemptiness of D ensures that both maxima in the cost are defined.

Let x,y have opposite outputs. Then x≠y, so there is i with x_i≠y_i. The symmetric matrix with entries 1 at (x,y),(y,x) and zero elsewhere is an admissible nonzero Γ; at least one Γ∘Δ_i has norm 1, while all have norm at most 1. Thus every nonconstant f has a positive-denominator admissible matrix.

If Γ is admissible and nonzero, some Γ_xy≠0. By Γ∘F=0 its endpoints have opposite outputs, hence differ at some coordinate i. Then |Γ_xy|=|(Γ∘Δ_i)_{xy}|≤||Γ∘Δ_i||, so max_i||Γ∘Δ_i||>0. The same argument shows that the normalization max_i||Γ∘Δ_i||≤1 forces every entry |Γ_xy|≤1.

The normalized set of real symmetric Γ with Γ∘F=0 and max_i||Γ∘Δ_i||≤1 is closed and bounded in the finite-dimensional matrix space, hence compact by [F4]. It is nonempty by step 1.1. The norm is continuous since $\mathrm{\mid }\mathrm{\parallel }\mathrm{\Gamma }\mathrm{\parallel }-\mathrm{\parallel }{\mathrm{\Gamma }}^{\mathrm{\prime }}\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\parallel }\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\mathrm{\prime }}\mathrm{\parallel }\le \mathrm{\parallel }\mathrm{\Gamma }-{\mathrm{\Gamma }}^{\mathrm{\prime }}{\mathrm{\parallel }}_F$, so [F5] gives a finite attained maximum; by homogeneity this maximum is exactly the ratio supremum in the definition.

Let H=span{|start⟩}⊕(C^N⊗K⊗C²). The algorithm input requires |start⟩ to be unit and orthogonal to every query mode; hence |start⟩⟨start| is the orthogonal projection onto its span. It also labels the standard address basis by |i⟩=e_{i−1}, i∈[N]. Under the standard coordinate pairing in [F25], ⟨e_j,e_k⟩=Σ_rδ_{rj}δ_{rk}=δ_{jk}, so these address vectors and the response basis vectors are orthonormal. Therefore the query summands |i⟩⟨i|⊗I_K⊗|x_i⟩⟨x_i| are mutually orthogonal projections and are orthogonal to the start projection. Thus Π_x is an orthogonal projection.

Append a clean scratch bit u=0. In query mode, call O_x at address i to write u=x_i. In start mode route the oracle address to a fixed i_0∈[N] and apply H to u so the target is |+⟩; since X^{x_{i_0}}|+⟩=|+⟩, the unconditional oracle call leaves start unchanged. Apply a fixed phase −1 exactly when c=1, the mode is a query state, and z≠u; apply +1 on the start mode and when c=0. On query basis states this phase is +1 exactly when z=x_i, and −1 otherwise.

Call O_x again at the same address to reset u to 0 in query mode, using O_x²=I from [F22]. In start mode the second call again fixes |+⟩, and the final controlled H returns u to |0⟩. For c=1 the induced operator on H is 2Π_x-I; for c=0 it is I. Thus this fixed circuit realizes controlled R_{Π_x} with the plus-on-range sign specified in [F24], without a controlled unknown-oracle call. By linearity the same control/data action holds for arbitrary superpositions with the scratch returned clean.

Call Γ admissible when it is a nonzero real symmetric D×D matrix with Γ∘F=0. Define d(Γ)=max_{i∈[N]}||Γ∘Δ_i|| and set Adv±(f)=sup_Γ ||Γ||/d(Γ) for nonconstant f; for constant f set Adv±(f)=0.

By [F3], d(Γ)>0 for every nonzero admissible Γ and the supremum is a finite attained maximum when f is nonconstant. The entries of Γ need not be nonnegative; negative entries are permitted by this feasible set. Restricting to Γ≥0 entrywise gives the separate nonnegative adversary value, which is a smaller feasible set.

If A_{xx}≠0, the factorization equation at (x,x) has right side zero because every Δ_i(x,x)=0, so A is infeasible. If A has zero diagonal, assign each off-diagonal entry A_{xy} to the least i with x_i≠y_i, forming matrices A^{(i)} supported on Δ_i and satisfying A=Σ_i A^{(i)}. For d=|D|, put u_{x,i}=(\overline{A^{(i)}{x1}},…,\overline{A^{(i)}{xd}}) and v_{y,i}=e_y in C^d; then ⟨u_{x,i}|v_{y,i}⟩D=A^{(i)}{xy}. This is a finite feasible factorization.

For any feasible factorization in finite dimension, take, for each i, the span of the d vectors $u_{x,i}$ and d vectors $v_{y,i}$. It has dimension at most $2d$; by [F4] choose an orthonormal basis and map its vectors to their coordinates, padding with zero coordinates in ${\mathbb{C}}^{2d}$. This preserves every inner product and norm. Thus every feasible candidate has a representation in one fixed finite product of coordinate spaces ${\mathbb{C}}^{2d}$.

By step 1.1 choose one feasible family and let $K$ be its finite cost. Use step 2.1 to represent feasible families in a fixed finite product of copies of ${\mathbb{C}}^{2d}$, viewed as a positive-dimensional real Euclidean space; $d\ge 1$ by [F7]. The set of coordinate families satisfying the factorization equations and having cost at most $K$ is nonempty, closed, and bounded: the equations and cost are continuous, and each vector norm is at most $\sqrt{K}$. By [F5] this set is compact. Its continuous cost function attains a minimum by [F6]. Any feasible family with lower cost would also belong to this set, so the minimum equals the global infimum and is attained. Thus every feasible $A$ has an attained finite value, while nonzero diagonal is exactly the infeasible case.

The algorithm contains exactly two designated calls to O_x: one before the equality-controlled phase and one after it. Both calls occur for every value of the control bit; the inactive branch is protected by its scratch/response state but does not remove a designated invocation.

The second call is valid uncomputation because O_x is self-inverse, as recorded in [F1]. The equality test, phase gate, control logic and scratch preparation are nonoracle operations, so [F2] excludes them from query cost. Therefore the cost is exactly two queries.

For nonconstant $f$, choose $x,y\in D$ with $f(x)\mathrm{\ne }f(y)$ and put ${\mathrm{\Gamma }}_{xy}={\mathrm{\Gamma }}_{yx}=1$, with all other entries zero. This is a nonnegative admissible matrix; the inputs differ in some coordinate, so its mismatch denominator is exactly one. Hence the nonnegative feasible set contains a nonzero witness. Restrict the admissible matrices of [F1] to entrywise nonnegative matrices and use the same mismatch denominator; define their maximum ratio to be Adv(f), with value zero for constant f.

Let $K_{+}$ be the set of real symmetric matrices with $\mathrm{\Gamma }\circ F=0$, $\mathrm{\Gamma }\ge 0$, and $d(\mathrm{\Gamma }):={\max }_i\mathrm{\parallel }\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\mathrm{\parallel }\le 1$. It is closed because its linear and entrywise inequalities are closed and each filtered norm is continuous; the norm continuity follows from $\mathrm{\mid }\mathrm{\parallel }A\mathrm{\parallel }-\mathrm{\parallel }B\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\parallel }A-B\mathrm{\parallel }$. If $\mathrm{\Gamma }\in K_{+}$ has a nonzero entry ${\mathrm{\Gamma }}_{xy}$, then $f(x)\mathrm{\ne }f(y)$ and some coordinate i differs, so $\mathrm{\mid }{\mathrm{\Gamma }}_{xy}\mathrm{\mid }=\mathrm{\mid }(\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i{)}_{xy}\mathrm{\mid }\le \mathrm{\parallel }\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\mathrm{\parallel }\le 1$ by the operator-norm entry bound in [F2,F3]. Hence $K_{+}$ is bounded, and [F4] makes it compact. It is nonempty by step 1.1, so [F5] gives a finite maximum of the continuous norm on $K_{+}$. Every nonzero admissible matrix has positive denominator by [F2]; scaling identifies this normalized maximum with the ratio supremum, and a nonzero norm maximizer must have $d(\mathrm{\Gamma })=1$ because otherwise it could be scaled up in $K_{+}$. Thus the nonnegative maximum is finite and attained with the same normalization as Adv±.

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.

Choose x,y∈D with f(x)≠f(y). They are distinct bit strings, so x_i≠y_i for at least one i. Set Γ_{xy}=Γ_{yx}=1 and every other entry to zero. This Γ is nonzero and real symmetric; its only nonzero entries join opposite outputs, so Γ∘F=0.

The restriction of Γ to span{|x⟩,|y⟩} is [[0,1],[1,0]], whose eigenvalues are ±1; hence ||Γ||=1. For every i, Γ∘Δ_i is either Γ or zero, and at least one differing coordinate gives Γ itself. Thus max_i||Γ∘Δ_i||=1 and the ratio is one.

An input-independent unitary between queries preserves every pairwise inner product, so only the oracle slot changes progress. For inputs x,y, the product O_x^*O_y acts at address i as X^{x_i⊕y_i}; in the response eigenstate |−⟩=(|0⟩−|1⟩)/√2 this is −1 exactly when x_i≠y_i, and it is +1 on |+⟩. Therefore O_x^*O_y−I=−2Σ_iΔ_i(x,y)P_i^-, where P_i^- is the address-i projector tensored with |−⟩⟨−| on response and identity on work.

Let ψ_x be the pre-query state and define Q_i:C^D→H by Q_i|x⟩=α_xP_i^-ψ_x. Substituting step 1.1 into W_{t+1}−W_t and collecting entries gives W_{t+1}−W_t=−2Σ_i tr((Γ∘Δ_i)Q_i^*Q_i) because Γ∘Δ_i is real symmetric and relabeling the two indices gives the trace exactly.

Fix i and write $A_i=\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i$ and $R_i=Q_i^{\ast }{Q}_i$. By [F6], $A_i$ has a real orthonormal eigenbasis $(e_j)$ with eigenvalues ${\lambda }_j$, and $\mathrm{\parallel }{A}_i\mathrm{\parallel }={\max }_j\mathrm{\mid }{\lambda }_j\mathrm{\mid }$. Evaluating the basis-independent trace [F9] in this basis and using [F8] gives $\mathrm{tr}(A_i{R}_i)={\sum }_j{\lambda }_j\mathrm{\parallel }{Q}_i{e}_j{\mathrm{\parallel }}^2$, so $\mathrm{\mid }\mathrm{tr}(A_i{R}_i)\mathrm{\mid }\le \mathrm{\parallel }{A}_i\mathrm{\parallel }{\sum }_j\mathrm{\parallel }{Q}_i{e}_j{\mathrm{\parallel }}^2=\mathrm{\parallel }{A}_i\mathrm{\parallel }\mathrm{tr}(R_i)$. Evaluating $\mathrm{tr}(R_i)$ in the standard input basis yields ${\sum }_x\mathrm{\parallel }{Q}_i\mathrm{\mid }x⟩{\mathrm{\parallel }}^2$. Therefore ${\sum }_i\mathrm{tr}(R_i)={\sum }_x{\alpha }_x^2{\sum }_i\mathrm{\parallel }{P}_i^{-}{\psi }_x{\mathrm{\parallel }}^2\le {\sum }_x{\alpha }_x^2=1$, since the $P_i^{-}$ are orthogonal subprojections of identity. Hence $\mathrm{\mid }{W}_{t+1}-W_t\mathrm{\mid }\le 2{\max }_i\mathrm{\parallel }\mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\mathrm{\parallel }$.

For $A=J-F$, minimize $t$ over real symmetric blocks $Z_i=\left[\begin{array}{cc}{X}_i& W_i\\ W_i^T& Y_i\end{array}\right]⪰0$ subject to ${\sum }_i{\mathrm{\Delta }}_i\circ W_i=A$, ${\sum }_i{X}_i(xx)\le t$, and ${\sum }_i{Y}_i(yy)\le t$ for every input. By [F5,F6], each $Z_i$ is a Gram matrix of real vectors $u_{x,i},v_{y,i}$ with $W_i(x,y)=⟨u_{x,i}\mathrm{\mid }{v}_{y,i}{⟩}_D$ and the diagonal entries equal to their squared norms. Conversely, realify any complex feasible families by $u\mapsto (\mathrm{Re}u,\mathrm{Im}u)$ and $v\mapsto (\mathrm{Re}v,\mathrm{Im}v)$; norms are preserved and each real dot product is $\mathrm{Re}⟨u\mathrm{\mid }v{⟩}_D$. Since each target entry $A_{xy}$ is real, taking real parts preserves every constraint. Thus the real SDP has the filtered factorization value in [F12].

Add nonnegative scalar slacks $s_x=t-{\sum }_i{X}_i(xx)$ and $r_y=t-{\sum }_i{Y}_i(yy)$, and include $t\ge 0$, which is already forced by the PSD constraints. The equalities are $t-{\sum }_i{X}_i(xx)-s_x=0$, $t-{\sum }_i{Y}_i(yy)-r_y=0$, and ${\sum }_i{\mathrm{\Delta }}_i\circ W_i=A$. For unrestricted equality multipliers $p_x,q_y,\mathrm{\Lambda }$, the Lagrangian for minimizing $t$ is $L=t-{\sum }_x{p}_x(t-{\sum }_i{X}_i(xx)-s_x)-{\sum }_y{q}_y(t-{\sum }_i{Y}_i(yy)-r_y)+⟨\mathrm{\Lambda },A-{\sum }_i{\mathrm{\Delta }}_i\circ W_i{⟩}_F$. Its infimum over nonnegative scalar variables is finite only if $p_x,q_y\ge 0$ and ${\sum }_x{p}_x+{\sum }_y{q}_y\le 1$. The coefficient of $Z_i$ is $⟨H_i,Z_i{⟩}_F$, where $\mathrm{Diag}(p)$ is the diagonal matrix with entries $p_x$, similarly for $q$, and $H_i=\left[\begin{array}{cc}\mathrm{Diag}(p)& -({\mathrm{\Delta }}_i\circ \mathrm{\Lambda })\mathrm{/}2\\ -({\mathrm{\Delta }}_i\circ \mathrm{\Lambda }{)}^T\mathrm{/}2& \mathrm{Diag}(q)\end{array}\right]$. The factor $1\mathrm{/}2$ accounts for the two off-diagonal blocks in the Frobenius pairing [F3]. The infimum over $Z_i⪰0$ is finite exactly when $H_i⪰0$: a negative quadratic direction gives an unbounded rank-one ray, while PSD matrices pair nonnegatively. Hence the dual maximizes $⟨A,\mathrm{\Lambda }{⟩}_F$ subject to $p,q\ge 0$, $\sum p+\sum q\le 1$, and $H_i⪰0$ for each $i$.

The primal is strictly feasible: assign each opposite-output entry of $A$ symmetrically to its first differing coordinate, obtaining $W_i$ with ${\sum }_i{\mathrm{\Delta }}_i\circ W_i=A$. Choose ${\lambda }_i>\mathrm{\parallel }{W}_i\mathrm{\parallel }$ and set $X_i=Y_i={\lambda }_{i}I$; Cauchy--Schwarz [F10,F11] gives $2\mathrm{\mid }{a}^T{W}_{i}b\mathrm{\mid }\le \mathrm{\parallel }{W}_i\mathrm{\parallel }(\mathrm{\parallel }a{\mathrm{\parallel }}^2+\mathrm{\parallel }b{\mathrm{\parallel }}^2)$, so each $Z_i$ is positive definite. Choose $t>0$ large enough that every slack $s_x,r_y$ is positive. The dual in step 2.1 is strictly feasible at $p_x=q_y=1\mathrm{/}(4\mathrm{\mid }D\mathrm{\mid })$ and $\mathrm{\Lambda }=0$: every $H_i$ is positive definite and the scalar slack $1-\sum p-\sum q=1\mathrm{/}2$ is positive. The primal infimum is finite and nonnegative. For any primal-feasible $(Z_i,s,r,t)$ and dual-feasible $(p,q,\mathrm{\Lambda })$, the cross constraint gives $⟨A,\mathrm{\Lambda }{⟩}_F={\sum }_i⟨{\mathrm{\Delta }}_i\circ \mathrm{\Lambda },W_i{⟩}_F$, while the block constraints give $\mathrm{tr}(H_i{Z}_i)={\sum }_x{p}_x{X}_i(xx)+{\sum }_y{q}_y{Y}_i(yy)-⟨{\mathrm{\Delta }}_i\circ \mathrm{\Lambda },W_i{⟩}_F\ge 0$. Summing and using ${\sum }_i{X}_i(xx)\le t$, ${\sum }_i{Y}_i(yy)\le t$, $p,q\ge 0$, ${\sum }_x{p}_x+{\sum }_y{q}_y\le 1$, and $t\ge 0$ yields $⟨A,\mathrm{\Lambda }{⟩}_F\le ({\sum }_x{p}_x+{\sum }_y{q}_y)t\le t$. Since a primal feasible point with finite $t$ exists, this proves the derived dual supremum is finite; $p=q=\mathrm{\Lambda }=0$ is also dual feasible. Arrange all $Z_i,s,r,t$ as diagonal blocks of one PSD matrix and constrain off-block entries to zero; the strict point makes this matrix positive definite. Maximizing $-t$ is the standard primal in [F3], with standard dual objective $-⟨A,\mathrm{\Lambda }{⟩}_F$ and the block constraints from step 2.1. Both sides are strictly feasible and have finite values, so [F3] gives equal attained optima; reversing signs yields an attained primal minimum and dual maximum with common value.