# 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.

Also, I have no idea how to prove the if-part.

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*}

More generally, I would say that if you have a separable state, if you apply any reversible 1-qubit gate then it stays separable.

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$$.