Performance of continuous time quantum walks under phase damping

A. Blumen, Oliver Mülken

Takuya Machida

Daniel ben‐Avraham, Eric M. Bollt, Christino Tamon

Joshua Lockhart, Carlo D. Franco, Mauro Paternostro

We study the behaviour of the glued trees algorithm described by Childs et al. in [STOC `03, Proc. 35th ACM Symposium on Theory of Computing (2004) 59] under decoherence. We consider a discrete time reformulation of the continuous time quantum walk protocol and apply a phase damping channel to the coin state, investigating the effect of such a mechanism on the probability of the walker appearing on the target vertex of the graph. We pay particular attention to any potential advantage coming from the use of weak decoherence for the spreading of the walk across the glued trees graph.

Xin Wang, Yi Zhang, Kai Lü +2 more

The source detection problem is the reverse of information diffusion. It is identifying information sources of the diffusion process. However, most existing algorithms have limited performance due to various reasons, therefore the application is limited. We propose an approach, namely Quantum Walk based Source Detection (QWSD), to identify the source nodes based on the continuous-time quantum walk (CTQW). The continuous-time quantum walk can be utilized to simulate the diffusion process. Therefore, we utilize the reversed quantum walk to reverse the diffusion, thus revealing the probability for a node to be a source node. It is the first time that the continuous-time quantum walk is applied to the source detection problem. Extensive experiments demonstrate that our algorithm outperforms other source detection algorithms on both synthetic datasets and real-world datasets.

Daniel ben‐Avraham, Eric M. Bollt, Christino Tamon