Find all the lines in $\mathbb{F}_3^2$ (think back to Monday’s class and tic tac toe); draw them all and give them their equations as names.
If a line goes through the origin, it is a subspace of dimension 1. Mark all the ones that are subspaces.
If a line doesn’t go through the origin, it is a translation of a line that does. For example, $y = x+2$ is a translation of $y=x$. Translation means sliding it around without changing its slope, or, equivalently, adding a constant to one side of the equation. For each subspace you marked, find out which lines are the translations of that subspace. The set of translations of a line are called its cosets.
Show that a line and a non-trivial translation of that line don’t intersect.
Suppose I send a message, which is an element of $\mathbb{F}_3^2$, i.e. a vector with two entries modulo $3$. Suppose the message is subject to a possible error (at most one) while in transit. Errors can happen in the following way: one of the two entries can accidentally be increased or decreased by one. If I sent $(1,2)$, what are the possible things that could be received? (E.g., $(1,1)$ is possible… there are five possibilities total, including no error.)
Now, continuing the situation above, which system (“code”) should I use to send a bit? I give two possibilities below. Which is the best system and why?
zero = (0,0), one = (0,1)
zero = (0,0), one = (1,1)
Can you come up with a better system to send a bit? What would better mean? (This is open ended.)
Let me know if there’s any problem scheduling the groups to present on Dec 6th and Dec 9th. If you need to be on one day instead of the other, let me know. Presentations will be 5 mins each with a very brief window for questions. I think we actually need to fit 8 talks in 50 minutes, so 5 mins present + 1 minute questions + 15 second changeover. I’ll bring a buzzer! You can arrange your presentation however you like, but I’ll put all the posters in a slide deck ahead of time.
I plan to put the posters up on a website (like the examples on the “Posters” tab, from other classes). Please let me know if you have any problem with your poster being publicly accessible. I think it would be great to make these available for future students! But it’s up to you.
Review Session Tuesday Nov 19th, 1:45-3 pm, starting in Math 350 and moving to Math 220 around 2:20 pm.
Test on Wednesday! I am working on putting up syllabus/review info in the usual place (Tests tab).
The Archive tab has the lecture notes, and the Overleaf text has a typeset version of Regev encryption (abstract & example).
Regev Encryption Ciphertext Chain!
Check out the Matrices Sage tools (a matrix calculator basically).
Decide on your favourite bit (either 0 or 1). You can interpret that in any way you want.
We will use $p = 3203$. Also $k = 13$, and $n=7$. (Note that in the Matrices tool above, there’s a hint about how to format matrices and vectors so they can be shared easily by cut and paste in discord. Send vectors as row vectors, so the entries are separated by commas, and people can transpose() them as needed.)
Play Bob: Set up a private/public key pair like Bob’s, and put the public portion as your public key on the #public-keys channel.
Play Alice: Find someone else’s public key and send them your message on the #ciphertexts channel.
Play Bob: Receive a message and decrypt it, posting it to the public channel in “spoiler” mode @mentioning the sender.
Play Alice: When someone reveals their decryption, please check it (it’s just a single bit, so this step is important so they know if it worked!) and let them know if it worked!
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 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?
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.