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.