Optimal quantum spatial search with one-dimensional long-range interactions

• URL: http://arxiv.org/abs/2010.04299v2
• Date: Thu, 13 May 2021 10:41:57 GMT
• Title: Optimal quantum spatial search with one-dimensional long-range interactions
• Authors: Dylan Lewis, Asmae Benhemou, Natasha Feinstein, Leonardo Banchi, Sougato Bose
• Abstract summary: 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$.
• Score: 0.5249805590164902
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in $\mathcal O(\sqrt n)$ time for $n$ entries. However the capability of models found in nature is largely unexplored - e.g., in one dimension only nearest-neighbour Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with $\mathcal O(\sqrt n)$ run time and large fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as $1/r^\alpha$ with distance $r$. In particular, near unit fidelity is achieved for $\alpha\approx 1$ and, in the limit $n\to\infty$, we find a continuous transition from a region where optimal spatial search does exist ($\alpha<1.5$) to where it does not ($\alpha>1.5$). Numerically, we show that spatial search is robust to dephasing noise and that, for realistic conditions, $\alpha \lesssim 1.2$ should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.

Related papers

• Quantum spatial search with multiple excitations [0.28675177318965045]
  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.
  arXiv  Detail & Related papers  (2024-10-08T11:53:57Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  Decentralized online convex optimization (D-OCO) aims to minimize a sequence of global loss functions using only local computations and communications. We develop novel D-OCO algorithms that can respectively reduce the regret bounds for convex and strongly convex functions. Our algorithms are nearly optimal in terms of $T$, $n$, and $rho$.
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• Holograms In Our World [0.0]
  In AdS/CFT, the entanglement wedge EW$(B)$ is the portion of the bulk geometry that can be reconstructed from a boundary region $B$. We define a max- and a min-entanglement wedge, $e_rm max(a)$ and $e_rm min(a)$.
  arXiv  Detail & Related papers  (2023-02-15T19:00:01Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• 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)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• 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)
• 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)
• Spin squeezing with short-range spin-exchange interactions [0.0]
  We investigate many-body spin squeezing dynamics in an XXZ model with interactions that fall off with distance $r$ as $1/ralpha$ in $D=2$ and $3$ spatial dimensions. A region of "collective" behavior in which optimal squeezing grows with system size extends all the way to the $alphatoinfty$ limit of nearest-neighbor interactions.
  arXiv  Detail & Related papers  (2020-06-01T05:11:12Z)

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.