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 settheoretic 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 complexitytheoretic 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 hardcoded settheoretic 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 selfstudy 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, nocloning, 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 onetime 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)
Prerequisites 
Students MUST have passed:
Introduction to Linear Algebra (MATH08057) OR
Informatics Research Review (INFR11034) OR
Informatics Research Review (INFR11136)

Corequisites  
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
Prerequisites  None 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2016/17, 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: Chris.Heunen@ed.ac.uk 
Course secretary  Mr Gregor Hall
Tel: (0131 6)50 5194
Email: gregor.hall@ed.ac.uk 

