Quantum Information and Computation

CS469 Quantum Information and Computation (Spring 2025)

Prerequisites: CS344, MA339 (linear algebra)
Instructor: Christino Tamon
Lectures: TR 3:00-4:45am SC356
Office hours: TR 11-12,2-3, Wed 1-3 (SC373)

Text: (recommended but not required):
M. Nielsen and I. Chuang, Quantum Information and Quantum Computation, Cambridge University Press, 2000.

Other:
T. Wong, Introduction to Classical and Quantum Computing, Rooted Grove, 2022. link.
D. Mermin, Quantum Computer Science, Cambridge University Press, 2007. link.
A. Shen, A. Kitaev, M. Vyalyi, Classical and Quantum Computation, AMS Press, 2002. link.

Syllabus

This course studies information and computation based on quantum mechanical laws. The first part of the course will cover the relevant background in quantum information theory. A brief discussion of several universal quantum computational models will be given. The second part will cover algorithmic techniques important for developing quantum algorithms. Topics to be covered include amplitude amplification, quantum walks, phase estimation, hidden subgroup problems, and quantum protocols. Background in physics would be helpful but is not required. Background in linear algebra (and basic complex numbers) will be essential.

Objectives and outcomes

The objective of this course is to learn the fundamentals of quantum information and quantum computation, to gain a solid understanding of basic quantum algorithms and techniques, and to understand limitations of the quantum computational model.

The specific outcomes are basic knowledge of the following:

Foundations of quantum information and quantum computation.
Techniques for designing quantum algorithms.

Requirements and Policies

Although attendance is not mandatory, students are responsible for all course materials covered in lectures and any quizzes given during class periods. Students that need to make up missing course work must provide the required Clarkson official exempt form. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

Grading Scheme

Homeworks and Quizzes (40%), Tests (50%), Project (10%).

Schedule (tentative)

Tuesday	Thursday
Jan 7	Jan 9 Classical vs quantum information. Outline: quantum protocols, quantum algorithms, quantum codes.
Jan 14 Bits/qubits, classical/quantum gates, and measurement. Universal gates. Reversible computation. Basic quantum gates: Pauli gates, Hadamard, CNOT, Toffoli. Reading: Kitaev.	Jan 16 No class (travel). Makeup class: Wed 01/22.
Jan 21 Entanglement: Bell circuit. Quantum teleportation. Related topic: gate teleportation.	Jan 23 Quantum key distribution (BB84). No Cloning Theorem.
Jan 28 Deutsch-Josza problem. Preemptive makeup class: Wed 01/29.	Jan 30 Fourier analysis on the Boolean cube.
Feb 4 Bernstein-Vazirani. Simon's problem.	Feb 6 Shor's algorithm. Number Theory. Fourier Transform.
Feb 11 Quantum Fourier transform: quantum circuit, rotations.	Feb 13 Quantum phase estimation. Reading: Kitaev.
Feb 18	Feb 20 Short break.
Feb 25 No class (travel). Makeup class: Wed 01/29.	Feb 27 No class (travel). Makeup class: Wed 02/05.
Mar 4 Grover search Analog (quantum walk version). Reading: Farhi-Gutmann.	Mar 6 Amplitude Amplification. Reading: Hoyer.
Mar 11	Mar 13
Mar 18 Spring Break	Mar 20 Spring Break
Mar 25 Analog Grover search.	Mar 27 Quantum error correction. Obstacles: no-cloning, destructive measurement, continuum of errors.
Apr 1 Quantum error correction. Repetition code. Partial measurements. Pauli errors.	Apr 3 Shor's 9-qubit code.
Apr 8 Stabilizer formalism. 5-qubit code.	Apr 10 Nonlocal games. GHZ and CHSH game.
Apr 15 HHL Sources: Aaronson. Ambainis.	Apr 17 HHL Sources: Childs et al. Gilyen et al.
Apr 22	Apr 24

Assignments

Please check our Moodle course page.

Useful software for formatting quantum circuits:

TeX: quantikz2 by Alastair Kay.
Qasm: qasm2circ by Isaac Chuang.

Project

Choose a project topic of interest; you may work in groups of up to three or four.
Indicate your topic and group by early April.
Submit a final report (hardcopy, 5-10 pages) that contains at minimum the following separate sections:
- Abstract (What/Why/How).
  Provide this on a separate page.
- Background information and literature: what has been done, what is the state-of-the-art ideas or methods in the area.
  Include proper and complete bibliography (at the end of the document) for your sources; see examples of some journal papers listed below.
- Identify at least an idea that can be done but has not been addressed in the literature.
  This can be either an improvement on implementation or on a mathematical idea.
Prepare a 5-10 minute talk to be delivered at the end of the semester (details TBA).
Submit by email your talk slides (PDF) before your talk.
Submit any other items, if any, related to your project (code, etc) by email.

Random topics

Cluster state: paper, survey.
Embezzlement of entanglement: van Dan-Hayden.
Fractional time: Sheridan-Maslov-Mosca.
Minimum finding: Durr-Hoyer.
All models (great and small): quantum walk. measurement-based. adiabatic. topological.
Miscellaneous: time travel, black holes (quanta, bellairs, blog).

Miscellany

Software: Qiskit. Liquid. Cirq. Quipper.
Resources: Watrous.
Notes: Motanaro, deWolf, Ozols, Ambainis-Regev.
Tools: Quirk. O'Reilly.
Tutorial: ASPLOS'19.

Quantum walk simulator (web-based).