Accelerated quantum search using partial oracles and Grover's algorithm

• URL: http://arxiv.org/abs/2403.13035v2
• Date: Mon, 18 Nov 2024 16:50:10 GMT
• Title: Accelerated quantum search using partial oracles and Grover's algorithm
• Authors: Fintan M. Bolton,
• Abstract summary: 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.
• Score: 0.0
• License:
• Abstract: 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. The Grover algorithm exploits the concept of an oracle function, which abstracts the process of matching a search item (returning 1 for a match and 0 otherwise), where searching for 1 target item in a search space of size $N$ scales as $\mathcal{O}(\sqrt{N})$ oracle queries. In this article, 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. Exploring this idea leads to a multi-stage hybrid search algorithm, whose performance can fall within a wide range, anywhere between $\mathcal{O}(\sqrt{N})$ (same as Grover) or $\mathcal{O}(\log(N))$. The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.

Related papers

• Near-deterministic quantum search algorithm without phase control [10.754825115553086]
  Grover's algorithm can find the target item with certainty only if searching one out of four. We propose a near-deterministic quantum search algorithm without the phase control.
  arXiv  Detail & Related papers  (2024-07-15T14:20:47Z)
• Auditable Algorithms for Approximate Model Counting [31.609554468870382]
  We develop new deterministic approximate counting algorithms that invoke a $Sigma3P$ oracle, but can be certified using a $SigmaP$ oracle on far fewer variables. This shows for the first time how audit complexity can be traded for complexity of approximate counting.
  arXiv  Detail & Related papers  (2023-12-19T17:47:18Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• 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)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• 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)
• 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)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• 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)
• 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)
• Grover's search algorithm for $n$ qubits with optimal number of iterations [0.0]
  Grover's search algorithm depends on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. General scheme for the construction of $n$-qubit Grover's search algorithm with $1 leq M leq N$ target states is presented.
  arXiv  Detail & Related papers  (2020-11-08T18:46:50Z)

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.