I am trying to understand the Deutsch-Jozsa algorithm for general $U_f$, but the following function is causing me trouble $f(x,y,z)=x\cdot y \oplus z$.

It gives rise to the following quantum gate $U_f:$

$\begin{align} U_{f}(|000x\rangle)&=|000(x)\rangle\\U_{f}(|001x\rangle)&=|001(x\oplus1)\rangle\\U_{f}(|010x\rangle)&=|010(x)\rangle\\U_{f}(|011x\rangle)&=|011(x\oplus1)\rangle\\U_{f}(|100x\rangle)&=|100(x)\rangle\\U_{f}(|101x\rangle)&=|101(x\oplus1)\rangle\\U_{f}(|110x\rangle)&=|110(x\oplus1)\rangle\\ U_{f}(|111x\rangle)&=|111(x)\rangle \end{align} $

From what I understand, for Deutsch-Jozsa to work we need to have $U_f|+++-\rangle =|----\rangle,$ for $f$ balanced.

However, when I try to compute the LHS I get

\begin{align} U_{f}|+++-\rangle&=U_{f}\frac{1}{4}(\sum_{x,y,z\in{0,1}}|xyz0\rangle-\sum_{x,y,z\in{0,1}}|xyz1\rangle)\\&=\frac{1}{4}(|0000\rangle+|0011\rangle+|0100\rangle+|0111\rangle+|1000\rangle+|1011\rangle+|1101\rangle+|1110\rangle\\&-(|0001\rangle+|0010\rangle+|0101\rangle+|0110\rangle+|1001\rangle+|1010\rangle+|1100\rangle+|1111\rangle))\\ &\not = |----\rangle. \end{align}

How can that be if $f$ is balanced?


1 Answer 1


Deutsch-Jozsa algorithm does not have a requirement $U_f|+++-\rangle =|----\rangle$ for the function to turn out balanced. The requirement is that after applying Hadamard gates to each of the qubits at least one of them ends in a state other than $|0\rangle$, that is, the state of those qubits immediately after applying the oracle is not $|+++\rangle$.

You should be able to factor out the last qubit in the $|-\rangle$ state, apply the Hadamard gates to the three input qubits, and get some state that is a superposition of some basis states without the $|000\rangle$ basis state.

  • $\begingroup$ So you are saying, that the requirement is $U_f|+++-\rangle\not = |000-\rangle$? Or that there's 0% probability for $|000-\rangle$ to be the answer? $\endgroup$
    – Punga
    Dec 10, 2021 at 10:26
  • 1
    $\begingroup$ That there is no component $|000-\rangle$ in the superposition after applying the Hadamard gates (remember that the measurement is done not immediately after the oracle application but after the Hadamard gates are applied) $\endgroup$ Dec 10, 2021 at 21:12
  • $\begingroup$ Thanks, I misunderstood the last "classical" step in the algorithm, which funnily enough works (checking for |111> in case of balanced) if f is an affine function. $\endgroup$
    – Punga
    Dec 11, 2021 at 9:24

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.