One oracle call changes adversary progress by at most filtered spectral norm

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 }$.