A particle following a classical random walk on a finite graph will explore the system completely, in time visiting every site repeatedly. The process is ergodic. Hence, starting from any one particular site, the probability to eventually reach any other site is, trivially, equal to one. For some sites, of course, the time required to get there may be much larger than for others. Only if a finite graph is de-composed into several disconnected parts does the dynamics become non-ergodic, with a random walk then prohibited from exploring part of the space.
Things work very differently for quantum walkers on finite graphs. Starting with a particle localized on one node of a finite graph, one may ask for the probability for this particle to be detected later on another node. For example, an observer situated on another node may perform measurements at regular intervals in an attempt to detect the particle. Due to destructive interference, it turns out, there may well be a set of initial states – known as dark states – for which the detection amplitude vanishes at all times. As a result, destructive interference can divide the Hilbert space into two components, dark and bright, yielding an effect similar to classical non-ergodicity, with the walk unable to reach some parts of the graph. More generally, for a generic initial state built as a linear combination of dark and bright states, the probability to be detected later at some node will lie somewhere between zero and one.
In a recent paper, LML Fellow Eli Barkai and colleagues aim to quantify this probability. As they note, a formal solution to this problem has been obtained explicitly for a few examples, but the problem is generally more difficult than the classical counterpart. In their work, Barkai and colleagues derive an uncertainty relation which relates the detection probability to both energy fluctuations and the commutation relation of the Hamiltonian with the projection operator describing the measurement. Whereas the standard uncertainty principle describes the deviation of the quantum world from classical Newtonian mechanics, the relation presented here reveals how quantum walks depart from the corresponding classical walks.
Researchers in quantum computing and information have explored the distinct differences between quantum and classical search processes. Barkai and colleagues hope their new results will encourage thinking about how concepts from quantum search could be applied in an engineering context, given that quantum searches are often more efficient.
The paper is available at https://www.mdpi.com/1099-4300/23/5/595
Leave a Reply