Constant search time algorithm via topological quantum walks

• URL: http://arxiv.org/abs/2406.18768v2
• Date: Thu, 4 Jul 2024 08:03:33 GMT
• Title: Constant search time algorithm via topological quantum walks
• Authors: D. O. Oriekhov, Guliuxin Jin, Eliska Greplova,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that quantum algorithms such as Grover's can provide a quadradic speed-up for unstructured search problems. By adding topological structure to a search problem, we show that it is possible to achieve a constant search-time quantum algorithm with a constant improvement of the search probability over classical search. Specifically, we study the spatial search algorithm implemented by a two-dimensional split-step quantum random walks that realize topologically nontrivial phases and show the asymptotic search behavior is constant with growing system size. Using analytical and numerical calculations, we determine the efficient search regions in the parameter space of the quantum walker. These regions correspond to pairs of trapped states formed near a lattice defect. By studying the spectral properties of the discrete time-evolution-operators, we show that these trapped states have large overlap with the initial state. This correspondence, which is analogous to localization by constructive interference of bound states, makes it possible to reach the best possible search-time asymptotic and produce a disorder-protected fast search in quantum random walks.

Related papers

• Quantum Dissipative Search via Lindbladians [0.0]
  We analyze the convergence criteria and the convergence speed of a Markovian, purely dissipative quantum random walk on an unstructured search space. We map the results onto an actual implementation to correctly estimate the potential and show that it is no more efficient than classical search.
  arXiv  Detail & Related papers  (2024-07-16T14:39:18Z)
• Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk [0.8057006406834466]
  This paper presents a deterministic search algorithm on complete bipartite graphs. We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states. We construct a quantum counting algorithm based on the spectrum structure of the search operator.
  arXiv  Detail & Related papers  (2024-04-02T05:09:33Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [5.478764356647437]
  We present an improved quantum algorithm for computing persistent Betti numbers. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
  arXiv  Detail & Related papers  (2022-09-26T17:56:11Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• 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)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Transition Probabilities in Generalized Quantum Search Hamiltonian Evolutions [0.0]
  We study the computational aspects necessary to calculate the transition probability from a source state to a target state in a continuous time quantum search problem. We find it is possible to outperform, in terms of minimum search time, the well-known Farhi-Gutmann analog quantum search algorithm.
  arXiv  Detail & Related papers  (2020-02-06T13:16:37Z)
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed [0.0]
  We report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state.
  arXiv  Detail & Related papers  (2020-01-13T19:01: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.