Structured search algorithm: A quantum leap

• URL: http://arxiv.org/abs/2504.03426v1
• Date: Fri, 04 Apr 2025 13:16:53 GMT
• Title: Structured search algorithm: A quantum leap
• Authors: Yash Prabhat, Snigdha Thakur, Ankur Raina,
• Abstract summary: Grover's quantum search algorithm showcases the prowess of quantum algorithms.<n>This letter advances Grover's algorithm using a structured search method to attain an unbounded search speed.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grover's quantum search algorithm showcases the prowess of quantum algorithms, phenomenally reducing the complexity of the search operation of unsorted data. This letter advances Grover's algorithm using a structured search method to attain an unbounded search speed. Remarkably, only two Oracle calls are required to search any element in a dataset of size $2^n$, $n$ being an integer. The algorithm leverages a fixed point approach, iteratively identifying the solution state for multiple qubits at a time, progressively narrowing the search space. The experimental outcomes affirm the algorithm's performance by searching a bit string in 5TB of unsorted binary data on QPU IBM Kyiv. The letter also hypothesizes a scalable classical simulation of the said algorithm.

Related papers

• The optimization of exact multi-target quantum search algorithm based on MindSpore [3.633444773654794]
  We present an optimized exact multi-target search algorithm based on the modified Grover's algorithm.<n>The proposed algorithm can reduce the quantum gate count by at least 21.1% and the depth of the quantum circuit by at least 11.4%.
  arXiv  Detail & Related papers  (2024-12-24T09:39:59Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Hybrid classical-quantum text search based on hashing [0.0]
  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.
  arXiv  Detail & Related papers  (2023-11-02T13:16:07Z)
• Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm [15.622577797491788]
  Isomap algorithm is widely used in neuroimaging, spectral analysis and other fields. We propose the quantum Isomap algorithm, which consists of two sub-algorithms. The time complexity of quantum Isomap algorithm is $O(dNpolylogN)$.
  arXiv  Detail & Related papers  (2022-12-07T12:29:41Z)
• Searching and Sorting Algorithms for Quantum Annealing Computers [0.0]
  A sorting algorithm for data sets is provided, with a consideration of sort stability. Scalability of the algorithms is characterized as a function of problem size.
  arXiv  Detail & Related papers  (2022-04-28T00:18:57Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• 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)
• Fast Search on Binary Codes by Weighted Hamming Distance [38.50174794945964]
  A fast search algorithm is proposed to perform the non-exhaustive search for $K$ nearest binary codes by weighted Hamming distance. A fast search framework based on the proposed search algorithm is designed to solve the problem of long binary codes.
  arXiv  Detail & Related papers  (2020-09-18T02:24:44Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)
• 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.