search

oreilly-qc / oreilly-qc.github.io

Code samples for Programming Quantum Computers, from O'Reilly Media
130 stars 59 forks source link

Kudos on Shor's Algorithm Implementation and Chapter #31

Open simplygreatwork opened 4 years ago

simplygreatwork commented 4 years ago

The only other moderately digestable implementation of Shor's algorithm in JavaScript I have found is the jsqubits example from David Kemp. However I discovered that example uses some powermod shortcuts to construct the circuit. I really like your Shor example - particularly that you have linked the fully classical implementation and the quantum implementation so cleanly. Great job. I'm beginning to work on transforming this example to run against the Quantastica engine.

machinelevel commented 4 years ago

Hi Philip, Thanks so much! I'm glad you like it, and your note made my day. Funny story about this one. My background is engineering, not QC, and in 2015 I'd started as a part-time researcher at Univ of Bristol's Centre for Quantum Photonics, filling in the massive gaps in my quantum knowledge.

There was a short-notice project where one of the really awesome senior researchers (Anthony Laing) needed a Shor implementation for noise modelling. I stayed up all night reading three papers on Shor, and by morning I realized I didn't understand two of them at all, and the third one didn't work.

On the 2-hour train ride from London to Bristol, I started with no time left and a blank page, suddenly realized I could shortcut the exponentiation by using 2 as the coprime, and by the time the train pulled in at Bristol Temple Meads it was running.

It's not optimal, and the modulo operation is a big bag of hamsters, but I've been using variations on this implementation ever since. :]

Cheers and thanks,

simplygreatwork commented 4 years ago

I did begin refactoring the Shor algorithm example to suit my personal structural taste. I've been using a pared down version of Quantastica: 9000 lines of code down to about 700 lines of code. Just the basics. So my own example is technically not using the Quantastica engine off the shelf. Anyway, this is what I have so far but I still need to dive more into num_shifts, condition, precision.bits(), .rollLeft() and all of the modulo code.

https://github.com/simplygreatwork/obvious/blob/master/examples/algorithm-semiprime-factoring-quantum.js https://github.com/simplygreatwork/obvious/blob/master/examples/algorithm-semiprime-factoring-classical.js https://github.com/simplygreatwork/obvious/blob/master/examples/algorithm-semiprime-factoring-naive.js

So not quite correct or finished - I might casually finish the rest one piece at a time. Lots of hamsters, yes.