© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Computers, materials & continua/Computers, materials & continua (Print)

A Quantum Algorithm for Evaluating the Hamming Distance

Sohail Khan, Mohammad Nauman, Suleiman Ali Alsaif, Toqeer Ali Syed, Hassan Ahmad Eleraky

Published Nov 3, 2021• 17 citations

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.

DOI: 10.32604/cmc.2022.020103

Related papers

Measuring Hamming Distance between Boolean Functions via Entanglement Measure

Khaled El-Wazan

In this paper, we present a fast quantum algorithm to measure the Hamming distance between two or more Boolean functions provided as black-boxes. The proposed algorithm constructs a new black-box with a certain property which is utilized to solve this problem. The introduced algorithm converts measuring the Hamming distance between Boolean functions to measuring entanglement between qubits, using concurrence entanglement measure.

arXiv:1903.04762•Mar 12, 2019•0 citations

Calculating Hamming Distance with the IBM Q Experience

José Manuel Bravo

In this brief paper a quantum algorithm to calculate the Hamming distance of two binary strings of equal length (or messages in theory information) is presented. The algorithm calculates the Hamming weight of two binary strings in one query of an oracle. To calculate the hamming distance of these two strings we only have to calculate the Hamming weight of the xor operation of both strings. To test the algorithms the quantum computer prototype that IBM has given open access to on the cloud has been used to test the results.

•Apr 16, 2018•1 citation

Calculating Hamming Distance with the IBM Q Experience

José Manuel Bravo

In this brief paper a quantum algorithm to calculate the Hamming distance of two binary strings of equal length (or messages in theory information) is presented. The algorithm calculates the Hamming weight of two binary strings in one query of an oracle. To calculate the hamming distance of these two strings we only have to calculate the Hamming weight of the xor operation of both strings. To test the algorithms the quantum computer prototype that IBM has given open access to on the cloud has been used to test the results.

•Apr 12, 2018•4 citations

Estimating the Number of Junta Variables for Optimizing Boolean Functions in Quantum Memories

Abdulaziz Mutlaq Alotaibi, Samar AbdelAzim, Sattam Alharbi +1 more

Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.

Mathematics•Oct 25, 2025•0 citations

A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure

Khaled El-Wazan, Ahmed Younes, Salah Badawi Doma

Given a black-box representing an unknown Boolean function $f$ of $n$ variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function $f$ is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.

arXiv:1710.10495•Oct 28, 2017•2 citations

A quantum algorithm based on entanglement measure for classifying Boolean multivariate function into novel hidden classes

Mohammed Zidan, Abdel‐Haleem Abdel‐Aty, Duc Manh Nguyen +4 more

In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.

Results in Physics•Aug 9, 2019•58 citations

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.

In this brief paper a quantum algorithm to calculate the Hamming distance of two binary strings of equal length (or messages in theory information) is presented. The algorithm calculates the Hamming weight of two binary strings in one query of an oracle. To calculate the hamming distance of these two strings we only have to calculate the Hamming weight of the xor operation of both strings. To test the algorithms the quantum computer prototype that IBM has given open access to on the cloud has been used to test the results.

In this brief paper a quantum algorithm to calculate the Hamming distance of two binary strings of equal length (or messages in theory information) is presented. The algorithm calculates the Hamming weight of two binary strings in one query of an oracle. To calculate the hamming distance of these two strings we only have to calculate the Hamming weight of the xor operation of both strings. To test the algorithms the quantum computer prototype that IBM has given open access to on the cloud has been used to test the results.

Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.

Given a black-box representing an unknown Boolean function

f

of

n

variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function

f

is a junta variable. The proposed algorithm creates entanglement between the variable under test and an auxiliary qubit, where the entanglement is measured using concurrence measure to decide if the variable is junta. The paper shows applications to the proposed algorithm in learning and categorization of Boolean functions.

In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.