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, , or . 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.

That is very interesting! I never heard about this method with primes! Nice post.

LikeLike

Glad you liked it! Have a (classical!) google for Shor’s algorithm if you want to know more of the details.

LikeLiked by 1 person

Thanks I will check it out!

LikeLike

Fascinating article Dave, really interested in how quantum computing might simplify list sorting (slim chance of understanding) and machine learning (minimal chance!)

LikeLike

Hey Alun, thanks for the questions. As I understand it, quantum computers don’t (generally) speed up list sorting. What they can do (via Grover’s algorithm) is speed up list searching from O(N) to O(sqrt(N)). They can do this because list searching can be reduced to an inverse problem, which quantum computers are good at solving. As for machine learning, I can’t really speak too much about that because it’s not my thing. But I do know that there is considerable interest in quantum neural networks and a bunch of other fancy stuff.

LikeLike