1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Hi and welcome to Quantum Computing SE. Could you please add link to the document you are asking about? $\endgroup$ – Martin Vesely Feb 12 at 7:05
  • 1
    $\begingroup$ The algorithm must have some entanglement somewhere. You do not consider just individual qubits, but the global state of the system. $\endgroup$ – DaftWullie Feb 12 at 7:40
  • $\begingroup$ Hello Martin. Thank you. I added a link to the document. $\endgroup$ – Dshepherd Mar 3 at 0:59
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you so much!! The reference you mentioned is awesome! Qiskit’s explanation was not very clear. There was no mention of entanglement. I worked on some math to understand it. What I found out was, if my math is correct, for a 3 qubit circuit with following operations in order: H on q1 , H on q2, CNOT q1->q3 , CNOT q2->q3, H on q1, H on q2 = The result is €*(|0⟩* |0⟩* |+⟩ + |1⟩* |1⟩* |-⟩) with € some constant. Is this about right? $\endgroup$ – Dshepherd Mar 3 at 1:23
  • $\begingroup$ To be honest I didn't try it by hand, but I coded it up the circuit you described on qiskit and got the same answer as you, so looks good to me! $\endgroup$ – Rajiv Krishnakumar Mar 3 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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