How Quantum is a "Quantum Walk"?

We consider the question of characterizing quantumness of so-called quantum random walks. Our measure is based on comparing a quantum walk with its associated nearest classical random walk, and transcends the existing measures in finding quantum properties. We also introduce a technique to attribute a classical random walk to a quantum walk by a contraction noise channel. We then define total quantumness for a walk as the minimum quantum relative entropy of a walker with respect to its genuinely classical cousin. This stronger nonclassicality measure is shown to include quantum coherence as well, and thus can have numerous applications. We discuss several examples to represent how this measure behaves under various quantum or classical noise scenarios. In particular, we employ our quantumness measures to investigate energy transfer or quantum transport on graphs, which has recently gained much attention and applications, e.g., in photosynthesis. We show that a nonvanishing quantumness measure unambiguously implies that a quantum-walk-based process can reach a higher energy/transport efficiency compared to its classical counterparts, and that decay noises do not necessarily kill all quantum effects in such processes---whence providing a partial explanation for why such processes may outperform relevant classical effects.