Table of Contents (click to expand)
The feat of being able to solve a problem that is seemingly impossible for even the greatest supercomputer is termed quantum supremacy.
Have you ever looked at a math problem in class, then immediately turned away and said to yourself with 100% certainty, “Wow, that’s impossible to solve.” If so, welcome to the club. If not, well your math class obviously wasn’t challenging enough.
Anyways, think about that one insane math problem. You gave it several attempts, used all the theorems and hacks in your mathematical arsenal, yet you simply couldn’t crack it. Let’s say you happen to have a supercomputer handy. You load it up, put in the math problem and voila, it spits out the answer in a matter of seconds, leaving you feeling utterly inadequate. Well, that’s how supercomputers feel when they step up against a quantum computer.
There are some complicated mathematical problems that would take even the world’s most powerful supercomputer thousands of years to solve. Theoretically, a quantum computer could solve these problems in a matter of minutes. This feat of being able to solve a problem that’s seemingly impossible for the greatest supercomputer is called quantum supremacy.
Recommended Video for you:
What Is A Quantum Computer?
A quantum computer is one that functions based on the laws of quantum mechanics. Computing devices, everything from your smartphone to a supercomputer the size of a room, have the primary function of storing and manipulating data.
Traditionally, computers have stored information in the form of bits that exist in a binary state of either 1 or 0. All manipulations of data are basically the modifying of these infinitesimal bits of 1s and zeros. On the other hand, quantum computers have the same primary function with one critical difference; they store and manipulate data by leveraging quantum mechanical properties, such as superposition and entanglement.
In quantum computers, data is stored in the form of quantum bits, commonly shortened to qubits. Qubits are different from conventional bits, as they can exist as both 1 and 0 at the same time by virtue of superposition. In addition, qubits can entangle with each other and behave as a system; these two qubits could be kept at opposite ends of the universe and would still hold a strong correlation to each other. Let’s uncomplicate this rather heady concept a little further.
Also Read: What Is Quantum Physics?
What Is Superposition?
Imagine every bit as a coin. The coin can either have a value of heads or tails. Every bit will store a value of heads (1) or tails (0). Contrary to this, qubits can be imagined as coins that are constantly spinning, never staying flat on the ground. In this state of spin, you could never firmly say whether a coin was a head or a tail. In fact, the coin would remain in both states at the same time.
Therefore, a qubit can store a value of heads (1) and tails (0) at the same time. Essentially, that’s superposition.
What Is Quantum Entanglement?
Now imagine that two of these coins always exhibit a correlated outcome, either the same or the exact opposite. If coin A shows heads, then coin B would automatically show heads. Or, if they are oppositely correlated, when coin A shows heads, coin B would automatically show tails.
This property of quantum particles to ‘entangle’ with one another and behave as a strong correlation system, even across interstellar distances, is called quantum entanglement. Einstein famously described this property as “spooky action at a distance”.
These and several other ‘spooky’ quantum properties are being leveraged to conduct some of the most complex calculations on quantum computers every single day. So, what are these bizarre calculations that are seemingly impossible for even the most powerful supercomputers to crack?
Also Read: Are Quantum Effects Restricted To A Scale?
What Is Shor’s Algorithm?
One of the most famous examples is Shor’s Algorithm, an algorithm that, in theory, could crack many of our modern encryption systems. I say “in theory” because it’s not as easy as it sounds. Before we get into the details of Shor’s Algorithm, let’s try to understand the basics of cryptography, at least enough to give you some context within which Shor’s algorithm can prove useful. Encryption is fundamentally a way to scramble data so that prying eyes cannot decipher what’s being shared.
Let’s say that James Bond wants to transfer some secret files he stole from Goldfinger’s hidden lair. Before he can share the files with M, he encrypts them beyond recognition by ‘locking’ the files with a 500+ digit number. For M to decrypt the files, she needs a ‘key’, which would be the prime factors of this complex number.
We all know how prime factorization works. We’ve done it in school scores of times. However, we’ve only dealt with numbers having 2 or maybe 3 digits, at most. Factorizing a 500-digit number is a serious task! If you want to break the ‘lock’ James Bond put on those secret files, try and guess every prime factor of the 500-digit number.
Let me save you some time and say that it’s impossible. Even a supercomputer making arbitrary guesses would take thousands of years to have any success in cracking that ‘lock’.
What Shor’s algorithm does is make the guessing a little more accurate. Let’s say that computer guesses the number 7. You may find out it is a factor, or it isn’t. This information is utilized in Shor’s algorithm to come up with a more educated guess for the next number, which could be a prime factor.
While this is still an iterative process, it significantly cuts down on the time needed to find success in the task. Where it once took 2000 years, Shor’s algorithm could get it done in 500. Not an ideal timeframe, but hey, a 75% reduction is a big deal!
Also Read: How Are Prime Numbers Used In Cryptography?
What Is Quantum Supremacy?
Peter Shor never meant for his algorithm to be used by a classical supercomputer running for 300 years looking for prime factors. Shor came up with the algorithm as a researcher at Bell Labs, AT&T, where he was focused on solving complex mathematical problems.
He imagined that in a future far far away, humans might successfully design a computer powerful enough to execute his algorithm within a reasonable time frame. The day a quantum computer could execute complex mathematical algorithms like Shor’s, which are nearly impossible for present computing technology to solve, it would have achieved quantum supremacy.
With companies like Google and IBM dedicating precious resources to the development of quantum computing, a successful codebreaking powerhouse may not be as distant as Shor imaginedt. In fact, Google’s quantum computer is said to have already achieved quantum supremacy last month by cracking a similar, albeit contrived, complex math problem faster than the fastest classical supercomputer. The problem, which was estimated to take a supercomputer 10,000 years to solve, was solved by Google’s quantum computer in 3 minutes and 21 seconds.
Achieving quantum supremacy is a big deal. Google’s achievement marks the very first time a quantum processor has successfully solved something a classical computer could not. However, Google’s machine was built to solve that one singular contrived complex problem.
The significance of that fact is simple: solving that problem has no practical applications. It simply acts as proof of concept for technologies to exist in the near future that can solve real-world complexities like Shor’s algorithm.
Moreover, cracking Shor’s algorithm may not be the end of all encryption, as popular blogs may have you believe. Just because you make a universal key that can break any lock does not mean we can never design a better lock.
Quantum computers of the future, those that would take quantum supremacy for granted, could give rise to quantum encryption, which would be even more secure and render Shor’s algorithm nothing more than an interesting theoretical concept of the past.
Also Read: Can Computers Keep Getting Faster Forever?
How well do you understand the article above!
References (click to expand)
- Shor, P. W. (1995). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Version 2). Arxiv.
- (2006) Quantum Computing - Stanford Encyclopedia of Philosophy. The Stanford Encyclopedia of Philosophy
- Google claims to have reached quantum supremacy. The Financial Times
- Google claims to have demonstrated “quantum supremacy”. economist.com
