Lecturer	Bob Coecke
Degrees	Part C — Mathematics and Computer Science Schedule C — MSc in Advanced Computer Science MSc by Research MSc in Mathematics and Foundations of Computer Science
Term	Hilary Term 2009  (24 lectures)

Overview

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 hence promises to play an important similar 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 realizing 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 (very) basic quantum mechanics (including finite dimensional Hilbert spaces and the tensor product thereof), 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 Shor's factorization algorithm, quantum teleportation and quantum key exchange, and analyze the challenges these pose for computer science, mathematics etc. We also provide a more conceptual semantic analysis of some of the above. Other important issues such as quantum information theory (including mixed states) will also be covered (although not in great detail). We also discuss alternative computational paradigms and models for the circuit model, we argue the need for high-level methods, provide some recent results concerning graphical language and categorical semantics for quantum informatics and delineate the remaining scientific challenges for the future.

Learning outcomes

The 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 concerning are. This includes a structural understanding of some basic quantum mechanics, knowledge of important algorithms such as Shor's algorithm and important protocols such as quantum teleportation. He/she will also know where to find more details and will be able to access these. Hence this course also offers computer science and mathematics students a first stepping-stone for research in the field, with a particular focus on the newly developing field of quantum computer science semantics, to which Oxford University Computing Laboratory has provided pioneering contributions.

Prerequisites

We do not assume any prior knowledge of quantum mechanics. Some knowledge of basic linear algebraic notions such as vector spaces and matrices is however a pre-requisite. The course notes do comprise 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.

Synopsis

• 1. Historical and physical context�
• 1.1 The birth of quantum mechanics�
• 1.2 The status of quantum mechanics�
• 1.3 The birth of quantum informatics�
• 1.4 The status of quantum informatics�

• 2 Qubits vs. bits�
• 2.1 Acting on qubits�
• 2.2 Describing a qubit with complex numbers�
• 2.3 Describing two qubits�

• 3 von Neumanns pure state formalism�
• 3.1 Hilbert space�
• 3.2 Matrices�
• 3.3 Tensor structure�
• 3.4 Dirac notation�

• 4 Protocols from entanglement�
• 4.1 Bell-base and Bell-matrices�
• 4.2 Teleportation and entanglement swapping�

• 5 The structure of entanglement and graphical calculus�
• 5.1 Graphical calculus for quantum theory�
• 5.2 Map-state duality and compositionality�
• 5.3 The logic of bipartite entanglement�
• 5.4 Quantifying entanglement�
• 5.5 Trace�

• 6 Algorithms and gates�
• 6.1 Special gates�
• 6.2 The Deutch-Jozsa algorithm�
• 6.3 Grover's algorithm�
• 6.4 Shor's factoring algorithm�
• 6.4.1 Period finding�
• 6.4.2 Factoring and code-breaking�
• 6.5 Quantum key distribution�

• 7 Mixed states�

• 8 Quantum logic and Gleason's theorem�

• 9 Mixed operations�

• 10 Semantics for quantum computing�
• 10.1 Quantum computing with relations�
• 10.2 Quantum computing with categories�
• 10.3 Further reading�

Syllabus

Finite dimensional vector space, inner-product, complex numbers, linear adjoints, unitary maps, projectors, trace, tensor product of Hilbert spaces, Dirac notation, bit, qubit, entanglement, map-state duality, no-cloning, quantum circuits, quantum gates, Shor's algorithm, Grover's algorithm, quantum teleportation, quantum key-exchange, teleportation and measurement based quantum computing, decoherence, mixed states, quantum information, quantum logic, quantum categorical semantics.

Reading list

Lecture notes which cover the whole course and which provide detailed pointers to additional reading will be made available. Standard books on the subject that might be of use are:

• Gruska, J. (1999) Quantum Computing. McGraw-Hill.
• Nielsen, M. and Chuang, I. L. (2000) Quantum Computation and Quantum Information. Cambridge University Press.
• Kitaev, A. Yu., Shen, A. H. and Vyalyi, M. N. (2001) Classical and Quantum Computing. Graduate Studies in Mathematics 47, American Mathematical Society.

On-line available courses elsewhere which can be consulted are:

• By Braunstein: http://www.weizmann.ac.il/chemphys/schmuel/comp/comp.html
• By Pub http://www.theory.caltech.edu/people/preskill/ph229/
• By Preskil http://www.theory.caltech.edu/people/preskill/ph229/

A different angle which is also very much reflected in the course is available at:

• http://arxiv.org/abs/quant-ph/0510032
• http://arxiv.org/abs/quant-ph/0506132

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.