One uniform phase query gives small trace-distance advantage

Let $\mathrm{\mid }s⟩=N^{-1\mathrm{/}2}{\sum }_{j=0}^{N-1}\mathrm{\mid }j⟩$, $P_s=\mathrm{\mid }s⟩⟨s\mathrm{\mid }$, and let the fixed marked coordinate be $i$. Its query address is $i-1$, so the phase query $O_i=I-2\mathrm{\mid }i-1⟩⟨i-1\mathrm{\mid }$ sends $s$ to the unit vector ${\psi }_i=s-2\mathrm{\mid }i-1⟩\mathrm{/}\sqrt{N}$ because it only flips one basis sign; set $P_{{\psi }_i}=\mathrm{\mid }{\psi }_i⟩⟨{\psi }_i\mathrm{\mid }$. Orthonormality [F2] gives $⟨s,{\psi }_i{⟩}_D=1-2\mathrm{/}N$; [F5]–[F6] give $D(P_s,P_{{\psi }_i})=\sqrt{1-(1-2\mathrm{/}N{)}^2}=2\sqrt{N-1}\mathrm{/}N=O(N^{-1\mathrm{/}2})$. This tends to zero with $N$.

Suppose instead the mark is unknown and uniform on $\{1,\dots ,N\}$. Each $P_{{\psi }_i}$ is a density operator by [F4], so their finite average $\rho =N^{-1}{\sum }_i{P}_{{\psi }_i}$ is self-adjoint, nonnegative, and trace one. Writing $e_i=\mathrm{\mid }i-1⟩$, expansion gives $P_{{\psi }_i}=P_s-\frac{2}{\sqrt{N}}(\mathrm{\mid }s⟩⟨e_i\mathrm{\mid }+\mathrm{\mid }{e}_i⟩⟨s\mathrm{\mid })+\frac{4}{N}\mathrm{\mid }{e}_i⟩⟨e_i\mathrm{\mid }$. The two cross sums each equal $\sqrt{N}{P}_s$, and ${\sum }_i\mathrm{\mid }{e}_i⟩⟨e_i\mathrm{\mid }=I$ by [F2]–[F3], so $\rho =(1-4\mathrm{/}N)P_s+4I\mathrm{/}{N}^2$. Then $X=\rho -P_s$ has eigenvalue $-4(N-1)\mathrm{/}{N}^2$ on $\mathrm{span}\{s\}$ and $4\mathrm{/}{N}^2$ on $s^{\perp }$ of dimension $N-1$; their sum with multiplicity is zero, so $X$ is trace-zero. Its negative part is $X_{-}=(4(N-1)\mathrm{/}{N}^2)P_s$, whose trace is $4(N-1)\mathrm{/}{N}^2$ because $P_s$ has trace one. By [F5] and [F7], $D(\rho ,P_s)=\frac{1}{2}\mathrm{\parallel }X{\mathrm{\parallel }}_1=4(N-1)\mathrm{/}{N}^2=O(N^{-1})$. If $N=1$, $s^{\perp }$ has dimension zero and the formula gives distance zero.

Fix an address-valued final measurement, let $r_i$ be its probability of output $i$ on $P_s$, and let $p_i(i)$ be its probability of outputting $i$ on $P_{{\psi }_i}$. The event form of [F8] and step 1.1 give $p_i(i)\le r_i+2\sqrt{N-1}\mathrm{/}N$. Since ${\sum }_i{r}_i\le 1$, the average success for a uniformly unknown marked coordinate is at most $N^{-1}+2\sqrt{N-1}\mathrm{/}N$, which tends to zero. Separately, [F8] and step 1.2 bound the total-variation change between the empty-input law and the uniform-mark mixture law by $4(N-1)\mathrm{/}{N}^2$, so this specified experiment also has vanishing decision advantage. The lower bound [F9] concerns arbitrary algorithms and is proved independently; it is not inferred from this example.