search

silq-lang / silq

Boost Software License 1.0
609 stars 52 forks source link

Added Shor's factoring algorithm example #12

Closed AbeerVaishnav13 closed 4 years ago

AbeerVaishnav13 commented 4 years ago

Hey @tgehr, this is an example of Shor's factoring algorithm in SILQ. Hoping this gets merged with the main repo.

Regards Abeer

AbeerVaishnav13 commented 4 years ago

Hello @tgehr, Just a reminder to add this Shor's factoring algorithm example to the repo. Hoping for it to get merged soon.

Regards Abeer

tjf801 commented 4 years ago

I don't see why this hasn't been merged, this is great example code.

tgehr commented 4 years ago

@tjf801 It has not been merged because it is not obviously correct (e.g., it does not perform any continued fraction expansion) and I have not gotten around to reviewing it in detail so far. (Also, there are some questionable choices of types in the implementation.)

tgehr commented 4 years ago

This is my own implementation of Shor's algorithm: https://github.com/eth-sri/silq/blob/master/test/shor.slq

@AbeerVaishnav13 It think your implementation is missing steps, it is using the result of the quantum subroutine directly as a candidate for the order. Also, I think the modular exponentiation part does not work correctly.

AbeerVaishnav13 commented 4 years ago

Ohh yes @tgehr. Thanks for pointing it out. I definitely forgot to consider the continued fraction part in my code.

Also thanks for sharing your version of the code. It helped me clear many things regarding the implementation of Shor's factoring algorithm in Silq!