Quantum Partial Search of a Database with Several Target Items

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, whi...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2007-08, Vol.6 (4), p.243-254
Main Authors: Choi, Byung-Soo, Korepin, Vladimir E.
Format: Article
Language:English
Subjects:
Algorithms
Search algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1570-0755
1573-1332
DOI:10.1007/s11128-007-0056-3