Ex9 9

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

Given a quantum black box for a function $f: \{0,\dots, N-1\} \to \{0,\dots, N-1\}$, design a quantum algorithm that finds the minimum with $O(\sqrt{N}\log{N})$ queries, where $N = 2^n$.

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