Optimality of spatial search in graphs with infinite tail
Weichen Xie, Christino Tamon · Physical Review A · 2023
Farhi and Gutmann [Phys. Rev. A 57, 2403 (1998)] proved that a continuous-time analog of Grover search (also called spatial search) is optimal on complete graphs. We extend this result by showing that spatial search remains optimal on a complete graph even in the presence of an infinitely long path (or tail). If we view the latter as an external quantum system that has a limited but nontrivial interaction with our finite quantum system, this suggests that spatial search is robust against a coherent infinite one-dimensional probe. Moreover, we show that the search algorithm is oblivious in that it does not need to know whether the tail is present or not, and if so, where it is attached to.