I will be giving feedback via canvas on the poster drafts. Keep working! It sounded like people wanted to have a “poster day” or two when we present them all, instead of a few at the beginning of each class. I’ll ask about that on discord to see.
It was pointed out to me that I have a unwitting habit of saying “first qubit” and “second qubit” when I mean “first register” and “second register” while discussing Shor’s algorithm. I apologize for this! I should never need to talk about the first and second qubits, so pretty much every time I’ve said the former, I meant the latter.
If you are interested in where continued fractions come from and why they are *SO* completely awesome, watch this video. It was one of the winners of #SoME3.
Compute the continued fraction expansion of 9/103 and the associated approximations.
Suppose you wish to factor N=35, using alpha = 9. Suppose you use 10 qubits in the first register and 6 qubits in the second register. Suppose Shor’s algorithm measures y=853 at the end (the final step measuring the first register). Explain how to finish off Shor’s algorithm to factor N.
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 second 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?
You have poster drafts due Friday! I’ll try to make this daily post short, but it would be good if you do a bit of basic computation with the QFT.
Apply the $4 \times 4$ QFT matrix to the state
$\frac{1}{\sqrt{2}} \left(
|00 \rangle +
\frac{1+i}{2} |01 \rangle +
\frac{1-i}{2} |11 \rangle
\right)$
Draw the 8th roots of unity in the complex plane and label them. You can use the $8$-th root of unity notation $\omega := \omega_8 = e^{i \pi/4}$. But simplify it so that the labels are from the set $\{1,-1,i,-i, \omega, -\omega, i\omega, -i\omega\}$.
Write down the QFT matrix of dimension $8 \times 8$. You can use the $8$-th root of unity notation $\omega := \omega_8 = e^{i \pi/4}$. But simplify it so that the entries are all from the set $\{1,-1,i,-i, \omega, -\omega, i\omega, -i\omega\}$.
Verify that the product of two unitary matrices is unitary. (This may require reviewing the transpose of a product.)
Verify that a unitary matrix is invertible and its inverse is unitary.
Apply the reversible AND gate (as demonstrated in class) to the state
$\frac{1}{2} \ket{000} + \frac{1}{2} \ket{011} + \frac{1}{2} \ket{101} + \frac{1}{2} \ket{111}$.
Make an 8×8 unitary matrix that implements a reversible OR gate.
Determine a $2$-qubit quantum circuit that will, on input $\ket{00}$, produce output
$\frac{1}{2} \ket{00} + \frac{1}{2} \ket{01} + \frac{1}{2} \ket{10} + \frac{1}{2} \ket{11}$. Hint: combine Hadamard gates.
Don’t forget to work on your posters! Next deadline is soon!
Compute the complex conjugates of $3+7i$, $8$ and $8i$.
Compute the conjugate transpose of the complex matrix $\begin{pmatrix} 1 & 2+i \\ 3i & i \end{pmatrix}$. Check if this matrix is unitary.
Apply the Pauli Z gate to the single-qubit state $\frac{1+2i}{\sqrt{6}}|0\rangle + \frac{1}{\sqrt{6}}|1\rangle$. What is the output?
Verify that the CNOT gate is unitary.
Apply the CNOT gate to the state $\frac{1+2i}{\sqrt{6}}|01\rangle + \frac{1}{\sqrt{6}}|10\rangle$.
Consider “applying the Hadamard gate the second qubit” as a two-qubit gate.
What does this do to the state $|00\rangle$?
What does this do to the state $|01\rangle$?
Write out the two-qubit 4×4 matrix that does this, and verify that it is unitary.
Begin with 2-qubit state $|00\rangle$.
Apply the CNOT gate the 2-qubit system and then the Hadamard gate the 2nd qubit.
Start over with $|00\rangle$. Now apply the Hadamard gate to the 2nd qubit and then the CNOT gate to the system.
Do you get the same answer?
Consider the single-qubit states $|\psi\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$ and $|\phi\rangle = \frac{1}{\sqrt{2}}|0\rangle – \frac{1}{\sqrt{2}}|1\rangle$.
Explain why, measuring the states in the basis $|0\rangle$, $|1\rangle$, you can’t tell the difference between these states.
Now apply the Hadamard gate $H$ to both states. Now explain what happens to $H|\psi\rangle$ and $H|\phi\rangle$ if you measure in the basis $|0\rangle$, $|1\rangle$. Can you tell the difference between these by measuring?
Create a unitary single-qubit gate that takes $|0\rangle$ to $|0\rangle + i|1\rangle$.
In the state $\frac{1}{\sqrt{2}}|010\rangle + \frac{1}{\sqrt{2}}|111\rangle$, what is the probability of measuring a 0 in the first qubit? middle qubit? last qubit?
Measure the following states in the first qubit and report the possible outcome bits, outcome states and probabilities. Don’t forget to normalize.
Quantum Key Distribution! (Section 6.7 in textbook)
I think this will get confusing with everyone simultaneously on the #ciphertexts channel, so I want you to do this in pairs in the “QKD pairs” channel category of discord. There you will find plenty of text channels, so fill them up with two people each as you arrive, taking the first empty spot (the first person needing a partner or the first unused channel). Announce your arrival. The first person to arrive in a channel is Alice, the second person to arrive is Bob. Once two people are there, it’s full, so pick the next channel. You’ll do all communication on the channel so I can help you debug if it doesn’t work.
Open up the QKD BB84 Tools. The first box contains some code to initialize; no need to read this, just run it. The second box is a spot where you can either create photons (in our instantiation, they are just mysterious looking integers), or measure existing photons. It just holds an example for now.
Once you know if you are Alice or Bob, follow the protocol for your role.
Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage).
Now choose a sequence of 16 bits: example 011001010101 etc. Again, true or good pseudo-randomness is best.
Use your two sequences to generate photons using the command create_photon in the QKD BB84 Tools page. This will create 16 integers (the photons), which you should obtain and paste into the channel as your “outgoing photon stream”.
Wait until Bob harvests your photon stream and reports that they are done “measuring” the photons.
Then, post to the channel the list of bases you used on your photons.
Bob will also post their list of bases used on the channel.
Then, determine the shared secret key from these two lists. Share it and see if Bob agrees.
Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage). Keep this secret for now.
Alice will create a stream of photons (integers). Harvest (cut-n-paste) Alice’s photon stream, and use the command measure_photon() in the QKD BB84 Tools page to measure them using your list of bases (first basis to measure first photon etc.) Record the measurements and keep them secret.
Report to the channel you have finished measuring.
Then, report to the channel your list of bases.
When Alice also reports her list of bases, derive the shared secret.
Then, post the shared secret you derived to check if it agrees with Alice’s.
To Do: When you’re done, just post to canvas a screenshot or record of your experience; you can screenshot the channel or you can screenshot your spreadsheet or a text file you kept a record in; whatever, just to show you did it.
Measure $|+\rangle$ in the $|0\rangle$, $|1\rangle$ basis (i.e. give results and probabilities).
Measure $|+\rangle + i|-\rangle$ in the $|0\rangle$, $|1\rangle$ basis (i.e. give results and probabilities).
Consider the state $|\psi\rangle = \frac{1}{\sqrt{5}} |0\rangle + \frac{2}{\sqrt{5}}|1\rangle$.
Measure it in the basis $|0\rangle$, $|1\rangle$. What are the possible outcomes and their probabilities?
Measure it in the basis $|+\rangle$, $|-\rangle$. What are the possible outcomes and their probabilities? (To do this, you will first need to write $|\psi\rangle$ as a normalized linear combination of $|+\rangle$ and $|-\rangle$.)
With what time remains, work through whatever parts are most useful or interesting to you of this worksheet. My suggestion: if you’re comfortable with the complex numbers as done in class, then start at “Domain Colouring” which is just lovely. If you need more practice with complex numbers because they are new, the earlier parts of the worksheet will provide that.
Find the square root(s), if any, of $3$ modulo $11$ using the algorithm from the end of class. Now draw the dynamical portrait of powers of $3$ modulo $11$. Label each vertex as $3^x = y$ for whatever x and y, so each vertex can be interpreted as its value mod $p$ and its power of $3$. Can you use this diagram to explain why the method works?
Write a small for loop in sage that runs the Blum-Blum-Shub pseudo-random number generator.
Invent a way to check that the output “looks random”. Do you know a good statistical test? Or could you graph it somehow? If you discover some type of non-random-ish behaviour, it could lead to a way to factor integers!
Explain how, if you can factor $n$, you could find square roots modulo $n = pq$ where $p,q$ are primes congruent to $3$ modulo $4$. This is basically just recalling something we did in class.
Explain how, if you can find square roots modulo $n$, this allows you to factor $n$. (Find square roots means find all square roots.) This is basically just recalling something we did in class. This and the previous exercise show that factoring $n$ is considered equivalent to finding square roots modulo $n$.
We are mid-semester, so please make sure your self-eval sheet is up to date and hand in a copy with today’s daily post, so I can see how things are going. Please contact me if you are concerned about your grade. The computed grade in canvas is NOT RELIABLE (the raw grades are reliable, but the conversion to estimated grade is not); you can compute for yourself using the grading tab above.
To Do: An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: best hallowe’en costume? You will encrypt your answer. Here are the steps:
As a group, we will all use the elliptic curve E given by $y^2 = x^3 + x^2 + x + 1$ over the finite field of p = 123456789101234567891027
elements. We will furthermore use the point P = [3,11655832467975276266127,1] on $E$, which has order 61728394550949287614731.
You should create a private and public key pair based on the information given above. Publish your public key on the #public-keys channel on discord (note: this is a point (x,y) on the curve). Keep your private key in a text document somewhere to use for decrypting later.
You should answer the question (Best hallowe’en costume?) with a word of 6 or fewer letters. Translate this to an integer (text to integer tool as usual) and add three digits of “padding” “000” at the end.
Turn your message into a point on the elliptic curve as described in class. This might mean updating the padding to “001”, “010” etc. until it works. For this step, you need to take modular square roots. The command is sqrt. For example, sqrt(Mod(2,7)) will give you the square root of 2 modulo 7 (which is 3). If it returns something with a the string ‘sqrt’ in it, that means it failed (no square root), e.g. sqrt(Mod(3,7)) will just return “sqrt3” — that means no square root.
You should then obtain the most recent public key on the #public-keys channel, and encrypt your ASCII message (turned into a point on the curve) to that public key. Post your encryption to the #ciphertexts channel, @mentioning the owner of the public key it is encrypted to.
You should then keep an eye on the channel and when someone encrypts a message to your public key (they should @mention you), you should decrypt it and announce what the plaintext was, @mentioning them back.
When someone decrypts your message, you should give them a thumbs up to let them know it’s right (or let them know if it isn’t).
Hand in your notes from this exercise to the canvas dropbox.