Bounded-error evaluation from a dual adversary certificate

Inputs. A finite nonconstant Boolean function $f:D\to \{0,1\}$ on $N\ge 1$ input bits and a supplied finite dual-vector certificate $\{v_{x,i}\}$ in a finite-dimensional complex inner-product space $V$, meaning that for every distinct $x,y\in D$, ${\sum }_{i:x_i\mathrm{\ne }{y}_i}⟨v_{x,i}\mathrm{\mid }{v}_{y,i}{⟩}_D=\mathbf{1}[f(x)\mathrm{\ne }f(y)]\mathrm{.}$ Its class costs $C_b:={\max }_{x:f(x)=b}{\sum }_i\mathrm{\parallel }{v}_{x,i}{\mathrm{\parallel }}^2$ satisfy $C_0,C_1\le A$ for a supplied bound $A\ge 1$. The declared standard XOR input oracle is available. The input-independent controlled witness-span reflection specified below is a nonoracle operation in this query model; no efficient gate implementation for it is assumed.

Output. A Boolean estimate of $f(x)$ for the promised input $x\in D$.

Instructions. Use the finite work space $\mathcal{H}=\mathrm{span}\{\mathrm{\mid }start⟩\}\oplus ({\mathbb{C}}^N\otimes V\otimes {\mathbb{C}}^2)\mathrm{.}$ Here the address basis is $\mathrm{\mid }i⟩=e_{i-1}$ for $i\in [N]$, and $\mathrm{\mid }start⟩$ is a specified unit vector orthogonal to the query summand. The witness family is classical instance data used to specify a subspace, not an input-dependent state preparation. Define ${\nu }_x=1+\frac{1}{2A}{\sum }_i\mathrm{\parallel }{v}_{x,i}{\mathrm{\parallel }}^2,\mathrm{\mid }{\psi }_x⟩={\nu }_x^{-1\mathrm{/}2}(\mathrm{\mid }start⟩+\frac{1}{\sqrt{2A}}{\sum }_i\mathrm{\mid }i⟩\mathrm{\mid }{v}_{x,i}⟩\mathrm{\mid }{x}_i⟩)\mathrm{.}$ Let $\mathrm{\Delta }$ project onto the span of all $\mathrm{\mid }{\psi }_y⟩$ with $f(y)=1$, and let ${\mathrm{\Pi }}_x=\mathrm{\mid }start⟩⟨start\mathrm{\mid }+{\sum }_{i=1}^N\mathrm{\mid }i⟩⟨i\mathrm{\mid }\otimes I_V\otimes \mathrm{\mid }{x}_i⟩⟨x_i\mathrm{\mid }$ project onto $\mathrm{\mid }start⟩$ plus query states whose response is $x_i$. Form the exact ordered product $U_x=(2{\mathrm{\Pi }}_x-I)(2\mathrm{\Delta }-I)\mathrm{.}$

Choose $M=2^m$ as the least power of two satisfying $M\ge 512A$. Initialize the data register to $\mathrm{\mid }start⟩$ and apply the coherent QPE gate list followed by its projective readout on $U_x$. Implement controlled $U_x$ in chronological order by controlled $(2\mathrm{\Delta }-I)$, then controlled $(2{\mathrm{\Pi }}_x-I)$, retaining both plus-on-range signs. Repeat that complete controlled circuit $2^j$ times for the required power $U_x^{2^j}$ at each $j=0,\dots ,m-1$. Each controlled input-dependent reflection is the two-unconditional-query consistency-reflection circuit of Controlled input-consistency reflection from a bit query. For the measured phase label $y$, return $1$ exactly when $y=0$ and return $0$ otherwise. No gate-complexity bound is asserted for the input-independent reflection about the full witness span or the remaining nonoracle gates.