Shor's algorithm on a Google Sheet

[Bob Walance]

TL;DR Summary

This is Shor's algorithm implemented on a Google Sheet. It demonstrates how Peter Shor's algorithm operates.

Here is a spreadsheet that demonstrates how Shor's algorithm works.

The user first enters a number 'N' that has only two prime factors. Then, the user enters a random integer 'x'. Shor's algorithm does the rest in the factorization of N. A different value for 'x' must be tried if the factoring was unsuccessful.

The second page on the spreadsheet shows values for 'N' and 'x' that have been tried. So far, N=5767 (with x=24) is the largest that works - thanks to PF user .Scott ! There are many others that should also work.

A quantum computer would use the quantum Fourier transform to calculate the period of the modular exponentiation function, but Google Sheets does not have a built-in DFT function. This is probably a good thing as it allows us to see the periodicity in the modular exponentiation function.

Here's a link to the Google Sheet. The 'N' and 'x' values can be modified here.
Shor's algorithm - Google Sheet

This is a view-only look at the Google Sheet.

 

[.Scott]

So I promised you some more magic:
You're calculating a GCD with N in cells H9 and H10. You can perform that GCD calculation mod N.
In fact, you have already calculated (x^(r/2)) mod N and it is waiting there in column L.

So here are the changes:

F11: Calculate r/2 with check for not-a-number and odd r.
F11: =IF(MOD(IFNA(E6,1),2),0,E6/2)
F12: Look up X^(r/2) - we have already calculated the modulus N version of it!
F12: =INDEX($L$18:$L$620,F11)
F9: =F12+1
F10: =F12-1

C9: 39203 (new test value)
C11: Any of 14, 92, 106, 183, or 191

(These cell locations are for yesterday's version of the spreadsheet. See #7 below for updates.)

 

[.Scott]

Hmmm... Were you going to post a link to the Google page version?
I think 5-digit values for N are running close to a few limits:
1) The spreadsheet numerical precision;
2) The sparsity of "hits" on the guesses; and
3) The length of the exponentiation table in column L.

 

[Bob Walance]

Well, I did paste the link. The spreadsheet is there and you can get to the second sheet, but for some reason cells B9 and B10 can't be changed by the user. When I paste the same link into a web browser then everything works as expected.

I'm not sure what is wrong.

Let me try pasting the link as 'plain text' here.

Nope, same results. Rather than a simple link, the PF text says something about 'MEDIA=...'

I'll need help on this. It's a puzzlement.

 

[.Scott]

I just went back and forth between this page and the spreadsheet. I changed B9 and B10 and everything worked as expected.
Cells A9 and A10 are suppose to be protected - and they are.

 

[Bob Walance]

In the Google Sheets version of the spreadsheet, B9 is 'N' and B10 is 'x'. C9 and C10 are blank

In #1 above, I can't modify B9 or B10 as desired. If I copy and paste the XX link in #1 into a browser then I can.

Are you seeing something different?

 

[.Scott]

No. You're right. I didn't notice that you had removed the old column A.
A9 and A10 do not change for me (good). And B9 and B10 do change (also good).
And I do have to go back and forth between the Google page and this page.
Nothing changes for me in #1 above.

So let me update the changes that got me to 39203:

You're calculating a GCD with N in cells H9 and H10. You can perform that GCD calculation mod N.
In fact, you have already calculated (x^(r/2)) mod N and it is waiting there in column L.

E12: Calculate r/2 with check for not-a-number and odd r.
E12: =IF(MOD(IFNA(D6,1),2),0,D6/2)
E13: Look up X^(r/2) - we have already calculated the modulus N version of it!
E13: =INDEX($J$18:$J$620,E12)
E9: =E13+1
E10: =E13-1

B9: 39203 (new test value)
B10: Any of 14, 92, 106, 183, 191, 196, 198, 200, 211, 217, 284, ...

And for more:
1) Extend your J column table to r=1200.
2) Change D6 and E13 to access that new length.
3) Try 47897 with 14, 23, 55, 104.

 

[.Scott]

It looks like for an "N", the exponent table should be roughly $6 \sqrt{N}$ rows in length.

But there are "discounts".
N = 998027 has "expensive" solutions a 18, 50, 52, 70,71, 77, and 86; but a discount (r=396) at 91.

 

[Bob Walance]

Scott - you are amazing. I've implemented your latest changes in a test version and factoring 47897 works. I haven't expanded the table yet to do 998027.

Six-hundred more digits and you'll be able to crack our beloved encryption schemes. You're starting to make Rivest, Shamir, Adleman, Diffie and Hellman very nervous.

 

[.Scott]

I really like your spreadsheet. I've run through Shor's algorithm many times with an eye for how I could explain it - or even simply characterize it - for others. I think this spreadsheet makes it very tractable.

I'm also thinking that numbers in the 998027 range make the point. They're big enough that finding good guesses starts to get hard. So the value of the QFT becomes evident.

 

[Bob Walance]

I really like your spreadsheet. I've run through Shor's algorithm many times with an eye for how I could explain it - or even simply characterize it - for others. I think this spreadsheet makes it very tractable.

I'm also thinking that numbers in the 998027 range make the point. They're big enough that finding good guesses starts to get hard. So the value of the QFT becomes evident.

But the QFT is just finding the period of the mod-exp function. You still have to come up with guesses for 'x'.

Unless I'm missing something, this is going to be tough even when we have thousands of error-corrected qubits. If it takes a quantum computer 30 minutes for one run through the algorithm then needing 100 guesses for 'x' would be a lengthy process, although still better than waiting a trillion years.

 

[.Scott]

But the QFT is just finding the period of the mod-exp function. You still have to come up with guesses for 'x'.

Unless I'm missing something, this is going to be tough even when we have thousands of error-corrected qubits. If it takes a quantum computer 30 minutes for one run through the algorithm then needing 100 guesses for 'x' would be a lengthy process, although still better than waiting a trillion years.

If it takes the quantum computer 30 minutes, it will never work, it will decohere. I am presuming that it will take microseconds - or nanoseconds.

 

[Bob Walance]

If it takes the quantum computer 30 minutes, it will never work, it will decohere. I am presuming that it will take microseconds - or nanoseconds.

I believe that it takes about a billion gate times to do one pass through Shor's. At one microsecond per gate time that's about 16 minutes.

We are many years away from having qubits that won't decohere in that amount of time, but that's the whole idea behind the so-called logical or error-corrected qubit.

I have read that it might take thousands of physical qubits to make one error-corrected qubit. That shouldn't be a problem for the people at Intel. Tens-of-millions of qubits on a piece of silicon should be easy-peasy ... someday.

 

[Bob Walance]

I'm having some fun playing with the Google Sheet spreadsheet with Scott's wonderful IF(MOD...) and INDEX(...) modifications.

There are a few more values of N that I've been able to crack (see below). The largest is 669043. My MOD-EXP table length is now 7080.

I'm not sure why 842603 doesn't work. Perhaps I just haven't found the right 'x'. N=998027 isn't working, even with Scott's known value(s) for 'x'. This might be due to a limitation in Google Sheets.

input N= 71273	input x=23	the period 'r' found is 2358	the factors are 271 * 263
168821	89	1400	401 * 421
372019	89	5150	601 * 619
669043	44	3304	809 * 827
842603	no joy		909 * 929
998027	no joy		?