Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal 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
Publisher

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•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 16, 2018•2 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 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•4 citations

Rotational Encoding of Objective Functions for Quantum Optimization

Sonia Yang, Ali Al-Bayaty, Shanyan Chen +1 more

In this paper, we introduce the Angular Rotational Counter (ARC), a novel approach to represent objective functions that can be decomposed as a weighted sum of Boolean functions. ARC encodes the objective as an accumulated sum of quantum rotations onto a single-qubit register instead of a multi-qubit register used in much of the previous literature. We mathematically establish and experimentally validate that these rotations sum to the objective value for all possible solutions and derive the relationship between the resulting measurement probabilities and the objective. This design was applied to construct a quantum oracle for the state assignment problem of finite automata and state machines using a weighted Hamming distance cost function, which is a special case of the quadratic assignment problem. We evaluate this oracle design on 26 benchmarks and compare it with corresponding Boolean-based oracles on four cost metrics. Across these benchmarks, the oracle with ARC produces a mean reduction in the qubit count of 20.8%, gate count of 89.3%, circuit depth of 92.4%, and quantum cost of 90.6%. These results demonstrate substantial reductions in circuit cost for the evaluated benchmarks and establish rotational encoding as a promising approach for representing objective functions in optimization based on quantum search algorithms.

arXiv:2611.11858•Nov 9, 2026•0 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 fff of nnn variables, in this paper we propose a fast quantum algorithm to test whether or not a certain variable in the function fff 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 introduce the Angular Rotational Counter (ARC), a novel approach to represent objective functions that can be decomposed as a weighted sum of Boolean functions. ARC encodes the objective as an accumulated sum of quantum rotations onto a single-qubit register instead of a multi-qubit register used in much of the previous literature. We mathematically establish and experimentally validate that these rotations sum to the objective value for all possible solutions and derive the relationship between the resulting measurement probabilities and the objective. This design was applied to construct a quantum oracle for the state assignment problem of finite automata and state machines using a weighted Hamming distance cost function, which is a special case of the quadratic assignment problem. We evaluate this oracle design on 26 benchmarks and compare it with corresponding Boolean-based oracles on four cost metrics. Across these benchmarks, the oracle with ARC produces a mean reduction in the qubit count of 20.8%, gate count of 89.3%, circuit depth of 92.4%, and quantum cost of 90.6%. These results demonstrate substantial reductions in circuit cost for the evaluated benchmarks and establish rotational encoding as a promising approach for representing objective functions in optimization based on quantum search algorithms.