Quantum Partial Search of a Database with Several Target Items |
| |
Authors: | Byung-Soo Choi Vladimir E Korepin |
| |
Affiliation: | (1) Department of Electronics Engineering, School of Information and Communication Engineering, Sungkyunkwan University, Sungkyunkwan, Republic of Korea;(2) C.N. Yang Institute for Theoretical Physics, State University of New York, Stony Brook, NY 11794-3840, USA |
| |
Abstract: | We consider unstructured database separated into blocks of equal size. Blocks containing target items are called target blocks.
Blocks without target items are called non-target blocks. We present a fast quantum algorithm, which finds one of the target
blocks. The algorithm uses the same oracle, which the main Grover algorithm does. We study the simplest case, when each target
block has the same number of target items. Our algorithm is based on Boyer, Brassard, Hoyer, and Tapp algorithm of searching
database with several target items and on Grover–Radhakrishnan algorithm of partial search. We minimize the number of queries
to the oracle. We analyze the algorithm for blocks of large size. In next publications we shall consider more general case
when the number of target items is different in different target blocks.
|
| |
Keywords: | database search partial search multiple target blocks Grover search quantum algorithm optimization |
本文献已被 SpringerLink 等数据库收录! |
|