By Jonas Helsen

One of the things that is often repeated about quantum computing is the idea that a quantum computer is somehow more powerful than regular computers because, when considering a problem it can “try all possible solutions at once”. Let’s get this out of the way first and say that this is not exactly the case. While we would very much love a computer that tries all solutions at once (this would be extremely useful) quantum computers sadly aren’t quite this powerful. Of course, as with all good clichés it does contain a grain of truth. In this blog post I will try to explain in a (sort of) simple way what makes quantum computers more powerful than classical computers.

A whole different ball game

In order to compare classical and quantum computers I’m going to start by explaining a simple game (for those interested, this game is based on the fabled Deutsch-Josza algorithm, one of the earliest quantum computing algorithms). This game is reminiscent of those street games you can play where you have to guess which cup hides the ball. In this case your friend, who for some reason owns a large amount of cups and red and green balls challenges you to the following: She has lined up a number (let’s call it N) cups and under each cup she has hidden either a red or a green ball. Now she promised you that she did one of two things. Either she has hidden equally as many red and green balls, or she has hidden only red balls (or only green balls). It is your task to figure out in which of these two situations she has put you. To make things even more difficult, you can only lift one cup at a time and you must be certain of your answer (all red, all green, or fully mixed) after lifting as few cups as possible. (The less cups you lift the better you score). Now it won’t be hard to convince yourself (if you feel so inclined you can take a piece of paper and try figuring out some cases) that you must lift at least half of the cups in order to be absolutely sure you are in one of the three cases. Now this isn’t the end of the world but if your friend brings a lot of cups you might spend a lot of time lifting them one by one before you get anywhere. We would like to do better, and with quantum we can!

An example of an all red ball configuration and an example of a configuration with equally many red and green balls. Note in the third diagram how it is impossible to tell the two apart with certainty without lifting an additional cup.

A quantum – sort of – computer

At this point I would like to get to the core of an important aspect of quantum computing (the one that inspired the “all possible solutions” adage) without bringing in the full complexity of quantum computing. In order to do this I will define a magical machine designed to solve the ball and cup problem in a quantum-y way. This machine might seem a little contrived at first but bear with me. This machine will take the shape of a long tube with N (the amount of cups) holes in the top. In these holes your friend will put her green and red balls, conveniently covering up the holes with lids so you can’t just look inside. It also has a number pad on the side that allows you to punch in numbers from one to N and the machine will then tell you the color of the ball in the corresponding hole. However it does so in a very specific way. If the ball is green it will output the number “1” and if the ball is red it will output the number “-1”. For the sake of the argument your friend will consider a single use of the number pad the same as lifting a cup. Hence the goal of the game is now to solve our friends problem with the smallest possible amount of number pad uses. If this just seems to you like an elaborate way of just lifting a cup and checking the color, you would be right, but we aren’t done describing the machine yet!

Next comes the “quantum” part of the machine. It turns out that the number pad also allows you to ask for multiple numbers in a single use, but only in a very specific way! If you type in multiple numbers ( For instance 1, 2 5 and 7) the machine will tell you the absolute value^* value of the sum of the individual numbers it would have generated for those locations. For instance if you asked for locations 1 and 2 and locations one and two contain red balls the machine would output |-1 + (-1)| = |-2| = 2. Note that if both balls are green it would also output 2, whereas if the balls were of different colors (red-green or green-red) the machine would output zero. This means that the machine will never tell you what the color of the balls are! This hardly seems like an improvement but it turns out we can exploit this curious behaviour in a clever way to answer our original problem!

The sum of all balls

Let’s restate the problem. Our friend has put N red or green balls into the machine with the promise that they are either all green (or all red) or half green-half red (assume that N is even). It is or job to figure out in which situation we are by using only a single query to the machine. This means we get to type in a single sequence of numbers and get a single output number in return. Inspired by the odd properties of the machine we propose the following solution: we simply type in all the numbers from 1 to N! I will leave it to you to convince yourself that if there are equally many red as green balls the machine will always return exactly zero and that if the balls are all green or all red the outcome will be the number N (this is fairly easy to check for yourself by picking N to be a small number, say 4, and trying various ball combinations). This outcome allows us to perfectly distinguish between the two situations using only a single query to the machine! Note also that the machine didn’t actually tell us anything about the colors of the actual balls! We for instance don’t know if ball number seven is red or green. The machine will also never give us that answer unless we specifically ask it to do so (which will cost us a query). Hence, while the machine has in a way “looked” at all balls, it will never tell us what it has seen, it only tells us some global property of all balls (are they all the same or not), and even then only if we ask the right questions. A similar thing is true for actual quantum computers. In a quantum computer we can input quantum superpositions of different states into the computer but if we ask it to produce an answer (this would then be a quantum measurement) it would never give us more than a single number which is related to all the different states we entered in a superposition.

So that should give you a very rough idea of where “trying all solutions at the same time” comes from. But again, that’s not exactly what’s going on. The truth is much more complicated and it is precisely that which makes designing algorithms for quantum computing so challenging.. And so interesting! Quantum computers will probably be able to answer amazing problems, but only if we learn to ask the questions in the right way.

^*The absolute value of a number, denoted | |, turns negative numbers into positive numbers but otherwise leaves it unchanged. So for instance |-2| = 2 but also |5| = 5.

Jonas Helsen is an aspiring theorist in the Wehner group where he works on verifying quantum computers. In his free time he enjoys improvisational theater and pretending to be a superhero. He likes the Netherlands but wishes they wouldn’t put peanuts in everything.