Computers, Materials & Continua DOI:10.32604/cmc.2022.020103 

Article 
A Quantum Algorithm for Evaluating the Hamming Distance
1Department of Artificial Intelligence, Hurghada Faculty of Computers and Artificial Intelligence, South Valley University, Egypt
2Faculty of Engineering, King Salman International University, South Sinai, Egypt
3Department of Mathematics and Computer Science, Faculty of Science, BeniSuef University, BeniSuef, Egypt
4Department of Machine Learning and Information Retrieval, Faculty of Artificial Intelligence, Kafrelsheikh University, Egypt
5Mechanical Department, Faculty of Technology and Education, Suez University, Suez, Egypt
6Faculty of Technological Industries, King Salman International University, South Sinai, Egypt
7Faculty of Engineering at Mataria, Helwan University, Cairo, Egypt
8Department of Mathematics, Faculty of Sciences, Sohag University, 82524 Sohag, Egypt
*Corresponding Author: Mohammed Zidan. Email: comsi2014@gmail.com
Received: 09 May 2021; Accepted: 29 July 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: Quantum computing; quantum algorithm; quantum circuit
Quantum algorithms have enormous technological and recent progress to solve the problem that needs highperformance computing on traditional computers [1–3]. Nowadays, quantum technologies stand at the crossroads between many areas of study, such as quantum information, combinatorics, computational complexity, and statistical mechanics [4–7].
Boolean functions play a critical role in cryptography, particularly in the design of symmetric key algorithms. Analyzing these functions can be done using many techniques, such as spectral techniques. The Hamming distance
Xie et al. [8] have calculated
Recently, it was proposed that the degree of entanglement can be used efficiently to develop new quantum computing model [7]. A generalized version of the DeutschJozsa problem was solved based on this quantum computing model [11]. Also, this model was used to propose quantum machine leaning algorithms based on this quantum computing model to perform competitive learning quantum mechanically [12,13]. Moreover, based on symmetric matrices in quantum stabilizer codes, a construction of binary and nonbinary quantum stabilizer codes is presented by [14,15]. In this paper, a novel quantum algorithm computes the Hamming distance Ham(f, g) between two unknown Boolean functions. Concretely, it is proposed based on adding four ancilla qubits, and two extra CNOT gates in addition to the degree of entanglementbased quantum computing model [7]. The proposed algorithm retrieves Ham(f, g) between two given oracles Uf and Ug. Then, the complexity of the proposed algorithm is compared with the classical algorithm. Finally, the proposed algorithm is verified using IBM's quantum computer simulator.
The next part of this paper is organized, as follows: In Section 2, the methodology that is used to propose the algorithm is explained. Section 3 shows the problem statement, the proposed algorithm and analysis of the performance of the proposed algorithm via a case study. Also, the complexity of the proposed algorithm compared with classical algorithm is investigated in Section 3. Verification of the proposed algorithm on IBM's quantum computer simulator, and results discussion is performed in Section 4. Finally, main conclusions are discussed in Section 5.
Recently, quantum computing model based on the degree of entanglement has been proposed [7]. This model utilizes concurrence measure to find the solution of some quantum problems based on the degree of entanglement C between two auxiliary qubits in a quantum system of n + 2, where n ≥ 0 [7,11–13]. In this model, the concurrence value C is estimated quantum mechanically via the operator Mz. Therefore, the solution of the quantum computing problems is obtained based on C. Moreover, it was proved that the operator Mz has the potential to distinguish between nonorthogonal states in the form
Mz operator receives two decoupled replicas of two inputs. The first input is the qubit
In the first operation, the operator Mz creates entanglement between each replica of the two qubits
This operation is achieved by applying CNOT on each replica of the two qubits
In the second operation, the operator Mz measures C between the two qubits
where P0011, P1100 are the probabilities of the states
In this section, we investigate the proposed algorithm for measuring the hamming distance between two functions including the problem statement, proposed algorithm, and performance analysis of the proposed algorithm by presenting a case study as in the following subsections.
The Hamming distance between two functions f and g, each acting on nvariable provided via two blackboxes, is defined according to the following definition:
• Definition: The Hamming distance Ham(f, g) between two Boolean functions f(x) and g(x) of n− Boolean variables is defined as:
The abstract problem of this paper can be defined, as follows:
• Given: Given two oracles represent two unknown Boolean functions such that
• Goal: Retrieve the Hamming distance
Now, the proposed algorithm that solves the above problem can be described, as follows:
(1) Step 1: Initialize the quantum register
(2) Step 2: Apply the Hadamard gates to the first n qubits.
(3) Step 3: Apply the oracle Uf and on the first n qubits and the qubit
(4) Step 4: Apply the CNOT gate twice, as follows:
(5) Step 5: Repeat steps 1, 2, 3 and 4 to get a novel decoupled copy of the system
(6) Step 6: Apply Mz between on the two replica of the two qubits
If P0000>P1111, then
If P1111
where C is determined as in Eq. (4).
3.3 Performance Analysis of the Proposed Algorithm: Case Study
Here, we analyze the performance of the proposed algorithm via a case study. Assume we have the two Boolean functions f(x) and g(x), such that n = 2, and corresponding results are defined as in Eq. (7).
To determine the Hamming distance between f(x) and g(x), the steps of the proposed algorithm act, as follows: In Step1, because the number of Boolean variables is 2, so the size of the register
In Step 2, the proposed algorithm applies 2 Hadamard gates on the first two qubits of the system
This step generates the whole domain of the two Boolean functions f(x) and g(x).
In Step 3, the proposed algorithm applies the oracle Uf on the first n qubits and the qubit
Similarly, the state of the system after applying the Oracle Ug is as in Eq. (9).
In Step 4, the proposed algorithm applies 2 CNOT gates simultaneously as follows:
By applying the
At the same time, by applying the
Now, it is clear from Eq. (11) that step 4 evolves the state of the qubit
Let,
Thus, Eqs. (12)–(13), the state system is summarized in Eq. (14).
According to Eq. (14), the first operation of the operator Mz applies the CNOTφ1φ2 to entangle the two qubits:
Now, for this case study at hands, n = 2 and
Consequently, the state of the system which consists of the two replicas, after applying the first operation of the operator Mz, is in Eq. (16).
In the second operation of the operator Mz, the last four qubits in Eq. (16), are measured and the probabilities P0000, P1100, P0011, and P1111 are estimated. Then, the degree of entanglement C among the two qubits of the register
which can be verified from Eq. (7).
Here, the complexity of the proposed algorithm is investigated. In quantum computing, the complexity of algorithms is calculated from the number of the oracle calls. It is evident from Eqs. (5)–(6) that the Hamming distance between the oracles Uf, and Ug depends on the value of the concurrence value C. This value can be determined based on the probabilities of states
4 Experimental Verification of the Proposed Algorithm
To verify the proposed algorithm practically, we will conduct some experiments for measuring the hamming distance between two oracles on IBM's quantum computer simulator called Qiskit Aer [16]. Here, for verification purpose, it is assumed that these oracles are well known for the examiner but unknown for each body else. In the conducted experiments, the oracles, Uf and Ug, represent a Boolean function of two Boolean variables f : {0, 1}2 → {0, 1} and g: {0, 1}2 → {0, 1}, respectively. Thus, the possible hamming distances between these two oracles are Ham(f(x), g(x)) = {0, 1, 2, 3, 4}. Therefore, five experiments are conducted. In the first simulation experiment, the two oracles Uf and Ug are implemented via the Boolean functions f(x0, x1) = 1 and g(x0, x1) = 1, respectively. The quantum circuits of these oracles are shown in Fig. 3. In the second simulation experiment, the two oracles Uf and Ug are implemented via the Boolean functions f(x0, x1) = x1, and g(x0, x1) = x0x1, respectively. The quantum circuits of these oracles are shown in Fig. 4. In the third simulation experiment, the two oracles Uf and Ug are implemented via the Boolean functions f(x0, x1) = x0x1, and g(x0, x1) = x0x1
It is clear from Section 3.2 that the proposed algorithm measures Ham(f(x), g(x)) between two given oracles Uf and Ug based on the concurrence value C by measuring the last four qubits of the system described by Eq. (16). The outcomes of this measurement process estimate the probabilities P0000, P0011, P1100, and P1111 after M shots of measurement. Then, C is calculated quantum mechanically using Eq. (4). The estimated probabilities P0000, P0011, P1100, and P1111 for the five conducted experiments are depicted in Figs. 8a–8e. The blue histograms represent the estimation of these probabilities by IBM's simulator and the green histograms represent the theoretical estimation. The results of the first simulation experiment that measures Ham(f(x), g(x)) between the Boolean functions f(x0, x1) = 1 and g(x0, x1) = 1 are shown in Fig. 8a. It shows that both the simulation results of estimating the probabilities P0000, P0011, P1100, and P1111 match the theoretical values exactly with fidelity F = 1. Theoretically, the Hamming distance between the Boolean functions f(x0, x1) = 1, and g(x0, x1) = 1 from their truth tables is Ham(f(x), g(x)) = 0. Practically, it is clear from Fig. 8a that the probabilities P0011, P1100 are zero; this implies that C = 0 from Eq. (4). According to Fig. 8a, it is obvious that P0000 > P1111.
Hence, the simulation result of measuring the hamming distance by the proposed algorithm is
Practically, it is clear from Fig. 8d that P0011 = P1100 = 0.1899, respectively. So, the concurrence value is C = 0.8716 by Eq. (4). Fig. 8d shows that P1111 > P0000. Thus, the simulation result of measuring the hamming distance by the proposed algorithm is
According to Fig. 8e, P1111 > P0000, so the simulation result of measuring the hamming distance by the proposed algorithm is
In this work, a novel quantum algorithm that measures the Hamming distance between two given oracles is explained. The proposed algorithm retrieves the hamming distances based on the degree of the entanglement between two auxiliary qubits. Therefore, the analysis of the performance of the proposed algorithm is investigated via a case study. Then, the complexity of the proposed algorithm compared to classical algorithm is explained in detail. Finally, the algorithm is verified by IBM's quantum computer simulator. The simulations results shows that the performance of the proposed algorithm is verified with fidelity close to 1.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
References
1. M. AbdelAty, “Delayed sudden birth and sudden death of entanglement in josephsoncharge qubits,” Laser Physics, vol. 19, no. 3, pp. 511–515, 2009.
2. M. AbdelAty, J. Larson, H. Eleuch and A. S. Obada, “Multiparticle entanglement of charge qubits coupled to a nanoresonator,” Physica E: LowDimensional Systems and Nanostructures, vol. 43, no. 9, pp. 1625–1630, 2011.
3. A. Drucker and R. De Wolf, “Uniform approximation by (quantum) polynomials,” Arxiv Preprint Arxiv:1008.1599, pp. 1–9, 2010.
4. A. Nayak and F. Wu, “The quantum query complexity of approximating the median and related statistics,” in Proc. of the ThirtyFirst Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, USA, pp. 384–393, 1999.
5. E. Bernstein and U. Vazirani, “Quantum complexity theory,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1411–1473, 1997.
6. A. De, I. Diakonikolas, V. Feldman and R. A. Servedio, “Nearly optimal solutions for the chow parameters problem and lowweight approximation of halfspaces,” Journal of the ACM (JACM), vol. 61, no. 2, pp. 1–36, 2014.
7. M. Zidan, “A novel quantum computing model based on entanglement degree,” Modern Physics Letters B, vol. 34, no. 35, pp. 2050401, 2020.
8. Z. Xie, D. Qiu and G. Cai, “Quantum algorithms on walsh transform and hamming distance for boolean functions,” Quantum Information Processing, vol. 17, no. 6, pp. 1–17, 2018.
9. K. Kathuria, A. Ratan, M. McConnell and S. Bekiranov, “Implementation of a hamming distance–like genomic quantum classifier using inner products on ibmqx2 and ibmq_16_melbourne,” Quantum Machine Intelligence, vol. 2, no. 1, pp. 1–26, 2020.
10. J. F. Doriguello and A. Montanaro, “Quantum sketching protocols for hamming distance and beyond,” Physical Review A, vol. 99, no. 6, pp. 062331, 2019.
11. M. Zidan, A. H. AbdelAty, D. M. Nguyen, A. S. Mohamed, Y. AlSbou et al., “A quantum algorithm based on entanglement measure for classifying boolean multivariate function into novel hidden classes,” Results in Physics, vol. 15, pp. 102549, 2019.
12. A. H. AbdelAty, H. Kadry, M. Zidan, Y. AlSbou, E. A. Zanaty et al., “A quantum classification algorithm for classification incomplete patterns based on entanglement measure,” Journal of Intelligent & Fuzzy Systems, vol. 38, no. 3, pp. 2809–2816, 2020.
13. M. Zidan, H. Eleuch and M. AbdelAty, “Nonclassical computing problems: Toward novel type of quantum computing problems,” Results in Physics, vol. 21, pp. 103536, 2021.
14. D. M. Nguyen and S. Kim, “New construction of binary and nonbinary quantum stabilizer codes based on symmetric matrices,” International Journal of Modern Physics B, vol. 33, no. 24, pp. 1950274, 2019.
15. D. M. Nguyen and S. Kim, “A novel construction for quantum stabilizer codes based on binary formalism,” International Journal of Modern Physics B, vol. 34, no. 8, pp. 2050059, 2020.
16. IBM Quantum Experience, 2020. [Online]. Available: https://www.ibm.com/quantumcomputing/.
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 