Description: Basic introduction to quantum computation. Topics include: quantum logic gates, quantum networks, quantum entanglement, decoherence, selected quantum algorithms, elements of computational complexity, quantum error correction, fault tolerant quantum computation, and physical implementations of quantum computation.

Desirable Previous Knowledge: The course is largely self-contained but elementary knowledge of quantum mechanics, at the level of The Feynman Lectures on Physics vol. III, is assumed. Familiarity with basic concepts of information theory and computational complexity is useful, however, the relevant material is introduced so you don't need to worry if you haven't seen it before. Some knowledge of rudimentary group theory while not essential, would also be helpful.

Lecturers: Alastair Kay

Class Instructor: Alastair Kay

Class Meetings: There will be three examples classes. The dates and times will be announced in due course, but can be expected to occur in approximately weeks 4, 6 and 8. The question sheets will be made available through this website, and in lectures when appropriate (at least 2 weeks before the relevant class).

• Class 1: Thursday, 1^st November, MR4, 2pm to 4pm.
• Class 2: Friday, 23^rd November, MR4, 1:30pm to 3:30pm.
• Class 3: Friday, 18^th January, MR14, 2pm to 4pm.

Textbooks:

• "Quantum computation and quantum information" by M.A. Nielsen and I.L. Chuang (CUP)
• "An Introduction to Quantum Computing" by P. Kaye, R. Laflamme and M. Mosca (Oxford University Press)
• "Feynman Lectures on Computation" edited by A.J.G. Hey and R.W. Allen (Addison-Wesley)
• "Quantum Computing" by Jozef Gruska (McGraw Hill)
• "Classical and quantum computation" by A.Yu. Kitaev, A.H. Shen and N.N. Vyalyi (AMS)
• John Preskill's lecture notes on Quantum Computation available online.
• For much broader perspective on quantum computation see "The Fabric of Reality" by David Deutsch (Penguin Books).

Some of you asked about good introduction to number theory. The classic textbook is "An Introduction to the Theory of Numbers" by G.H. Hardy and E.M. Wright (OUP). "A Friendly Introduction to Number Theory" by J.H. Silverman (Prentice Hall) is also to be recommended.

A good overview of classical reversible computation can be found in "The Fundamental Physical Limits of Computation" by Charles H. Bennett and Rolf Landauer, Scientific American, July 1985, pages 48-56. You may also want to have a look at the original paper by Landauer titled "Irreversibility and heat generation in the computing process" IBM J. Res. Dev. vol. 5, 183 (1961).

• [Oct 31 07] Please note that there is an error in the current version of the notes regarding phase estimation. I will attempt to fix it and post a new version on 2/11/07.
• [Nov 9 05] For those interested in learning more about the hidden subgroup problem I recommend a review by Chris Lomont (quant-ph/0411037).
• [Dec 1 04] Some of you expressed an interest in how Grover's algorithm works if you don't know the probability of getting a correct outcome (which tells you how many rotations to perform). As always, the http://uk.arxiv.org/ is a useful resource. For example, check out http://arxiv.org/abs/quant-ph/9902049/
• [Oct 27 04] Those of you who showed interest in universal quantum cloning may find the following papers of some interest:
  
  The two original papers where the no-cloning result was stated:
  
  Wootters, W.K. and Zurek, W.H.: A Single Quantum Cannot be Cloned. Nature 299, pp. 802-803 (1982).
  Dieks, D.: Communication by EPR devices. Physics Letters A, vol. 92(6), pp. 271-272 (1982).
  
  For a semi-popular account of more recent developments see:
  
  Buzek, V. and Hillery, M. : "Quantum cloning". Physics World 14 (11) (2001), pp. 25-29
  
  
• [Oct 27 04] Here is a question received via email
  
  
  > My question concerns entanglement. I cannot see why the entangled
  > state
  >
  > (1/sqrt(2)) (|00> + |11>)
  >
  > can not be viewed as maybe |00> or maybe |11>, the decision as to
  > which one it is having been made at the moment of entanglement. No
  > experiment, after all, can distinguish between these possibilities ---
  > am I correct here?
  
  1/sqrt(2)) (|00> + |11>) is different from 50% |00> or 50% |11> and, given enough identically prepared copies, there are experimental tests that can distinguish between the two preparations. Can you think about one? Consider applying the Bell measurement, which we discussed last Tuesday in connection with the teleportation, to two qubits in the state 1/sqrt(2)) (|00> + |11>). What will happen? How does it compare with the Bell measurement on two qubits in state |00> or |11>? The difference between 1/sqrt(2)) (|00> + |11>) and 50% |00> or 50% |11> is of the same nature as the difference between (1/sqrt(2)) (|0> + |1>) and 50% |0> or 50% |1>, which we discussed at some length in connection with the square root of NOT gate.
  

The lecture notes listed here are provided with a severe health warning - they are a work in progress and, as such, contain errors and omissions. Furthermore, they are not to be used to define the course material; their scope is much broader than we can hope to cover in the lectures, but may be of interest to some students who wish to get a flavour of how close the course material is to the front line of research in some areas. These notes are certainly no subsititute for attending the lectures. This early verion of the notes if fairly detailed in the first 6 chapters, and will roughly correspond to the first half of the course. The rest will be of limited use for now, except to see the sort of topics that we may tackle later in the lecture course.

• Version 0.8 (updated 11/12/07)
• Lecture 1

Please email any corrections that you spot to Alastair Kay.

There is some additional material that has previously been produced, and may be useful.

• Overview
• Classical Computation and Logical Operations
• Classical Cryptography - RSA

Example sheets for the Michaelmas 2007 course will appear shortly.

• Example Sheet I - Classical Computation and Introductory Quantum Mechanics - Solutions
• Example Sheet II - Quantum Algorithms - Solutions
• Example Sheet III - Quantum Simulations and Error Correction - Solutions

• 2004
• 2005
• 2006
• 2007

The following are some photos taken of the video lecture given on 11^th November 2003.