# Entanglement in Shor's algorithm

One deals with the notion of superposition when studying Shor's algorithm, but how about entanglement? Where exactly does it appear in this particular circuit? I assume it is not yet present in the initial state $\left|0\right>\left|0\right>$, but how about in further process, after applying Hadamard gates, the controlled-U gates and the inverse Fourier transform? I understand that the first and second register have to be entangled, otherwise the final measurement on one of them wouldn't collapse the other one, which gives us the period (well, kind of, we need to use continuous fractions to infer it).

• It is worth knowing that every interesting quantum computation on pure states has to contain entanglement somewhere. If it doesn’t, the circuit is easily simulated on a classical computer. Of course, that doesn’t explain the ‘where’ for a particular circuit, but that’s already in your answer! – DaftWullie May 22 '18 at 6:12

Your question contains the answer, as you mention the controlled-U gate which is an entangling gate. You will see in the page I linked, that the action of c-U on $|+\rangle|0\rangle$ for example can turn the state into one which cannot be written as a product:
$|+\rangle|0\rangle = \left( \frac{|0\rangle+|1\rangle}{\sqrt{2}} \right)\otimes |0\rangle = \left( \frac{|00\rangle+|10\rangle}{\sqrt{2}} \right)= \left( \frac{|00\rangle+|1\rangle U| 0\rangle}{\sqrt{2}} \right) = \left( \frac{|00\rangle+|1\rangle \left(u_{00}|0\rangle + u_{10}|1\rangle\right)}{\sqrt{2}} \right)$
In the last step, I used the definition of $U$ from the linked controlled-U description:
An example where this gate is entangling is where $u_{00}$ = 0 and $u_{10}=1$, which is just the $\rm{CNOT}$ gate. In that case we get $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ which is the Bell state and is maximally entangled.