Quantum Computing 101 - Part Two (Shor's Algorithm)
Welcome to part two of our series on Quantum Computing, in which security research Kaboom hurts our heads with math by explaining Shors Algorithm.
A Q-bit is like a classical bit but with a state that is 0 or 1 and neither at the same time. This opens a bunch of new possibilities for us, in context quantum computer has a computational advantage in a lot of the jobs that classical computers just cannot perform in a reasonable amount of time. This state in which the Q-bit is a 0 and a 1 is called a superposition. One very importent fact of Q-bits in superposition is that when we measure will fall to either 0 or 1 on a 50-50 chance.
Before you read this article you should read the part one which you can find here, this makes sure that you know what we are going to talk about.
Read this if you want to know exactly how RSA works this, it will also help you in part 3 of this series.
Advantages of Q-bits
Now that we have a refresher on what Q-bits are lets take a look at how they can be helpful. Lets say that we have 3 bits and the same number of Q-bits, we can have a total of 3 * 2 number of possibilities or combinations of bits, but with the same number of Q-bits we have 3^2 (3 Squared) total possibilities or combinations, because each one of those 3 bits has an extra state called a superposition.
This gives Quantum Computers a massive exponential computational advantage over Classical Computers. This however doesn't mean that Quantum Computer will be better or faster at all the task that a Classical Computer can do, but it does mean for specific computation a Quantum Computer will win by default because a Classical Super Computer would take years to perform it or will not even be able to perform it. There is also a lack of good Quantum Algorithms, this however will be fixed as we get better at making these Quantum Computers and making them available to people who develop algorithms. Remember as of right now the main advantage we have over classical supercomputer is running quantum algorithms, but that would be the only reason to choose it not the speed its actually very slow on classical algorithms, the only place where we see the speed is in Quantum Algorithms.
Shor's algorithm is the most famous Quantum algorithm,it is not a very special algorithm as you can essentially run it on your normal home PC, but it runs exponentially fast on a Quantum Computer. Am going to try and attempt to explain this algorithm without using a lot of math and physics, which is really hard to do since its pretty much all math and physics.
So here goes a 4 weeks worth of my study notes covering a complicated algorithm in one big paragraph! Shor's algorithm's "basic" functionality is that it can guess factors of given number N (Really Big Number), we already have a basic algorithm that finds factors called The Euclidean Algorithm, which tell us the factor of N, so we take a guess "g". This "g" doesn't have to be a factor of N it can be a number that shares a factor of N( how 4 isn't a factor of 6 but shares a number that is 2).if you want more reading on this basic algo read this.
So lets look at shor's algorithm, it helps us make a better guess "g" as a factor, if there are 2 whole number(x,y) which don't share a factor to N, if we raise x to a certain power x^p we will have k * y+1, (x^p = k * y+1).
So now the main problem for us is to guess the right p. So for a very large number N and a arbitrary starting guess "g", we would have an equation:
g^p = k * N+1. Now if we rearrange this in a clever way we would arrive at this useful equation: (g^(p/2) +1) * (g^(p/2) -1) = k * N.
This looks like the factor equation which we are trying to find (N = a * b). This is the math part of shor's algorithm. The clever part is the science, The advantage we have with Quantum Computer is that we can input multiple bits in superposition which will all simultaneously calculate all the possible values of "p" and "g", however the problem comes from the fact that even if we do that and have an answer in superposition we will only get one of the answers and a low probability of the right one.
To solve this we also calculate the frequency ( sin and cos graphs) and these are also superposition, which helps us cancel out the wrong superposition and arrive to the correct answer, in the "first try".
This whole thing happens so fast that its mind blowing, Classical Computers would take thousands of years to calculate it. This would easily break all the encryption that we use right now. This also poses a big threat to the Cyber Security of Computers/Networks and Applications.If you wanna read more on the Shor's Algotithm you should read this article
This Video can help you understand the algo itself in great detail here. We will talk about Quantum Encryption in the next article in this series, which will solve this problem of breaking all encryption.For updates on these articles follow secjuice on twitter or Me. I am sorry about not posting article's, its just hard will a lot of stuff going around me.
You should also check out IBM Q. As well as Qiskit, a programming language to write and run code on a quantum computer.