Sotd 35: Quantum Computing, Supremacy and Google’s Sycamore

Image taken from: https://www.machinedesign.com/cad/quantum-computing-simulates-interactions-holding-universe-together

Computer Science generates a lot of buzzwords, and when things get fuzzy, the reporting often gets fuzzier. Quantum Computing has been making the news lately – with several articles claiming it can ‘break all encryption’ , ‘give rise to AI’ and many other things. A while back, Google built a famous Quantum Computer called Sycamore and claimed that it had achieved ‘Quantum Supremacy‘ by solving a problem that would take a classical computer 10,000 years to solve. The paper making these claims was later retracted, but many sites managed to get a copy. You can read the original paper: Quantum Supremacy Using a Programmable Superconducting Processor

Image credits: https://medium.com/@kareldumon/the-computational-power-of-quantum-computers-an-intuitive-guide-9f788d1492b6

So what gives? as with everything, there’s a catch. Lets begin by understanding what a Quantum computer is.

So what exactly is a Quantum computer?

Normal computers or ‘Classical’ computers work by manipulating bits – 0’s and 1’s. The fact that they use binary is not particularly important. A computer using say, -1,0,1 (trits) or even 0,1,2,3,4,5,6,7,8,9 (decimal) would still be a classical computer. In a classical computer, the input and output are well defined. So well defined that you can even represent 0’s and 1’s as voltages that you can directly measure!

A quantum computer uses Quantum Bits, or qubits. A qubit is basically the quantum analog of the two-state bit. The spin of an electron (+1/2 or -1/2) can be taken as spin up or spin down. Or the polarization of a photon can be taken as horizontal polarization or vertical polarization. A qubit can exist in multiple states at once – this is the consequence of a phenomenon known as quantum superposition. This phenomenon allows for some kinds of computation to be done exponentially faster on a quantum computer than a normal one, while for others it doesn’t make much difference.

Of course, humans are governed by classical physics, and we ultimately live in a world governed by classical physics (for anything larger than an atom). So it naturally follows that the output must be classical – but the act of measuring the values causes the qubit to lose coherence and collapse into one of the possible states that a system can occupy. It’s here that one of the first weird properties of quantum computers becomes apparent –

Quantum Computing is Probabilistic

Without realizing it, one of the features we take for granted in modern day computers is their deterministic nature – for a fixed input, the computer will give a fixed output. Quantum computing in contrast is inherently probabilistic. You can never state a result with 100% confidence. You can solve this problem by running the same problem on multiple quantum computers and comparing the results but its a pretty big fundamental shift on how we look at things.

A Quantum Computer cannot automatically create an AI

A quantum computer can be ‘Turing complete’ just like a normal computer. So in theory, any quantum computer can be simulated in a classical computer and vice versa although there is a caveat – A quantum computer can easily simulate a classical computer, but simulating a quantum computer on a classical computer takes a lot of memory.

For example, take a system with 5 qubits. Each qubit can be a bit, but it can also be 2 bits at the same time due to quantum superposition. So a system of just 5 qubits requires 2^2^5 classical bits to simulate, which is about 536 megabytes! This might not seem like a lot, but its only 5 qubits, computer systems today easily cross billions of bits. A system of a billion qubits would require an exponentially large amount of memory to simulate in a classical computer.

As stated before, a quantum computer can only offer a speedup and allow us to solve some problems that can exploit features of quantum computing. But it isn’t a one size fits all approach to magically finding solutions to problems that we don’t know how to approach. We are pretty far away from an AI, and we still have to do all the thinking. In simple words, quantum computing may be a faster, newer type of car compared to a bullock cart that a classical computer is, but we still have to do the driving.

Quantum Computing is bad news for many types of cryptography

Increase in computational power are always welcome, especially with the end of moore’s law in sight. But there are some aspects that rely on certain operations being difficult to be effective – cryptography being the prime example. While it might not be obvious to the general public, cryptography and encryption underlies much of the world wide web. When a user interacts with a website a protocol called ‘https‘ is used to encrypt the data that the user sends to the website and the data that comes back. Similarly, passwords must be stored in an encrypted format so that they are not vulnerable to attack.

Quoting Quantum Computing: Progress and Prospects:

Creating a secure communication channel between two people is usually done as a two-step process: two people are given a shared secret key in a process called key exchange, and then this shared secret key is used to encrypt their communication so it cannot be understood (decrypted) by anyone without the secret key. The message encryption is called symmetric encryption, since both parties used the same shared secret key to encrypt and decrypt the communications traffic.

The key exchange protocols function under the assumption that certain problems are intractable. One such example is “discrete-log problem on elliptic curves” . This problem can be solved in time 2^n/2, or exponential time n. Usually the size of n is 256 bits, so the time required to solve is of the order 2^128, which is an inordinately large amount of time.

Quantum Algorithms

Algorithms that exploit the features of quantum computers have already been developed. The two most famous examples are Grover’s algorithm , for searching an unordered list or an unstructured database and runs quadratically faster than the best classical algorithm – A linear search. Shor’s algorithm is even crazier, it runs almost exponentially faster than the best algorithm for factoring, the number field sieve.

RSA is one famous algorithm that can easily be broken by even a small quantum computer. It is estimated that in order to break RSA 1024, one needs a quantum computer of 2,300 qubits. This is not a very large number of qubits, we currently have quantum computers that run into 100’s and allegedly even 1000’s of qubits (D-wave). This could spell bad news for a whole lot of things that use RSA.

The Internet is a behemoth, and adapting to change takes a lot of time. When a vulnerability was found in an algorithm called MD5, it took the internet almost a decade to move onto better algorithms. This necessitates post-quantum cryptography to become a mainstream thing before quantum computers arrive, and the world might not react in time.

Quantum Computing can probably solve a lot of interesting problems

Image of nitrogenase, this is currently too difficult to simulate even in a supercomputer. Image credits: https://www.pnas.org/content/early/2017/06/30/1619152114

In a paper, Microsoft and ETH Zurich outlined how Quantum computing could potentially reduce energy consumption of the world by up to 3% by making the production of fertilizer much more efficient. How? currently the production of nitrogen based fertilizers has not changed much since the advent of the Haber’s process over a 100 years ago, but in nature, bacteria use an enzyme called nitrogenase to convert nitrogen to ammonia way more efficiently. Nitrogenase is a very complicated molecule and is currently out of reach of even supercomputers to simulate, but theoretically a much smaller quantum computer could do it!

To quote Microsoft’s research blog:

Today, we spend approximately 3 percent of the world’s total energy output on making fertilizer. This relies on a process developed in the early 1900s that is extremely energy intensive—the reaction gas required is taken from natural gas, which is in turn required in very large amounts. However, we know that a tiny anaerobic bacteria in the roots of plants performs this same process every day at very low energy cost using a specific molecule—nitrogenase.

This molecule is beyond the abilities of our largest supercomputers to analyze, but would be within the reach of a moderate scale quantum computer. Efficiently capturing carbon (to combat global warming) is in the same class of problem. The search for high-temperature superconductors is another example.

What did Google exactly do with Sycamore?

Developing and maintaining coherence in a quantum computer is a difficult task – so much so that google could not initially control a 72 qubit version of the quantum computer they built and had to cut it down to 54 qubits, of which 53 qubits were found to be working. What does achieving ‘quantum supremacy‘ mean? to quote the wiki:

Quantum supremacy is the potential ability of quantum computing devices to solve problems that classical computers practically cannot. Quantum advantage is the potential to solve problems faster. In computational-complexity-theoretic terms, this generally means providing a superpolynomial speedup over the best known or possible classical algorithm.

Google’s computer was able to solve a problem- proving the randomness of numbers generated by a random number generator. This would have taken Summit, the worlds fastest supercomputer 10,000 years to solve, but took sycamore only 3 minutes and 20 seconds to solve. This means it is practically impossible for an everyday computer to solve this problem, hence google’s claim of quantum supremacy. Google predicts that quantum computers will grow at a double exponential rate, while moore’s law predicted doubling of power every 18 months or so.

Of course, this is a somewhat contrived problem, and attracted a lot of criticism from Google’s detractors:

Dario Gil, head of research at Google competitor IBM, criticised Google for its claim of quantum supremacy, telling the FT is is “just plain wrong”.

He said the work was a “laboratory experiment” designed to implement a specific procedure with “no practical applications”, and that as such it was misleading to use the term “quantum supremacy”.

Regardless of whether Google did achieve quantum supremacy, they did show something interesting – that quantum computing was not some far off dream and within our lifetimes we could see giant strides in this area. Companies like IBM and D-wave have already demonstrated quantum computers that have upto 1000 qubits, and with increased funding and work being done in this area, the future holds a lot of promise!