Dual reflection evaluator has bounded-error correctness

Use the supplied finite dual certificate from [F21] and its bound A≥max{C_0,C_1,1}; the domain condition A≥1 agrees with [F22]. The algorithm input specifies |start⟩ to be a unit vector orthogonal to the query summand. In the finite space H=span{|start⟩}⊕(C^N⊗V⊗C^2), define ν_x=1+(1/(2A))Σ_i||v_{x,i}||², |ψ_x⟩=ν_x^{-1/2}(|start⟩+(1/√(2A))Σ_i|i⟩|v_{x,i}⟩|x_i⟩). The start mode and distinct addresses are orthogonal, so ||ψ_x||²=ν_x^{-1}ν_x=1.

Let Δ be the orthogonal projection onto span{|ψ_y⟩:f(y)=1}, and let Π_x be the consistency projection onto |start⟩ and query states with response x_i. Set R_Δ=2Δ−I, R_{Π_x}=2Π_x−I, and U_x=R_{Π_x}R_Δ in exactly this order. [F25] makes both reflections unitary involutions. Controlled U_x is implemented by first applying controlled R_Δ and then controlled R_{Π_x} using [F26]; the first is input-independent, and the second is supplied by [F23]. Preserve the exact signs: the standalone state-phase invariance in [F27] does not permit changing the controlled powers, and [F28] makes a scalar phase on their target unitary a relative control phase.

Choose M=2^m to be the least power of two with M≥512A. Run the circuit [F29] on U_x with input |start⟩, implementing each controlled U_x^{2^j} by 2^j repetitions of the controlled U_x circuit, as in [F30]. Measure its phase label y∈{0,…,M−1}; output 1 exactly when y=0, and output 0 otherwise. The Δ reflection, witness-space construction, state-preparation description and all other nonoracle gates are not asserted to have an efficient gate implementation.

Suppose f(x)=1. Then ψ_x lies in ran Δ by the definition of Δ, and lies in ran Π_x because every response register in it equals x_i. Thus U_xψ_x=ψ_x, so ψ_x is a phase-zero eigenvector. The zero-label probability from |start⟩ is at least its squared projection onto that eigenspace: |⟨ψ_x|start⟩|²=1/ν_x≥2/3, since Σ_i||v_{x,i}||²≤C_1≤A gives ν_x≤3/2. The exact reflection signs in [F4] ensure both range eigenvalues are +1.

Suppose f(x)=0 and define |φ_x⟩=μ_x^{-1/2}(|start⟩−√(2A)Σ_i|i⟩|v_{x,i}⟩|1−x_i⟩), μ_x=1+2AΣ_i||v_{x,i}||²≤1+2A². Its displayed terms are orthogonal, so it is unit. For each y with f(y)=1, the certificate constraints give ⟨ψ_y|φ_x⟩=ν_y^{-1/2}μ_x^{-1/2}(1−Σ_{i:x_i≠y_i}⟨v_{y,i}|v_{x,i}⟩)=0. Therefore Δφ_x=0. The response |1−x_i⟩ is orthogonal to |x_i⟩, so Π_xφ_x=|start⟩/√μ_x.

Set ω=1/(4A)≤1/4 and let E_ω project onto eigenphases |φ|≤ω of U_x. Applying [F2] to the unit vector φ_x and using step 4.1 gives ||E_ω|start⟩||²≤μ_xω²/4≤(1+2A²)/(64A²)≤3/64.

For an eigenphase outside this interval, the QPE event y=0 is contained in the event that the measured grid point is at circular phase distance at least η=ω/(2π) from the true phase. Since Mω/(2π)≥64/π>224/11>20 by [F31], K=floor(Mη)≥20, and [F3] bounds this conditional probability by 1/38. Spectral components are orthogonal, so the total false-positive probability is at most 3/64+1/38<1/3. Thus the output is correct with probability at least 2/3 on 0-inputs; step 3.2 gives the same guarantee on 1-inputs.