Searches with non-Hermitian quantum walks

Search problems are prevalent in science and nature. In an unsorted database of Ν items, a classical search requires a runtime of Ο(Ν) to locate the target. Grover's quantum search algorithm promises a quadratic speedup, enabling the task to be completed in Ο(√Ν) iterations. Notably, an analogue of Grover's search can be realized using a continuous-time quantum walk, which achieves the quadratic speedup for certain graph topologies. In this work, we analyse an extension of this dynamics, where the quantum walk is non Hermitian. We determine the scaling of the search time with Ν and perform a systematic comparison with the corresponding unitary implementation. Our study provides insights into the resources, that non-Hermitian dynamics can offer for quantum searches and quantum algorithms in general.