Spatial search with multiple marked vertices is optimal for almost all queries and its quantum advantage is not always guaranteed

We contribute to fulfil the long-lasting gap in the understanding of the spatial search with multiple marked vertices. The theoretical framework is that of discrete-time quantum walks (QW), i.e. local unitary matrices that drive the evolution of a single particle on the lattice. QW based search algorithms are well understood when they have to tackle the fundamental problem of finding only one marked element in a $d-$dimensional grid and it has been proven they provide a quadratic advantage over classical searching protocols. However, once we consider to search more than one element, the behaviour of the algorithm may be affected by the spatial configuration of the marked elements, due to the quantum interference among themselves and even the quantum advantage is no longer granted. Here our main contribution is twofold : (i) we provide strong numerical evidence that spatial configurations are almost all optimal; and (ii) we analytically prove that the quantum advantage with respect to the classical counterpart is not always granted and it does depend on the proportion of searched elements over the total number of grid points $\tau$. We finally providing a clear phase diagram for the QW search advantage with respect to the classical random algorithm.