If anyone got only one of the two square roots on the exam, problem 1.2 part 2 (square roots of 3 mod 11), you should get one point out of two. If you got zero points, send me a screenshot via DM on discord or via email and I’ll give you your point.
This series of problems asks you to work through Shor’s period-finding algorithm with two 3-qubit registers by hand. We begin with $|000\rangle |000\rangle$, and then we apply a QFT on the first register to get a uniform superposition. Demonstrate this (you have the 8×8 QFT from last daily post, solution is on #daily-collaboration on discord or in overleaf text). What is the output (as a combined state of both registers)? (Note: I said QFT inverse in class, but plain QFT does it too, so I didn’t need to say that.)
The next step in Shor’s algorithm is to apply $U_f$ for a periodic function $f$. Suppose we get the quantum state $\frac{1}{2\sqrt{2}}\left(|000\rangle |001\rangle + |001\rangle |010\rangle +|010\rangle |100\rangle +|011\rangle |011\rangle +|100\rangle |001\rangle +|101\rangle |010\rangle +|110\rangle |100\rangle +|111\rangle |011\rangle \right)$. This is the quantum state obtained in Shor’s algorithm immediately after applying the gate $U_f$ evaluating a function $f(x) = a^x \pmod{N}$ for some $a$ and $N$. Can you identify $a$ and $N$? (it’s ok if $N$ is prime or composite for this baby example)
Now, measure the second register in the state above. What are the possible output states (of the combined two registers) and probabilities?
Choose one of the four possible outputs from the last part. Apply the QFT on the first register (you have the QFT from the last daily post, and you have to do a matrix multiplication). What is the resulting state (of the combined two registers)?
Now measure the first register. What are the outputs and probabilities?