Ex9 7

$\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.7}$

Suppose $P: \{0,\dots, N-1\} \to \{0,1\}$ is zero except at $x = t$, and suppose we are given not only a quantum oracle $U_P$, but also the information that the solution $t$ differs from a known string $s$ in at most $k$ bits. Exhibit an algorithm that finds the solution with $O\left(\left(\begin{array}{c} n \\ k \end{array} \right) \right)$ calls to $U_P$.

page revision: 0, last edited: 18 Nov 2012 19:40