Quantum Processes and Computation: 2022-2023
Schedule C1 (CS&P) — Computer Science and Philosophy
Schedule C1 — Computer Science
Schedule C1 — Mathematics and Computer Science
Michaelmas Term — MSc in Advanced Computer Science
Michaelmas Term 2022 (24 lectures)
Both physics and computer science have been very dominant scientific and technological disciplines in the previous century. Quantum Computer Science aims at combining both and may come to play a similarly important role in this century. Combining the existing expertise in both fields proves to be a non-trivial but very exciting interdisciplinary journey. Besides the actual issue of building a quantum computer or realising quantum protocols it involves a fascinating encounter of concepts and formal tools which arose in distinct disciplines. This course provides an interdisciplinary introduction to the emerging field of quantum computer science, explaining basic quantum mechanics (including finite dimensional Hilbert spaces and their tensor products), quantum entanglement, its structure and its physical consequences (e.g. non-locality, no-cloning principle), and introduces qubits. We give detailed discussions of some key algorithms and protocols such as Grover's search algorithm and Shor's factorisation algorithm, quantum teleportation and quantum key exchange. At the same time, this course provides an introduction to diagrammatic reasoning. As an entirely diagrammatic presentation of quantum theory and its applications, this course is the first of its kind.
This course will be given online.
- Lectures will be held in person in the Tony Hoare Room, every Monday, Wednesday, and Friday 12:00-13:00 UK time (full timetable here). Recordings will appear online after each lecture.
- Class info, including weekly deadlines is on Minerva
- Everything else (problem sheets, schedule of material, etc) is here on the course website
The course consists of:
- 24 lectures (see Lectures below)
- 6 classes (weeks 3, 4, 5, 6, 7, 8). Here are the problem sheets:
- Assignment 1 due Mon week 3 (Groups 3 and 4) or Weds week 3 (Groups 1 and 2) ... solutions
- Assignment 2 due Fri week 3 (Groups 3 and 4) or Weds week 4 (Groups 1 and 2) ... solutions
- Assignment 3 due Fri week 4 (Groups 3 and 4) or Weds week 5 (Groups 1 and 2) ... solutions
- Assignment 4 due Fri week 5 (Groups 3 and 4) or Weds week 6 (Groups 1 and 2) ... solutions
- Assignment 5 due Fri week 6 (Groups 3 and 4) or Weds week 7 (Groups 1 and 2) ... solutions
- Assignment 6 due Fri week 7 (Groups 3 and 4) or Weds week 8 (Groups 1 and 2) ... solutions
- The miniproject. This will have a similar format to the problem sheets, but questions will be much more in-depth and/or open-ended.
The following is a provisional list of topics / sections covered in the lectures. This schedule is subject to change.
Handwritten lecture notes (part 1, part 2, part 3, part 4, part 4a, part 5) cover the material in each lecture. Note these are from a previous year, so they might not line up with lecture numbers precisely.
- Lecture 1, Oct 10: Introduction to diagrammatic reasoning
- Lecture 2, Oct 12: Circuit diagrams
- Lecture 3, Oct 14: Special processes
- Lecture 4, Oct 17: (Non-)separability and string diagrams
- Lecture 5, Oct 19: Transpose, adjoint, and conjugate processes
- Lecture 6, Oct 21: Quantum-like features from string diagrams
- Lecture 7, Oct 24: Quantum-like features from string diagrams (cont'd)
- Lecture 8, Oct 26: Bases, sums, and Hilbert spaces
- Lecture 9, Oct 28: From linear maps to (pure) quantum maps
- Lecture 10, Oct 31: Discarding, mixture, and causality
- Lecture 11, Nov 2: Non-determinism and measurement
- Lecture 12, Nov 4: Classical/quantum interaction
- Lecture 13, Nov 7: Classical data as wires
- Lecture 14, Nov 9: Spiders!!!
- Lecture 15, Nov 11: Classical, quantum, and bastard spiders
- Lecture 16, Nov 14: Phases and complementarity
- Lecture 17, Nov 16: Stern-Gerlach and quantum key distribution
- Lecture 18, Nov 18: Strong complementarity and the ZX-calculus
- Lecture 19, Nov 21: Universality, completeness, and quantum computation
- Lecture 20, Nov 23: Anatomy of a quantum algorithm
- Lecture 21, Nov 25: Strong complementarity and graphical group theory
- Lecture 22, Nov 28: The hidden subgroup problem and factoring
- Lecture 23, Nov 30: Grover's search algorithm
- Lecture 24, Dec 2: Quantum non-locality and GHZ/Mermin
Learning outcomesThe student will know by the end of the course what quantum computing and quantum protocols are about, why they matter, and what the scientific prospects of the field are. This includes a structural understanding of some basic quantum mechanics, knowledge of important algorithms such as Grover's and Shor's algorithm and important protocols such as quantum teleportation.
At the same time, the student will understand diagrammatic reasoning as an alternative form of mathematics.
We do not assume any prior knowledge of quantum mechanics. However, a solid understanding of basic linear algebra (finite-dimensional vector spaces, matrices, eigenvectors and eigenvalues, linear maps etc.) is required as a pre-requisite. The course notes and the slides contain an overview of this material, so we advise students with a limited background in linear algebra to consult the course notes before the course starts.
To do the practicals, you will need to have a basic working knowledge of the Python programming language. If you've never used Python before, I suggest working through the first 4 sections of: https://docs.python.org/3/tutorial/.
[from CUP book page] The unique features of the quantum world are explained in this book through the language of diagrams, setting out an innovative visual method for presenting complex theories. Requiring only basic mathematical literacy, this book employs a unique formalism that builds an intuitive understanding of quantum features while eliminating the need for complex calculations. This entirely diagrammatic presentation of quantum theory represents the culmination of ten years of research, uniting classical techniques in linear algebra and Hilbert spaces with cutting-edge developments in quantum computation and foundations. Written in an entertaining and user-friendly style and including more than one hundred exercises, this book is an ideal first course in quantum theory, foundations, and computation for students from undergraduate to Ph.D. level, as well as an opportunity for researchers from a broad range of fields, from physics to biology, linguistics, and cognitive science, to discover a new set of tools for studying processes and interaction.
Summary / keywords: diagram, parallel and sequential composition of diagrams, string diagram, transpose, adjoints and conjugate, umitarity and inner-product, Bell state, teleportation, no universal separability, no universal cloning, matrix calcu;us, Hilbert space, completeness for string diagrams, logic gate, Bell-basis, doubling, eliminating global phases, discarding, causality, Stinespirng dilation, no-signalling, Krauss decomposition and mixing, ONB measurements, entaglement swapping, gate-teleportation, Naimark dilation, von Neumann measurements, POVM measurements, tomography, classical wires, dense coding, classical-quantum map, copy, delete, measure, encode, classical, quantum and bastard spiders, phase spiders, phase group, complementarity, QKD, strong complementarity, classical subgroup, ZX-calculus, its universality and completeness for stabiliser QM, quantum non-locality, Spekkens' toy theory, circuit model of quantum computing, quantum algorithms (DJ, search, HS), MBQC, resource theories, purity theory, LOCC- and SLOCC-entanglement
The textbook for this course is Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning.
It should be available in many libraries throughout the university and most online bookstores. The ebook PDF is also available for free to all members of Oxford University through a deal between the Bodleian Library and Cambridge University Press:
If the link above doesn't work, go to http://solo.bodleian.ox.ac.uk, search for the book title, and click on the "Online Access" version. Under the section "View Online", click the link to Cambridge Core to view the book on CUP's website.
Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.