## Courses of interest being held at the University of Waterloo

CO681/CS767/Phys767

Quantum Information Processing

Instructor: Richard Cleve

---------------------------------------------------------------------

Evaluation:

3 Homeworks-- 2 Tests.-- Project + write-up (3 page) + presentation.

------------------------------------------------------------------

Detailed description

A ?? tag designates an optional topic

INTRODUCTORY MATERIAL

Basics of Computational complexity

- Church-Turing thesis

- Circuit model

- Basic complexity classes: P, NP, BPP, PSPACE, EXP

- NP-completeness

- Proof systems and MA vs. QMA ??

Basic framework of Q systems

- postulates of QM

- qubits, unitary ops, measurements

- quantum circuits

- superdense coding

- teleportation

- no-cloning

- non-locality

- density matrices, ensembles, partial trace

- Schmidt decomposition

- purification of a density matrix

- CPTP maps, Kraus representation, POVMs

Simple quantum algs

- black-box framework

- Deutsch's algorithm

- Deutsch-Jozsa

- Bernstein-Vazirani

- Simon algorithm & classical lower bound

Simple quantum and classical simulations

- universality of simple sets of gates

- approximate universality (statement of Solovay-Kitaev,without proof)

- simulating classical circuits with quantum circuits

- simulating quantum circuits in classical exponential-time

- simulating quantum circuits in classical polynomial-space ??

---------------------------------------------------------------------

ALGORITHMS

Shor's factoring algorithm

- QFT

- some number theory background, reduction of factoring to order-finding
(basic level without proofs regarding order-finding and continued fractions)

- above but with details (e.g., proofs)??

- complete analysis of the algorithm (one among the various approaches
possible)

Grover's search algorithm

- classical case (costs order N)

- quantum version

- complete analysis of the algorithm (among one the various approaches
possible), at least in the case of a known number of marked items

- some discussion of case with unknown number of marked items

- application to combinatorial search problems

- optimality of algorithm (by, say, hybrid method)

---------------------------------------------------------------------

IMPLEMENTATIONS

Computing devices

- general principles (e.g. DiVincenzo criteria) and overview

- examples such as ion traps, quantum optics, NMR

---------------------------------------------------------------------

ERROR CORRECTION AND FAULT TOLERANCE

Basic overview of QECCs

- basics of classical ECCs

- Shor's 9-qubit code

- CSS codes, discussion of asymptotics of QECCs

Fault-tolerance

- very general discussion of fault-tolerance, and the threshold theorem
(need not be complete)

---------------------------------------------------------------------

CRYPTOGRAPHY

Quantum key distribution

- BB84, general sketch of protocol and intuition behind it's security,
including discussion of what has to be addressed in the actual security
proof

- Lo and Chau protocol and proof of security

---------------------------------------------------------------------

OTHER TOPICS

[if time permits] Communication complexity, Information theory, Simulation
of physical systems.

---------------------------------------------------------------------

back to top