Quantum spatial search with multiple excitations
- URL: http://arxiv.org/abs/2410.05945v1
- Date: Tue, 8 Oct 2024 11:53:57 GMT
- Title: Quantum spatial search with multiple excitations
- Authors: Dylan Lewis, Leonardo Banchi, Sougato Bose,
- Abstract summary: We show that a continuous-time quantum walk in the $k$-excitation subspace of $n$ spins can determine the binary string of $k$ marked with fidelity in time $O(sqrtn)$
Numerically, we show that this algorithm can be implemented with interactions that decay as $1/ralpha$, where $r$ is the distance between spins, and an $alpha$ that is readily available in current ion trap systems.
- Score: 0.28675177318965045
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - On the Unlikelihood of D-Separation [69.62839677485087]
We provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist.
For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case.
For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
arXiv Detail & Related papers (2023-03-10T00:11:18Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$.
We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
arXiv Detail & Related papers (2023-02-13T22:51:07Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs.
The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
arXiv Detail & Related papers (2022-03-27T20:22:17Z) - Universality of the fully connected vertex in Laplacian continuous-time
quantum walk problems [0.0]
We prove that the continuous-time quantum walk (CTQW) -- with Hamiltonian $H=gamma L$ -- does not depend on the graph $G$.
We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices.
arXiv Detail & Related papers (2022-02-28T14:33:44Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
We generalise the Childs & Goldstone ($mathcalCG$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks.
We demonstrate the effectiveness of the algorithm by applying it to obtain $mathcalO(sqrtN)$ search on a variety of graphs.
arXiv Detail & Related papers (2021-09-29T11:16:52Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$.
We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
arXiv Detail & Related papers (2021-05-17T16:40:48Z) - Unstructured Search by Random and Quantum Walk [0.0]
Find an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer.
We derive how discrete- and continuous-time random walks and quantum walks solve this problem.
arXiv Detail & Related papers (2020-11-30T04:00:31Z) - Optimal quantum spatial search with one-dimensional long-range
interactions [0.5249805590164902]
Continuous-time quantum walks can be used to solve the spatial search problem.
We prove that optimal spatial search is possible in one-dimensional spin chains with long-range interactions that decay as $1/ralpha$ with distance $r$.
arXiv Detail & Related papers (2020-10-08T23:28:47Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.