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.

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.

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.

What is the length of C?

What is d(C) (the minimum distance)?

What are q, n, M and d if C is a q-ary (n,M,d)-code?

How many errors can C detect?

How many errors can C correct?

Show that C is not linear.

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?

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’.

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)}.

What is the length of C?

What are the Hamming distances between the codewords (there are 6 pairs to check)?

How many errors can C detect?

How many errors can C correct?

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?

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.

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:

If you measure “0”, why is this not helpful? What other measurements seem to be unhelpful and why?

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.)

Try alpha = 19 and explain how it fails. What is wrong with this alpha? (Again with reference to the aforementioned proposition.)

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.

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 Know: Don’t forget Assessment Module 4 is open, due Monday. I added some more detailed Ring-LWE lecture notes to the History page, in case that is helpful.

To Do: Compare your answers to the last daily exercise to these solutions.

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: 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.

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.

To Do: Listen to this podcast (26:53). It’s a quantum computing entrepreneur talking about the current (well, 2017) take on how it fits in the big picture. He discusses things like Moore’s Law and the current state of computing, and what quantum computers should be able to do in the future.

To Do: Here’s an exercise (here’s latex source) in measuring a qubit with respect to different bases. Please hand in the answer on canvas.

To Do: Think about the polarized filter experiments I referred to at the end of the lecture — I’ll start with them next lecture, so try to figure out what happens in them before you come to class.