Quantum walk, entanglement and Markov process

Eman Hamza, Alain Joye

Ulrich Faigle, Alexander Schönhuth

While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations M1, M2resp. two QRW parametrizations Q1, Q2in time O(|Σ| max(N1, N2)4), where N1,N2are the number of hidden states in M1, M2resp. the dimension of the state spaces associated with Q1, Q2, and Σ is the set of output symbols. Previously avail able algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subrou tines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.

Diego de Falco, Dario Tamascelli

A. Romanelli

The asymptotic behavior of the quantum walk on the line is investigated, focusing on the probability distribution of chirality independently of position. It is shown analytically that this distribution has a longtime limit that is stationary and depends on the initial conditions. This result is unexpected in the context of the unitary evolution of the quantum walk as it is usually linked to a Markovian process. The asymptotic value of the entanglement between the coin and the position is determined by the chirality distribution. For given asymptotic values of both the entanglement and the chirality distribution, it is possible to find the corresponding initial conditions within a particular class of spatially extended Gaussian distributions.

Diego de Falco, Dario Tamascelli, Centro Interdipartimentale +1 more

K. Shiokawa