Ex9 13
$\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.13}$
For the quantum counting procedure of section 9.5.2, show how the estimate of $t$ is obtained in the case that a bad state is measured.
page revision: 0, last edited: 18 Nov 2012 19:43
The text actually handles the case where a bad state is measured in the right register, so let's assume a good state is measured. The left register then collapses to
(1)As a function of $k$, the sine function $g_k = \sin((2k+1)\theta)$ has period $r = \pi/\theta$.
(2)Introduce the frequency $u = M/r = M\theta/\pi$ and apply the quantum Fourier transform to $\ket{\psi}'$ to obtain the state
The $G_j$ will be close to 1 for $j$ close to the frequency $u$, so after the Fourier transform, with high probability the measured state $\ket j$ will be close to $M\theta/\pi$ and for $\theta$ we can take
(3)As before, the probability of a good state is $t = g_0^2 = \sin^2\theta$. Note, the text has is wrongly as $t = \sqrt{\sin\theta}$.