Dylan Lewis

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.

Linear ion trap chains are a promising platform for quantum computation and simulation. The XY model with long-range interactions can be implemented with a single side-band Molmer-Sorensen scheme, giving interactions that decay as $1/r^α$, where $α$ parameterises the interaction range. Lower $α$ leads to longer range interactions, allowing faster long-range gate operations for quantum computing. However, decreasing $α$ causes an increased generation of coherent phonons and appears to dephase the effective XY interaction model. We characterise and show how to correct for this effect completely, allowing lower $α$ interactions to be coherently implemented. Ion trap chains are thus shown to be a viable platform for spatial quantum search in optimal $O(\sqrt{N})$ time, for $N$ ions. Finally, we introduce a $O(\sqrt{N})$ quantum state transfer protocol, with a qubit encoding that maintains a high fidelity.