# Prove entanglement in the final state of the Deutsch-Jozsa circuit

I am asked to prove the following:

Consider the Deutsch-Jozsa circuit. The output of the circuit is of the form $$|\psi\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$$. Prove that the state$$|\psi\rangle$$ right before the measure is entangled if and only if it is entangled right before applying the final series of $$H$$ gates (Hadamard gates)

Here's my attempt.

Let $$|\psi_m\rangle$$ be the state right before the measure and $$|\psi_h\rangle$$ be the state right before applying the final Hadamard gates (i.e $$|\psi_m\rangle = H^{\otimes n}|\psi_h\rangle$$)

$$|\psi_m\rangle$$ entangled $$\Rightarrow |\psi_h\rangle$$ entangled :

Assume $$|\psi_h\rangle$$ is not entangled. Then $$|\psi_h\rangle$$ can be written as:$$|\psi_h\rangle =|x_1\rangle \otimes...\otimes|x_n\rangle$$

If we now apply the $$H$$ gates, we get:$$H|x_1\rangle \otimes...\otimes H|x_n\rangle$$ $$=\frac{1}{2^{n/2}}\big[(|0\rangle+(-1)^{x_1}|1\rangle) \otimes ... \otimes (|0\rangle+(-1)^{x_n}|1\rangle) \big]$$

Unless there's something I misunderstood or miscalculated, I do not see how this could be not entangled.

Suppose we have two n-qubits states such that $$H^{\otimes n}|\psi\rangle = |\varphi\rangle$$. Then you have the following (remember that H is reversible meaning we can go from the first to the second line) :
\begin{align*} |\psi\rangle \text{ is separable iff }& \exists (|\psi_i\rangle)_{i \in [\![1,n]\!]} \text{ such that } |\psi\rangle = |\psi_1\rangle \otimes ... \otimes |\psi_n\rangle \\ \text{iff } & \exists (|\psi_i\rangle)_{i \in [\![1,n]\!]} \text{ such that } \underbrace{H^{\otimes n} |\psi\rangle}_{= |\varphi\rangle} = \underbrace{(H|\psi_1\rangle)}_{= |\varphi_1\rangle} \otimes ... \otimes \underbrace{(H|\psi_n\rangle)}_{= |\varphi_n\rangle} \\ \text{iff } & \exists (|\varphi_i\rangle)_{i \in [\![1,n]\!]} \text{ such that } |\varphi\rangle = |\varphi_1\rangle \otimes ... \otimes |\varphi_n\rangle \\ \text{iff }& |\varphi\rangle \text{ is separable} \end{align*}
By the way, the last state you wrote is indeed separable, notice you were able to factorize it (i.e. write it with tensor products), and you also forgot the $$1/\sqrt{2}$$ factor for each $$H$$ you apply, meaning the state should have a total factor of $$1/2^n$$.