Quantum multi-object search algorithm

Hao Li, Daowen Qiu

Zijian Diao, Peter J.-S. Shiue, Goong Chen

Goong Chen, Zijian Diao

Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several pre­scribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.

Stefano Olivares

Jerzy Klamka

Hao Li, Daowen Qiu, Le Luo

Multi-objective search means searching for any one of several objectives in an unstructured database. Grover's algorithm has quadratic acceleration in multi-objection search than classical ones. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification. In this paper, we design two distributed iterated operators and therefore two new distributed Grover's algorithms are obtained with the following advantages: (1) Compared to Grover's algorithm and the modified Grover's algorithm by Long, our distributed algorithms require fewer qubits; (2) Compared to the distributed Grover's algorithm proposed by Qiu et al., one of our distributed algorithms is exact. Of course, both our distributed algorithms require quite quantum communication and involve a number of more complicated unitary operators as cost, but there still may have certain advantage of physical realizability in the Noisy Intermediate-Scale Quantum (NISQ) era.