Spatial search is the problem of finding a marked vertex in a graph. A continuous-time quantum walk in the single-excitation subspace of an n spin system solves the problem of spatial search by finding the marked vertex in O(n) time. Here, we investigate a natural extension of the spatial search problem, marking multiple vertices of a graph, which are still marked with local fields. We prove that a continuous-time quantum walk in the k-excitation subspace of n spins can determine the binary string of k marked vertices with an asymptotic fidelity in time O(n), despite the size of the state space growing as O(nk). Numerically, we show that this algorithm can be implemented with interactions that decay as 1/rα, where r is the distance between spins, and an α that is readily available in current ion trap systems.
Abstract A fully connected vertex w in a simple graph G of order N is a vertex connected to all the other N − 1 vertices. Upon denoting by L the Laplacian matrix of the graph, we prove that the continuous-time quantum walk (CTQW)—with Hamiltonian H = γL —of a walker initially localized at | w ⟩ does not depend on the graph G . We also prove that for any Grover-like CTQW—with Hamiltonian H = γL + ∑ w λ w | w ⟩⟨ w |—the probability amplitude at the fully connected marked vertices w does not depend on G . The result does not hold for CTQW with Hamiltonian H = γA (adjacency matrix). We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices, proving that CTQWs on any graph G inherit the properties already known for the complete graph of the same order, including the optimality of the spatial search. Our results provide a unified framework for several partial results already reported in literature for fully connected vertices, such as the equivalence of CTQW and of spatial search for the central vertex of the star and wheel graph, and any vertex of the complete graph.