1
$\begingroup$

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.

$\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
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.