Add a negative phase to selected states

I have $$n$$ qubits in superposition. I want to add a negative phase to all states with more than $$m$$ $$1$$s, e.g. for $$n=3$$ qubits and $$m=1$$ I want to get:

$$\frac{1}{\sqrt{N}}(|000\rangle + |001\rangle + |010\rangle - |011\rangle + |100\rangle - |101\rangle - |110\rangle - |101\rangle - |111\rangle)$$

I know that I can use CZ gate to add the negative phase, but if I have many qubits do I need to add CZ, C2Z, C3Z to cover any possible state? That would be $$O(2^n)$$ in the number of gates.

• Welcome to QCSE. Please search this site for “Hamming weight”. A trick that is commonly done is to add an extra ancillary register that records the Hamming weight, then add one more single qubit gate to see if the weight is greater than $m$, then $CZ$ that ancilla, and lastly uncompute. I haven’t worked out the complexity of calculating but it’s polynomial, not exponential… Aug 4 at 15:59