Quantum mechanics is probably the most unintuitive scientific theory in the history of humankind—nothing behaves like we are used to. In this essay, we will try to get back some intuition of how to think about quantum mechanics, more specifically the quantum random walk. No worries, there are going to be no equations—this is not a scientific paper. The main purpose of this essay is to make the reader curious by showing how weird our reality is and how this knowledge might help us in the future.

Most people are familiar with the classical random walk which is a mathematical framework used to describe a lot of phenomena—e.g. Stock-prices and Brownian motion. The quantum random walk is less known and not as useful for explanations, but there are some interesting fields it might get more important in. The most notable cases are quantum computing—specifically Grover’s Algorithm—and quantum biology. The later field is the study of how and why quantum mechanics is important for explaining biology and it is still a pretty new and often controversial field.

Classical

The classical random walk in one dimension can be thought of as flipping a coin and going one step forward (+1) if it shows heads and one step backward (-1) if it shows tails. This is the simplest version of the random walk but it is sufficient to illustrate some important concepts.

The first thing to note is that probabilities approach a normal distribution (Gaussian). After one coin flip—T=1 steps—we find ourselves with the probability of 1/2 at 1 and with the probability of 1/2 at -1. After T=2 steps we find ourselves with a probability of 1/4 at 2, with the probability of 1/4 at -2, and with the probability of 1/2 at 0 (Figure 3). By continuing this sequence, we can see the normal distribution emerging.

One important but counter-intuitive fact is that after T steps the average distance from our starting point (0) is not 0. You might expect that if we always move +1 or -1, we would on average not move way from the start (0), but that is not the case. The average distance from our start after T steps is roughly √(T). We will not prove this fact since I promised not to use equations but we will at least see why 0 is the wrong answer.

The distance from our starting point can never be negative—a distance is only ever positive. Even if we find ourselves after T=2 at the point -2, the distance to our starting point (0) is not -2 but 2. Put differently, it does not matter in which direction you go, you cannot be -5 meters away from your home (try it at home). Starting from this point, the interested reader can figure out (or lookup) why the average distance is of the order of √(T).

Quantum

For a quantum random walk, we need what I will call a “quantum coin”; it is a fair coin that just likes the classical one has the probability of 1/2 for heads and 1/2 for tails. Note that this quantum coin does not exist and in reality and the “coin flip” is a mathematically defined unitary operation manipulating the state of a system—spin—in Hilbert space. We will use the balanced—fair—quantum coin named Hadamard coin for our example. The most important thing to understand here is that we have defined this coin to be fair. When we flip it, we get heads half of the time and tails the other half of the time. As with our classical coin, we will move one step forward (+1) if it lands on heads and one step backward (-1) if it lands on tails. After T=1 flips (or steps) we will be at 1 with the probability of 1/2 and at -1 with the probability of 1/2. So far, so good—everything is behaving “classically.”

Now comes the weird part, instead of measuring after each step, we will measure only at the end—let us say, after T=5 flips. This represents, in a way, the quantum version of Galton’s Board. If everything behaved classically, it would not make a difference if we looked—i.e. measured—after every step or just at the end, but since we are dealing with weird quantum mechanics it makes a huge difference. The probability distribution looks like this:

Keep in mind that to measure the probabilities for T=5, we are only allowed to measure after those 5 flips—never in-between. To get the probabilities for the other steps we need to measure only after e.g. T=3 but we cannot continue the experiment afterward and measure T=5.

Looking at the table (Figure 4), we can see a couple of interesting things. First, the distribution starts to differ from the classical one after T=3. Second, the distribution is not symmetric; in this case, it is skewed to the left (negative) side. This is the case because we started with the initial state “spin down”. In our coin analogy, this corresponds to which side is facing upwards before you flip the coin. Take a moment to appreciate how unbelievable this is.

We defined the coin so it has exactly 1/2 chance of landing on heads and 1/2 of landing on tails; and if we look after one flip, it works perfectly and it does not matter in which initial condition the coin was—i.e. which side was facing upward before the flip. But if we only look after T=5 flips, it matters a lot in which initial condition the coin was; it is suddenly important which side of the coin was facing upwards before we flipped it. This is because of a phenomenon at the heart of Quantum Mechanics called interference.

If we experiment with our system having “spin up” we will get the same distribution skewed to the right. To get a symmetrical distribution, we have to put the system into a superposition of the two states “spin up” and “spin down.” Superposition means that the system is in both states at the same time and only when we “measure” it, the system decides the state. In our analogy, we have to prepare the coin so that it lies with heads up and tails up at the same time. This is, obviously, not possible with a real coin but doable with a quantum system.

The most interesting and useful feature of the quantum walk is that in contrast to the classical walk, the expected distance from the origin is not √(T) but T. This means that a quantum walk is quadratically faster than a classical random walk. In T flips—steps—we expect to find ourselves at the distance T from the start. This is incredible. One cannot understand this feature by thinking “classically.” We can only imagine that the quantum random walk is not going +1 or -1 at each step but rather both at the same time and the system only decides on one alternative when being measured (this mixture of superposition and interference makes everything extremely counter-intuitive). Now, let us see why is it useful to know about this weird quantum random walk.

(A note for the technical reader: another big difference to the classical random walk can be seen by adding an absorption barrier. While the classical walk has the probability of p=1 to be eventually absorbed, the quantum walk has, as described in this paper, a chance of escaping to infinity.)

Grover’s Algorithm

Searching through lists and sorting them is one of the most popular tasks computers nowadays perform. Finding fast search and sorting algorithms is getting increasingly important because the amount of available data is skyrocketing and unsearchable or unsorted databases are mostly useless. This is where—in theory—Grover’s algorithm comes in; it is a quantum algorithm for searching an item in an unsorted list. Only in theory because a good enough quantum computer has not been built yet and scaling up from the ones we have already built is not trivial.

If you want to find a particular item in a list with N items classically, you need to check all N items—N evaluations—because the item you are searching for could be the last in the list. (If you are sure that the item is in the list, the correct number of evaluations is N-1, but this does not matter much here.) This means searching through an unsorted database with N entries takes—classically—N steps. However, with Grover’s quantum algorithm—which can be viewed as a quantum random walk—it takes √(N) steps. It allows for the same quadric speedup as the quantum random walk. For large databases—lists with big N— this can mean a lot fewer evaluations.

(A note for the technical reader: it is sadly (or luckily?) not possible to solve NP-Complete problems in polynomial time with this algorithm.)

Photosynthesis

In the book Life on the Edge, Johnjoe McFadden and Jim Al-Khalili argue that quantum physics is needed to explain biological phenomena. One of the most important processes in biology is photosynthesis which, according to the authors, probably relies on the quantum random walk since such efficient transportation seems difficult to explain otherwise. However, quantum biology is a new and often controversial field and I am sadly not in the position to judge the credibility of this claim because my knowledge of biology is rudimentary at best.

Some people believe that uncovering this mechanism of nature can help us build technologies that more efficiently convert the energy of sunlight into electric energy and I hope they are right. For those who are interested, I can highly recommend the already mentioned book Life on the Edge.

Curious?

I hope this essay has shown the reader how weird our world at the smallest scale behaves without asking for many technical prerequisites. I have done my best to keep the explanations as intuitive as possible which is why I had to omit many details. For the interested reader, I would suggest “Quantum random walks: An introductory overview” by J. Kempe as a further reading—it is also the source for most of the figures. Keep in mind that you will need a decent amount of mathematical and physical background knowledge to understand it though.