Quantum computers can break the internet sooner than you think (2024)

All our digital systems that we use consist of transistors. You can consider them as tiny switches that either sends electrons or stops them.

In recent times, each CPU chip holds billions of transistors and all in size of an Apple watch. The sizes of each transistor differ from 7 nm to the cutting edge 5 nm(nanometers).

The sheer size of the transistor is unimaginable, each transistor is thinner than a strand of hair. This transition took more than two decades, starting from over 1000 nm to 5 nm.

So if we could decrease the size of the transistors annually, why are we still stuck at 5 nm from past 5 years?

There is a physical limit[1] on how small we can make our transistors, going down 3 or 2 nm isn’t viable as quantum tunneling kicks in.

Quantum Tunneling

It’s a phenomenon where the electrons typically teleport onto the other side of the transistor wall. Scientifically, Quantum tunneling occurs because there exists a nontrivial solution to the Schrödinger equation in a classically forbidden region, which corresponds to the exponential decay of the magnitude of the wavefunction.[2]

What this implies is that even though a transistor of size 4 nm might exist, it loses it’s core fundamental application of stopping electrons from flowing.

Scientists came up with a way to take advantage of the quantum properties of materials to come up with quantum computers.

They are fundamentally very different from classical computers, they’re just not faster than a supercomputer in every case. Playing Valorant on a quantum computer will not get you 1000+ FPS.

The problems they solve are different from what a classical computer is good at. A 100 by 100 digit multiplication is still good on a classical computer.

Quantum Computing

A ‘bit’ is the most basic unit of information in computing and digital communications. It can be either a 0(low) or 1(high).

In a quantum computer, we use ‘qubits’, instead of bits. where each qubit can hold a different value of 0 and 1 at once. This is known as superposition. Meaning, a qubit can have a 0.54 probability of being 1 and 0.46 of 0. This feature introduces a new dimension of complexity.

The superposition doesn’t last in it’s happy space for long. Depending on it’s probabilities, the state collapses to either 0 or 1 the moment we measure it.

The fact that n qubits can store all the numbers from 0 to 2^n, while n bits can store one number between 0 and 2^n. This is where quantum computers shine. A mere 300 qubits could hold around 2300 binary strings each of size 300 bits.

A qubit takes up less memory space than a regular bit, but this is more than just space — it provides a computational space.

Quantum Entanglement

Quantum entanglement is this amazing, counterintuitive phenomenon which explains how two sub-atomic particles are connected or correlated to each other even when they are light years away.

This was recently visualized[3], and it looks like yin-yang.

But what this typically means for our quantum computers is that we can measure both of our qubit states by just looking at one of them, when they’re entangled.

Now that we know about quantum properties that enable us to build quantum computers, are you wondering how would they look?

The long chandelier is a cryogenic refrigerator, which cools qubits to 10mK(milli Kelvin), that’s colder than space!

We’re not here to discuss on how this looks or what parts does it has. Thats a topic for another blog.

Internet Encryption(RSA)

Most of the internet encryption works on the fact that it’s really hard to factorize two large numbers.

It is very easy for a computer to multiply two large numbers, but given any number — say 732443. It is difficult to determine all of its prime factors; the number I used as an example is simpler, but picture a number with 2048 digits — even a supercomputer may take years to factorise it!

Let’s take an analogy to understand this easily, in these 3 steps.

1. Creating the lock(key generation):
   Assume you have a rare padlock (the public key). When you close this padlock, it can only be opened with a specifically crafted key (the private key). You may offer this padlock to anyone without worry since, while they can use it to lock items, they can’t open it once they’ve locked it.
   Consider this padlock to have a unique feature: anyone can see how it’s built (the visible mechanics, similar to the large product of two prime numbers), but recreating the specific key that opens it (factorising those numbers) is extremely difficult unless you know a secret about the original materials used to make the padlock.
2. Locking the Treasure box(Encryption):
   Your friend has a valuable message (or treasure) they want to securely convey to you. They use your public padlock to secure a box containing the message. The message is now safe. Unless they have the unique key, no one can read the message.
3. Unlocking the Treasure box(Decryption):
   When you receive the locked box, you use your specially designed key, which is the only key in the world capable of opening that padlock, and access the message. This action is like using the private key to decrypt a message encrypted with the public key.

The fundamental idea is that while multiplying two prime numbers together is simple (even for computers), determining which two prime numbers were multiplied to make a huge number is extremely difficult, especially as these numbers grow larger and larger. In our instance, giving someone the locked box (encrypted communication) does not provide them with an easy means to unlock (decrypt) it without the special key.

Shor’s Algorithm

Enter Shor’s algorithm, it can factorize large numbers in polynomial time making it exponentially faster than any known classical algorithm.

Instead of explicitly attempting to factor numbers, Shor’s technique logically uses quantum mechanics’ principles to identify the period of a certain function connected to the number to be factored. Once this period is known, the factorization is relatively simple to derive.

Given any period r, our two factors would be (a^r/2 −1) and (a^r/2 +1). And by making more probable guesses we can identity our two numbers.

Let’s go through the algorithm by factoring 15. Though 15 is a simple number to factor traditionally, it serves as a manageable example for our needs.

Step 1: Choose a Random Number
Pick a number a randomly such that 1<a<15. For our purposes, let’s choose a=7.

Step 2: Check if a shares a factor with N
Compute the greatest common divisor (GCD) of 7 and 15. If GCD is neither 1 nor 15, we’ve found a non-trivial factor. In this case, GCD(7,15) = 1, so we continue.

Step 3: Find the Period of the Function
We want to find the smallest r such that:
a^r mod 15=1
For a=7, the sequence is:
7^1 mod 15 = 7,
7^2 mod 15 = 49 mod 15 = 4,
7^3 mod 15 = 343 mod 15 = 13,
7^4 mod 15 = 1

Here, the period r = 4.

The quantum part of Shor’s algorithm is mainly used for efficiently finding this period r.

Step 4: Calculate Factors
Now, we have the period r=4, which is even. We compute:
(a^r/2 −1) and (a^r/2 +1).
So, for our example, (7^4/2 −1) = 48 and (7^4/2+ 1) = 50.
Finding the GCD of 48 and 15 gives us 3, and finding the GCD of 50 and 15 gives us 5. So, 15 can be factored into 3 and 5.

The quantum advantage is this ability of a quantum system to exist in a superposition of states.

Shor’s algorithm’s actual beauty resides in its brilliant use of quantum physics to change a problem that is difficult for classical computers to solve (i.e., identifying the period) into a problem that quantum computers can solve effectively.

Shor’s algorithm requires at least twice the number of qubits as the number of digits in the number being factored. For example, if the number being factored is a 1024-bit number, then it would require at least 2048 qubits.

Most estimates say that a quantum computer will need around 1,000 physical qubits to represent just one logical qubit. However, in practice, you’ll need a lot more for error correction.

Shor’s algorithm can break asymmetric encryption with twice as many qubits as the key size. For example, breaking AES-128 encryption should require a quantum computer with around 2,953 logical qubits, while breaking AES-256 would need around 6,681 qubits.

Looking at IBM’s roadmap[4]

We would almost have 4000+ working qubits, so just in the next decade we can look at breaking encryption.

References

[1] — Tunable electronic properties of germanene and two-dimensional group-III phosphides heterobilayers(physical limits of silicon transistors) — link
[2] — Quantum tunneling — link
[3] — Entanglement visualization —link
[4] — IBM Quantum —link

Further Resources

Quantum Computers Explained — Limits of Human Technology — Kurzgesagt(link)
How Quantum Computers Break Encryption — MinutePhysics(link)
What is quantum computing? — IBM(link)
RSA Algorithm — Brilliant(link)