There is such a concept in modern mathematics as “random walks.” It describes a series of changes that happen on a probability basis according to some rule set. A classic example is what happens to a bead on the so-called Galton board.
“The Galton board seems quite simple: you’ve got a vertical board with rows of pegs sticking out,” says Aleksandr Alodjants, a professor at ITMO University’s Faculty of Laser Photonics and Optoelectronics. “Small beads dropped from above fall onto the pegs and randomly go left or right, then so on and so on. In this manner, the bead seems to “walk” until it arrives at a point on the bottom. Even though each bead’s path is random, the classic theory states that, if there were enough beads, they would form a pile at the central point.”
Since what happens to the beads can be presented as a sequence of elementary operations and explained with simply physical and mathematical laws, models of such “walks” are widely used to create various computer algorithms. The way in which the pegs are located (the “topology”) can be changed to fit a given problem – quite similarly to the billiard-ball model proposed by Fredkin and Toffolio in their well-known 1982 article Conservative Logic.
Upon connecting with a peg, the bead can ricochet left or right with an equal probability. In the same way, every bit in binary code could have two values: zero or one. But what happens if we decided to reproduce this process in the microworld, with quantum particles for beads and tiny, invisible obstacles in place of pegs?
“If a multitude of quantum particles begins to “walk” such a board, the larger number of them will accumulate not in the center, but near the sides,” explains Aleksandr Alodjants. “There is a simple reason for it: a quantum particle, upon encountering an obstacle, acts as a wave. It both passes through the obstacle and is refracted off it. So it goes both left and right at the same time. That’s a quantum random walk.”
This process resembles the way data is processed by quantum computers, wherein data is encoded with qubits, which have the value of zero and one simultaneously. Just like the description of a regular random walk can be used to create computer algorithms, so can mathematical analysis of the above process be used in quantum computing and some quantum algorithms. Among them are, for instance, search and machine learning algorithms.
Speed squared
The main practical difference between quantum random walks and regular ones is that the speed of a walk is squared in the former case. This is what’s called quantum acceleration.
This begs the natural conclusion: if random walks are at the basis of computer algorithms, then quantum calculations, too, must be faster to the second power than regular ones. That is why the creation of a full-fledged quantum computer is expected to bring on a new technological revolution. But, scientists explain, reality is much more complicated.
“In theory, quantum algorithms should indeed work faster,” says Aleksandr Alodjants. “But there is an important caveat that is often forgotten – “should”, not “will”. When we’re dealing with calculations, the “pegs” on a Galton board are “played” by graph nodes. The question is, will quantum acceleration be present on any graph? To answer this question is to know which algorithm would work faster with a given graph, a classic or a quantum one.”
Quantum becomes non-quantum
To answer this question, an international research team that includes specialists from ITMO University has developed a special convolutional neural network. Its purpose is to predict the speed of random walks depending on the graph structure, quantum measurement methods of the walking particle, and the level of decoherence.
“Everything here works thanks to machine learning,” explains Alexey Melnikov, a co-author of the article and a researcher at ITMO University and the University of Basel. “An expert who has spent years studying graphs could take a look at one and, with a certain degree of probability, say whether random walks of the graph would exhibit quantum acceleration. But this only works for a small number of graphs that have already been researched. Besides, our “vision” is not fit for looking at similar graphs. Sometimes, a graph seems new and unusual, but once you move a few nodes around, it turns out that it’s similar to ones we’re already familiar with. Our neural network combines expert knowledge with the ability to see similarities between complex systems. There’s a direct similarity to computer vision, as our neural network uses convolutions to identify specific qualities of a graph’s connectivity.”
The researchers’ software is, in essence, a quantum machine learning program capable of identifying and classifying the speed of classical and quantum random walks in a system all while answering the question of which algorithm is more effective for a given graph.
“It depends on many factors, such as the graph’s connectivity, its topology, and the distance between its nodes,” explains Alodjants. “There is also the factor of decoherence. The higher it is, the less a quantum model will be effective at its purpose.”
The researchers have demonstrated that, depending on the relative value of the decoherence parameter, quantum random walks can lag enough to become equal to classical ones. In that case, an algorithm run on a quantum computer would be no better than one performed by a regular computer.
“All things point to the fact that, when developing a quantum computer, we’ll need to do our best to isolate the computing processor from decoherence so that it is not affected by noise or heat – so that it works purely based on quantum principles,” says Alodjants. “But any physicist would know that no such system can be fully isolated from the external world. The question is – what is the threshold of quantum coherence we should maintain to preserve the quantum nature of computation? Our research has shown that there is no such universal threshold. Each graph has its own. This would apply to almost any system be it a photonic chip, superconducting circuit, or an atomic ensemble – these complex systems are characterized by a specific level of decoherence.”
He adds that, since every algorithm implemented through these systems can be mathematically recorded as a random walk, scientists will be able to definitively predict whether it would function as a quantum or classical algorithm. According to the researcher, this process would be over 70% accurate for new graphs and over 80% accurate for known graphs. Such an approach would help significantly reduce the amount of resources spent on the development of a quantum computer.
Quantum software, data distribution, and the power industry
This research is beneficial not only to the creation of quantum computers. It also has the potential to serve as the basis in the development of quantum computer software.
“If we see that quantum random walks don’t work well with a certain graph, then we know this graph is more suitable to a classical system. That means it’s not useful in the creation of quantum systems,” explains Alexey Melnikov.
In addition to quantum calculations, the idea of quantum random walks would come in handy when studying the propagation of information on social networks. Researchers from ITMO University are currently at work on a joint project in this field with their colleagues from France.
“Besides making quantum computing viable, another important application of this research is in the delivery of power from point to point with minimal energy spending on the transportation itself,” notes Alexey Melnikov. “For instance, to transport electrons over a cable, you’ll need to apply voltage, or, in other words, spend energy on changing their potential from positive to negative. But we could find a graph in which the electrons traverse a system randomly, but end up arriving at the necessary point thanks to quantum superposition. This is what’s called an ideal transport, and that’s what we’re striving towards.”
Reference: Melnikov A.A., Fedichkin L.E., Lee R‐K., Alodjants A., Machine Learning Transfer Efficiencies for Noisy Quantum Walks. Advanced quantum technologies, 2020/10.1002/qute.202070043
