Quantum Algorithm for Partial Search

V. E. Korepin, Lov K. Grover

Jie Sun, Songfeng Lu, Fang Liu

V. E. Korepin, Jinfeng Liao

Ri‐Gui Zhou

A multi-pattern partial quantum search algorithm was proposed to increase database searching speed.The algorithm groups the items of a database into equal blocks,neglects some unimportant information,and uses the multi-pattern quantum search algorithm to increase searching speed and concurrently search multi-patterns in the database.An example indicates that the proposed partial algorithm saves 1.325×106 iterations against the global search algorithm in a database with 7.206×1016 items.

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.

Jerzy Klamka