12
$\begingroup$

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 registers 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).

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ 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! $\endgroup$
    – DaftWullie
    May 22, 2018 at 6:12
  • $\begingroup$ @DaftWullie entanglement is not enough for quantum advantage, per Gottesman-Knill theorem. $\endgroup$
    – Mauricio
    Sep 3, 2021 at 12:20
  • 2
    $\begingroup$ @Mauricio necessary is not the same as sufficient! $\endgroup$
    – Mark Spinelli
    Sep 3, 2021 at 13:12

1 Answer 1

Reset to default
7
$\begingroup$

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:

enter image description here

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.

You may also be interested in this article on: "Entanglement and it's role in Shor's algorithm".

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the insight. So one can for sure say that after Hadamard gates there is still no entanglement. It can happen only after the c-U gates and the degree of entanglement further is already harder to analyze. Correct? $\endgroup$
    – wondering
    May 22, 2018 at 11:10
  • $\begingroup$ You are absolutely correct that the Hadamard's do not entangle anything. They are single qubit gates. Entanglement is about two or more systems. Entanglement is defined as not being able to write the state as a product. Hadamard turns |0>|0>|0>|0> into |+>|+>|+>|+> which means a product state remains a product state. You are also correct that the degree of entangment is hard to analyze. For 2-qubit entanglement it's not so bad, but for multi-qubit entanglement there's two many different ways to characterize the entanglement. Look up "entanglement witnesses". $\endgroup$
    – user1271772
    May 22, 2018 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.