# Building the period-finding circuit for Shor's Algorithm & the classical complexity of finding the period

I've been trying to learn about Shor's algorithm by writing out implementations of the circuit for modular exponentiation, $${ a }^{ x }\; ({ mod }\; N)$$, to find the period $$r$$ for small numbers such as:

$$(N=15,\quad a=11)\quad \longrightarrow \quad r=2$$,

$$(N=35,\quad a=13)\quad \longrightarrow \quad r=4$$,

$$(N=21,\quad a=5)\quad \longrightarrow \quad r=6$$.

I know these are incredibly small numbers, but I realised that in order to actually start building the cicuit at all (using the binary exponentiation method), I needed to calculate the values of $${ a }^{ { 2 }^{ k } }\; ({ mod }\; N)$$ for all $$0\;\le\;k \; <\; 2\; \lceil { \log _{ 2 }{ N } }\rceil$$, which pretty much immediately made the values of $$r$$ obvious before I'd even started building the circuit.

For example, take the least trivial case from the above, where $$r=6$$. I needed to calculate:

$${ 5 }^{ 0 }\; ({ mod }\; 21)=1$$,

$${ 5 }^{ 1 }\; ({ mod }\; 21)=5$$,

$${ 5 }^{ 2 }\; ({ mod }\; 21)=4$$,

$${ 5 }^{ 4 }\; ({ mod }\; 21)=16$$,

$${ 5 }^{ 8 }\; ({ mod }\; 21)=4$$,

$${ 5 }^{ 16 }\; ({ mod }\; 21)=16$$.

Simply by inspection, I can already see what the value of $$r$$ must be, because the result is the same when $$x$$ increases by six or twelve, but not after increasing by two or three.

I therefore have two questions:

1. Is calculating these modular exponentials of $$a$$ to powers of two required when building these circuits, or is there some way of not even having to do that?

2. If we do need to calculate these values, can we not find the period $$r$$ of this modular exponentiation function classically in an efficient way, starting with these values and then using a method analogous to 'interval halving', or an I being misled by using small numbers? [SEE EDIT]

EDIT: As Mark S points out, the results of modular exponentiation have very little structure, and so although perhaps faster than $$O(N)$$, such an 'interval halving' method would not have logarithmic complexity, thus would be slower than Shor's algorithm for large enough $$N$$.
The fast "modular exponentiation by repeated-squaring" part of Shor's algorithm is only one of the many ideas in Shor's paper, and I think a more critical idea/breakthrough is the QFT itself. However, without something equivalent to modular exponentiation by repeated-squaring, you have no way of having a small circuit to evaluate $$f(x)$$, so that you can perform the QFT on $$\vert x\rangle\vert f(x)\rangle$$.
I also think you are being significantly misled by looking at such small numbers. You'll need to prepare a state $$\vert x\rangle\vert f(x)\rangle$$ somehow; here $$f(x)$$ is evaluated with repeated-squaring, which is honestly pretty darned fast already, when $$x$$ gets large. It's not clear if a "binary search" is not already what the repeated-squaring is effectively doing.
• Maybe what I meant by 'binary search' in my second question wasn't clear. What I mean to ask is whether it is possible to quickly find the period r (without any quantum computation) by looking at the values of the modular exponentiation to powers of two, then based on the answers, selectively calculate other values of a^x (mod N) via a form of 'interval halving' until we can deduce what the period is. Surely we don't have to calculate it for every single value of x to do that? I suppose the complexity of doing this must be larger than building and using the cicuit, but I can't see how. May 15, 2020 at 23:03
• But $a^x\bmod N$ doesn't have much structure that you could leverage for interval halving? You'll need at least two different $x$ such that $a^x\bmod N$ is the same, in order to have a chance of knowing the period... May 15, 2020 at 23:51
• Yeh, you must be right, but I just need to convince myself of it. You get quite a lot of tests done each time you calculate a new value, so my original thought was that it would be faster than $O(N)$, but I suppose it isn't logarithmic, which it would have to be to beat Shor's. May 16, 2020 at 2:02