THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2017/2018

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Categories and Quantum Informatics (INFR11128)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 11 (Year 5 Undergraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryCategory 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-requisitesNone
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:
  1. Illustrate the idea behind and breadth of categorical semantics;
  2. Apply and prove basic results about monoidal categories;
  3. Fluently manipulate the graphical calculus for compact categories;
  4. Model quantum protocols categorically and prove their correctness graphically;
  5. 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.
KeywordsCategory Theory,Quantum Computing,Semantics
Contacts
Course organiserDr Christiaan Heunen
Tel: (0131 6)50 2865
Email: Chris.Heunen@ed.ac.uk
Course secretaryMr Gregor Hall
Tel: (0131 6)50 5194
Email: gregor.hall@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information