47-779 / 47-785 course syllabus - Fall 2021

QuIP & QML - Quantum Integer Programming and Quantum Machine Learning

Tuesdays and Thursdays 4:40 p.m. - 6:30 p.m. EST. Room 2701 Tepper Quad.

You can review our previous course on Quantum Integer Programming contents which are available here.

Lecturers: Prof. Sridhar Tayur (4216 Tepper Quad), Prof. Elias Towe (Roberts Engineering Hall 147), Dr. Davide Venturelli (online), and Dr. David Bernal (DH3116).

Teaching Assistant: Maximiliano Stock (4218A Tepper Quad).

News

Our collaboration with USRA and Amazon Web Services was recently featured in this news release from the Tepper School of Business at Carnegie Mellon Univerity. The article also mentions the motivation for 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:

• Identify the current status of quantum computing and its potential uses for integer programming
• Access and use quantum computing resources (such as DWave Quantum Annealers)
• Set up a given integer program to be solved with quantum computing
• Work in groups collaboratively on a state-of-the-art project regarding applications of quantum computing and integer programming

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

• Computational complexity theory
• Quantum Information Theory
• Analysis of speedup using differential geometry, algebraic topology.

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 helpful in 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: Review of Linear algebra for Quantum Mechanics and Quantum Machine Learning.

Week 2: Mathematical Programming basics (classical methods).

Week 3-4: Basic Classical Machine Learning, Ising, QUBO.

Week 4: Ising, QUBO (GAMA).

Week 4: Graver Augmented Multiseed algorithm (GAMA).

Week 5: Axioms of Quantum Mechanics, Quantum Measurements, Qubit Gate model of quantum computing.

Week 6: Quantum methods for solving Ising/QUBO: Adiabatic Quantum Computing (AQC), Quantum Alternating (Approximate) Optimization Ansatz (Algorithm) (QAOA). Midterm Project Presentations.

Week 7: Break

Week 8: Midterm Project Presentations.

Week 9: Specialized hardware for solving Ising/QUBO. Quantum Algorithms for future quantum processors; HHL; Grover’s search algorithm.

Week 10: Guest speakers. Term Project Noise in quantum computing and quantum error correction.

WeekS 11: Recent advances and other topics.

WeekS 11-12-13: Term Project

Week 14: Term Project Presentations.

Grading

Weekly homework and quizzes (30%), Final Project (70%).

• There will be 4 quizzes to evaluate the concepts covered in class—each worth 10 points. Only the best 3 quizzes will count toward the 30%.
• The final project will be submitted in groups. It will require the implementation and solution of an integer programming instance using quantum computing resources. This final project deliverable will be a report and a presentation.

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, physics, to 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

• Access to D-Wave systems might be available via written proposals to the University Space Research Association (USRA). See RIACS website for terms and conditions. The course will discuss proposal preparation.
• Students of this course are encouraged to apply to the Feynman Academy Internship program that sponsors research projects at NASA Ames Research Center.

Amazon Braket Collaboration

• Access to D-Wave, IonQ and Rigetti is also made possible through Amazon Braket.

Full Syllabus

The complete syllabus can be downloaded here.