Deutsch-Jozsa on balanced 3 bit function

Question

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?

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.