Quantum Processes and Computation: 2020-2021
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 live on MS Teams here, every Monday, Tuesday, and Friday 11:00-12:00 UK time (full timetable here). Recordings will appear on Teams shortly after each lecture.
- Discussion (annoucements, offline Q&A, research questions, etc) on chat.cs:
- Everything else (problem sheets, schedule of material, etc) is here on the course website
The course consists of:
- 24 lectures (see Lectures below)
- 4 classes (weeks 3, 5, 7, 8). For all groups, problem sheets are due on Wednesday of the previous week:
- Assignment 1 due Wednesday 21 Oct @ 17:00
- Assignment 2 due Wednesday 4 Nov @ 17:00
- Assignment 3 due Wednesday 18 Nov @ 17:00
- Assignment 4 due Wednesday 25 Nov @ 17:00
- a graded practical assignment (10% of final grade), based on the PyZX tool
- A graded miniproject (90% of final grade). This will have a similar format to the problem sheets, but questions will be 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.
- Lecture 1, Oct 12: Introduction to diagrammatic reasoning (slides)
- Lecture 2, Oct 13: Circuit diagrams
- Lecture 3, Oct 16: Special processes
- Lecture 4, Oct 19: (Non-)separability and string diagrams
- Lecture 5, Oct 20: Transpose, adjoint, and conjugate processes
- Lecture 6, Oct 23: Quantum-like features from string diagrams
- Lecture 7, Oct 26: Bases, sums, and Hilbert spaces
- Lecture 8, Oct 27: From linear maps to quantum maps
- Lecture 9, Oct 30: Pure quantum processes
- Guest Lecture, Nov 2: CQM in Industry (guest lecture by Bob Coecke)
- Lecture 10, Nov 4 @ 9:00: Discarding and causality
- Lecture 11, Nov 6: Non-determinism and measurement
- Lecture 12, Nov 9: Classical/quantum interaction
- Lecture 13, Nov 10: Classical data as wires
- Lecture 14, Nov 13: Spiders!!!
- Lecture 15, Nov 16: Classical, quantum, and bastard spiders
- Lecture 16, Nov 17: Phases and complementarity
- Lecture 17, Nov 20: Consequences of complementarity
- Lecture 18, Nov 23: Strong complementarity
- Lecture 19, Nov 24: The ZX-calculus, universality and completeness
- Lecture 20, Nov 27: Quantum computation and the circuit model
- Lecture 21, Nov 30: Quantum algorithms 1: DJ and search
- Lecture 22, Dec 1: Quantum algorithms 2: the hidden subgroup problem
- Lecture 23, Dec 4: Quantum non-locality, Spekkens' toy theory and GHZ/Mermin
The practical for this course will be in 2 parts:
- Part 1 is unmarked. It is intended to be a tutorial for the PyZX library, and you are free to discuss it with your fellow students, your teacher, on Element/Teams etc. and to work in groups. I only ask that you not spoil the problems for other students by sharing full solutions en masse.
- Part 2 will be assessed as part of your miniproject. You MAY NOT discuss these problems with other students or your teacher until after the hand-in date.
Click the links above to download Part 1 and Part 2 (note: you may need to right click the link and click "Save As").
The practicals are given as Jupyter notebooks. There are (at least) two ways to complete this practical, depending on whether you want to install some software on your own computer or just do everything in a browser.
- Local option: install Python 3, Jupyter, and the required libraries (
qiskit) on your computer. Anaconda is a popular way to install everything at once. It is available on Windows, Mac, and Linux. For Linux, it may be easier to use your system's package manager. Once you have Python 3 and Jupyter set up,
qiskitcan be installed using pip, possibly directly from the Jupyter notebook via the
%pipcommand. Note you will not need
qiskituntil Part 2.
- Cloud option: create a free account on the IBM Quantum Experience and sign in with your IBMid. Click the icon for "Quantum Lab" in the sidebar, and click "Import" to upload a Jupyter notebook into cloud storage. Click on the notebook to edit it online. Once your notebook is finished, you can download it again by clicking
File > Download As > Notebook. I suggest you do this regularly to avoid accidentally losing work.
I've tested both of these options, and the both seem to work pretty well. You may have your own preferences (e.g. Google Colab might work, but I haven't tried it). However, to complete Part 2, you will still need to set up a free account on the IBM Quantum Experience, even if you went with the Local option. This is because you will need an IBMid to set up the IBM Quantum Provider, which will allow cloud access to IBM's public quantum computers. This is a bit tricky to get working, so I suggest doing it in advance. If you use the Cloud option via IBM, this extra bit of setup is not necessary.
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.