Periodicity Determination

Input

Black box for a function
is periodic with a period

Output

Return with some desired accuracy independent of

Algorithm

Construct

Consider a state (where )
Apply the quantum oracle of the function

Since is the period of :
and let be the number of periods

Do a measurement on the second register of basis
Let outcome be
is the smallest value of for which

Probability of outcome is
Terms contributing to this outcome are

By the extended Born Rule

So the measurement gives a uniformly random outcome
Post measurement state of the first register is

We apply Quantum Fourier Transform

We can calculate

Thus

Measurement on the first register in
Say outcome is for some

We try in the hope that is coprime to . If that is the period, we are done, otherwise, repeat.

Coprimality Theorem
So repeat this times to find at least one coprime.