Hybrid classical-quantum text search based on hashing

• URL: http://arxiv.org/abs/2311.01213v1
• Date: Thu, 2 Nov 2023 13:16:07 GMT
• Title: Hybrid classical-quantum text search based on hashing
• Authors: Farid Ablayev and Marat Ablayev and Nailya Salikhova
• Abstract summary: It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given. We propose a hybrid classical-quantum algorithm that implements Grover's search to find a given in a text.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The paper considers the problem of finding a given substring in a text. It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given substring. At the same time, Grover's quantum search provides a quadratic speedup in the complexity of the query and gives the correct result with a high probability. We propose a hybrid classical-quantum algorithm (hybrid random-quantum algorithm to be more precise), that implements Grover's search to find a given substring in a text. As expected, the algorithm works a) with a high probability of obtaining the correct result and b) with a quadratic query acceleration compared to the classical one. What's new is that our algorithm uses the uniform hash family functions technique. As a result, our algorithm is much more memory efficient (in terms of the number of qubits used) compared to previously known quantum algorithms.

Related papers

• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• 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)
• Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer [2.487445341407889]
  Combination of Depth-First Search and Grover's algorithm to generate Depth-First Grover Search(DFGS) DFGS handles multi-solution searching problems on unstructured databases with an unknown number of solutions. New algorithm attains an average complexity of $mathcalO(msqrtN)$ which performs as efficient as a normal Grover Search.
  arXiv  Detail & Related papers  (2022-10-10T13:10:28Z)
• 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)
• Hybrid Quantum-Classical Search Algorithms [0.0]
  We show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. We generalize this result to algorithms with subconstant success probabilities.
  arXiv  Detail & Related papers  (2022-02-23T11:43:17Z)
• Deterministic Grover search with a restricted oracle [2.976027966501599]
  Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms. We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.
  arXiv  Detail & Related papers  (2022-01-01T02:04:11Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Quantum Algorithms for String Processing [58.720142291102135]
  We provide a quantum algorithm for the String matching problem that uses exponentially less quantum memory than existing ones. Using the same ideas, we provide two algorithms for the String comparing problem. The second algorithm works exponentially faster than the existing one.
  arXiv  Detail & Related papers  (2020-12-01T09:59:06Z)
• Quantum Search with Prior Knowledge [15.384459603233978]
  We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
  arXiv  Detail & Related papers  (2020-09-18T09:50:33Z)
• 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)

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.