COMPSCI 692QA: Quantum and AI

Website at lab.krastanov.org/grad-quantumai.

Signup page for office hours TBA.

The intersection of quantum information science and machine learning has evolved from a field of heuristic exploration into a rigorous discipline of mathematical foundations. This seminar explores the fundamental limits of information processing where the statistical principles of learning theory meet the computational capabilities of quantum mechanics. As we transition from classical to quantum-enhanced sensing and computation, the traditional frameworks of PAC (Probably Approximately Correct) learnability and VC dimension are being redefined to account for uniquely quantum phenomena such as state collapse, non-cloning, and entanglement.

Understanding these boundaries is essential for identifying where quantum resources provide a provable advantage over classical learners. Recent theoretical breakthroughs—ranging from exponential separations in sample complexity for learning physical systems to the establishment of query complexity bounds for quantum channels—provide a roadmap for what is physically learnable and what remains computationally hard. By focusing on mathematically rigorous results, this seminar addresses the core questions of the field: how many copies of a quantum state are required to predict its properties, when can a quantum algorithm outpace any classical counterpart in extracting patterns from data, and what are the inescapable no-go theorems that define the frontier of the quantum information era?

The revolutionary applications of AI&ML to Physics, Chemistry, Pharma, and Material Science are the tangible outcomes of such work. Moreover, AI&ML and inching closer and closer to solving problems we thought only quantum computers can solve efficiently – if such a breaktrough is achieved it will be paradigm shattering in both CS Theory and in many engineering and life-science disciplines.

The first one or two sessions will include a primer on Quantum Information Science led by the instructor.

Students will be expected to fully participate in classroom discussions. Class time will be focused on:

• Short presentations by students

• QnA with students, led by the presenting student and moderated by instructors

• Each presenting student would be expected to discuss their presentation a week in advance with the instructors, in order to polish their presentation and get help on topics of interest. It is the student's responsibility to sign up for office hours!!!

Each paper presentation will be an hour, maybe multiple hours over consecutive sessions, with many interruptions for clarifying questions. The presenter's goal should be to teach the audience about the concepts presented in the paper, why are they valuable, how they might be applied, etc. The instructors will also try to help with the thornier questions. Many questions will probably remain unanswered and will be left as follow-ups for future sessions.

Prerequisites

Students will need strong understanding of linear algebra, probability theory, and statistics. A self-contained intro to quantum information science will be provided in the first few sessions.

Required Texts and Materials

A list of general Quantum Information textbooks is made available and a list of suggested papers will be provided in advance. The first 5 chapters of the Aaronson lecture notes would be particularly useful.

Topics

We will aim to cover the following topics (with links to suggested papers):

• Surveys of the recent results in the field

• Classical AI for problems in Physics and Chemistry

• Quantum Computing techniques related to AI

• Tomography (learning of states of physical systems)

Assessments

The grade will be weighted as:

• 80% from oral presentations

• 20% from participation in discussions (you actually have to come to class)