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
