An efficient quantum search engine on unsorted database - Computer Science > DatabasesReport as inadecuate

An efficient quantum search engine on unsorted database - Computer Science > Databases - Download this document for free, or read online. Document in PDF available to download.

Abstract: We consider the problem of finding one or more desired items out of anunsorted database. Patel has shown that if the database permits quantumqueries, then mere digitization is sufficient for efficient search for onedesired item. The algorithm, called factorized quantum search algorithm,presented by him can locate the desired item in an unsorted database using$Olog {4}N$ queries to factorized oracles. But the algorithm requires thatall the property values must be distinct from each other. In this paper, wediscuss how to make a database satisfy the requirements, and present a quantumsearch engine based on the algorithm. Our goal is achieved by introducingauxiliary files for the property values that are not distinct, and convertingevery complex query request into a sequence of calls to factorized quantumsearch algorithm. The query complexity of our algorithm is $OP*Q*M*log {4}N$,where P is the number of the potential simple query requests in the complexquery request, Q is the maximum number of calls to the factorized quantumsearch algorithm of the simple queries, M is the number of the auxiliary filesfor the property on which our algorithm are searching for desired items. Thisimplies that to manage an unsorted database on an actual quantum computer ispossible and efficient.

Author: Heping Hu, Yingyu Zhang, Zhengding Lu



Related documents