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.
On the curve $y^2 = x^3 +2x + 1$ modulo 5, try to compute the addition of the two points P = (3,3) and Q = (1,2) by hand.
On the curve $y^2 = x^3 +2x + 1$ modulo 7, try to compute the addition of the two points P = (0,6) and Q = (0,1) by hand. The result should be the point at infinity (because these are inverses of each other), so the computation will “fail” — explain what fails that lets you know the result is the point at infinity.
On the curve $y^2 = x^3 +2x + 1$ modulo 35, try to compute the addition of the two points P = (28,13) and Q = (21,22) by hand. The result will fail. Explain why it fails and how it factors 35. Explain the relationship to the previous two problems.
Use EC Factoring Tools to factor n = 290265623. You might want to increase the size of the loop! Write up a short explanation of your work.
Write a small Sage for loop to implement Pollard p-1 factoring. Use it to factor n=16637. Some hints so you don’t get stuck:
remember to make $a$ into a value modulo $n$, for example with a = Mod(2,n) (it will actually work with integers but they grow so fast it isn’t efficient).
when you want to take a gcd of a value mod n, you need to make it an integer again by putting a ZZ around it, so like gcd(ZZ(a)-1,n).
start your loop at power 2 (squaring), not zero
If time remains, explore EC Factoring:
Do the example above again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs). Factor n.
Try modifying one of the middle digits of n, and see how long it takes. Factor n completely using Sage’s factor() function, to see what kinds of primes it has in it. Repeat a few more times.
Report/discuss on discord on how long it took (i.e., what multiple of P blew up) on different curves and points, and different n. Explain why you think it was fast sometimes and slow other times. You can use the #daily-collaboration channel.
Your group Poster Plan is due on Wednesday on canvas; please make contact with your group and make a plan. Click “Posters” above for all the details.
Make sure you did last day’s daily post and compare to solutions (link here). Those computations are important; we’ll use them more. Notice in particular what to do if your slope has a denominator, or you are adding a point to itself.
Give an example of four different vectors in $\mathbb{R}^2$ which become the same in $\mathbb{P}^1_\mathbb{R}$.
In the notes, we studied $\mathbb{P}_{\mathbb{F}_3}^2$, showing 26 equivalence classes, each a different colour. Pick one colour, write out the vectors in that equivalence class, and check that they are equivalent.
Compute a full list of the elements in $\mathbb{P}_{\mathbb{F}_5}^1$. Each element is an equivalence class (a bunch of different vectors that differ by scalar multiplication), so write out all the vectors in each equivalence class. (We did this for $\mathbb{P}_{\mathbb{F}_3}^1$ in class.)
In general, in $\mathbb{P}_{\mathbb{F}_{p}}^k$, how many vectors are in each equivalence class? For example, in the example from lecture, in $\mathbb{P}_{\mathbb{F}_{3}}^1$, there were 2 in each class. What is the size of $\mathbb{P}_{\mathbb{F}_{p}}^k$ (i.e. how many equivalence classes)?
Find all the points of the affine equation $y^2 = xy – 1$ on the “line at $\infty$”. (Hint: we did this with the elliptic curve at the end of lecture: first homogenize the equation so all terms have the same degree, then break into $Z=0$ and $Z \neq 0$ cases.)