47-779 course syllabus - Fall 2020

QuIP - Quantum Integer Programming

Tuesdays and Thursdays 5:20p.m. - 7:10p.m. EST. Lectures on Zoom.

Prof. Sridhar Tayur (4216 Tepper Quad), Dr. Davide Venturelli (online), David Bernal (DH3116).

News

Our collaboration with USRA and Amazon Web Services was recently featured in this news release from the Tepper School of Businees at Carnegie Mellon Univerity. The article also mentions the motivation of creating this course, so enjoy the read!

Objectives

This course is primarily designed for graduate students (and advanced undergraduates) across CMU campuses interested in integer programming (with non-linear objective functions) and the potential of near-term quantum computing for solving combinatorial optimization problems. By the end of the semester, someone enrolled in this course should be able to:

This course is not going to focus on the following topics:

Students with backgrounds in operations research, industrial engineering, chemical engineering, electrical engineering, physics, computer science, or applied mathematics are strongly encouraged to consider taking this course. Enroll here.

Prerequisite classes and capabilities

Although this class has no explicit prerequisites we consider a list of recommended topics and skills that the student should feel comfortable with. An undergraduate-level understanding of probability, calculus, statistics, graph theory, algorithms, and linear algebra is assumed. Knowledge of linear and integer programming will be useful for this course. Programming skills are strongly recommended. Basic concepts in physics are recommended but lack of prior knowledge is not an issue as pertinent ones will be covered in the lectures. No particular knowledge in quantum mechanics or algebraic geometry is required.

Basic course structure

Weeks 1-2: Integer programming: classical methods, Grobner Basis. Test-sets.

Week 3: Graver Basis, Ising model.

Week 4: Quadratic Unconstrained Binary Optimization (QUBO), Graver Augmented Multiseed algorithm (GAMA).

Week 5: Quantum methods for solving Ising/QUBO: Adiabatic Quantum Computing (AQC), Quantum Approximate Optimization Algorithm (QAOA).

Week 6: Specialized hardware for solving Ising/QUBO.

Week 7: Applications, Compiling and Final Project presentations.

Grading

Weekly homework and quizzes (50%), Final Project (50%).

Highlights

The specific skills that students will gain that will make them “quantum ready” for industry or further academic research in this course are:

A. Classical

  1. Given a practical problem (from supply chain or physics or anything else), formulate it as a non-linear integer program. We will provide a few practical problems, but we encourage you to suggest one that you are already working on or are interested in.
  2. Solve such formulations via classical solvers.

B. Quantum

  1. Reformulate the problem to be “quantum ready” by making it in the form of a QUBO.
  2. Solve the QUBO “brute force” through D-Wave or IBM (via QAOA).

C. Hybrid Quantum-Classical

  1. Reformulate the problem again in the form suitable for GAMA.
  2. Solve GAMA compatible formulation via D-Wave and/or via QAOA.

USRA Collaboration

Amazon Braket Collaboration

Full Syllabus and Lecture Notes

The complete syllabus can be downloaded here. Thanks to the students at IIT-Madras, we have lecture notes for all the classes transcribed and freely available in arXiv.