Related papers: Quantum Search with Prior Knowledge

Quantum Search with Prior Knowledge

URL: http://arxiv.org/abs/2009.08721v1
Date: Fri, 18 Sep 2020 09:50:33 GMT
Title: Quantum Search with Prior Knowledge
Authors: Xiaoyu He, Jialin Zhang, Xiaoming Sun
Abstract summary: 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.
Score: 15.384459603233978
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes 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.

Related papers

Rectangle Search: An Anytime Beam Search (Extended Version) [9.59799149404787]
Anytime search algorithms try to find a (potentially suboptimal) solution as quickly as possible. We propose a new algorithm, rectangle search, that is instead based on beam search.
arXiv Detail & Related papers (2023-12-19T19:50:45Z)
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)
Complement Grover's Search Algorithm: An Amplitude Suppression Implementation [0.5352699766206808]
Grover's search algorithm was a groundbreaking advancement in quantum algorithms. An extension of Grover's search algorithm is derived where the focus of the query is on the undesirable items. Results are compared against QAOA.
arXiv Detail & Related papers (2022-09-21T16:38:36Z)
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)
A Meta-Heuristic Search Algorithm based on Infrasonic Mating Displays in Peafowls [0.0]
Simplistic methods such as exhaustive search become computationally expensive and unreliable as the solution space for search algorithms increase. This research proposes an Infrasonic Search Algorithm, inspired from the Gravitational Search Algorithm and the mating behaviour in peafowls.
arXiv Detail & Related papers (2021-06-28T09:04:51Z)
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)
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)
Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
arXiv Detail & Related papers (2020-08-29T14:58:26Z)
Best-First Beam Search [78.71330480725668]
We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
arXiv Detail & Related papers (2020-07-08T05:56:01Z)
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.