Quantum supremacy and the threat to the digital economy
Dystopian fantasies cannot get any bleaker than an army of hackers equipped with quantum computers. However, the prohibitive cost of developing these machines has insofar kept them away from the reach of miscreants.
Röhan Abraham
In the conspicuously titled collection of essays, ‘Small is beautiful,’ the economist E.F. Schumacher makes a case for reductionism as a sign of superior intelligence. “Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius — and a lot of courage — to move in the opposite direction,” he wrote in 1973.
In the intervening years, mankind has exhibited the requisite acumen to engineer hardware that is incrementally smaller and more capable than its predecessors. In computing terms, processing power has increased while algorithms have become more complex than ever.
Technology has indisputably acquired ubiquity, but this is also a cause for worry.
The recent fiasco at the social networking website Facebook is ample proof that without an active security net in place, private information on the internet can be subverted without much effort.
With increase in proliferation of the internet, many essential services have moved online. Brick-and-mortar stores are witnessing diminishing footfalls, with their clientele swapping the lures of the bazaar for the hefty discounts offered by online retailers. To service this demand for goods and services that is being transacted electronically, financial institutions have also expanded operations to encompass the airwaves.
Internet banking, mobile wallet apps and electronic funds transfer have been around for a while now, but so have the cryptographic algorithms which form the security backbone of their operations.
The reductionist zeal with which researchers are developing quantum computers, could, however, pose an existential threat to cryptography as we know it. Last month, Google unveiled a 72-qubit gate-based superconducting system that it claims “will be able to outperform a classical supercomputer on a well-defined computer science problem, an achievement known as quantum supremacy.”
Theoretically, quantum computers can successfully sift through the infinitesimal possibilities accorded by public key cryptography, a system which uses two keys for decryption. Algorithms used for data encryption online, such as RSA, which find use in payment gateways, have been broken by tests involving Shor’s algorithm running on quantum computers.
As the race for quantum supremacy hots up, scalability is set to rise, and correspondingly, the ability of these small and beautiful computers to chew through extant cryptographic standards without much ado. Here is all you need to know about the technology that could potentially force a rethink of governing standards in information security.
What is quantum computing?
Quantum mechanics forms the bedrock of quantum computing. Digital computers based on binary logic use transistors for their realization. Semiconductor chipsets for conventional computers are designed by keeping in mind that data is to be encoded into binary digits, or bits, each of which can either be in two states, one or zero.
A qubit, the building block of quantum computers, can encode one and zero into two distinguishable states while existing in a number of other states through the principles of superimposition and entanglement, which are borrowed from quantum mechanics.
A Bloch sphere is the logical representation of a qubit. The two poles represent the states one and zero. At any given time, a qubit can exist in a superimposed state, which can be represented as one among the infinitesimal points on the sphere. These superimposed states are a vector combination of one and zero.
In effect, quantum states exploit the fact that an entity can be more than one thing at the same time. To better understand this, consider the case of a coin flipped in the air. From the point it is tossed, we do not know on which face it will land. When airborne, the coin can be thought of as being a combination of heads and tails simultaneously.
Interference and duality
Quantum mechanics relies on the fact that particles and waves have a dual nature. For example, particles like electrons tend to behave like waves, whereas light waves have also been shown to display particle nature. This can be best described using the double slit experiment.
In this experiment, a pair of parallel slits is made on a partition placed between an electron gun and a screen. The particle-waves traveling through either slit end up interfering with each other. If the peak of one wave aligns with that of the other, the signal captured on the screen will be brighter whereas if a trough and a peak interfere, then thy mutually cancel each other out, and no luminescence is captured on the screen.
Particle waves take the form of sine curves, with the trough and peak representing -1 and +1 respectively, the range of the function extending to all real numbers in between. If these two states can be thought of as those in a binary computer, then a quantum state can capture the interference in the system.
So how does this phenomenon affect quantum computers?
Quantum computing can be thought of as being analogous to flipping millions of coins simultaneously. The key to predicting the outcome of this event is by using probability to exact the quantum states each of these coins take up once midair. The coins are bound to interfere.
Alternately, if the outcome is known beforehand, the initial state of all the participants in the event can be determined. However, this is much more difficult, and is beyond the ken of most classical computers.
This problem can be thought of as an event where five coins are tossed simultaneously in a closed environment. Let us assume that this resulted in the drawing of four heads and one tail. Quantum theory can help in reverse-engineering the sequence of motion of the coins to determine the result according to order.
Instead of manually skimming through the sample size of binary possibilities (a coin being either head or tail), quantum theory considers a coin as being both heads and tails during its flight. This is analogous to a bit being both one and zero simultaneously.
The motion of the coin can be a vector combination of these two states, and depending on the spin, and interference with the path of other coins, the quantum state can predict with a high degree of probability, the face of the coin at the other end-point of its flight path.
The cryptographic standards of today use the inadequacy of classical computers to work backwards to find the factors of extremely large numbers. Quantum computers outsmart their classical peers by parsing the range of possibilities into well-defined periods and using quantum states to check for the answer in different periods simultaneously.
As Scott Aaronson, a theoretical computer scientist at the University of Texas, Austin told Gizmodo, “… the idea is to choreograph a pattern of interference” so that everything cancels out except for the answer you were looking for.” This is particularly useful in solving complicated numerical problems that arise in cryptography.
Encryption and quantum states
Modern computers evolved from primitive counting machines, and to this day, binary addition remains the foundation of all other operations in a computer’s repertoire. The act of multiplying two numbers, whatever their size is a feat that most conventional computers can accomplish without breaking a sweat.
However, things get more complicated if computers are asked to calculate the factors of a very large number, say, one which comprises of a few hundred digits. Such tasks are near-impossible for most computers and even sophisticated workstations with greater processing capability.
This vulnerability is taken advantage of by cryptographic algorithms like RSA. The inability to factor very large numbers forms the underlying basis of modern cryptography.
Cryptography is reliant on the handicap of classical computers running on binary logic to factor 500-digit numbers in a time-bound manner.
Whenever you send a message on WhatsApp, buy a book on Amazon, or order food on Zomato, the RSA algorithm is called into action and encodes your personal details inside a long stream of digits.
The website or entity, with which you want to transact, generates a public key, which is an extremely large number. This is publicly available and contains your financial credentials such as credit card number and bank details. The key to this cryptosystem is the product of two prime numbers (N = p * q) which is known only to the seller.
In order to obtain the key, and hence hijack your account, hackers have to factor the large public key generated by the seller. The numerical heft of the number makes it computationally impossible for the system to be breached. However, quantum computers running Shor’s algorithm could alter the status quo.
Shor’s algorithm
The eponymous algorithm for integer factorization was formulated by Peter Shor in 1994. The solution proposed by Shor in finding the prime factors of an integer has subsequently found application in quantum computing. Peter Shor was awarded the Gödel Prize for his efforts.
Shor’s algorithm consists of two parts, the first of which is a period finding problem that can be solved on a regular computer. The second part, which is responsible for expediting the speed of computation, involves finding the period using the quantum Fourier transform. Here is a brief overview of the algorithm.
Step 1: Let m be a random non-zero integer. Use the greatest common divisor (gcd) algorithm for classical computing to find the gcd (N,m).
[gcd is the largest positive integer that divides each of the integers. For example, the gcd of 30 and 12 is 6.]
If, gcd (N,m) = 1, proceed to step 2. Otherwise, a non-trivial solution has been found.
Step 2: Find the period P of: m mod N, m^2 mod N, m^3 mod N, m^4 mod N, …
[The modulo operation finds the remainder after one number is divided by another (sometimes called modulus). Given two positive numbers, m and N, m modulo N (abbreviated as m mod N) returns the remainder of the division of m by N.]
Step 3: If the period P is odd, go back to step 1 and proceed with another random integer. If P is even, go to the next step.
Step 4: Check if: m^(P/2) + 1 is not equal to 0 mod N. If true, proceed to the next step, otherwise, go to step 1.
Step 5: Find the gcd (m^(P/2) -1, N).
The answer is a non-trivial prime factor of N. More importantly, this gives us the key to breaking the RSA cryptosystem.
The algorithm might seem confusing, but it isn’t. Let us try and solve Shor’s algorithm by taking N=91.
Step 1: Let us consider a random number 3 such that N-91, m=3
gcd (3,91) = 1 [since they have no common factors]
Therefore, proceed to the next step.
Step 2: Find the period P of : 3 mod 91, 3^2 mod 91, 3^3 mod 91, 3^4 mod 91, …
A quantum computer finds the period of the above function by performing the quantum Fourier transform operation. This relies on the ability of quantum computers to be in multiple states at the same time, thereby allowing the function to be evaluated simultaneously for different values.
In this case, we manually find the period P through repeated long division. When remainder obtained by the modulo function starts repeating, we have found the period of the function.
Here, the remainder returns to 3 after 6 rounds. Hence, P=6.
Step 3: Since P = even, we proceed to the next step.
Step 4: We check if: m^(P/2) + 1 is not equal to 0 mod N
Here, 3^(P/2) + 1 = 3^(6/2) + 1 = 3^3 + 1 =27 + 1 + 28 is not equal to 0 mod N
Step 5: Find a factor q such that q = gcd (m^(P/2) -1, N)
Here, q = gcd (3^(P/2)–1, N) = gcd (3^(6/2)–1, 91) = gcd (2^6, 91) = 13
Since 26 = 13 *2
91 = 13 *7
Hence p = 13 , q = 7. RSA has been broken for this example.
However, in real life N will be infinitesimally larger than 91, making factorization impossible for classical computers, leave alone solving the period-finding problem by long division.
If at all human beings were to manually factorise a 1000-digit number, it would take multiple generations of a family, billions of reams of paper, and an equal number of pencil stubs, to obtain the required factors.
While the intractability of modern cryptography is a cause of great civilisational triumph, the dawn of quantum supremacy could be the undoing of society since almost all facets of life, from communication to commerce, are now conducted online.
Although Google, IBM, and D-Wave Systems have made giant strides in increasing the number of qubits in a quantum processor, mass production still remains a pipe dream.
Moore’s Law
Like E.F. Schumacher, Gordon Moore, one of the co-founders of the chipmaker Intel, was also one to make grand pronouncements. Mr. Moore said that the number of transistors on a silicon chip will double approximately every two years. This means that computers are going to shrink, or conversely, the productivity of silicon as real estate for transistors, is going to rise.
While classical computers have broadly adhered to this trend, the birth of quantum computing has brought Moore’s Law to a dead end. The fabrication of processors capable of attaining quantum states follows a different approach from the transistor-driven chipsets working on binary logic.
Graphics Processing Units (GPUs), which are more sophisticated processors used for applications involving high-end graphics — like gaming, and lately, cryptocurrency mining — also pose a credible threat to Moore’s law. Nvidia CEO Jensen Huang stated at the GPU Technology Conference (GTC) 2017 in Beijing that Moore’s law was dead and that GPUs would ultimately replace conventional CPUs.
Intel still believes computer processors can get even smaller, and aesthetically, more beautiful. Intel CEO Brian Krzanich subsequently downplayed the assessment of his peer from Nvidia. While a saturation point will be hit only when chip size has contracted to that of atomic proportions, the present developments in alternate processing technologies could alter Moore’s law, or possibly, amend it.
Post-quantum cryptography
Dystopian fantasies cannot get any bleaker than an army of hackers equipped with quantum computers. The prohibitive cost of developing these machines has insofar kept them away from the reach of miscreants. However, information security wonks are taking no chances.
The best antidote against quantum computers has been found to be cryptosystems that employ the same principles derived from physical phenomena as its nemesis– namely the duality of particles and waves, and the existence of quantum states.
Post-quantum cryptography has been focused on six main approaches of which lattice and multivariate-based cryptosystems are a part. These are said to be quantum-resistant, but the cost overheads and time latency involved in authentication make them unsuitable in dealing with heavy traffic in real-world situations.
Both two-factor authentication and public key encryption — which find application in financial transactions — are structurally sound, but can be cracked using a sufficiently powerful quantum computer running Shor’s algorithm. Since quantum computing is still in its infancy, these vulnerabilities remain chinks in the armour.
Quantum supremacy might yet be far away, but the threat is tangible.
