Accelerated quantum search using partial oracles and Grover's algorithm
- URL: http://arxiv.org/abs/2403.13035v1
- Date: Tue, 19 Mar 2024 11:32:02 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 as a technique for extracting solutions from the result sets generated by quantum computations.
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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used as a technique for extracting solutions from the result sets generated by quantum computations. The 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). This black-box approach hides the details of a search problem and works with the assumption that the items in the search space are completely unordered. In this case, searching for 1 target item in a search space of size $N$ scales as $\mathcal{O}(\sqrt{N})$ oracle queries (or $\mathcal{O}(\sqrt{N/M})$ oracle queries for $M$ target items in a search space of size $N$). Hidden inside the typical black-box oracle, however, the process of matching an item usually involves matching multiple data bits. 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))$ (exponentially faster). Apparently, the search acceleration works by dynamically discovering order in the search space, where the order consists of correlations between the partial oracle functions and the search index. This new algorithm is validated against the simplest kind of search scenario.
Related papers
- BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
We focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting.
We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires $Theta(n)$ queries to an NP oracle, quantumly $Theta(log n)$ queries suffice.
Moving to approximate counting, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal.
arXiv Detail & Related papers (2024-01-08T14:59:48Z) - Fast Interactive Search with a Scale-Free Comparison Oracle [17.38671584773247]
A comparison-based search algorithm lets a user find a target item $t$ in a database by answering queries of the form.
We propose a scale-free probabilistic oracle model called $gamma$-CKL for such similarity triplets $(i,j;t)$.
We develop a search algorithm with provably exponential rate of convergence under the $gamma$-CKL oracle, thanks to a backtracking strategy.
arXiv Detail & Related papers (2023-06-02T09:33:19Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $s, s'$.
Also, we present a quantum algorithm consuming $fracn2+O(sqrtn)$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+Omega(1)$ queries.
arXiv Detail & Related papers (2022-11-19T11:14:19Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems.
The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical.
We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
arXiv Detail & Related papers (2022-05-19T16:04:40Z) - 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) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
We consider the basic problem of querying an expert oracle for labeling a dataset in machine learning.
We present a randomized batch algorithm that operates on a round-by-round basis to label the samples and achieves a query rate of $O(fracNk2)$.
In addition, we present an adaptive greedy query scheme, which achieves an average rate of $approx 0.2N$ queries per sample with triplet queries.
arXiv Detail & Related papers (2021-10-05T20:15:35Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $Csubseteq0,1n$.
The goal is to identify $x$ using as few queries to the oracle as possible.
We develop a quantum query algorithm for this problem with query complexity $Oleft(sqrtfracnlog M log(n/log M)+1right)$, where $M$ is the size of $C$.
arXiv Detail & Related papers (2021-09-08T19:48:27Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
We propose an elegant theoretical model for studying clustering with a faulty oracle.
It was left as an open question whether one can obtain a query-optimal, time-efficient algorithm for the general case of $k$ clusters.
We provide a time-efficient algorithm with nearly-optimal query complexity (up to a factor of $O(log2 n)$) for all constant $k$ and any $delta$ in the regime when information-theoretic recovery is possible.
arXiv Detail & Related papers (2021-06-18T22:20:12Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z)
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.