Arithmetic Block in Shor Algorithm

[Ricardo Belchior]

Hello everyone!

So I was looking at Shor Algorithm for prime factorization and I have some doubts in the arithmetic part.

Let's define a function f that : f(x) = a^x mod N. The middle step in shor algorithm is to calculate, simultaneously, all values of f. In some papers and books, I saw some high level implementation of this block, but nothing concrete. Can someone explain to me, how they do this?

In some implementations they use Controlled-Gates. Ok, that's fine, but the control qubit is always in some superposition of states. So what happens in this cases?Thanks!

 

[Strilanc]

I've been working on a paper that explains how to implement Shor's algorithm from top to bottom using 2n+1 qubits (w/ n-1 in an unknown state that must be preserved) (the previous best was 2n+2 w/ none in an unknown state). Here's a few diagrams from it.

The fact that the exponentiation is calculated under superposition doesn't really matter at all. All the arithmetic can be done with classical reversible circuits. There are some optimizations made possible by quantum gates, and of course the very top level has some quantum stuff, but all the arithmetic really is just standard classical reversible stuff.

An adder (not novel):

Incrementing (novel):

Scaled modular addition (not really novel; clearly I should just be adding 2^p*K instead of doing this doubling stuff):

Transitive reduction of the dependency graph between constructions:

As that last diagram shows, there's a rather lot of constructions on the path from exponentiation to Toffolis. But they all basically look like the diagrams I showed: take what you've built up so far, and combine it to build the next thing.

 

[Strilanc]

Incidentally, you can simulate the period-finding part of Shor's algorithm in my quantum circuit simulator Quirk.

You can't do the follow-up continued fractions algorithm to turn the period into a factor in Quirk, so mostly you can just see that "Yup, there's strong peaks near 2^n*k/p where p is the period and k is arbitrary". But still Quirk is a tool I used when looking for / optimizing / checking most of the constructions. I would add a known-good construction plus its inverse to the circuit, set up a "test harness" that made/unmade random test vectors, and then just watched to make sure the output stayed consistently off as I tried to optimize one of the constructions.

 

[Ricardo Belchior]

Thanks a lot! That schemes where very helpful. But I still don't get that superposition thing. If I don't know the control qubit value, how do I do it? I suppose you assume some value? I think that I do not get that superposition part.

 

[Strilanc]

You just do a controlled operation with the appropriate phase estimation qubit as the control. The operation will only affect the part of the superposition where the control is on.

Controlled operations are also a classical reversible computing concept, so again you don't need to know any quantum computing to implement circuits that do controlled arithmetic. (Notice that the diagrams do include controls)

 

[Ricardo Belchior]

Ok Thanks, I think I got it.