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.
Randomness computes
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.
A computation can be performed by encoding the problem in the network of paths available to a quantum state. The qubits will spread out through the network and interfere with themselves and each other at any locations where the paths cross. Upon exit, the most likely value for the qubits corresponds to the answer to the problem.
The difficulty with this approach is creating the network of paths and ensuring that the qubits stay, well, united. Essentially, we require that each qubit behaves in a perfectly predictable way as it moves through the network. We might not be able to predict the value of the qubit if we were to measure it, but we should be able to predict the probability of the measurement outcome.
Unfortunately, every imperfection in the network disturbs the qubit and reduces its predictability. That, in turn, reduces the chance of obtaining the correct answer to our computation. Enough imperfections, and the computer is no better than random guessing.
Walking into computations
To demonstrate that quantum information is preserved as it propagates through a random walk, a group of researchers strung together a string of 12 superconducting qubits. The researchers set the middle qubit in a specific state. That state can then jump from its home qubit to the next qubit in either the left or the right direction. So, being a qubit, it goes in both directions at once.
The properties of the string mean that the qubit will jump locations at well-defined times, so by repeating the experiment and stopping it at many different times, the researchers were able to track the qubit's progress along the string. They observed the qubit hit both ends of the string simultaneously and start returning to the middle. The qubit does this more than twice before finally decaying into noise, which is quite remarkable.
That was nice, but it's not going to get any calculations done. Those require that, if two qubits are correlated when they are set loose, they should still be correlated later after they've walked up and down the string. The researchers performed that test by setting the value of two qubits and letting them interfere with each other. They showed that the correlations were preserved. Even better, the nature of the correlation they observed (anti-bunching, for those who want the technical term) was determined by how they had set up the coupling between the qubit locations in the chain.
This demonstrates an important third point. Computation relies on more than just having and preserving qubits; you also need to control their interactions. Although the researchers don't play with this, the very fact that they can set the coupling to obtain specific correlations shows that they already have control.
Nature beat us to it
Perhaps the most interesting part of random walk quantum computers is that they already exist, and we would not exist if it didn't work.
Maybe I should explain that. Photosynthesis works because light creates a quantum particle called an exciton that has to travel to a reaction center before it decays away to nothing. The only way that it can do this is by traveling all possible paths simultaneously. Through the power of constructive interference (or, if you prefer, quantum computing), the exciton survives about a 1,000 times longer than it would otherwise be expected to, allowing it to reach the reaction center.
Since photosynthesis takes place at room temperature, it gives me hope that, eventually, the quantum computer will move out of the helium dilution fridge.
Science, 2019, DOI: 10.1126/science.aaw1611 (About DOIs)
