BBBV hybrid lower bound for unstructured search

Let a bounded-error decision algorithm use $T$ queries. Apply [F2] and use the common final acceptance event. For each $i$, correctness [F5] gives acceptance at least $2\mathrm{/}3$ on $e_i$ and at most $1\mathrm{/}3$ on $0^N$. By [F3], $\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0\mathrm{\parallel }\ge 1\mathrm{/}6$.

Summing the squares of these $N$ inequalities gives $N\mathrm{/}36\le {\sum }_i\mathrm{\parallel }{\psi }_T^i-{\psi }_T^0{\mathrm{\parallel }}^2$. By [F4], the right side is at most $4T^2$, so $T\ge \sqrt{N}\mathrm{/}12$.

Now let a bounded-error finder use $T$ queries. Append a decision step that measures its output and, if it is a coordinate $i$, makes one standard bit query at address $i-1$ with response initialized to $0$; accept exactly when that response is $1$. If the output is none or invalid, reject without a query. On $0^N$ this decision never accepts; on $e_i$ it accepts whenever the finder returns $i$, which has probability at least $2\mathrm{/}3$ by [F1]. This is a bounded-error decision procedure with at most $T+1$ queries, so [F6] and step 2.1 give $T+1\ge \sqrt{N}\mathrm{/}12$.

If $N\ge 576$, then $\sqrt{N}\mathrm{/}12\ge 2$, and step 3.1 gives $T\ge \sqrt{N}\mathrm{/}12-1\ge \sqrt{N}\mathrm{/}24$. If $1\le N<576$, a zero-query finder has the same output law on $0^N$ and $e_1$, yet success would require probability at least $2\mathrm{/}3$ on the disjoint outcomes none and $1$ under this one common law. Their probabilities would sum to at least $4\mathrm{/}3$, impossible; hence $T\ge 1\ge \sqrt{N}\mathrm{/}24$.