Open Access

ARTICLE

A Quantum Algorithm for Evaluating the Hamming Distance

Mohammed Zidan^1,2,*, Manal G. Eldin³, Mahmoud Y. Shams⁴, Mohamed Tolan^5,6, Ayman Abd-Elhamed^2,7, Mahmoud Abdel-Aty⁸

1 Department of Artificial Intelligence, Hurghada Faculty of Computers and Artificial Intelligence, South Valley University, Egypt
2 Faculty of Engineering, King Salman International University, South Sinai, Egypt
3 Department of Mathematics and Computer Science, Faculty of Science, Beni-Suef University, Beni-Suef, Egypt
4 Department of Machine Learning and Information Retrieval, Faculty of Artificial Intelligence, Kafrelsheikh University, Egypt
5 Mechanical Department, Faculty of Technology and Education, Suez University, Suez, Egypt
6 Faculty of Technological Industries, King Salman International University, South Sinai, Egypt
7 Faculty of Engineering at Mataria, Helwan University, Cairo, Egypt
8 Department of Mathematics, Faculty of Sciences, Sohag University, 82524 Sohag, Egypt

* Corresponding Author: Mohammed Zidan. Email:

(This article belongs to the Special Issue: Role of Computer in Modelling & Solving Real-World Problems)

Computers, Materials & Continua 2022, 71(1), 1065-1078. https://doi.org/10.32604/cmc.2022.020103

Received 09 May 2021; Accepted 29 July 2021; Issue published 03 November 2021

Abstract

We present a novel quantum algorithm to evaluate the hamming distance between two unknown oracles via measuring the degree of entanglement between two ancillary qubits. In particular, we use the power of the entanglement degree based quantum computing model that preserves at most the locality of interactions within the quantum model structure. This model uses one of two techniques to retrieve the solution of a quantum computing problem at hand. In the first technique, the solution of the problem is obtained based on whether there is an entanglement between the two ancillary qubits or not. In the second, the solution of the quantum computing problem is obtained as a function in the concurrence value, and the number of states that can be generated from the Boolean variables. The proposed algorithm receives two oracles, each oracle represents an unknown Boolean function, then it measures the hamming distance between these two oracles. The hamming distance is evaluated based on the second technique. It is shown that the proposed algorithm provides exponential speedup compared with the classical counterpart for Boolean functions that have large numbers of Boolean variables. The proposed algorithm is explained via a case study. Finally, employing recently developed experimental techniques, the proposed algorithm has been verified using IBM's quantum computer simulator.

---

Keywords

---