Quantum walk search on a two-dimensional grid with extra edges

• URL: http://arxiv.org/abs/2503.04016v1
• Date: Thu, 06 Mar 2025 02:11:02 GMT
• Title: Quantum walk search on a two-dimensional grid with extra edges
• Authors: Pulak Ranjan Giri,
• Abstract summary: Quantum walk has been successfully used to search for targets on graphs with vertices identified as elements of a database.<n>We show that the optimal time complexity of $mathcalO(sqrtN/M)$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum walk has been successfully used to search for targets on graphs with vertices identified as the elements of a database. This spacial search on a two-dimensional periodic grid takes $\mathcal{O}\left(\sqrt{N\log N}\right)$ oracle consultations to find a target vertex from $N$ number of vertices with $\mathcal{O}(1)$ success probability, while reaching optimal speed of $\mathcal{O}(\sqrt{N})$ on $d \geq 3$ dimensional square lattice. Our numerical analysis based on lackadaisical quantum walks searches $M$ vertices on a 2-dimensional grid with optimal speed of $\mathcal{O}(\sqrt{N/M})$, provided the grid is attached with additional long range edges. Based on the numerical analysis performed with multiple sets of randomly generated targets for a wide range of $N$ and $M$ we suggest that the optimal time complexity of $\mathcal{O}(\sqrt{N/M})$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges.

Related papers

• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices. We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Quantum walk search by Grover search on coin space [0.0]
  Lackadaisical quantum walk can search for target vertices on graphs without the help of any additional amplitude amplification technique.<n>We propose a modified coin for the lackadaisical quantum walk search.
  arXiv  Detail & Related papers  (2025-03-06T02:30:37Z)
• 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)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  Decentralized online convex optimization (D-OCO) is designed to minimize a sequence of global loss functions using only local computations and communications. We develop a novel D-OCO algorithm that can reduce the regret bounds for convex and strongly convex functions to $tildeO(nrho-1/4sqrtT)$ and $tildeO(nrho-1/2log T)$. Our analysis reveals that the projection-free variant can achieve $O(nT3/4)$ and $O(n
  arXiv  Detail & Related papers  (2024-02-14T13:44:16Z)
• 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)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• 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)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• 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)
• Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
  Lackadaisical quantum walk (LQW) is a quantum analog of a classical lazy walk. We numerically study search by LQW for different types of 2D grids -- triangular, rectangular and honeycomb.
  arXiv  Detail & Related papers  (2021-04-20T13:33:16Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)

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.