OurBigBook.comSite Source code

Exact period recovery from a Fourier sample

For the exact sample

c = s N / r

, reducing

\frac{c}{N} = \frac{s}{r}

recovers denominator

r / g cd (s, r)

. Thus one sample reveals the full period exactly when

s

is coprime to

r

; otherwise it reveals only a proper divisor and the algorithm must obtain more information.

Table of contents 120 1
- Heralded exact quantum period finding when the period divides the register size Exact period recovery from a Fourier sample 77

 Ancestors (6)

 Incoming links (1)

Solution