Engineering Papers⌕ Search

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

BibTeXRIS

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.