Beyond the Binary

Google recently claimed to have achieved ‘quantum supremacy’ — a practical demonstration of a problem that can be solved much faster on a quantum computer than on a ‘simple’ supercomputer. Some have claimed that this heralds a new era in computing. It paves the way for computers to far surpass their current limited abilities enabling new applications in AI, medicine, data science and more. IBM has refuted Google's claims of quantum supremacy.

If you are involved in developing new technology, is it time to change your strategy and think of quantum computing as your platform of choice? Did Google really achieve quantum supremacy and how should we think about it? Let us begin by understanding what quantum computers are, and why we continue to believe (since the day Feynman said it so many years ago) that quantum computers could surpass vanilla computers in their computational abilities.

[Psst. If you know a little bit of quantum physics and quantum computing, jump directly to my analysis of quantum supremacy.]

Beyond the binary

Schrödinger came up with a famous thought experiment, which is still used to explain quantum physics today. Imagine a cat placed in a box. A particularly sadistic individual has placed a vial of air-borne cat poison in the box with the cat, but the vial is currently sealed. Unfortunately, the vial is rigged to have a 50% chance of breaking open on its own. No one can predict whether this will actually happen or not.

Imagine the box is closed, and you are staring at it from the outside wondering if the cat is still alive. A normal person would say, “Either the vial is intact and the cat is alive, or the vial is broken and the poor cat is dead”. A quantum physicist watching the same situation says, “The cat is both alive and dead; the vial both intact and broken. The moment I open the box, the cat will ‘collapse’ into either a live cat or a dead cat”. To the quantum physicist, the cat seems to have momentarily transcended the binary of life and death.

You would be excused if you thought this is just some strange mystical philosophy. After all, whenever something (like the lid of the box) is obstructing observation, you can come up with any fantastical explanation of what may be happening. Just like the philosophical question “if a tree fell when no person was around, did it make a sound?” is logically unanswerable, so is the question of what the cat was doing before our physicist saw it alive or dead. Then why make a fantastical theory of cat superposition and delayed fate?

This is where quantum physics becomes strange: it turns out that while the cat is suspended in a state that is both life and death, these two states can interact with each other! It is almost as if there is a ‘quantum realm’ in which the alive and dead cat can meet each other. While in this quantum realm, our transcendent cat can meet and tangle with other objects also in the quantum realm at that time (such as the vial of poison, or other cats that may also be present in the box). Fantastical as this sounds, this interaction in the quantum realm has been shown to have a measurable effect on the final observable outcome when the box is opened.

A cat has sixteen lives

How can this strange truth about the quantum realm be used to build a faster computer? To understand quantum computing, I invite you to imagine a modified thought experiment.

This experiment has four vials of four distinct poisons. No poison is strong enough to kill the cat on its own, but it is possible that some combination of these poisons is lethal. So now let us put all these poisons and the cat in our box and close the lid. Each vial is independently rigged to have a 50% chance of breaking open. Counting carefully, there are 16 possibilities of what could happen inside the box.

Quantum physics says that before you open the box, all these 16 possibilities are present inside the box at the same time. It is almost as if you have the ability of running 16 experiments in parallel on a single cat. If your intent was to find a combination of poisons that can kill a cat, a classical algorithm could require you to run as many as 16 experiments: either on one cat one after the other, or on 16 cats in parallel. A quantum algorithm is able to run all experiments in parallel on the same cat!

Sorry for the macabre example: Schrödinger started it. Quantum computer scientists call each vial of poison a ‘qubit’ (short for ‘quantum bit of information’). The 4-qubit quantum computer that we built above is 2⁴ = 16 times faster than a classical computer.

But waiiiiiit a minute, you say. Maybe you run the 16 experiments in parallel, yes, but when you open the box, you will see the results of only one experiment. Right? One of the 16 outcomes will become manifest, seemingly at random. So even if the 16 experiments were run in parallel in this quantum fantasy of yours, you got to see the results of only one, so your quantum method is no better (and possibly worse) than trying all the 16 combinations one after the other.

Well, here's where the fact that quantum cats can entangle with other quantum cats comes in. It so turns out that you can build a complicated box having 4 actual cats in such a way that the 4^th cat will almost certainly die of poisoning and you will be able to tell what combination of the four poisons it died by. And it took 4, not 16 cats (or time equivalent to 4, not 16 experiments). This speedup is called ‘quantum amplification’ and such schemes are at the heart of why quantum computers can become astoundingly fast compared to classical computers as the number of qubits increases.

If this is the case, then why are we not doing everything with quantum computers already? What's the holdup? An important problem is the problem of ‘information leakage’. Suppose you were standing outside the box, thinking “the cat inside the box is a combination of a cat alive and dead”. Opening the box is just one way you could understand the true (classical) status of the cat. Suppose you hear the cat meow. You now know the cat is alive, which means that its state collapses into the single state of being alive.

There would be many other subtle ways that the information about the cat could leak outside the box. This is why keeping an object as large and as active as a cat in the quantum realm is almost impossible. Scientists trying to build quantum computers are not building them out of cats (thankfully, for the cats). They are using small groups of molecules which are almost at a physical standstill, to try to control this leakage of information. And yet, they have been able to only reduce, not eliminate the leakage of information.

Due to this problem, building working quantum computers is very hard. In fact, till very recently it has never been demonstrated that a quantum computer has done anything better than a classical computer. And now, by building a 53-qubit quantum computer, Google claims it has achieved exactly that — a demonstration of quantum supremacy!

Do you guys just put ‘supremacy’ in front of everything?

Consider a hypothetical “cloud computer”. Our hypothetical cloud computer is made up of an actual cloud. A real live cloud in the sky. The job we give this computer is “simulate the formation and propagation of a cloud in the sky”. How well do you think this computer will do this job? Perfectly, of course! Do you think any kind of supercomputer we have today can do the job of simulating a cloud as perfectly as this cloud computer of ours? Of course not! Thus, we have demonstrated the supremacy of cloud computing to traditional computing for this specific task of simulating clouds. We are now but one creative algorithm away from valuable near-term applications of this cloud computing.

Sounds farcical right? Google's quantum supremacy cannot be as trivial as our hypothetical cloud computing scenario (not to be confused with the actual cloud computing). Right? Consider, though, the following:

On what task did Google's quantum computer Sycamore demonstrate superiority to classical computers? It was the task of “simulating a quantum circuit”. What is the Sycamore quantum computer? It is a quantum circuit. OK … which quantum circuit did the Sycamore quantum computer simulate? Errrrm, … itself.

Is Google's achievement a complete joke then? Well no. To begin with, the actual situation is slightly more subtle than an experiment simulating itself. If you are interested in a slightly technical description, read the box below.

In brief, Sycamore is not simulating itself, but an ideal quantum circuit. The choice of the quantum circuit and the 'fidelity' with which the Sycamore is supposed to simulate the circuit are chosen quite narrowly, though, in such a way that practically the situation is not very different from the Sycamore simulating itself. But there are other differences between our self-simulating cloud computing example and the Sycamore; distinctions that are subtle — but not inconsequential, according to Google.

First of all, a classical computer will find it impossible to simulate our cloud not only because of the difficulty of computation, but also because we do not have perfect information about the cloud to begin with: the classical computer will find it difficult to simulate the quantum circuit that the Sycamore simulates in spite of knowing the exact construction of the quantum circuit in mathematical detail. Secondly, the cloud as a computer is not repeatable as an experiment, whereas Google's Sycamore can run the same experiment repeatedly and produce the same answer (this is not actually true, Sycamore is only “stochastically repeatable” but let us overlook this detail). Thirdly, a cloud is not programmable.

Then is the Sycamore programmable? This depends on what you mean by ‘programmable’. The Sycamore can certainly be configured to run various quantum experiments (unlike a cloud which runs a single experiment: itself). In the sense of being somewhat configurable, the Sycamore is programmable.

But programmability can mean various things. For years, computer scientists held that a certain type of computer called the Turing machine was by definition programmable, and anything that could behave like this Turing machine (including our modern computers) would hence be called programmable. The field of quantum computation is evolving their own definition of programmability, and one proposal is to use a ‘quantum circuit’ in place of the Turing machine. These ‘quantum circuits’ — idealized versions of physically realizable quantum circuits — have the power to run various useful algorithms at speeds that seem unachievable to current supercomputers. No one has built such ideal quantum circuits yet.

In arguing that the Sycamore is programmable, Google goes to great lengths to prove that it could be made to behave like any quantum circuit. This would make the Sycamore really really powerful, but there are two important caveats. Yes, the Sycamore can imitate any quantum circuit, but (a) only up to a width of 53 qubits and more importantly (b) the imitation will be noisy and leak quantum information. This leakage of quantum information unfortunately makes the Sycamore not powerful enough to run any of the known useful quantum algorithms at sizes that will be difficult for traditional computers — including the ‘quantum amplification’ schemes that will lend quantum computers real power. The Sycamore is just about powerful enough to run the totally made-up task specifically made to show that there is some task on which a quantum computer wins. The Sycamore, though, is the most powerful a quantum computer has ever been, and so Google's absolutely real technical achievements are quite amazing.

(Interestingly there is a proposal by Scott Aaronson (who graciously pointed out inaccuracies in a previous version of this blog) about how this totally made-up task can be used to do something useful — to create ‘provably random’ numbers. Essentially a task that can be performed realistically only by quantum sampling (like the task on which the Sycamore wins), must have been performed by quantum sampling. The output of this task must have then come about by quantum collapse, which physicists accept to be the de-facto definition of randomness. Somewhat ironically, actually proving the randomness of the generated provably random number requires massive computation on a traditional supercomputer!)

In conclusion …

Google's achievement in the Sycamore project is great and advances the field of quantum computing both theoretically and practically. But in the long march towards real quantum supremacy, the medal of 'quantum supremacy' has been won ‘on a technicality’.

In their paper, Google cites a widely held belief in quantum computing circles that while the power of traditional computers is increasing exponentially, the power of quantum computers is increasing doubly exponentially. The argument is as follows: qubits in quantum computers will grow exponentially, and thus the computing power of quantum computers — which itself grows exponentially with increasing qubits — will grow doubly exponentially. I personally have a tough time subscribing to this view because it disregards the pesky problem of quantum information leakage: the very problem that causes Google Sycamore's quantum fidelity to be so low. If double exponentiality turns out to be true, then quantum computers will one day surpass traditional computers. But the arguments for and against this belief are both anecdotal, which is a way to say no one knows what will actually happen.

So is it time to put down our CPUs and our GPUs and go fully quantum in all (or some) of our projects? No. Absolutely not. Not yet anyway. Will quantum computers one day beat traditional computers? No one knows. We are all guessing. Only time will open that box. But if the information leaks, we will be sure to let you know!

Like / share this article on: