Quantum Query Lower Bounds and Search Optimality — Examples

Let $\mathrm{\mid }s⟩=\frac{1}{2}(\mathrm{\mid }0⟩+\mathrm{\mid }1⟩+\mathrm{\mid }2⟩+\mathrm{\mid }3⟩)$ be the first query's address state, with any fixed unit response and work state. By [F1], $\mathrm{\parallel }s\mathrm{\parallel }=1$ and each address probability is $q_{0,i}=1\mathrm{/}4$. Hence ${\sum }_i{q}_{0,i}=1$.

Put $e_3=\mathrm{\mid }3⟩$ and $u=s-e_3$. By [F1], $⟨s,e_3{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=1\mathrm{/}2$, so $\mathrm{\parallel }u{\mathrm{\parallel }}^2=1+1-2(1\mathrm{/}2)=1$. The map $P_u=\mathrm{\mid }u⟩⟨u\mathrm{\mid }$ is an orthogonal projection by [F5], and $R=I-2P_u$ satisfies $R^{\ast }R=R^2=I$. By [F2], $P_{u}s=⟨s,u{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}u=(1\mathrm{/}2)u$, so $Rs=s-u=e_3$. Use this input-independent reflection between the first and second queries. The all-zero oracle is identity, so the second pre-query address state is $\mathrm{\mid }3⟩$; thus $q_{1,4}=1$, $q_{1,1}=q_{1,2}=q_{1,3}=0$, and ${\sum }_i{q}_{1,i}=1$.

Apply [F4]. For $i=1,2,3$, $\mathrm{\parallel }{\psi }_2^i-{\psi }_2^0\mathrm{\parallel }\le 2(1\mathrm{/}2+0)=1$; for $i=4$, $\mathrm{\parallel }{\psi }_2^4-{\psi }_2^0\mathrm{\parallel }\le 2(1\mathrm{/}2+1)=3$. Therefore the sum of squared bounds is at most $3\cdot 1^2+3^2=12$, and the average squared distance is at most $12\mathrm{/}4=3$. The general bound $4T^2$ gives total at most $16$ and average at most $4$, so the explicit address allocation is consistent with that budget.

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.