CS419 Quantum Computing

CS419 15 CATS (7.5 ECTS) Term 2

Availability

Option - MEng CS and DM, MSc CS

CS130 + CS131: Mathematics for Computer Scientists 1 + 2, or

CS136 + CS137 Discrete Mathematics and its Applications 1 + 2, or

MA106 Linear Algebra + ST111 Probability A

Understand the quantum computing paradigm: Have an overview of a range of project management techniques. Understand how failure to correctly manage a project can lead to failure. Understand how project management techniques provide quantifiable metrics for project progress.
Understand the power and limitation of quantum computers: Understand the underlying power of quantum mechanics for computation. Identify problems for which a quantum speedup is possible. Understand the fundamental limitations of quantum algorithms.
State the four postulates of quantum mechanics and their application to computation: Design and analyse quantum algorithms. Grasp the notions of quantum states, unitary evolution, measurements, and composite systems. Restate the postulates in terms of density matrices.
Analyse fundamental quantum algorithms: Shor's algorithm. Grover's search. The Berstein-Vazirani algorithm. Simon's problem. The Deutsch-Jozsa paradigm.
Understand the principles of quantum information and quantum communication: Understand quantum teleportation and its limits. Describe the framework of quantum error-correcting codes. Discuss Everett's many worlds interpretation.
Understand the implications of quantum computing on cryptography and security: Understand the foundations of post-quantum cryptography. Hack the RSA cryptosystem via a quantum computer. Use quantum mechanics to obtain a monetary scheme.

Week 1: Quantum computing - motivation, foundations and prominent applications.

Week 2: Review of linear algebra in the context of quantum information, Dirac's bracket notation, limitation of classical algorithms.

Week 3: The four postulates of quantum mechanics, qubits, quantum gates and circuits.

Week 4: Basic quantum algorithms I - Deutsch's algorithm, analysing quantum algorithms, and implementing quantum circuits via QISKIT.

Week 5: Basic quantum algorithms II - Simon's problem and the Bernstein-Vazirani algorithm.

Week 6: Grover's quantum search algorithm, the BBBV Theorem, and applications of Grover's algorithm.

Week 7: RSA, and Shor's integer factorisation algorithm.

Week 8: Introduction to quantum cryptography (post-quantum security, quantum key distribution).

Week 9: Introduction to quantum information (superdense coding, no-cloning theorem, quantum teleportation).

Week 10: Applications (quantum money, the Elitzur-Vaidman bomb).

Nielsen, Michael A.; Chuang, Isaac L. (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.

Three-hour examination (70%), Assessed work (30%)

30 hours of lectures and 10 hours of seminars.