Ex8 5

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

Show that in the general case in which $r$ does not divide $2^n$, the parts of Shor's algorithm need to be repeated only $O(\log\log r)$ times in order to achieve a high probability of success.

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