Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk

A random walk(RW) is one of the most ubiquitous stochastic processes and is employed for both mathematical analyses and applications, such as describing real-world phenomena and constructing various algorithms. Meanwhile, along with the increasing interest in quantum mechanics from both theoretical and applied perspectives, the quantum counterpart of a RW, known as a quantum walk (QW), is also attracting attention [1-4]. A QW includes the effects of quantum superposition or time evolution. In classical RWs, a random walker(RWer) selects in which direction to go probabilistically at each time step, and thus one can track where the RWer is at any time step. On the other hand, in QWs, one cannot tell where a quantum walker (QWer) exists during the time evolution, and the location is determined only after conducting the measurement. QWs have a property that classical RWs do not possess: the coexistence of linear spreading and localization [5, 6]. As a result, QWs show probability distributions that are totally different from those of random walks, which weakly converge to normal distributions. The former behavior, linear spreading, means that the standard deviation of the probability distribution of measurement of quantum walkers (QWers) grows in proportion to the run time t.