Grover$$s Algorithm

Consider the search problem: we have oracle access to x in $\{0,1\}$N $,$ with unknown Hamming weight

t $=|$x$|.$ We want to find a solution, i$.$e$.,$ an index i in $\{0,...,$ N $1\}$ such that xi $=1.$ If x $=0$N then our

search algorithm should output $$no solution.$$

$($a$)$ Suppose we know an integer s such that t in $\{1,...,$ s$\}.$ Give a quantum algorithm that finds a

solution with probability $1,$ using O$($sN $)$ queries to x$.$

Hint: Try running the exact version of Grover $($see Prof. Ronald de Wolf$$s lecture notes in Chapter $7)$

with different guesses for what the actual t is$.$

$($b$)$ Suppose we know that t in $\{$s $+1,...,$ N $\}.$ Give a quantum algorithm that finds a solution with

probability at least $12$s$,$ using O$($sN $)$ queries to x$.$

$($c$)$ For given $\backslash$epsi $>0,$ give a quantum algorithm that solves the search problem with probability $>=1\backslash$epsi

using O$($pN log$(1/\backslash$epsi $))$ queries, without assuming anything about t$.$

NB: The important part here is that the log$(1/\backslash$epsi $)$ is inside the square$-$root; usual amplification by

O$($log$(1/\backslash$epsi $))$ repetitions of basic Grover would give the worse upper bound of O$($N log$(1/\backslash$epsi $))$ queries$\mathrm{.}1$ Grover's Algorithm

Consider the search problem: we have oracle access to xin$\{0,1{\}}^N,$ with unknown Hamming weight

$t=|x|.$ We want to find a solution, i$.$e$.,$ an index iin$\{0,$dots,$N-1\}$ such that $x_i=1.$ If $x=0^N$ then our

search algorithm should output $"$no solution."

$($a$)$ Suppose we know an integer $s$ such that tin$\{1,$dots,$s\}.$ Give a quantum algorithm that finds a

solution with probability $1,$ using $O(\sqrt[\phantom{2}]{sN})$ queries to $x.$

Hint: Try running the exact version of Grover $($see Prof. Ronald de Wolf's lecture notes in Chapter $7)$

with different guesses for what the actual $t$ is$.$

$($b$)$ Suppose we know that tin$\{s+1,$dots,$N\}.$ Give a quantum algorithm that finds a solution with

probability at least $1-2^{-s},$ using $O(\sqrt[\phantom{2}]{sN})$ queries to $x.$

$($c$)$ For given $>0,$ give a quantum algorithm that solves the search problem with probability $1-$

using $O(\sqrt[\phantom{2}]{Nlog(\frac{1}{})})$ queries, without assuming anything about $t.$

NB: The important part here is that the $log(\frac{1}{})$ is inside the square$-$root; usual amplification by

$O(log(\frac{1}{}))$ repetitions of basic Grover would give the worse upper bound of $O(\sqrt[\phantom{2}]{N}log(\frac{1}{}))$ queries.