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.

Quantum algorithms have enormous technological and recent progress to solve the problem that needs high-performance computing on traditional computers [

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. [^{2}^{n}

Recently, it was proposed that the degree of entanglement can be used efficiently to develop new quantum computing model [_{f}_{g}

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 [

In the first operation, the operator

This operation is achieved by applying

In the second operation, the operator

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

The abstract problem of this paper can be defined, as follows:

Now, the proposed algorithm that solves the above problem can be described, as follows:

_{f}_{g}

If _{0000}>P_{1111}

If _{1111}_{0000}

where C is determined as in

Here, we analyze the performance of the proposed algorithm via a case study. Assume we have the two Boolean functions

To determine the Hamming distance between

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

In Step 3, the proposed algorithm applies the oracle _{f}_{g}_{f}

Similarly, the state of the system after applying the Oracle _{g}

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 _{φ1φ2}

Thus,

According to _{φ1φ2}

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

In the second operation of the operator _{0000}, _{1100}, _{0011}, and _{1111} are estimated. Then, the degree of entanglement _{0000} = _{1111} after measuring operation. So, according to step 6 in the proposed algorithm (see Section (3.2)), the Hamming distance between the Boolean functions

which can be verified from

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 _{f}_{g}_{f}_{g}_{f}, and U_{g}^{14} times on this real quantum computer. _{f}_{g}_{f}_{g}_{f}_{g}

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 [_{f}_{g}^{2} → {0, 1}^{2} → {0, 1}, respectively. Thus, the possible hamming distances between these two oracles are _{f}_{g}_{0}, x_{1}) = 1_{0}, x_{1})_{f}_{g}_{0}, x_{1}) = x_{1}_{0}, x_{1}) = x_{0}x_{1}_{f}_{g}_{0}, x_{1}) = x_{0}x_{1}_{0}, x_{1}) = x_{0}x_{1}_{f}_{g}_{0}, x_{1}) = x_{0} ⊕ x_{1}_{0}, x_{1}) = x_{0}x_{1}_{f}_{g}_{0}, x_{1}) = 1_{0}, x_{1})

It is clear from Section 3.2 that the proposed algorithm measures _{f}_{g}_{0000}, _{0011}, _{1100}, and _{1111} after _{0000}, _{0011}, _{1100}, and _{1111} for the five conducted experiments are depicted in _{0}_{1}) = 1 and _{0}_{1}) = 1 are shown in _{0000}, _{0011}, _{1100}, and _{1111} match the theoretical values exactly with fidelity _{0}_{1}) = 1, and _{0}_{1}) = 1 from their truth tables is _{0011}, _{1100} are zero; this implies that _{0000}_{1111}.

Hence, the simulation result of measuring the hamming distance by the proposed algorithm is _{0}_{1}) = _{1}, and _{0}_{1}) = _{0}_{1} are shown in _{0000}, _{0011}, _{1100}, and _{1111} match the theoretical values expressively with fidelity _{0}_{1}) = _{1}, and _{0}_{1}) = _{0}_{1} from their truth tables is _{0011}, _{1100} are 0.1912 and 0.1899, respectively. Hence, the concurrence value is _{0}_{1}) = _{0}_{1}, and _{0}_{1}) = _{0}_{1} ⊕ _{1} are shown in _{0000}, _{0011}, _{1100}, and _{1111} match the theoretical values expressively with fidelity _{0}_{1}) = _{0}_{1}, and _{0}_{1}) = _{0}_{1} ⊕ _{1} from their truth tables is _{0011}, _{1100} are 0.2513 and 0.2487, respectively. Hence, the concurrence value is _{0000} _{1111}. Accordingly, the simulation result of measuring the hamming distance by the proposed algorithm is _{0}_{1}) = _{0} ⊕ _{1}, and _{0}_{1}) = _{0}_{1} are shown in _{0000}, _{0011}, _{1100}, and _{1111} match the theoretical values expressively with fidelity _{0}_{1}) = _{0} ⊕ _{1}, and _{0}_{1}) = _{0}_{1} from their truth tables is

Practically, it is clear from _{0011} = _{1100} = 0.1899, respectively. So, the concurrence value is _{1111 }_{ }_{0000}. Thus, the simulation result of measuring the hamming distance by the proposed algorithm is _{0}_{1}) = 1 and _{0}_{1}) = 0 are shown in _{0000}, _{0011}, _{1100}, and _{1111} match the theoretical values exactly with fidelity _{0}_{1}) = 1, and _{0}_{1}) = 0 from their truth tables is _{0011}, _{1100} are zero; this implies that

According to _{1111 }_{ }_{0000}, 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.