Tuning for Quantum Speedup in Directed Lackadaisical Quantum Walks

Abstract

Quantum walks constitute an important tool for designing quantum algorithms and information processing tasks. In a lackadaisical walk, in addition to the possibility of moving out of a node, the walker can remain on the same node with some probability. This is achieved by introducing self-loops, parameterized by self-loop strength $l$, attached to the nodes such that large $l$ implies a higher likelihood for the walker to be trapped at the node. In this work, {\it directed}, lackadaisical quantum walks is studied. Depending on $l$, two regimes are shown to exist -- one in which classical walker dominates and the other dominated by the quantum walker. In the latter case, we also demonstrate the existence of two distinct scaling regimes with $l$ for quantum walker on a line and on a binary tree. Surprisingly, a significant quantum-induced speedup is realized for large $l$. By tuning the initial state, the extent of this speedup can be manipulated.