Time complexity of a spatial search with resetting

Searching a database is a central task in computer science and is paradigmatic of transport and optimization problems in physics. For an unstructured search, Grover’s algorithm predicts a quadratic scaling of the search time with the database size Ν, t_s∼ √Ν. We determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in its simplest form. The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector. Additionally, the quantum state is reset to the initial state if the detector does not click within a specified time interval. This yields a non-unitary, non-Markovian dynamics. We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate. We identify parameter regimes in which the search time scales as t_s∼ N^α with α <  1/2, achieving a time complexity that may surpass the Grover optimal bound.