The Quantum Walking Dead Are Scared To Death
Climbing down a binary tree is harder than you might think
he quantum walking dead had imagined things differently. Yes, they wanted to stop being so bored. But this?
They climbed the tree and can't get back down.
In our previous step, we let the walkers climb a binary tree from the root. And they successfully reached the top.
But a characteristic of the quantum walk is that they can move in all directions. For our binary tree, this means that they can either climb up the left branch, climb up the right branch, or climb down again.
The following drawing shows the three possibilities.
Let's show the quantum walking dead how to get back down the tree. It actually sounds quite simple. But quantum computing wouldn't be so exciting if it made implication easy.
It starts with the quantum coin toss. So far, we have always used a single qubit. That sufficed to decide whether to send the walker to the left or to the right. With one qubit, there are only two possible states |0> and |1>.
But how does this work with three possible states?