Hamming Weight algorithm

Question

Is there any quantum algorithm that can improve a calculation time for determining the Hamming weight of an arbitrary bit string? The Deutsch-Jozsa algorithm seems like it would be useful for this algorithm. I could not find any papers on this though.

smapers · Accepted Answer

This corresponds to the problem of counting the number of 1's in some $n$-bit input string. It is well known that for exact counting there can be no significant speedup. This follows from the $Omega(n)$ lower bound on the quantum query complexity of parity (see here). For approximate counting you can get a quantum speedup, as is described here.

Alain Chancé · Answer

I found a paper not yet peer-reviewed by José Manuel Bravo which presents a quantum algorithm to calculate the Hamming distance of two binary strings of equal length and in particular the Hamming weight of a binary string, the number of 1's in the string. It is based on the Deutsch-Jozsa algorithm. Two experiments have been simulated on the IBM Q Experience composer. Bravo, J.M. Calculating Hamming Distance with the IBM Q Experience. Preprints 2018, 2018040164 (doi: 10.20944/preprints201804.0164.v2)

Answered by Alain Chancé on April 1, 2021

Hamming Weight algorithm

2 Answers

Add your own answers!

Ask a Question