# Hamming Weight algorithm

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.

• 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? – Mark S Jun 23 '20 at 0:46

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.