Section: New Results

Quantum Walks and accelerated mixing algorithms

Participants: A. Sarlette

This major line of work has been pursued together with S.Apers (UGent) and F.Ticozzi (U.Padova), in an attempt to distinguish what is "necessarily" quantum in such models, and what could be explained by memory effects which we could mimic with just classical dynamic controllers. We hence have a series of papers on both sides (quantum and non-quantum): the conference papers are published, the journal papers will be for 2018.

In [19], we investigate under which conditions a higher-order Markov chain, or more generally a Markov chain on an extended state space, can mix faster than a standard Markov chain on a graph of interest. We find that, depending on the constraints on the dynamics, two very different scenarios can emerge: under strict invariance of the target marginal and for general initialization of the lifted chain no speedup is possible; on the other hand, if these requirements are both relaxed, the lifted dynamics can achieve mixing in a time that corresponds to the diameter of the graph, which is optimal.

In [20], we establish a discrete-geometric bound on the convergence speed of mixing with any local stochastic process, under the key assumption that it leaves the target distribution invariant at each time. These processes include classical algorithms, any quantum algorithms, as well as possibly other strategies that obey the non-signalling criterion of probability transmission. We explicitly give the bound in terms of isoperimetric inequalities. We illustrate how this general result leads to new bounds on convergence times beyond the explicit Markovian setting. Mixing is essentially concerned with the discrete-time spreading of a distribution along the edges of a graph. In essence we establish that even by exploiting global information about the graph and allowing a very general use of this information, this spreading can still not be accelerated beyond the so-called conductance bound. An upcoming journal paper will discuss which assumption changes do lead to faster algorithms, and argue how relevant they are for practical applciations.

In [26], we give a preview on our specific results about Quantum walks. Quantum walks have been linked to acceleration in various information processing tasks, and proposed as a possible model for quantum-enhanced behavior in biological systems. These links and acceleration claims have been made with various levels of detail. Here we consider discrete-time quantum walks, and focus on the task of mixing, i.e., distributing the state over a graph. Previous papers have observed that the so-called coined quantum walks can accelerate mixing on certain graphs with respect to the optimal classical Markov chain. We here show that the same speedup can be attained with a classical process, if a similar classical coin is added. We establish a precise correspondence between the mixing performance of quantum walks and such " lifted walks " for all (finite) graphs, and thereby improve known bounds on quantum walk mixing time. We conclude that the advantage of quantum walks with respect to classical processes is not in the mixing speed of the optimal design. However, a notable quantum advantage might reside in the fact that the mixing speed obtained with suboptimal designs, due to for instance limited graph knowledge, appears to be generically faster. The journal version is being finalized and will be sumbitted before the end of 2017.