No Infinite Tail Beats Optimal Spatial Search

• URL: http://arxiv.org/abs/2301.07251v2
• Date: Fri, 20 Jan 2023 14:18:41 GMT
• Title: No Infinite Tail Beats Optimal Spatial Search
• Authors: Weichen Xie and Christino Tamon
• Abstract summary: We show that spatial search remains optimal in a complete graph even in the presence of an infinitely long path (or tail) We show that the search algorithm is oblivious in that it does not need to know whether the tail is present or not, and if so, where it is attached to.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Farhi and Gutmann (Physical Review A, 57(4):2403, 1998) proved that a continuous-time analogue of Grover search (also called spatial search) is optimal on the complete graphs. We extend this result by showing that spatial search remains optimal in a complete graph even in the presence of an infinitely long path (or tail). If we view the latter as an external quantum system that has a limited but nontrivial interaction with our finite quantum system, this suggests that spatial search is robust against a coherent infinite one-dimensional probe. Moreover, we show that the search algorithm is oblivious in that it does not need to know whether the tail is present or not, and if so, where it is attached to.

Related papers

• Constant search time algorithm via topological quantum walks [0.0]
  We show that it is possible to achieve a constant search-time quantum algorithm with a constant improvement of the search probability overtrivial search. Specifically we study the spatial search algorithm implemented by a two-dimensional split-step quantum random walks.
  arXiv  Detail & Related papers  (2024-06-26T21:36:47Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs.
  arXiv  Detail & Related papers  (2023-07-30T05:14:19Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• k-Means Maximum Entropy Exploration [55.81894038654918]
  Exploration in continuous spaces with sparse rewards is an open problem in reinforcement learning. We introduce an artificial curiosity algorithm based on lower bounding an approximation to the entropy of the state visitation distribution. We show that our approach is both computationally efficient and competitive on benchmarks for exploration in high-dimensional, continuous spaces.
  arXiv  Detail & Related papers  (2022-05-31T09:05:58Z)
• Of Shadows and Gaps in Spatial Search [0.0]
  We show that some families of distance-regular graphs, such as Hamming and Grassmann graphs, have optimal spatial search. We also show a matching lower bound on time for spatial search with constant fidelity, which extends a bound due to Farhi and Gutmann for perfect fidelity.
  arXiv  Detail & Related papers  (2022-04-09T02:02:53Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• BR-NS: an Archive-less Approach to Novelty Search [70.13948372218849]
  We discuss an alternative approach to novelty estimation, dubbed Behavior Recognition based Novelty Search (BR-NS) BR-NS does not require an archive, makes no assumption on the metrics that can be defined in the behavior space and does not rely on nearest neighbours search. We conduct experiments to gain insight into its feasibility and dynamics as well as potential advantages over archive-based NS in terms of time complexity.
  arXiv  Detail & Related papers  (2021-04-08T17:31:34Z)
• Deterministic spatial search using alternating quantum walks [0.0]
  We prove that for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established. This improves on the original spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. It is expected that this new framework can be readily extended to deterministic spatial search on other families of graph structures.
  arXiv  Detail & Related papers  (2021-04-08T14:32:48Z)
• Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces [63.22864716473051]
  We propose a novel BO algorithm which expands (and shifts) the search space over iterations. We show theoretically that for both our algorithms, the cumulative regret grows at sub-linear rates.
  arXiv  Detail & Related papers  (2020-09-05T14:24:40Z)
• On the optimality of spatial search by continuous-time quantum walk [0.0]
  We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm. Our predictions are valid, for example, for Hamiltonians whose spectral gap is considerably larger than $n-1/2$.
  arXiv  Detail & Related papers  (2020-04-27T10:05:55Z)

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.