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

Question

I am asked to prove the following:

Consider the Deutsch-Jozsa circuit. The output of the circuit is of the form $|psirangle otimes frac{1}{sqrt{2}}(|0rangle-|1rangle)$. Prove that the state$|psirangle$ 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_mrangle$ be the state right before the measure and $|psi_hrangle$ be the state right before applying the final Hadamard gates (i.e $|psi_mrangle = H^{otimes n}|psi_hrangle$)
$|psi_mrangle$ entangled $Rightarrow |psi_hrangle$ entangled :
Assume $|psi_hrangle$ is not entangled. Then $|psi_hrangle$ can be written as:$$|psi_hrangle 
=|x_1rangle otimes...otimes|x_nrangle$$
If we now apply the $H$ gates, we get:$$H|x_1rangle otimes...otimes H|x_nrangle$$ $$=frac{1}{2^{n/2}}big[(|0rangle+(-1)^{x_1}|1rangle) otimes ... otimes (|0rangle+(-1)^{x_n}|1rangle) big] $$
Unless there's something I misunderstood or miscalculated, I do not see how this could be not entangled.
Could you please help me out there, please?
Also, I have no idea how to prove the if-part.

Lena · Accepted Answer

Suppose we have two n-qubits states such that $H^{otimes n}|psirangle = |varphirangle$. Then you have the following (remember that H is reversible meaning we can go from the first to the second line) :
begin{align*}
|psirangle text{ is separable iff }& exists (|psi_irangle)_{i in [![1,n]!]} text{ such that }  |psirangle = |psi_1rangle otimes ... otimes |psi_nrangle 
text{iff } & exists (|psi_irangle)_{i in [![1,n]!]} text{ such that } underbrace{H^{otimes n} |psirangle}_{= |varphirangle} = underbrace{(H|psi_1rangle)}_{= |varphi_1rangle} otimes ... otimes underbrace{(H|psi_nrangle)}_{= |varphi_nrangle} 
text{iff } & exists (|varphi_irangle)_{i in [![1,n]!]} text{ such that }  |varphirangle = |varphi_1rangle otimes ... otimes |varphi_nrangle 
text{iff }& |varphirangle 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$.

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

One Answer

Add your own answers!

Ask a Question