Do states get entangled in Grover’s algorithm?

Question

I am new to QC and right now trying to understand Grover’s algorithm. In Qiskit documents, in the section about solving Sudoku using Grover’s, the first step is explained to be creating three register: $|x\rangle$ $|c\rangle$ and $|out\rangle$

The next step is to initialize $|x\rangle$ by $H|0\rangle$. I get up to here.

Then we apply controlled Not gates to flip the $|c\rangle$ (clause) registers. Here I am stuck because I thought doing a CNOT on $|0+\rangle$ leads to entangled states.

The Qiskit document is here:

https://qiskit.org/textbook/ch-algorithms/grover.html

Do the states really get entangled and if so how can the rest of the circuit work whilst considering the individual qubits?

Answer 1

Indeed the qubits do get entangled! It's not immediately very intuitive as to why the qubits have to be entangled for the Grover algorithm to work. I would recommend this tutorial on Grover's algorithm to understand why. If you're very new, I would start from the beginning. If you know what gates are but are not comfortable with the concept of changing basis, I would start on the slide called "Changing the basis" (page 26 on the pdf). If you are already comfortable with that, then you can straight away start on the slide called "Reflections" (page 40 on the pdf). And then keep going until the end of section on Amplitude Amplification (page 119 on the pdf)

https://drive.google.com/file/d/14G_0TwdxBFpI_Ylj5lb_imVtcnunrQcB/view?usp=sharing