2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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… $\endgroup$
    – Mark Spinelli
    Aug 4, 2022 at 15:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.