THEMATIC PROGRAMS

March 29, 2024

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