A new quantum random walk technique developed by engineers at Purdue University could eventually allow computers to search through data at speeds beyond that of conventional computers.
In a random walk, an agent randomly moves to the right or left at each time interval, much like a ball in a Galton board hopping to adjacent slots at each step. Such an agent can sweep a database space to search for a special value, for example finding its minimum.
In the quantum realm, the laws of random walks are fundamentally different. A quantum agent can move to right and left simultaneously at each step. In other words, a quantum particle can travel in several trajectories at the same time, which can lead to searches of large-scale databases dramatically faster.
Andrew Weiner, Purdue University’s Scifres Family Distinguished Professor of Electrical and Computer Engineering, said their technique uses photons at specific colors, or frequencies.
“We like to refer to this as the quantum walk of the rainbow,” Weiner said. “One major advantage is that, unlike other types of quantum computing, this technique can be done at room temperature.”
Another advantage is that experiments can be done with integrated photonics and other components common in lightwave or optical communication, which could reduce cost and bring compatibility with fiber optics communications infrastructure.
“In the future, quantum walks could be used to search through massive amounts of data in a reasonable time,” he said, “This might include quickly searching through all of the world’s fingerprints or finding a microscopic defect in a newly manufactured airplane wing or defects in microprocessors.”
The discovery was recently published in Science Advances.
In October 2019 Google announced the results of a “quantum supremacy” experiment using the 53-qubit processor “Sycamore,” which executed a highly complex quantum random walk. It was a dramatic achievement, but quantum computing using qubits has its challenges. Primarily, quantum computers need to be cooled to near absolute zero, which is best expressed on the Kelvin temperature scale, in order to maintain the superposition of the qubits.
“The superconducting quantum circuit works at about 20 degrees milli-Kelvin. So, it’s a huge, very complex refrigerator that allows the qubits to store the quantum information and act in a quantum way,” Weiner said. “We’re using photons instead of superconducting qubits, which allows our work to be done at room temperature. To be fair, photons have their challenges as well, and cannot yet rival the complexity of operations achieved with superconducting qubits. The point is that quantum walks are a central part of the development of quantum computers. And we’re saying there’s another way of doing quantum walks but at room temperature using photons in a way that hasn’t been done before.”
The photons used in this technique walk in the color (i.e., frequency) space, randomly changing colors in a quantum manner during the walk. The photons come in highly entangled pairs, such that the walking pattern of one photon is highly dependent on how the other twin photon walks. By programming the quantum state, the photons can walk in an attractive or repulsive way. Such photons can also store and process multivalued quantum information known as qudits (with a “d”). In 2019, Weiner and postdoctoral researcher Poolad Imany (who is now a postdoctoral associate at the National Institute of Standards and Technology) announced that they had created a two-qudit gate, which would be the equivalent to a transistor in conventional computing.
Random walking, using computer bits, is analogous to a coin flip because bits have values of either 1 or 0, Weiner said. The movement of the walker (a step to the right or left) is then dependent on the outcome of this coin flip. But quantum walking using qudits is more like throwing a die, which has six sides and can represent six different movement trajectories. In this case, the entangled photons were the equivalent of an eight-sided die, such as the type used in Dungeons and Dragons. Qudits bring the potential for placing more information on each photon and exploring more quantum random walk outcomes in parallel.
Imany said that what they demonstrated was a continuous quantum walk.
“Previously, changing the evolution time of photons required changing the physical size of the quantum walk circuit. In this case there is no abrupt step where the particle jumps to multiple position. It just continuously “leaks” to multiple positions with a walking-depth that can be electrically tuned,” he said. “This is especially important because this is how natural phenomena evolve. Consequently, continuous quantum walks are especially well-suited to the simulation of quantum phenomena like molecular dynamics.”
This work was supported in part by the National Science Foundation.
Courtesy Purdue News.