When I think about computing, I usually think about it in terms of individual logic gates performing specific operations. These can be strung together to create more sophisticated and useful operations and can be ultimately built into a disaster like EndNote. Even when I make a conceptual switch and think about quantum computing, I still get stuck thinking about quantum logic gates.
But there is a better-than-even chance that quantum computing will not make direct use of logic gates. If logic gates aren’t going to be a thing in quantum computing, how will we compute? One way is through annealing, which I’ve written about a lot.
But the neglected stepchild of quantum computing is something called a “quantum random walk.” In a minor miracle, researchers have shown a quantum random walk through a string of 12 quantum bits. This is the sort of step that may herald the beginning of actually demonstrating a quantum computer based on a random walk.
The quantum random walk takes advantage of the idea that quantum objects do not have to be localized in space or time: a particle is also a wave, and waves are spread out. So, if I have a quantum object and offer it two paths to travel, it will spread out and travel down both at the same time. Only after I make a measurement, or there is something along the path that destroys the quantum state, will the path the object took be certain.