Efficient Quantum Algorithms for Set Operations on IBM Q: Design and Experimental Implementation

Abstract

Recent advances in the quantum computing field of computer science that apply the power of quantum mechanics to perform calculations have led many companies, such as IBM, Google, Microsoft, D-Wave Systems, and Xanadu Quantum Technologies, to invest in the field of quantum computing. The main goal of this paper is to apply the Elgendy et al. algorithm, which proposes quantum algorithms for set operations such as true intersection, false intersection, difference, and union, on the current viability of available IBM quantum computers. Moreover, this paper includes a new 5-qubit implementation of Elgendy et al., tests results showing the current capabilities of quantum computers, extends to greater scales, and evaluates algorithm performance on available noisy devices. Elgendy et al. algorithms use a two-stage quantum amplitude amplification technique: The first stage involves preparing the truth set of the first Boolean function using incomplete superpositions, which is done using the Younes et al. technique which performs quantum searching via entanglement and partial diffusion. In the second stage, set operations are handled using an oracle that represents the second Boolean function and a modified version of Arima's algorithm. Among the potential uses are machine learning, cryptography, pattern recognition, and database querying.