Shor’s Algorithm: How Does it Work?
Finding Prime Factors of Integer using Quantum Computer
We all have possibly read stories and news about the encryption schemes to protect our credit cards, confidential files will be broken by the advancement of quantum computing technology in recent years. Here’s another recent Nature article (from this year, February) about it and how we can safeguard our privacy. Professor Peter Shor proposed the basis of factoring large numbers into primes using a quantum algorithm that can perform this calculation exponentially faster than a classical computer [1].
Here we discuss the basics of Shor’s algorithm and where quantum computers actually play a part in all of these in brief. Shor’s algorithm uses the quantum phase estimation algorithm which is based on Quantum Fourier Transform and both algorithms have already been discussed before in separate posts. Here, we make use of those concepts later, but if you remember some high school algebra and linear algebra (in relation to Quantum Mechanics) from undergrad school then, you will be able to understand the basics of Shor’s algorithm quite well and that’s the target. We will start by reviewing some mathematical terms/calculations that we learned in high school and during our undergraduate. Let’s begin!
