Are the order finding and period finding algorithms the same thing?

Do they both just use similar methods of calculation, or are they completely interchangeable?

1 Answer

If you look at Nielsen and Chuang, figure 5.5, page 241 (at least in my 2002 version), order finding and period finding are separated. (Note that this is talking about the problem definition, not the algorithm for solving them). Essentially, period finding aims to find the least positive $$r$$ such that $$f(x+r)=f(x)$$ for all $$x$$, while order finding is doing a special case of this where the function is of a specific form: $$f(x)=a^x\text{ mod }N$$.

In terms of an algorithm for solving them, it turns out that a quantum computer gives us a good algorithm for period finding, and hence it can also be applied to the special case of order finding. Strictly, this doesn't rule out the possibility that there could be something better for order finding than there is for period finding in general, I guess.