All posts by profstange

Your friendly professor.

Due Friday December 4th

Due Fri:

  • Please know that online FCQs are open until Friday.  FCQs are used to evaluate your instructors for reappointment, promotion and tenure, and to inform the department about their teaching effectiveness.  I, personally, greatly appreciate feedback and work to improve my teaching using your feedback.
  • Also, if you haven’t answered my own additional feedback form, please do!
  • The last module, Module 5 (quantum and coding) will be available for the entire exam period.  It will be take-home style, on canvas, due at 11:59 pm on the 13th.  This is a HARD DEADLINE.  Plan ahead!  Plan to complete it the day before the deadline if possible.  Upload a draft of whatever you have earlier in the day so that if you have internet troubles, you don’t lose the entire exam.  Email me before the deadline if you are having problems.
  • Here are solutions to the last two daily posts.
  • To Do:  Here are some coding theory questions to try:  Textbook (available on canvas) Chapter 18 Problems 1, 3, 4, 9.  Hand in on canvas.

Due Wednesday, December 2nd

For Wed:

  • Please know that online FCQs are open.  FCQs are used to evaluate your instructors for reappointment, promotion and tenure, and to inform the department about their teaching effectiveness.  I, personally, greatly appreciate feedback and work to improve my teaching using your feedback.
  • If needed, you’ll want to review the following aspects of linear algebra for studying linear codes:
      • vectors and matrix multiplication
      • vector space and subspace
      • span
      • basis (independence, uniqueness of expression in terms of a basis)
      • dimension
      • kernel of a linear transformation
      • rowspace and column-space
      • rank-nullity theorem
      • transpose of a matrix
  • To Do:
    • Please take some time to fill in this feedback form on aspects of the course.  I list some of the design aspects of our course and ask whether they were helpful or problematic.  It’s a big help to me for designing for future students.  It’s anonymous.
    • Consider the binary code C = {(0,0,1),(1,1,1),(1,0,0),(0,1,0)}.  The alphabet is {0,1}.  This is the same one as last daily post.  Some of the questions that follow are also repeated; you can just revisit your answers.
        1. What is the length of C?
        2. What is d(C) (the minimum distance)?
        3. What are q, n, M and d if C is a q-ary (n,M,d)-code?
        4. How many errors can C detect?
        5. How many errors can C correct?
        6. Show that C is not linear.
        7. 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?
        8. Show that C is a coset of a linear code.  (The definition of a coset is on page 413 of the text, although I talked about it informally in class today:  it’s a translation, by some vector, of a subspace).  What is the linear code?  Call it C’.
        9. Find n and k so that C’ is an [n,k]-code.
        10. Define C’ by linear equation(s).
        11. Give a basis for C’.
        12. Give a matrix for which C’ is the rowspace.

Due Monday, November 30th

For Mon:

  • I hope everyone has/had a wonderful thanksgiving, whether remote, take-out, whatever it is/was.  🙂
  • I’ve opened a “Re-Do Module 3 and 4” assignment on canvas.  It will work like the Re-Do for Module 1 and 2.  In other words, you can do a replacement problem for problems on the assessments, for up to 80% replacement credit.  Please email me to request that I add problems to it, and I will keep adding them as needed.  This will be due the last day of class (December 7th), so make requests by December 4th at latest (note: solutions and grading for Mod 4 will happen this weekend).
  • To Do:
    • Compute the continued fraction of 31/64 by hand.
    • Consider the binary code C = {(0,0,1),(1,1,1),(1,0,0),(0,1,0)}.
        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?
    • 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?

Due Wednesday November 25th

For Wed:

  • Please know that online FCQs are open.  FCQs are used to evaluate your instructors for promotion and tenure, and to inform the department about their teaching effectiveness.  I, personally, greatly appreciate feedback and work to improve my teaching using your feedback.
  • To do:  Try out the Shor’s Algorithm simulation.  More specifically:
      • Try to factor 35.  Use 10 qubits in the first register and 6 in the second (this is already set up by default).  Try alpha = 9.  Trace through the outputs and eventually obtain the measurement of the first register at the 5th box.  Make sure you understand what is happening in each step (i.e. use this as an opportunity to review the material from Monday).  Note: The QFT step can be really slow on the online sage server.  (I just timed it at around 15 or 20 seconds.)
      • With this measurement, use the 6th box to compute the continued fraction convergents.  Pull out the smallest EVEN denominator and try that as your guess for r in the last box.  Did you succeed in factoring?  If not, try measuring again (no need to re-compute the QFT, just go back one box and measure again), and using the new convergents.  It may take several tries!
      • Hand in answers to these questions:
        1. If you measure “0”, why is this not helpful?  What other measurements seem to be unhelpful and why?
        2. Try alpha = 11 and explain how it fails.  What is wrong with this alpha? (With reference to the proposition that we began Monday’s class with.)
        3. Try alpha = 19 and explain how it fails.  What is wrong with this alpha? (Again with reference to the aforementioned proposition.)

Due Monday, November 23rd

Due Mon:

  • To Know:  Your assessment for Module 4 is due Monday!
  • To Know:  Here are solutions to the last daily.
  • To Do:  For the daily post, demonstrate the classical part of Shor’s algorithm using Sage, as follows:
      • Choose N = 33463.
      • Let a be your favourite random integer between 1 and N-1.
      • 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.
      • 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 alpha (as you would in Shor’s algorithm).
      • Hand in a record of the task to the daily dropbox.

Due Friday November 20th

For Friday:

  • To Know:  Assessment 4 is still open, due Monday.
  • To Do:  Compare your solutions to the last daily exercises to my solutions.
  • Optional but recommended:  watch this WONDERFUL 3blue1brown video on Fourier Analysis (19:43).  An important thing to note here:  he’s doing a continuous input variable, whereas for us the domain is Z/nZ.  There are lots of slightly different contexts where one does fourier analysis.  But the principles are the same, although we do a sum where he does an integral.
  • To Do:  Here are some exercises to do on the quantum fourier transform, to get your hands dirty with it.  Hand these in for the daily.

Due Monday November 16th

For Monday:

  • To Know:  I have posted the Module 4 Assessment, to be due Monday November 23rd. Material includes finite fields, elliptic curves, projective space, lattices.
  • To Know:  The last assessment will be due during exam period.  We’ll have to see how the end of the course plays out whether we’ll do separate Module 5 and 6 or combine.  (Module 5 is quantum stuff; Module 6 is coding theory; it remains to be seen how fast we cover material.)
  • To Know:  Here’s an article about a Bell test at NIST here in Boulder and how they are using it to make random numbers.
  • To Know:  Excellent 3Blue1Brown/MinutePhysics video (17:34) which closely related to what we did today.
  • To Do: Exercises on entanglement (and latex source).  Hand in on canvas.
  • To Know:  The DeLong Lectures are next week.

Due Friday November 13

For Fri:

  • To Do:  Look at the solutions to the previous Daily Post if needed.
  • To Know:  The “Quantum” chapter of the text is now up in canvas.
  • To Do: Quantum Key Distribution!
      • I think this will get confusing with everyone simultaneously on the #ciphertexts channel, so I want you to do this in pairs in the “IN CLASS” 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 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.
      • If playing the role of ALICE:
          • Here’s a spreadsheet you might find useful (optional; view only but you can copy it).
          • 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.
      • If playing the role of BOB:
          • Here’s a spreadsheet you might find useful (optional; view only but you can copy it).
          • 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.

Due Wednesday November 11th

For Wed: