For Wed:

1. This is your last daily post!  Thank you all so much for bringing your enthusiasm to the class.  This has really been one of my favourite classes ever.
2. This daily post was posted late!  Please give yourself an extra day to hand it in if needed.  Apologies.
3. Many last announcements:
   1. 1. Today was the last lecture with content for the final exam.  Wednesday will be a presentation by our graduate student; attendance is still expected!
      2. FINAL DAILY POST GRADE (due before exam).  When you are all done daily posts, you should complete your self eval form and upload it to canvas in the special-purpose drop box for that (not the usual one) before the exam (due the minute the exam starts).
      3. MODULE 4 & 5 RETAKES (due before exam).  These are written at this point; you’ll find the opportunity and dropbox on canvas.
      4. Did you miss a Retake?   For each one, there is/was an opportunity to make up one Part B problem to improve your grade (either in person or written).  If you missed out on one of these opportunities, please contact me and we can re-open an opportunity for you.  Please look through your records and your canvas grades and let me know if I’ve made any errors.
      5. Please complete the FCQs for this course.  I really appreciate the time you take.  They are used for my own professional development, to inform decision-making in the department, and for promotion, among other things.  The last day is Tuesday.
      6. Please also answer a few more specific questions about the course here for me (if you haven’t already):  here.  (This is an anonymous google form where you can help me understand how things like discord/daily posts etc. are helpful/not.)  I really appreciate this!
      7. Don’t interpret canvas’ “total” or “letter” grade as meaning anything.  It’s just a storage depot for the raw grades, so you can compute your letter grade by hand.  I have no idea what formula canvas is using (or more importantly how to turn it off!)
      8. There was a grading correction to the Module 5 Question 1 Part 3.  Details sent to your email; let me know if you missed this.
4. For today’s daily, please complete the following:
   1. 1. Please take time to do the FCQs first — DIRECT LINK — (if you don’t have time to finish this stuff below, you can finish it while studying for the final later).
      2. Here are some daily post questions to do.

For Monday:

1. Please complete the FCQs for this course.  I really appreciate the time you take.  They are used for my own professional development, to inform decision-making in the department, and for promotion.
2. Please also answer a few more specific questions about the course here for me:  here.  (This is an anonymous google form where you can help me understand how things like discord/daily posts etc. are helpful/not.)
3. Consider the binary code C = {(0,0,1),(1,1,1),(1,0,0),(0,1,0)}.
   1. 1. What is the length of C?
      2. What are the Hamming distances between the codewords (there are 6 pairs to check)?
      3. How many errors can C detect?
      4. How many errors can C correct?
      5. Suppose you send the codeword (1,1,1) and 2 errors are made on the noisy channel, in the first and last positions. Explain what message is received and what it decodes to. Was communication successful?
4. In general, suppose a code has codewords which are all at Hamming distance d from each other (in other words, every pair is distance d).  How many errors can it detect?  How many errors can it correct?

For Fri:

1. Don’t forget FCQs are open!  I really appreciate your feedback and read them very carefully.
2. There were a lot of administrative announcements in yesterday’s daily, you might want to review them.
3. Compare your last daily to the solutions.
4. I have intentionally NEVER done this all semester, but I had ten more minutes of riveting information to share about lattice-based cryptography, so I made a bonus 10-minute video.  (I’ve allowed myself this luxury because I really don’t want to delay coding theory.)  Watch it here.  The lecture notes include this material.
5. A Ring-LWE ciphertext chain!  You may want to review the course video on canvas and I’ve made careful overleaf notes.  Here’s what you’ll need:
   • • Our general setup with be the prime p = 100003 and n=8.  We will use l=10.  This will allow us enough room for each coefficient to hold one letter from the text-to-integer-to-text tools.  Because there are 8 coefficients, you can store 8 letters.
     • Answer the question “what’s the best part of crypto?” in 8 letters or less, and store it as an element of the ring $R_p$ using one letter per coefficient (coefficient of $x^7$ is the first letter, coefficient of $x^6$ is the second letter, etc.).  This will be your message.
     • At the Ring-LWE Tools page you’ll see how to initialize the polynomial ring, and you’ll have two functions that generate short and random elements.  In our case, “short” means coefficients from {-1,0,1}.
     • First, generate your own private/public key pair and post the public key (g,B) on the discord #ciphertexts channel.  Keep your secret key for later (e.g. in a text file).  Important note:  discord normally interprets asterisks and stuff in special ways; to make it easier on everyone, surround your polynomials with backticks ` when pasting into discord, and it will post it verbatim.  This will make cutting-and-pasting to/from Sage easier.
     • Now, encrypt your message to the most recent unused public key on the #ciphertexts channel.  Post your message (K,C) on the #ciphertexts channel and mention the appropriate person.
     • Wait until someone sends you a message.  When this happens, decrypt it using your secret key, and announce their favourite part of crypto on #ciphertexts, mentioning them so they can confirm.
     • Post your record of the events/computations to the canvas dropbox.

For Wed:

1. Some announcements:
   1. 1. All the in-class assessments are complete.  For each one, there is/was an opportunity to make up one Part B problem to improve your grade.  For each there was a grade cutoff for doing the retake written (in-person only for grades below 7 on module 2, below 6 on module 3, below 5 on module 4 and all on module 5).  You will find written retake problems for all of these on canvas (the final assessment will be written-retakes-only in the interests of time).  If you missed out on one of these opportunities, please contact me and we can re-open an opportunity for you.  Please look through your records and your canvas grades and let me know if I’ve made any errors.
      2. The final day of class there will be an in-class presentation (to which I will be joining virtually).
      3. That leaves us four lecture days for lattices & coding (sadly not enough).  For this reason the final exam will be a larger proportion of comprehensive review than expected.
      4. I apologize for not getting through material at the rate predicted.  The grading adjustments have now been made on the website in red under “Grading” in the top bar.
      5. Please go through your daily post activities and make sure I have a current version of your daily post self-evaluation sheet (and that you do too!).
2. By hand, find a reduced basis and a shortest nonzero vector in the lattice generated by (58,19) and (168,55).  (We covered this in Monday’s class; also see section 17.2 in text, and the example in class is written up in the overleaf notes.)

Happy Thanksgiving!

For Friday:

1. You have a test!  I’ll be happy to have office hours, which I will announce on discord if we set some times, but that will include the hour 9-10 am before the test for last-minute stuff (room 308).  Thursday I can be found on discord/zoom.
2. Please play with the Shor’s Algorithm Demo and do a couple continued-fraction expansions by hand to match with the Sage output there, to make sure you know how.
3. Good luck Friday!

1. I have posted some quantum-review questions on the “Goals” page (with solutions).
2. Demonstrate the classical part of Shor’s algorithm using Sage, as follows:
   1. 1. Choose N = 33463.
      2. Let a be your favourite random integer between 1 and N-1.
      3. Define R = IntegerModRing(N) and alpha = R(a).  The Sage command alpha.multiplicative_order() will play the role of the quantum computer; it outputs the multiplicative order of alpha.
      4. Use the result to factor N, in the manner of Shor’s algorithm, as described in class.  If it doesn’t work, try another random a (as you would in Shor’s algorithm).
3. This exercise gets you closer to computing a discrete logarithm on a quantum computer.  Suppose $h = g^a$ for some unknown $a$.  Consider the function $f: \mathbb{Z}/(p-1)\mathbb{Z} \times \mathbb{Z}/(p-1)\mathbb{Z} \rightarrow \mathbb{Z}/p\mathbb{Z}$ given by $(x,y) \mapsto h^{-x} g^y \pmod p$.
   1. 1. For what values of $(x,y)$ do you have $f(x,y)=1$?
      2. For what values of $(x,y)$ do you have $f(x,y) = g$?
      3. Show that the function $f$ is constant on any line $L_K$ given by $y= ax + K$ for any constant $K$.
      4. Show that $f$ is `periodic’ in the sense that it repeats when we add any $(z,az)$ to the input values.  In other words, $f(x,y) = f(x+z,y+az)$.
      5. Suppose you somehow discover that $f(x_1,y_1) = f(x_2,y_2)$ for different input pairs.  Explain how you can compute $a$ from this.

For Monday:

• I know the course has been covering lots lately.  On Monday we will pull it all together and factor with a quantum computer.   Please take your weekend daily post time and do what is most useful for you.  Some ideas (just ideas, don’t feel obligated) are:
  1. 1. Catch up/revisit the last daily post (here are solutions) or earlier ones.
     2. Revisit course notes and videos to solidify what we’ve got.
     3. Read your textbook’s chapter on quantum, which is much more big-picture and fewer details.
     4. Play with colour graphing the Fourier transform matrix.
     5. Watch this 3blue1brown video about the continuous Fourier tranform.  It isn’t exactly the same as the QFT, but the fundamental underlying  ideas are similar, and time spent with 3blue1brown is never wasted.
     6. Relax, have some chicken soup, and catch up on the cryptography news.

For Friday:

1. There is a Module 5 Test on Friday, November 18th, 2022.  As usual, I’ll try to update the “Goals” page with topics/review.
2. See the last daily post for retakes on last module test.
3. Compare your last daily post to the solutions here.
4. Read the Overleaf Notes section on “Quantum Fourier Transform” (currently 6.10 toward the end).  This addresses notational handling of the QFT. (1 page)  Please read actively, which means testing yourself as you go (for example, cover up the display we just derived and re-derive it).
5. Do these exercises on QFT.

For Wed:

• If you want to do a written retake for the earlier modules (2 and 3) they are due on canvas — I’ve moved the due date back to Wednesday in case you lost track of this (I didn’t remind people a lot).
• Module 4 retakes:  if you wish to retake a grade of 0, 1, 2, 3, or 4, we will do it in person; otherwise we’ll have a written retake.  Email or discord me to set up an in-person retake.  The written retakes will open on canvas soon and you’ll have a few weeks.
• Compare your answers to the last daily exercise to these solutions.
• Here are some exercises on quantum gates.