An Exact Quantum Search Algorithm with Arbitrary Database

H.Y. Li, Chun-Wang Wu, Wei-Tao Liu +2 more

김정산

Harishankar Mishra, Asvija Balasubramanyam, Gudapati Naresh Raghava

Searching for index corresponding to a given data in an unsorted database represents a nontrivial unstructured search problem with wide-ranging applications in fields like data mining, cryptography, and bio-informatics. Unlike the reverse query, where the data can be trivially obtained from a known index, retrieving the index from data lacks order preservation, making efficient classical search infeasible without linear traversal. To address this problem, we propose a deterministic quantum search algorithm, which provides a solution for the database having any arbitrary number of entries while always guaranteeing success in a single execution. The algorithm is formulated within the quantum circuit model, employing amplitude manipulation techniques that eliminate probabilistic outcomes and ensure exact retrieval of the location of data. We present a scalable circuit construction adaptable to databases of varying sizes, without constraints such as number of entries equal to power-of-two. Because of its adaptability, the proposed algorithm is directly applicable to real-world datasets without the need for costly pre-processing or ineffective data padding. The proposed work presents a resilient and exact technique for the quantum index retrieval problem by providing a solution offering wide applicability and dependable outputs. Our findings shows a clear way towards quantum primitives that can be easily included into deterministic computing workflows, bridging the gap between theoretical speedup and the real-world requirement for dependable outputs.

Sándor Imre, F. Bal�zs

V. E. Korepin, Brenno Carlini Vallilo

Searching and sorting are used as a subroutine in many important algorithms. Quantum algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is a partial search. For example, an exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally, a partial search considers the problem in which a database is separated into several blocks and we want to find a block with the target item, not the target item itself. In this paper, we reformulate a quantum partial search algorithm in terms of group theory.

Songfeng Lu, Yingyu Zhang, Fang Liu