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

The final group project accounts for 70% of the total grade.

This project will be completed in groups of 2-4 students. It will reflect the understanding of the students of the material covered in the lecture. The components of this project are the following:

- Identify a problem that can be posed as an Integer Optimization Problem or a Machine Learning Problem. Discuss the importance of this problem.
- Summarize the literature surrounding the problem. How is it solved at this point? Which computational methods are employed to tackle these problems?
- Find or generate a family of instances or input data of the problem to test solution algorithms on it (consistent with literature or industrial application).
- Attempt to reproduce the state-of-the-art approach to address the problem using classical computing. Identify the sources of complexity while solving this problem that might benefit from quantum/quantum-inspired/unconventional (physics-inspired) methods.
- Map the problem and solve it using physics-inspired methods:
- If you choose an Integer Optimization Problem:
- Model the problem as a Quadratic Unconstrained Binary Optimization (QUBO). Verify that the reformulation of the problem is valid in the sense that it represents the original problem.
- Solve it using simulated annealing as a benchmark.

- If you choose a Machine Learning Problem:
- Formulate a machine learning problem that is amenable to solution by a noisy intermediate-scale quantum (NISQ) device such as those available in the computing cloud (e.g., Amazon Could Services).
- Solve it using neural networks and classical computing methods (consider solving it without using GPUs as a baseline for the comparison) as a benchmark

- If you choose an Integer Optimization Problem:
- Perform simulations of NISQ devices and/or analytical resource estimates for this problem (so that we know what would be needed at scale when more mature NISQ devices become available in the future).
- If you choose an Integer Optimization Problem:
- Tackle the resulting QUBO using non-conventional methods, e.g., Quantum Annealing, QAOA, simulated annealing in GPUs/TPUs, etc. Compare at least two different methods.

- If you choose a Machine Learning Problem:
- Solve the learning task using hardware accelerators, e.g., GPUs or TPUs. Perform simulations or runs in limited-sized instances in NISQ devices.

- If you choose an Integer Optimization Problem:
- Provide a mid-term report with initial results and plan (15/70) with a short presentation (10/70).
- Write a report outlining strengths-limitations-functional requirements-opportunities of the different approaches used, highlighting the knowledge obtained while developing the project supported by computational results (25/70).
- Make a presentation to the class reporting the findings of the project (20/70).

There will be an ungraded submission at the beginning of week 3 with the proposed problem to be solved (we can guide you if you are out of ideas). There is a presentation at the middle of the semester (when the mid-term report is submitted), allowing students to present their partial progress in front of the class and receive feedback.

Much of the second half of the course is devoted to the final project completion, with the office hours aimed at each final project group.

One of the essential learning objectives of this course is completing the project in a group (with a considerable amount of work distributed among several individuals). The groups are self-created, although we will support you in finding a group if you want to join one. Individual projects are only allowed under exceptional cases.