CS101-3 Quantum Algorithms and Programming

9 units (3-0-6), P/F. Spring term 2020. Prerequisites: CS 1, CS 21, CS 38, Ma 1b., or equivalent. Lectures: Mon & Wed. Instructor: Alexandru Gheorghiu (andrugh@caltech.edu). TA: Alexander Poremba (aporemba@caltech.edu). Course website: Moodle Outline This course will teach the fundamentals of quantum algorithms through a combination of theory and programming. The goal will be to understand how quantum algorithms work, what advantages they offer over non-quantum (classical) algorithms, as well as the limitations of efficient quantum computation. On the theory side, this will be done using tools from algorithms analysis and computational complexity theory. On the programming side, we will be implementing a number of algorithms in Microsoft's quantum programming language Q#. The course will cover standard quantum algorithms, such as those of Deutsch-Jozsa, Simon, Shor and quantum simulation, as well as some of the more modern ones, such as algorithms for near-term devices and quantum machine learning. The main programming languages used in the course will be Python and Q#. Students should have basic familiarity with Python. No prior knowledge of Q# is required, though students will be expected to learn it throughout the course. The course will introduce the basics of quantum computation and so no prior knowledge of the subject is required.

Image courtesy of Vivian Uhlir.

Requirements: Students taking this course should be familiar with the basics of linear algebra, programming, algorithms and data structures. While the course will also serve as an introduction to quantum computation, students that have completed a quantum computing course (such as Ph 219), and wish to deepen their understanding of quantum algorithms are encouraged to take this course.

Resources

The main resources for the course will be the lectures themselves and the lecture notes. In addition, these other resources will be useful:

• Quantum Computation and Quantum Information, by Nielsen and Chuang.
• Ph 219: Quantum Computing.
• Quantum Katas (the Q# language tutorial).

See also:

• APh 250/ME 201: Physics on near-term quantum computers.
• Computational Complexity: A Modern Approach, by Arora and Barak.
• Qiskit (IBM's quantum programming language).

Grading

Students will be evaluated based on 4 homework assignments and one group project. The homeworks will consist of 3 programming assignments and one written assignment. The programming assignments will involve solving various problems in either Python or Q# (2 assignments in Q# and one in Python). These problems will be very similar in style to the Quantum Katas from the Q# website . The written assignment will be a problem set and will involve proofs pertaining to complexity theory and algorithms analysis. Finally, the group project will be a team-based assignment in which students will be asked to do a quantum algorithms project in their programming language of choice and write a short report (around 10 pages) on the project and the obtained results. Suggested ideas for projects will be posted in the second half of the course. The exact breakdown as well as the time period for each assignment are as follows:

• 15% Homework 1. Programming assignment in Python. Issued beginning of Week 1, due end of Week 2.
• 15% Homework 2. Programming assignment in Q#. Issued beginning of Week 3, due end of Week 4.
• 15% Homework 3. Written assignment. Issued beginning of Week 5, due end of Week 5.
• 15% Homework 4. Programming assignment in Q#. Issued beginning of Week 6, due end of Week 7.
• 40% Group project. Programming in language of choice + written report about the project and a presentation. Project suggestions listed beginning of Week 6. Code and report due end of Week 9.

As the course is P/F, students are required to complete at least 50% in order to pass.

Collaboration policy

The collaboration policy is the same as for CS/Ph-120, see collaboration table and ask the instructor in case of confusion.

Lecture schedule

• Week 1 (HW 1 issued)
  • Lecture 1 (April 6)
    • Introduction (randomness as a resource for computation; classical probabilities versus "negative probabilities"; interference as a resource for computation)
    • Language used: Python
    • Notes. Code.
  • Lecture 2 (April 8)
    • Solving hard problems using interference 1 (Bernstein-Vazirani as the main example; decision versus search problems)
    • Language used: Python
    • Notes. Code.
• Week 2 (HW 1 due end of the week)
  • Lecture 3 (April 13)
    • Solving hard problems using interference 2 (a linear algebra perspective)
    • No programming.
    • Notes.
  • Lecture 4 (April 15)
    • Solving hard problems using interference 3 (Simon's problem)
    • Language used: Python
    • Notes. Code.
• Week 3 (HW 2 issued)
  • Lecture 5 (April 20)
    • Quantum computing basics (states, gates, measurement)
    • Language used: Q#
    • Notes. Code.
  • Lecture 6 (April 22)
    • Quantum algorithms 1 (Deutsch-Jozsa, Bernstein-Vazirani and Simon algorithms in the quantum setting)
    • Language used: Q#
    • Notes. Code.
• Week 4 (HW 2 due end of the week)
  • Lecture 7 (April 27)
    • Quantum algorithms 2 (Quantum Fourier Transform, order finding and Shor's algorithm)
    • Language used: Q#
    • Notes. Code.
  • Lecture 8 (April 29)
    • Complexity theory 1 (basic complexity classes: P, NP, EXP, BPP, BQP, PSPACE; their known and conjectured relations)
    • Language used: Python
    • Notes. Code.
• Week 5 (HW 3 issued and due end of the week)
  • Lecture 9 (May 4)
    • Complexity theory 2 (advanced classes PH, #P, PP, AWPP; Gap functions and interference computation through the complexity perspective)
    • No programming.
    • Notes.
  • Lecture 10 (May 6)
    • Quantum computational advantage (sampling problems; why we expect quantum sampling to be classically hard; random circuit sampling and the Google result)
    • Language used: Q# (and Qiskit)
    • Notes. Code.
• Week 6 (HW 4 issued; project ideas listed)
  • Lecture 11 (May 11)
    • Quantum simulation 1 (Hamiltonian formalism; time-dependent evolution; Trotter-Suzuki approach)
    • Language used: Q#
    • Notes. Code.
  • Lecture 12 (May 13)
    • Quantum simulation 2 (quantum phase estimation; finding eigenstates and eigenvalues)
    • Language used: Q#
    • Notes. Code.
• Week 7 (HW 4 due end of the week)
  • Lecture 13 (May 18)
    • Hybrid quantum-classical algorithms with applications (variational quantum eigensolver, quantum chemistry applications)
    • Guest lecturer: Alexander Poremba.
    • Language used: Pyquil.
    • Notes. Code.
  • Lecture 14 (May 20)
    • Machine learning and quantum systems (learning quantum states, predicting observables, random matrix theory)
    • Guest lecturer: Hsin-Yuan Huang (Robert).
    • Languages used: Cirq, Python, C++
    • Notes. Code 1, code 2.
• Week 8
  • Lecture 15 (May 25)
    • Quantum algorithms for linear algebra (block encoding; the Harrow-Hassidim-Lloyd algorithm via block encoding)
    • Language used: Q#
    • Notes. Code.
  • Lecture 16 (May 27)
    • The role of entanglement in quantum speedups (Bravyi, Gosset, Koenig result and followups; parity halving problem)
    • Language used: Q#
    • Notes. Code.
• Week 9 (projects due end of the week)
  • Lecture 17 (June 1)
    • Grover's algorithm (quantum search and its limitations, the need for structure in quantum speed-ups)
    • Language used: Q#
    • Notes. Code.
  • Lecture 18 (June 3)
    • Classically simulating quantum circuits (Schroedinger and Feynman simulation approaches; Clifford computations and the stabilizer formalism)
    • No programming.
    • Notes.