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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Hi, welcome to QCSE. What's wrong with the classical algorithm of just counting the number of $1$'s in the string? That seems to take a linear amount of time. Or perhaps you are trying to prepare a uniform superposition over all strings that have a given Hamming weight? $\endgroup$– Mark SJun 23, 2020 at 0:46
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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)
