Contemporary mathematics - American Mathematical Society
HIERARCHICAL QUANTUM SEARCH
V. E. Korepin, Ying Xu
Abstract
We consider a database with one target item. Partial search is designed to find a part of a database [a block] containing the target item. After a user finds the target block he/she might want to make another partial search: subdivide the target block into sub-blocks and look for a sub-block containing the target item. An example: if we need to go to a hotel in USA in a remote location, we first look at a State map [to find highways, which lead to a town with that hotel] and then at the town map [to find a local approach to the hotel]. Minimal number of queries necessary for sequential searches is calculated in the paper. Sequential partial search can be done faster the first one.