Steve Vickers: Quantum Computing and Cryptography

News! (22 Mar 2011) Four Qbit "RezQu" quantum computer reported on BBC. It's expected to be scaled up to 10 Qbits by the end of the year.

Quantum Computing and Cryptography

I taught this module in years 2009-10 and 2010-11.

Slides and exercise sheets

Note: For reference, last year's slides are included to cover the whole module. However, the module contents are being changed in some places, and the slides will be updated. Also, some of the week numbers have changed.

The introductory slides on quantum key distribution (guest lecture in the Cryptography module).

Week by week:

  1. Slides: Introduction, Classical bits and vectors; Exercises
  2. Slides: General vectors, Review notes on complex numbers; Exercises
  3. Slides: Qbits and their states; Exercises
  4. Slides: Cryptographic protocols; Exercises
  5. Slides: Cryptography issues; Exercises
  6. Slides: More applications of entanglement; Exercises
  7. Slides: Quantum algorithms: Introduction, More simple quantum algorithms; Exercises
  8. Slides: Special gates for quantum algorithms (includes Grover's search algorithm); Exercises
  9. Slides: Quantum Fourier Transform; Exercises.
    You can also try my QFT applet. It is not very polished. Rough instructions: States for n Qbits are displayed with the 2n amplitudes arranged in a circle. (You can select to see their real parts in red or imaginary parts in green.) You can set up states with a given number of oscillations or with a single spike by using the left-hand entry field with the appropriate button; you can also change the number of Qbits the same way. For the single spike, ensure that the right-hand field is zero - a non-zero entry will give a Gaussian spread to the spike. To set up a state as in the period-finding problem, use both entry fields, the left-hand for the period k and the right-hand for the starting value x0, with the "period" button. The slider on the right scales the heights.
  10. Slides: Breaking RSA; Exercises
  11. Last year's slides: Introduction to quantum error correction; Exercises
Also from last year, here are two guest lectures (unexaminable) by members of the School of Physics. Thanks very much to both of them. Revision notes.



Final exam

The module is assessed 100% by exam. The exam takes place in May and lasts 1.5-hour.

Links to past papers can be found through my.bham, using the my.exams tab. Search for assessment code A10893. This is the official way to get past papers, but I have noticed problems with it and have also put the papers here. You may also find my papers go back further. If you do have problems with the official route, please let me know.

You can also find solutions to last year's paper.

The past papers up to year 2008-9 were for a different module "Introduction to Quantum and Molecular Computation" that was half quantum computing and half molecular computing. Starting last year (2009-10) the exam was "Quantum Computation and Cryptography", all quantum computing and a little deeper too. This year's will have the same arrangement of questions as last year's: one compulsory question for 40%, and then a choice of 2 out of 3 for 30% each. Note that this year's week 5 material "Cryptography issues" is new. (See Nielsen and Chuang.)

The questions in the past papers will be good practice. You should also look at the exercise sheets. The questions there vary. Some are extras to stretch you, but some are examples of what to expect in the exam, particularly those about practical issues of how to carry out an algorithm (e.g. what to do with results).

Textbooks

(See module page for more details.)

Mermin: Quantum Computer Science. Cambridge University Press, 2007.

Mermin's book is the course text. You may be able to do without it, but it is an excellent book and I shall follow it quite closely.

Nielsen and Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2002. Detailed, and in particular covers the material of week 5.

Outline of module

  • Week 1 (Mermin 1.1 - 1.4): Introduction, Cbits and vectors, Reversible operations and matrices.
  • Weeks 2, 3 (Mermin 1.5 - 1.12): Qbits, Superposition of computational basis states, Bloch sphere, Entanglement, Unitaries, Measurements, Born rule.
  • Week 4 (Mermin 6): Protocols - Bell states, Quantum key distribution (BB84), Bit commitment.
  • Week 5 (Not in Mermin - see Nielsen and Chuang 12.6): More cryptographic issues - responding to evidence of errors, information reconciliation, privacy amplification, possible attacks.
  • Weeks 6 (Mermin 6 continued): More on entanglement - Quantum dense coding, Teleportation.
  • Weeks 7-8 (Mermin 2, 4): Quantum computation - Introduction: General process, Problems of Deutsch, Bernstein-Vazirani and Simon problem, Toffoli gates, Grover's algorithm.
  • Week 9, 10 (Mermin 3): RSA - Underlying number theory, RSA encryption, Period finding, Period finding and factoring, Quantum Fourier transform.
  • Week 11 (Mermin 5): Quantum error correction (briefly)