How Quantum Computing Breaks Internet?

In today's world, every nation and individual actors are intercepting and storing lot's of data like passwords, bank details and social security numbers. But they can't open these files. So why are they doing it? Well because they believe that  within the next 10 to 20 year they will have access to quantum computers that can break the encryption in minutes. This procedure is known as Store now, Decrypt Later or SNDL And it works because there is information around today that will still be valuable in a decade. Things like industrial and pharmaceutical researches and top secret government intelligence, and everyone is aware of this threat. The National Security Administration says that a sufficiently large quantum computers if built would be capable of undermining all widely deployed public key algorithms.

"You know in 5 to 10 years quantum computing will break encryption as we know it today." - Sundar Pichai CEO-Google

Even though sufficient powerful quantum computers are still years away they're already a threat because of SNDL, which is why the US Congress just passed legislation mandating all agencies start transitioning right now to new methods of cryptography that can't be broken by quantum computers. 

How quantum computer breaks encryption?

In normal computers , a bit can only be in one state 0 or 1 at a time. So, if you had two bits, they could be in one of four possible state 00,01,10, or 11. Each of these state represents a number 0, 1, 2,or 3. If we want to calculation, for example, raising seven to the power of one of these numbers, we can do it for one state at a time, in this case 7squared and so we get the answer 49. 

Quantum computers consists of qubits which also have states 0 or 1. But unlike a classical bit, a qubit , doesn't have to be in just one state at a time. It can be in any arbitrary combination of those states, a superposition if you will, of 0 and 1. So if you have two qubits, they can exist simultaneously in a superposition of 0, 1, 2 and 3. Now, when we reapeat the same calculation, it will perform calculations for all 7four states at a same time. with superposition of the different answers. |1>+|7>+|49>+|343>. If we add another qubit we double the number of possible states. So with three qubits, we can represent eight states, and thus perform eight calculations all at once.

All of this answers to the computation are embedded in a superposition. When you make a measurement, you only get a single value from the superposition basically at random, and all the other information is lost. So in order to harness the power of a quantum computer, you need a smart way to convert a superposition of states into the information you want. This is an incredibly difficult task, which is why for most applications, quantum computers are useless.

In 1994, Peter Shor and Don Coppersmith figured out how to take a quantum Fourier transform. It works as normal Fourier transform, apply it to some periodic signal,  and it returns the frequencies that are in that signal. 

Consider this If we have a superposition of states that is periodic, that is the terms in the superposition are separated by some regular amount, we can apply the quantum Fourier transform and will be left with states that contain the frequency of the signal. So those we can measure The quantum Fourier transform, allows us to extract frequency information from a periodic superposition,

So, here is how we can do that. So let's say we have a number N, which is the product of two primes, p and q.

N = p.q

For sake of this example, let's set N equal to 77.

Now pick a number g that doesn't share any factors with N.

If you multiply g by itself over and over, you will eventually reach a multiple of N+1.

g.g.g.g.g.g.g.g.g.g.g = mN+1

In other words, you can always find some exponent of r, such that g to the power of r is a multiple of N+1.

Let's see how this works. 

Pick any number that is smaller than 77. I will pick the number 8.

this number doesn't share factor with 77.

Now multiply eight by itself once, twice, three times and so on, raising eight higher powers and divide each of these numbers by 77. we're not really interested in how many times 77 goes in that number, just remainder, what's left over, because at some point, 77 should divide one these numbers with a remainder of exactly one.

So there we have it, 8 to the power of 10 is 1 more than a multiple of 77.

So we've found the exponent R that satisfies this equation

8 to the power R = mN + 1

But how this help find the factor of N?

We will rearrange the equation to bring 1 over the left side

g^r – 1 = mN

And than we can split it into 2 terms like so.

(g^r/2+1)(g^r/2-1) = mN

Since r=10 , the two terms are

(g^r/2+1)=(8⁵+1)=32,769 

(g^r/2-1)=(8⁵-1)=32,767

These two numbers probably share factors with N. So how do we find them?

We use Euclid's algorithm. If you wanna find the greatest common divisor of two numbers, say 32,769 and 77, divide bigger number by smaller one and record the remainder.

32,769/77 = 425 R 44

Then Shift the number one position left and repeat.

77/44 = 1 R 33

Repeat the process again and again

44/33 = 1 R 11

33/11 = 3 R 0

When the remainder is zero, the divisor is the greatest common factor between two numbers. In this case, it's 11.

You could do same procedure with 77 and 11 to find another prime factor which is 7.

Here is the recap of the process to find factors of the number.

Now, you don't need quantum computer to run any of these steps, but on classical computer, this methos wouldn't be any faster than other methods. The key process quantum computer speed ups is step 2, finding the exponent you raise g 2 = mN+1.

To see why, let's go back to our example where 8 to the power of 10 is 1 more than multiple of 77. watch what happens to the remainders if we keep going 8 to the 11, 8 to the 12, and so on.

The remainders cycle and they will just keep cycling. Notice how the exponent that yields a remainder of one is 20, which is 10 more than the first exponent.

So you can find the exponent of R that gets us to one more than a multiple of n, by looking at the spacing of any remainder, not just one.

Now, we are ready to use a quantum computer to factor any large product of two primes. First split up the qubit into two sets. The first set we prepare is superposition of 0, 1, 2, 3, 4 ........ all the way up to 10 to the power of 1243. Yeah this is a huge superposition, but if we had perfect qubits,  it would required only around 4100. the other set contains a similar number of qubits all left in the 0 state for now.

Now make our guess G, which most likely doesn't share factors with N. We raise g to the power of the first set of qubits and then we divide by N and store the remainder in the second set of qubits leaving the first set of qubits as it was. 

With this operation we have entangled our two sets of qubits, but we can't measure this superposition. If  we do, we would get nothing but any random value and nothing. But there is a trick we can use. If we only measure remainder part we will obtain some random remainder. But this remainder won't occur just once. It will occur multiple times every time it comes up in the cycle they are each separated by a number and that value is the exponent that satisfies our equation. So more generally after measuring the remainder, we left with superposition of states that share the same remainder and the exponents will all be separated by the amount R. This is the number we are looking for.  Now, remainder for all state is same we have superposition that is periodic. Now if we aplly the quantum Fourier transform to this superposition of states  and we simplify a little here we will be left with states containing one over R. So all that's left to do now is perform a mesurement and find R by inverting it. And that's it for the quantum part.

Now, as long as r turns out to be even we can use r to turn our bad guess g into two numbers that likely share factors with N. And as long as these terms themselves are not multiple of N, we can use Euclid's Algorithm to find the factors of N and break the encryption. This would take only several thousand perfect qubits, but the qubits we have today are imperfect, so we need additional qubits to act as redundant information.

In 2012, it was estimated that it would take a billion physical qubit to break RSA encryption, but by five years later that number had dropped to 230 million And in 2019, after more technological breakthroughs, that estimates plummeted to just 20 million physical qubits. So how many qubits do we have today? Well , if we look at the state of IBM's quantum computers, we are nowhere near that number of qubits, But progress look to be exponential. So now it's just a question of when these two curves will collide before all our existing public key encryption can be broken. 

Because we've long known this threat is coming, scientists have been looking for new ways to encrypt data, which can withstand attacks from both normal and quantum computers.