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$\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 S Jun 23 at 0:46
$\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.
