Chapter 8

Exercises are from QUANTUM COMPUTING: A GENTLE INTRODUCTION, by Eleanor Rieffel and Wolfgang Polak, published by The MIT Press.

$\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}\mathbf{Exercise\ 8.1}$

Give the exact value of the scale factor $C$ in equation 8.2 in terms of properties of $f$ and $u$.

$\mathbf{Exercise\ 8.2}$

Show that with high probability $v$, the value obtained from the quantum core of Shor's alorithm described in section 8.2.1 is within $\frac{1}{2}$ of some multiple of $\frac{2^n}{r}$.

$\mathbf{Exercise\ 8.3}$

Determine the efficiency of Shor's algorithm in the general case when $r$ does not devide $2^n$.

$\mathbf{Exercise\ 8.4}$

Show that the probability that the period of $f(x) = a^x \mod M$ is odd is at most $1/2$.

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

$\mathbf{Exercise\ 8.6}$

Explain how Deutsch's problem of section 7.3.1 is an instance of the hidden subgroup problem.

$\mathbf{Exercise\ 8.7}$