Ex9 8

$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 9.8}$

Suppose $P: \{0,\dots, N-1\} \to \{0,1\}$ is zero except at $x = t$, and suppose we are given a quantum oracle $U_P$ and told that with probability $0.9$ the first $n/2$ bits of the solution $t$ are zero. How can we take advantage of this information to obtain an algorithm that is more efficient, in terms of the number of calls needed, than $O(\sqrt{2^n})$?