DOE OSTI · 2482487
Quantum spatial search with multiple excitations
Abstract
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(\sqrt{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(\sqrt{n})$, despite the size of the state space growing as $O(n^k)$. Numerically, we show that this algorithm can be implemented with interactions that decay as $1/r^\alpha$, where $r$ is the distance between spins, and an $\alpha$ that is readily available in current ion trap systems.
Keep this discovery
Explore connections, maps & timelines
Lewis, Dylan, Banchi, Leonardo, Bose, Sougato. 2024-10-08. Quantum spatial search with multiple excitations. https://engineeringpapers.com/record/osti%3A2482487/quantum-spatial-search-with-multiple-excitations
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.