# What is quantum supremacy?

The race to make faster and faster computers – whether they are designed to play the newest games or predict the weather – has been a cut-throat business for many decades. But there is another computing race that has also been getting more competative in the last few years: The race between quantum computers and the machines they are intended to replace.

Quantum computers work quite differently from the regular computers that power the modern world. Regular computers process and store data as a series of binary bits, which can be either zero or one. On the other hand, quantum computers process data using qubits (quantum bits) that can be zero, one, or any combination of them both. By utilising the immense scope of this additional freedom in how data is encoded, computer scientists have shown that several common computing tasks can be massively speeded up. I wrote about some of the possibilities before, so that post might be a good background.

At the moment, performing a particular task using a quantum computer is generally slower than using a regular (or “classical”) one. In fact, some tasks that quantum computers should be very good at are simply too complicated for existing quantum hardware to attempt. But as the technology progresses, eventually quantum machines might be able to out-perform classical ones.

If it happens, that is the moment at which “quantum supremacy” is established.

One factor in determining when quantum supremacy is reached is obviously the performance of quantum computers. More on that later. But their competitors – the classical computers – are also getting faster. Recently, a big step forward in the ability of classical supercomputers to perform tasks that should be well suited to quantum computers was reported by researchers at IBM.

As classical computers get better, the bar for quantum supremacy is being raised.

It is possible to simulate a quantum computer by running a program on a classical computer. The output of the simulated quantum machine should be exactly what an actual quantum device would create. The problem is that the amount of processing power and memory required to do this goes up very quickly as more qubits are simulated. It had been thought that the maximum number of qubits that could be simulated in a classical supercomputer was roughly fifty. After that, it would simply require too much memory.  So quantum supremacy would be established if a quantum computer with 50 working qubits could be made.

What the researchers from IBM have done is to design a program which allows the simulation of 56 qubits. This makes it just that bit harder to get to quantum supremacy!

But what about the other side in the race? The hardware for quantum computing is also getting better, and just this week, Intel announced that it now has a chip that contains 49 qubits. This sounds great, but so far it is quite difficult to assess how good it actually is because a lot of the important data is not available.

The number of qubits is an important indicator of the overall performance of a quantum computer, but there are other very important factors. For instance, qubits have to be linked to each other (or, in the quantum-mechanical language, “entangled”) so that they can share quantum information and carry out the multi-qubit operations that are required to exploit their power. It can be hard to entangle two qubits unless they are close to each other and so, in current devices, often not all the qubits in a chip will be linked. The fewer qubits that each one is linked to, the more inefficient it is to do a calculation, and so this connectivity has a big impact on performance.

Secondly, controlling a qubit is much more difficult than the control of a classical bit. Usually, delicate pulses of microwave radiation are needed to manipulate them, and so they can make errors. Because of this, calculations often have to be repeated several times to make sure that the answer is correct, and not the result of a control error. The higher the error rate, the more times a calculation must be run to be sure that it gives the right answer.

Finally, there is the decoherence time of the qubits. This one is a bit more technical, but the data stored in a qubit can be lost because the outside world impinges on the qubit, destroying the sensitive quantum information. Because of this, the decoherence time limits how long a quantum computer has to complete a calculation: If it can’t finish in time, it might lose the data it is working on. So, if the decoherence time for the qubits is too short, they are next to useless.

And of course, none of these things are problems for simulations using classical computers, because those programs work perfectly!

So far, these numbers are not available for Intel’s new chip. In contrast, IBM have this information freely accessible on github for their machines! Getting this information will be crucial to understanding just how close they are to establishing quantum supremacy.

But for now, the race is well and truly on!

If you want to read a preprint of the paper reporting the 56 qubit simulation, you can find it here.

Also, if you want to learn more about quantum computing, and even run your own programs on a small quantum computer, check out IBM’s public web site. They’ve got a bunch of neat tutorials and a four-qubit machine on their cloud that you can play with.

# Justin Trudeau and quantum computing

You’ve probably seen already that clip of Justin Trudeau, the Prime Minister of Canada, explaining to a surprised group of journalists why quantum computing excites him so much. In case you haven’t seen it, here is a link. A number of things strike me about this. Firstly, of course, he’s right: If we can get quantum computing to work then that would be a really, really big deal and it’s worth being excited about! Second, it’s a bit depressing that a politician having a vague idea about something scientific is a surprising exception to the rule. Thirdly, while his point about storage of information is right, there’s a whole lot more that quantum computers can do that he didn’t mention. Of course, that’s fair enough because he wasn’t trying to be comprehensive, but it gives me an opportunity to talk about some of the stuff that he missed out.

Before that, let’s go over exactly what a quantum computer is. As the Prime Minister said, a normal (or “classical”) computer operates using only ones and zeroes which are represented by current flowing or not flowing through a small “wire”. (However, as you might have already read, this might have to change in the future!) A quantum computer is completely different because instead of these binary bits, it has bits which can be in state that is a mixture of zero and one at the same time. This like the electron simultaneously going through both slits in the two slit experiment, or Schrödinger’s famous cat being alive and dead “at the same time”: It’s an example of a quantum mechanical superposition of states. A quantum computer is designed to operate on these quantum states and to take advantage of this indeterminacy, changing them from one superposition to another to do computations. If you can get the quantum bits to become entangled with each other (meaning that the quantum state of one bit will be affected by the quantum state of all the others that it is entangled with) then you can do quantum computing! Exactly how this would work from a technological point of view is a big subject which I’ll probably write about another time, but options that physicists and engineers are working on include using superconducting circuits, very cold gases of atoms, the spins of electrons or atomic nuclei, or special particles called majorana fermions.

A big field of study has been to find algorithms that allow this quantum-ness to be used to do things that classical computers can’t. There are a few examples that would really change everyday life if they could be implemented. The first sounds a bit boring on the face of it, but quantum algorithms allow you to search a list to determine if an item is in a list or not (i.e. to find that item) in a much shorter time than classical algorithms. So, if you want to search the internet for your favourite web site, a quantum google will do this much faster than a classical google. Quantum algorithms can also tell quickly whether all the items in a list are different from each other or not.

Another application is to solve “black box” problems. This has nothing to do with the flight data recorders in aircraft, but is the name given to the following problem. Say you have a set of inputs to a system and their corresponding output, but you don’t know what the system does to turn the input into the output. The system is the black box, and the difficult problem is to determine what operations the system does to the input. This is important because these black box problems occur in many different areas of science including artificial intelligence, studies of the brain, and climate science. For a classical computer to solve this exactly would require an exponential number of “guesses”, but a quantum computer could do this in just one “guess”!

But perhaps the most devastating use of a quantum computer is to break the internet. Let me explain this a bit! There is a mathematical theorem which says that every number can be represented as a list of prime numbers multiplied together, and that for each number there is only one such list. For example, $30=2\times 3\times5$, or $247=13\times19$. This matters because most digital security currently depends on the fact that this is a very difficult thing for classical computers to start with a big number and work out what the prime factors are. The way that most encryption on the internet works is that data is encoded using a big number that is the product of only two prime numbers. In order to decrypt the information again, you need to know what the two prime numbers that give you the big number are. Because it’s hard to work out what the two prime numbers are, it is safe to distribute the big number (your public key) so that anyone can encode information to send to you securely. But only you can decode the information because only you know what the two primes are (this is your private key). But, if it suddenly becomes easy to factorise the big number into the two primes then this whole mode of encryption does not work! Every interaction that you have with your bank, your email provider, social media, and online stores could be broken by someone else. The internet essentially wouldn’t be private! Or at least, it wouldn’t be private until a new method for doing encryption is found. This is the main reason why security agencies are working so hard on quantum computing.

Finally, I want to quickly mention one application is a bit more specialised to physics: Quantum computers will allow us to simulate quantum systems in a much more accurate way. Currently, the equations that determine how groups of quantum mechanical objects behave and interact with each other pretty much can’t be solved exactly, in part because the quantum behaviour is difficult to model accurately using classical computing. If you have a quantum computer, then part of this difficulty goes away because you can build the quantum interactions into the simulation in a much more natural way, using the entanglement of the quantum bits.

So in summary, Prime Minister Trudeau was right: Quantum computers have the potential to be absolutely amazing and to change society and are really exciting (and possibly slightly scary!) But storing information in a more compact manner is really only the tip of the iceberg.