The period-finding circuit for Shor's algorithm

[tomdodd4598]

TL;DR

Building the period-finding circuit for Shor's algorithm & the classical complexity of finding the period of modular exponentiation

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 realized 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 deduce the period $r$ of this modular exponentiation function classically in an efficient way, starting with these values and then using a method analogous to a binary search (or 'interval halving'), selectively calculating other values of ${ a }^{ x }\; ({ mod }\; N)$, or an I being misled by using small numbers? [SEE EDIT]

Thanks in advance!

EDIT: It has been pointed out to me that 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$.

 

[Strilanc]

Yes, you can (and should) pre-calculate all of the numbers that need to be multiplied by and use that knowledge when generating the quantum circuit. In this sense Shor's algorithm is just a series of multiplications by easily computed constants, with the catch being that each multiplication is controlled (it may or may not occur) and each control qubit is in superposition.

I gave a talk on optimizing circuits for Shor's algorithm:

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?

I don't see any way to avoid computing them. You could obfuscate the fact that they were being computed, e.g. do the computation in ternary instead of binary, but basically you're asking for a way to perform modular exponentiation that doesn't use repeated squaring.

can we not deduce the period r of this modular exponentiation function classically in an efficient way

There's no known way to do this.

 

[tomdodd4598]

Yes, you can (and should) pre-calculate all of the numbers that need to be multiplied by and use that knowledge when generating the quantum circuit.

I don't see any way to avoid computing them.

I see, thanks. I watched your talk, which was very interesting, though a bit beyond me for now at points :P

There's no known way to do this.

Right - for some reason I thought that as you already have to pre-calculate all of the numbers to build the gates anyway, you would already have made progress at working out what the period is, but the smallness of the examples I was looking at in detail are misleading; the amount of classical computation still required is still exponential in the number of bits.

 

[f95toli]

I gave a talk on optimizing circuits for Shor's algorithm:

I finally had time to watch the video and that was a very nice talk
I've been sending the link to everyone I work with suggesting that they should watch it.