Quantum spatial search with multiple excitations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910641006051328 |
|---|---|
| author | Lewis, Dylan Banchi, Leonardo Bose, Sougato |
| author_facet | Lewis, Dylan Banchi, Leonardo Bose, Sougato |
| contents | 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^α$, where $r$ is the distance between spins, and an $α$ that is readily available in current ion trap systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05945 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum spatial search with multiple excitations Lewis, Dylan Banchi, Leonardo Bose, Sougato Quantum Physics 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^α$, where $r$ is the distance between spins, and an $α$ that is readily available in current ion trap systems. |
| title | Quantum spatial search with multiple excitations |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2410.05945 |