Computational Problems, Promises, and Cost Models — Examples

A multitape machine computes $r(x)=xx$ by copying $x$ twice, using $O(\mathrm{\mid }x\mathrm{\mid }+1)$ transitions under [F7], so $r$ is total and polynomial time. Moreover, $r(0)=00\in Y_T$ and $r(1)=11\in N_T$, giving $r(Y_S)\subseteq Y_T$ and $r(N_S)\subseteq N_T$. Thus $r$ is a promise-preserving reduction by [F8]. No image condition is needed for source strings outside $\{0,1\}$.

For the search reduction, the only promised source input is $z=0$, and $r(0)=00\in D_T$. Every valid target witness is $v\in \{0,1\}$, so $L(0,v)=0v$ is either $00$ or $01$ and satisfies $R_S(0,L(0,v))$. Both maps are total as defined on all binary strings, even though witness validity is required only on the promise.

For every four-bit $z=u\mathrm{\parallel }v$, the table assigns one two-bit value to address 0 and one to address 1, so $f_z$ is total on its two-address domain. Starting at target $00$, the oracle call at address 0 returns $00\oplus f_z(0)=u$; it is one invocation and therefore one query by [F2]–[F3].

The full output state after the oracle call is the basis vector $\psi =\mathrm{\mid }0⟩\mathrm{\mid }u⟩$, which is a unit vector by orthonormality [F12]. Its rank-one projector $\rho =\mathrm{\mid }\psi ⟩⟨\psi \mathrm{\mid }$ is a density operator by [F14]. For output word $y$ and remaining address bit $a$, the product basis is orthonormal by [F12], so $⟨e_{y,a},\psi ⟩=1$ exactly when $(y,a)=(u,0)$ and is zero otherwise. The projector formula [F13] gives $\rho e_{y,a}=⟨e_{y,a},\psi ⟩\psi$; root first-linearity and conjugate symmetry therefore give $⟨\rho e_{y,a},e_{y,a}⟩=⟨e_{y,a},\psi ⟩⟨\psi ,e_{y,a}⟩=\mathrm{\mid }⟨e_{y,a},\psi ⟩{\mathrm{\mid }}^2$. Summing over the unmeasured address bit as in [F10] gives output weight one at $u$ and zero elsewhere. If $u=00$ the rule answers yes; if $u=11$ it answers no, so the solver is exact on the promise by [F4]. For off-promise $u\in \{01,10\}$ the same rule outputs no, but the decision task imposes no condition there; the two total completions assigning either answer on these inputs agree on $Y\cup N$.

The matrix in [F9] satisfies $H^2=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$ by finite row-by-column multiplication [F11]. Therefore the two extra gates in the second circuit return the first target bit to its initial value before the same oracle call. The target entering $U_{f_z}$ is again $00$, so both query circuits have the same output law and one query; their nonoracle gate counts are 0 and 2 by [F5]–[F6].

Step 1.1 gives the reduction's linear transition bound in the table. In either query circuit, the fixed two-bit reply and one-bit output rule take $O(1)$ transitions. These transition counts are separate from the one oracle query and from the quantum gate counts by [F7].