A Quantum Algorithm for Finding Common Matches between Databases with Reliable Behavior

Abstract

Given $\kappa$ databases of unstructured entries, we propose a quantum algorithm to find the common entries between those databases. The proposed algorithm requires $\mathcal{O}(\kappa \sqrt{N})$ queries to find the common entries, where $N$ is the number of records for each database. The proposed algorithm constructs an oracle to mark common entries, and then uses a variation of amplitude amplification technique with reliable behavior to increase the success probability of finding them.