Grover's search with an oracle distinguishing between solutions

• URL: http://arxiv.org/abs/2508.19793v2
• Date: Sat, 30 Aug 2025 10:16:31 GMT
• Title: Grover's search with an oracle distinguishing between solutions
• Authors: Hristo Tonchev, Rosen Bahtev,
• Abstract summary: modification can be used to maintain a high probability of finding a solution for a number of iterations equal to or more than the one required by the deterministic Grover's algorithm.<n>We use various semiempirical methods to show that the interval of number of iterations for which the algorithm keeps the probability of finding solution high depends on the register size and the oracle phases.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Here we suggest a modification of Grover's algorithm, based on a multiphase oracle which marks each solution with a different phase when there is more than one solution. Such a modification can be used to maintain a high probability of finding a solution for a number of iterations equal to or more than the one required by the deterministic Grover's algorithm (the one based on generalized Householder reflections). We use various semiempirical methods to show that the interval of number of iterations for which the algorithm keeps the probability of finding solution high depends on the register size and the oracle phases.

Related papers

• Quantum algorithm for unstructured search of ranked targets [0.0]
  Grover's quantum algorithm can find a marked item from an unstructured database faster than any classical algorithm.<n>We show that the coherence between multiple marked items tends to increase the probability of finding the most prioritized one in Grover's algorithm with our oracle operator.
  arXiv  Detail & Related papers  (2024-11-30T03:11:09Z)
• The Differentiable Feasibility Pump [49.55771920271201]
  This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost.
  arXiv  Detail & Related papers  (2024-11-05T22:26:51Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
  Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations. We explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently. The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.
  arXiv  Detail & Related papers  (2024-03-19T11:32:02Z)
• Robustness of different modifications of Grovers algorithm based on generalized Householder reflections with different phases [0.0]
  We study five Grovers algorithm modifications, where each iteration is constructed by two generalized Householder reflections. By using semi-empirical methods, we investigate various characteristics of the dependence between the probability to find solution and the phase errors.
  arXiv  Detail & Related papers  (2024-01-07T23:04:39Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• 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)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Towards Meta-Algorithm Selection [78.13985819417974]
  Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates. We show that meta-algorithm-selection can indeed prove beneficial in some cases.
  arXiv  Detail & Related papers  (2020-11-17T17:27:33Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
  arXiv  Detail & Related papers  (2020-09-11T17:31:39Z)

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.