Finite hybrid budget for a four-address search space

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.