Shor’s Algorithm — Tips and Tricks
--
One thing that I have noticed about this algorithm is that there is NO GOOD CONTENT for how to code it. I am a quantum computing developer and after realizing I could no longer do it myself, I turned to the internet.
After researching ways to recreate it on my Jupyter notebook for over 4 months, I had finally given up. After a stroke of inspiration hit me, I finally got back on the grind and was determined to find a found out why there was no content for how to recreate it… it was because the math behind it is literally too complex.
A naive understanding
When looking at the separate components from Wikipedia the majestic algorithm looks soooo simple:
It tells the story of a very intuitive algorithm that simply uses a couple of well-defined gates and some more quantum subroutines. But, when you go about actually trying to create this factoring machine yourself, you will quickly run into some major challenges.
With this article, I want to make sure I can help you save your time recreating this algorithm on a quantum computer by sharing some of my major takeaways.
Tips
- Learn about the major quantum short forms like a tensor exponent to understand the papers
- Learn about simple quantum mathematics like what the sigma sign does (I got so many people to explain this to me)
- Learn about how to manipulate qubits on the imaginary axis and play around with gates (don’t waste too much time)
- Learn about how to manipulate qubits in the Fourier space (easier said than done)
- Know that NOTHING IS AS EASY AS IT SEEMS
The misunderstandings
What is the quantum Fourier transform
Probably one of the most difficult concepts to understand if you are new to computing. The easiest way to understand this for most people is that this is a normal Fourier transform in a sense with cool new abilities. Also, it’s quantum so has quantum parts that make it faster.
If you need more help to understand the quantum Fourier transform, watch the 3Blue1Brown video, and read this super interesting blog post on it.
If you are still confused, it simply just finds the period of a function. The data of almost ANYTHING can be plotted as a function.
Quantum Fourier transform initialization VS Hadamard gate initialization
Number two, the quantum Fourier transform does the exact same thing as using Hadamard gates on the initial qubit register. No matter which you use, the 0 state qubits are put into an equal superposition of all states no matter which method is used.
The difference between these two subroutines is that the Fourier transform is more complicated (more capable of other cool things).
It can also find the period of a function in states other than that in the computational basis. Finds you the period of harder functions. Using the phase estimation subroutine, the QFT is the only viable method to find the period.
🔑 Using Hadamard gates after phase estimation would not give you the period for the Shor’s algorithm periodic function… unlike Simon’s algorithm.
Making the QFT
Super basic and quick thing. QFT is a subroutine in its self. For some reason qiskit does not have a function that I know of that can create the QFT algorithm so you are going to have to make it yourself using controlled U1 gates and Hadamard's.
A super easy thing to look up.
You could also check out Quantum Circuit, an insanely useful simulator that can also create QFTs.
Extra note: The inverse QFTs are just negative numbers as input parameters.
I just wanted to add this because I was confused about this in the beginning.
The limitation of using binary
This is part of the reason why the math behind recreating the algorithm was super hard because the computational bases were so confined.
For something like the phase estimation subroutine, the only values that you can use are 0 and 1. This means that when you are trying to apply a function, the code and circuit becomes a lot more complicated.
The Shor’s function is:
Using the circuit from Wikipedia all the way at the top, this function is used in Shor’s algorithm for the middle phase estimation part. AKA the Unitary Operators.
This constrains your ability to easily build up a circuit because the only numbers that any qubit can hold are 0 and 1 in the computational basis. But because qubits are 3-Dimensional mediums of information, you will have to use its other dimensions to hold their results to the Shor’s function.
The reason why it's so hard to recreate
Because it is complex.
Straight up, the math is just way too hard. I have spent months looking at the algorithm and developing an understanding. After spending days trying to replicate my understanding of the algorithm on a primitive quantum circuit, it proved to defeat me because the primitive circuit is soooo much harder to use.
In the end, I finally found some code on the internet that worked on a super small number like 15. But to go deeper into it, I scoured all the 498 lines the code line by line trying to understand everything.
Shameless plug: If you are interested in learning more, I made a short video about how the algorithm works so check it out!
Another one of the few great resources on Shor’s algorithm on the web for recreating it on a quantum circuit is this paper. The code I found was based on the paper so try to understand as much as you can.
If I remember correctly, this is probably one of the only papers I have seen that don’t use super hard to understand math to explain Shor’s but instead super complicated circuits which were actually helpful.
Note to another professional that can understand this algorithm super well… MAKE SOME CONTENT, THE QUANTUM COMMUNITY NEEDS YOU.
And that is basically it
Those are some of the main challenges that I can think of when I tried to replicate Shor’s algorithm. I hope you don’t have to waste close to as much time on these problems as I did.
Thank you so much for reading my article.
I hope you learned something new and continue looking into quantum computing! If you really enjoyed reading this post, follow me on LinkedIn, and hit this article with some claps 👏! Thanks for reading.
