The 1992 Hollywood thriller Sneakers foretold a world in which a computer could decode massive amounts of encrypted information. “Cryptography systems are based on mathematical problems so complex that they cannot be solved without a key,” says Irwin “Whistler” Emery, a character in that movie, while a mathematician named Gunter Janek programs a chip inside a small box, disguised as an answering machine, to decode all the computerised classified data in the world.
In the 1980s, physicists like Richard Feynman and David Deutsch pointed out the possibility of very fast quantum computing. In 1981, Feynman famously quipped: “Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical.” Two years after Sneakers broke into the theatres, MIT mathematician Peter Shor in 1994 derived the math that makes cryptography vulnerable to quantum computers. This stimulated subsequent research on the feasibility of constructing quantum computers. A quarter of a century on, quantum computing isnow one of the hottest topics in both quantum physics and computer science. Suppose we’d like to find the Jack of Hearts from a pack of cards. An ordinary computer uses bits, which assigns everything 0 or 1.
The computer may mark the required card ‘1’, and each of the other 51 cards ‘0’. A search operation goes on checking every card—whether it is 1 or 0, and this takes 26.5 operations on an average. However, a 6 qubit (quantum bit) quantum computer, if possible, having 26 (i.e., 2x2x2x2x2x2) parallel bits, will be able to identify the required card at one shot. Such is the magic of quantum computing! A quantum computer with N coupled qubits has computing power equivalent to a classical computer with 2N parallel bits. It could be interesting to see how quickly 2N diverges with N.
Suppose grains of wheat are placed in the squares of a chessboard in such a way that one grain is placed on the first square, and from the second square onwards, we put twice the number of grains of the previous square in each square—this would result in 1, 2, 4, 8, 16, 32 grains in thegrains in the 64th square. Eventually there will be only 255 grains in total in the first row, nearly 4.3 million grains in the first half of the board, a n d a t o t a l o f 18,446,744,073,709,551,615 (yes, 20 digits!) grains would be on the chessboard, an unbelievable number! This is about 1,645 times the global yearly production of wheat.
A bit in an ordinary computer takes either 1 or 0; however, in a quantum computer, the qubit can take 1 or 0 or both at the same time. A bit specifies only two poles of a sphere, whereas a qubit may correspond to points on the sphere; such is the scope of quantum computing. With two large prime numbers p and q, we can easily multiply them and find M = pxq.
Conversely, it is easy to factor a small number, say 21, which is the product of two prime numbers, 3 and 7. However, it becomes extremely difficult to find the two prime factors if M contains several hundred digits; it might take billions of years and require the use of several hundred supercomputers. This difficulty, the ‘factoring problem’, is the basis of many encryption schemes forprotecting credit cards, state secrets, military and other confidential data. Sneakers thought standard encryption was so safe, and they were silly.
Gunter Janek, in the film Sneakers, mentions “an intriguing possibility for a far more elegant approach” to factoring large numbers. We can see that a quantum computer with moderate qubits might be able to find the prime factors in a few seconds, by using hundreds of atoms, essentially in parallel, to quickly factor huge numbers. How far away are quantum computers? In November 2017, IBM announced it had built a 50-qubit quantum computer, far from stable though, as the system could only hold its quantum microstate for 90 microseconds, much less than the times needed to make quantum computing practically viable. In early 2018, Google announced it had a quantum processor with 72 qubits.
It might not be a distant future when stable quantum computers with reasonable qubits would be commercially available. In India, the Department of Science & Technology has set up a programme called Quantum- Enabled Science & Technology (QuEST), and will invest `80 crore in the next three years to facilitate research on quantum computers. And after three years, the effort would be to push QuEST to the next phase to ensure that India’s quantum computing programme matches international standards.
The first-ever meeting for the QuEST programme was held in early January 2019 at IIIT-Hyderabad where a roadmap was discussed that would help in laying the groundwork for building quantum computers in India. When quantum computers are fully functional even in the modest range of qubits, the exponential speedup could solve many currently unsolvable computational problems including decryption, quantum chemistry, and combinatorial optimisation.
The quest for finding a prime number with a billion digits might be over in no time. However, this would invariably render most of the modern cryptography useless; security based on ‘standard’ cryptography could be broken immediately, and the dystopian story of Sneakers might become a reality!