A Quantum Algorithm for Finding Common Matches between Databases with Reliable Behavior
Khaled El-Wazan · Quantum Information Review · 2018
Given $κ$ databases of unstructured entries, we propose a quantum algorithm to find the common entries between those databases. The proposed algorithm requires $\mathcal{O}(κ\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.