# Computer Laboratory

Course pages 2016–17

# Quantum Computing

Principal lecturer:
• Māris Ozols <[Javascript required]>
Supervisors:
• Cambyse Rouze <[Javascript required]>
• Johannes Bausch <[Javascript required]>
• Mithuna Yoganathan <[Javascript required]>
• Sathy Subramanian <[Javascript required]>

### Slides

This year's lecture notes are based on Anuj Dawar's notes from the previous year. However, the content of the new lecture notes is significantly updated and in some places differs from that of the previous years.

### Extra resources

If you are looking for more background material, here are some suggestions for each lecture:

1. You can take a look at the first few pages of a tutorial on Quantum computation by Samuel L. Braunstein.
2. Take a look at John Watrous lecture 1 notes. I also recommend the book Linear Algebra Done Right by Sheldon Axler.
3. This lecture is based on Section 2.2 of [NC] (see below).
4. Check out The IBM Quantum Experience where you can learn more about quantum computing and try running your own algorithms! Reversible classical computation is covered well in Section 3 of [Bra]. Deutsch's algorithm is covered well in Section 2.2 of [Mer]. Relevant sections of [NC]: 1.4.1 Classical computations on a quantum computer, 1.4.2 Quantum parallelism, 1.4.3 Deutsch's algorithm. Relevant sections of [KLM]: 1.5 Reversible computation, 6.2 Phase kick-back, 6.3 The Deutsch Algorithm.
5. QKD and BB84: 12.6.3 Quantum key distribution [NC]. Bell states: 1.3.6 Example: Bell states [NC]. Superdense coding: 2.3 Application: superdense coding [NC], 5.1 Superdense Coding [KLM]. Teleportation: 1.3.7 Example: quantum teleportation [NC], 5.2 Quantum Teleportation [KLM].
6. Quantum search and Grover's algorithm: 6.1 The quantum search algorithm [NC], 8.1 Grover's Quantum Search Algorithm [KLM], 13 Grover's Algorithm [LR], 4 Searching with a quantum computer [Mer].
7. Quantum Fourier transform and Shor's algorithm for factoring: 5 The quantum Fourier transform and its applications [NC], 3 Breaking RSA encryption [Mer], 11 Shor's Algorithm, 12 Factoring Integers [LR], 7 Algorithms with superpolynomial speed-up [KLM].
8. A much more thorough introduction to classical and quantum complexity theory: 3.2 The analysis of computational problems [NC], 9 Quantum computational complexity theory and lower bounds [KLM], 16 Quantum Computation and BQP [LR]. I also recommend John Watrous' excellent survey and talks (Part 1 and Part 2). To discover even more complexity classes, take a look at the Complexity Zoo!

### References

1. [Bra] Braunstein S.L., Quantum computation.
2. [KLM] Kaye P., Laflamme R., Mosca M. (2007). An Introduction to Quantum Computing. Oxford University Press.
3. [LR] Lipton R.J., Regan K.W. (2014). Quantum Algorithms via Linear Algebra: A Primer. MIT Press.
4. [Mer] Mermin N.D. (2007). Quantum Computer Science: An Introduction. Cambridge University Press.
5. [NC] Nielsen M.A., Chuang I.L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
• © 2016 Computer Laboratory, University of Cambridge
Information provided by Dr Maris Ozols