Quantum algorithms: explained in simple language
We have all heard about the quantum computers and the potential impacts that they may have in our future lives. Every once in a while news about some extraordinary feat of quantum computers floods the tech news. You may wonder what makes quantum computers so powerful? How different are they from the digital computers that we use daily? Here, I try to answer these questions in plain English.
Computers and algorithms
The first things that we need to get out of the way here is the difference between computers, programs, and algorithms. It is a big mistake to think of them as synonyms. Algorithms are a series of instructions to solve a problem. They usually result in finding an answer. For example, imagine you live in a big house with many rooms, and you have a cat. One day you wake up and you can’t find your cat. Now, you have a problem: “finding your cat.” What is the solution? There are literally thousands, but it is likely that your solution would be something like this:
- List all the rooms in your house (in your mind, or … whatever works)
- Choose one of the rooms from your list arbitrarily
- Go to the room that you have selected
- If you see the cat there, the search is over (problem solved), otherwise, remove this rooms from your list, go back to step #2 and continue.
As simple as that! You may say “but that was obvious”; and you are right. We are using algorithms in our daily life, often without even noticing it. Now imagine instead of looking for your cat in your house, you are searching for the term “Schrödinger’s cat” in a quantum physic book that has 500 pages. You may easily repurpose the above algorithm — just need to replace rooms with pages in the book. We all know that this is going to be an easy yet tedious and frustrating chore. Only if we had a machine that could meticulously follow the steps of an algorithm … well, that’s exactly what we made computers for! We only need to write our algorithm in a language that a computer could understand (surprisingly it is called a computer programming language), and voila! We have a homemade Google (just a bit more complexity needs to be added).
Quantum world
Discovering the quantum world has been one of the greatest achievements of mankind in the last century. We all know the classic world of physics very well, because we live in it. But when it comes to the quantum world we can not trust some of the most obvious facts that we take for granted. Let’s explain this using an example.
Basketball in the classic physics world
Imagine there is a tall barrier in front of you that you can not easily see what’s behind it. You know that there are two slots behind this barrier, and a very tall end wall behind them (the picture above). You throw the basketball at the end wall, it bounces back and falls in one of the two slots. At this point, you know that ball is in one of the slots and it will stay there. If your basketball skills and aiming is anything like me, there is no way to say for sure where the ball has ended up: there is a 50–50 chance that it could be in any of them. For example, the picture above shows the basketball in slot A. You do not know this yet, but you are certain that the ball is only in one of the slots and it will remain there until someone moves it (this sounds obvious but become important later). All you need to do is to look behind the barrier to see where the ball is, and was since you threw it. Now, let’s see what happens in the quantum realm.
Basketball in the quantum world
Now let’s repeat the same mental experiment in the quantum world. We said that in the world of classical physics there is 50–50 chance that the ball will end up in any of the above two slots. What happens in the quantum world is that the ball ends 50% in both slots. Wait, whaaat?! The ball is going to be at both slots at the same time. I should clarify that this does not mean that the ball breaks in half and each half of it ends up in one of the slots. No! The ball exists in both slots simultaneously. We refer to this phenomena in quantum physics as quantum superposition. In other words, the place that the ball ended up is a combination of both of the possible places that it can be, with 50% chance being in each (notice that the balls in the left picture have 50% opacity).
It might get a bit frustrating not to know where the ball really is. You may lose your patience and peek at the other side of the wall to see where the ball is. This is the point that quantum collapse happens. As a result of quantum collapse (the correct scientific term is wave function collapse), the ball comes out of quantum superposition, chooses one of the slots and remains there. Now, all you see is that the ball is sitting in only one of the slots, like what you saw in the world of classical physics.
It sounds bizarre doesn’t it?! Explaining quantum effects was one of the most controversial discussions between physicists in the 20th century. Even smart people like Einstein were in doubt about the spooky behaviour of the quantum world. But extensive experiments have strongly approved these behaviour. Now that you read this far, it is really fun to take a look at Schrödinger’s cat mental experiment (let’s say this is the same cat that we are trying to find here, the cat knows what we have in mind!).
Quantum algorithms
Alright, now that we know the quantum world. Let’s see how we may take advantage of its principles in our algorithms. We go back to the problem of finding the cat in the house, and see what is the difference between the best algorithm we can come up with in the classical physics world versus one in the quantum world.
Starting with the classical physic world, we said that the advantage of creating an algorithm is that we can pass it to a computer to run our chores for us. Smart robots are computers too! Right? So let’s give the algorithm to a smart robot to follow.
The above image schematically shows how this search may go: robot starts at the red circle in the center. Then, it goes to each room (according to an arbitrary order) until it finds the cat. While the robot is searching, we can sit back and relax, or even better, follow the robot via a tracking device that is mounted on it.
Now let’s go to the quantum world. As we saw in the basketball example, in quantum world, objects and entities (that includes smart robots) can be in multiple places simultaneously. This means that our robot can be in multiple rooms at the same time (remember the quantum superposition). Therefore, instead of telling the robot to visit the rooms one by one, our algorithm can tell the robot to go to all the rooms in one step. This is impossible in classic world, but sounds like a normal Tuesday in the quantum world. This is the root of the immense power that a quantum algorithm may unleash.
But still there is a big catch. Again as we saw in the basketball example, our robot is in all the rooms with equal probability. So, if we turn on our tracker to see where the robot is we may see the robot that is in a room with no cat in it. In fact, our chance of finding the robot in a room with cat is not more than picking a room at random and checking it. So, the naive search in superposition by itself is not very useful. Now what?!
Amplitude amplification
Now we are ready to talk about the real magic of the quantum algorithms: amplitude amplification. In our quantum algorithm for finding cat, so far, our robot is in each room with the same probability. As we said this does not give us enough motive to check the location of our robot for finding the cat. The amplitude amplification is a set of instructions that we add to our algorithm to increase the probability of finding the robot in the room that cat is there (in other words, the answer). Amplitude amplification gradually and in multiple steps redistributes the probability of being in the rooms that cat is not there towards the room with more probability of finding the cat. Keep in mind that we should not check the robot while the algorithm runs, because that causes the collapse of the quantum states, and with it the amplitude amplification. We can only check the robot when the algorithm is finished. And even at that point we are dealing with a probability distribution. For example, in the above picture that shows the quantum states of our robot after the algorithm is finished, we have 70% chance of seeing robot in the room with our cat (notice 70% opacity of robot symbol). But still there is 5% chance of robot appearing in every other room (5% opacity of robot in other rooms). This means that our quantum algorithm has 70% success rate, but 30% chance of failing. Quantum algorithms almost always have to deal with a probabilistic choice. Their advantage though is in significantly increasing the chances in favor of the correct answers.
Real world quantum algorithms
How useful are the quantum algorithms in the real world, you may ask. We may often have to solve problems that the only way to find a solution for them is to try a large number of potential answers to see which one works (think about the above example of finding your cat, or finding the password to a system). In the above example, we only had seven choices. Imagine you are dealing with a problem where the number of potential answers you may try is more than the number of atoms that makes the earth (believe it or not, they come up more than what you may think). Even a supercomputer may take years to finish crunching number on that one, if it ever finishes. Quantum computers that take advantage of algorithms in quantum world can try all the possible combinations of potential answers simultaneously. Then they use amplitude amplification to increase the chances of reading the correct answer at the end. And this is how quantum algorithms work!
Notes
- It makes me happy to hear from you. Share your comments here. I will be glad to read them and respond.
- This is translated from another article on virgool.io, with very minor changes.
