Undergraduate Course: Categories and Quantum Informatics (INFR11128)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 11 (Year 5 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 10 |
ECTS Credits | 5 |
| Summary | Category theory is a powerful mathematical tool in logic and informatics, that has influenced the design of modern (functional and quantum) programming languages. It replaces concrete and often cumbersome set-theoretic encodings with more elegant abstractions that reveal the intrinsic structure underlying them. Category theory shines at easing complicated bookkeeping. In particular, a powerful graphical calculus lets us draw pictures instead of writing algebraic expressions. This technique is visually extremely insightful, yet completely rigorous. For example, correctness of protocols often comes down to whether a picture is connected or disconnected, whether there is information flow from one end to another. This course develops the basic ideas of category theory by applying them to quantum informatics. It investigates the conceptual reasons why quantum protocols and quantum computing work, rather than their algorithmic and complexity-theoretic aspects. |
| Course description |
The course begins by introducing the idea behind category theory and the breadth of its scope. Why would it be a good idea to abstract away from specific hard-coded set-theoretic structures, and have compositional denotational semantics, in general? Illustrations from functional programming and categorical methods in logic are given.
We then focus more specifically on monoidal categories. Via lectures and self-study reading, the course teaches students the basics of dual objects in monoidal categories. Specific attention is paid to the graphical calculus, which makes the topic visually apparent. Via weekly exercise sheets, and their review incorporated into the contact hours, the student learns to graphically manipulate algebraic objects such as monoids and Frobenius structures. He/she will understand that this still allows perfectly rigorous proofs of correctness, and be able to see the information flow of a protocol that is often hidden behind superfluous details.
Throughout the course, the abstract material is linked to quantum informatics. We will categorically model notions typically thought to belong to quantum theory, such as entanglement, no-cloning, teleportation, and complementarity. But it will turn out some of these notions also make perfect sense in other settings. For example, the very same categorical description of quantum teleportation also describes classical encryption with a one-time pad. We identify characteristics of classical and quantum information, aiming to equip students to choose the right tools and techniques for future problems they may encounter.
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
Students MUST have passed:
Introduction to Linear Algebra (MATH08057) OR
Informatics Research Review (INFR11034) OR
Informatics Research Review (INFR11136)
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | Introduction to Quantum Computing (INFR11099) is complementary to this course. Although the two are independent, it is suggested that students wishing to get a comprehensive overview take both.
This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser. Basic knowledge of linear algebra, vector spaces, and complex numbers will be assumed, as well as experience with mathematical abstraction. Undergraduates must have passed Introduction to Linear
Algebra (MATH08057). Postgraduate or visiting students must have taken similar courses providing this background.
No programming experience is required. |
Information for Visiting Students
| Pre-requisites | None |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2017/18, Available to all students (SV1)
|
Quota: None |
| Course Start |
Semester 2 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Lecture Hours 15,
Seminar/Tutorial Hours 5,
Feedback/Feedforward Hours 1,
Summative Assessment Hours 10,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
67 )
|
| Assessment (Further Info) |
Written Exam
70 %,
Coursework
30 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
Written exam and one piece of coursework. The written exam will mostly test learning objectives 3, 4, and 5. The coursework will be similar to weekly exercise sheets, is due shortly after the course is halfway, and will mostly test learning objectives 1, 2, and 3.
Written Examination: 70%
Practical Examination: 0%
Coursework: 30% |
| Feedback |
Part of every second lecture will be run as a tutorial, reviewing exercise sheets. This gives students opportunity to compare answers with each other, and will also include students working through exercises on the board, thus giving them feedback. The coursework will be marked within two weeks. Part of a the lecture after that will be dedicated to discussions and matters arising.
As is standard in Informatics, individual feedback will not be provided on the written exam. The lecturer will produce brief notes on what was done well or badly, common mistakes, and points of note. |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S2 (April/May) | | 2:00 | |
Learning Outcomes
On completion of this course, the student will be able to:
- Illustrate the idea behind and breadth of categorical semantics;
- Apply and prove basic results about monoidal categories;
- Fluently manipulate the graphical calculus for compact categories;
- Model quantum protocols categorically and prove their correctness graphically;
- Differentiate between categories modelling classical and quantum informatics.
|
Reading List
| Categories for Quantum Theory: An Introduction¿ by C. Heunen and J. Vicary, to be published by Oxford University Press. |
Additional Information
| Graduate Attributes and Skills |
- Obtain, organise, and use factual, theoretical, and/or hypothetical information in problem solving.
- Make generalisations and predictions.
- Present and evaluate arguments, information and ideas routine to the subject.
- Undertake critical analysis, evaluation and synthesis of ideas and concepts within the common understandings of the subject. |
| Keywords | Category Theory,Quantum Computing,Semantics |
Contacts
| Course organiser | Dr Christiaan Heunen
Tel: (0131 6)50 2865
Email: |
Course secretary | Mr Gregor Hall
Tel: (0131 6)50 5194
Email: |
|
|
University Homepage