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

Calculating Hamming Distance with the IBM Q Experience

José Manuel Bravo

Published Apr 16, 2018• 1 citation
Publisher

Abstract

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.

DOI
10.20944/preprints201804.0164.v2

Related papers

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

Quantum circuits for new applications of the Deutch-Jozsa algorithm

José Manuel Bravo

In this paper a serial of new applications on binary strings based on the Deutch-Jozsa algorithm are presented. These new applications can be used to calculate the Hamming weight and the Hamming distance of a binary string or to compare if two binary strings have the same Hamming weight or the same Hamming distance. To test the applications the quantum computer prototype that IBM has given open access to on the cloud has been used to test the results.

•Apr 25, 2018•0 citations

A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance

Marcos Villagra

The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance $h$ between two strings of length $n$ is greater than $a$ or less than $b$, where the gap $g=|a-b|\geq 1$ and $a$ and $b$ could depend on $n$. In this short note, we give a lower bound of $Ω( \sqrt{n/g})$ on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght $n$. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.

arXiv:1705.09710•May 26, 2017•0 citations

A Quantum Algorithm for Evaluating the Hamming Distance

Sohail Khan, Mohammad Nauman, Suleiman Ali Alsaif +2 more

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.

Computers, materials & continua/Computers, materials & continua (Print)•Nov 3, 2021•17 citations

String Comparison on a Quantum Computer Using Hamming Distance

Mushahid Khan, Andriy V. Miranskyy

The Hamming distance is ubiquitous in computing. Its computation gets expensive when one needs to compare a string against many strings. Quantum computers (QCs) may speed up the comparison. In this paper, we extend an existing algorithm for computing the Hamming distance. The extension can compare strings with symbols drawn from an arbitrary-long alphabet (which the original algorithm could not). We implement our extended algorithm using the QisKit framework to be executed by a programmer without the knowledge of a QC (the code is publicly available). We then provide four pedagogical examples: two from the field of bioinformatics and two from the field of software engineering. We finish by discussing resource requirements and the time horizon of the QCs becoming practical for string comparison.

arXiv:2106.16173•Jun 30, 2021•3 citations

Exact quantum query complexity of weight decision problems.

Xiaoyu He, Xiaoming Sun, Guang Yang +1 more

The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-$n$ input is $k$ or it is $l$. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and sufficiently large $n$, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of $(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.

•Jan 17, 2018•3 citations
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.
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance hhh between two strings of length nnn is greater than aaa or less than bbb, where the gap g=∣a−b∣≥1g=|a-b|\geq 1g=∣a−b∣≥1 and aaa and bbb could depend on nnn. In this short note, we give a lower bound of Ω(n/g)Ω( \sqrt{n/g})Ω(n/g​) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght nnn. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
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.
The Hamming distance is ubiquitous in computing. Its computation gets expensive when one needs to compare a string against many strings. Quantum computers (QCs) may speed up the comparison. In this paper, we extend an existing algorithm for computing the Hamming distance. The extension can compare strings with symbols drawn from an arbitrary-long alphabet (which the original algorithm could not). We implement our extended algorithm using the QisKit framework to be executed by a programmer without the knowledge of a QC (the code is publicly available). We then provide four pedagogical examples: two from the field of bioinformatics and two from the field of software engineering. We finish by discussing resource requirements and the time horizon of the QCs becoming practical for string comparison.
The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-nnn input is kkk or it is lll. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of (kn,ln)(\frac{k}{n},\frac{l}{n})(nk​,nl​) and sufficiently large nnn, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of (kn,ln)(\frac{k}{n},\frac{l}{n})(nk​,nl​) with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.