Columbia University, Computer Science Department

COMS 6998: Quantum Optimization

Location/Time: F 10:10pm - 12:00pm, 606 Martin Luther King Building

Contact: vk2599(at)columbia.edu

Course Description

This course investigates modern optimization methods at the intersection of classical algorithms, artificial intelligence, high-performance computing, and quantum computing. The course is organized around four themes: basics on optimization; AI for optimization, including data-driven optimization with graph neural networks and large language models; quantum optimization, including QUBO/HUBO modeling, Ising formulations, QAOA, annealing-inspired methods, and variational quantum algorithms; and integrated AI+Quantum solutions for end-to-end optimization pipelines. The course emphasizes both theory and implementation, including classical baselines and hybrid workflows using mathematical programming solvers such as CPLEX, GPU/MPI-based high-performance computing, and quantum-centric supercomputing workflows.

Prerequisites

The minimum requirements for the course are basic concepts of linear algebra, algorithms, probability, and programming. Knowledge and experience with optimization, machine learning, high-performance computing, or quantum computing will be helpful. The course will involve rigorous theoretical analyses, paper reading, and programming assignments involving classical solvers, AI tools, quantum software stacks, and HPC-style benchmarking.

Grading Policy

Grading is based on problem sets, project/presentation, and class participation. There will be no exams. The breakdown is as follows:

Homework & coding assignments - 70%: Four assignments including problem sets and programming exercises.
Paper reviews & class participation - 15%
Final project (research report + presentation) - 15%: There will be a project selection before Spring break, and a final presentation of the projects during the last week of the semester, along with a final report submission.

Assignments are to be submitted through Canvas, and should be individual work. You are allowed to discuss the problems with your classmates and to work collaboratively. The preferred format is to upload your work as a single PDF, preferably typewritten using LaTeX, Markdown, or another mathematical formatting program. In general, late assignments will not receive credit.

Tentative Weekly Schedule

Week	Title	Topics
1	Introduction & Motivation	Optimization in operations research, ML, scientific computing, and quantum computing; scheduling, MaxCut, portfolio optimization, PDE-constrained optimization, routing, and quantum circuit compilation.
2	Basics of Continuous and Discrete Optimization	LP, QP, integer programming, convexity, duality, relaxations, optimality gaps, approximation algorithms, and CPLEX/open-source solver baselines.
3	QUBO, HUBO, and Ising Modeling	Binary and higher-order unconstrained formulations, penalties, reductions, quadratization, sparsity, graph structure, and constraints.
4	High-Performance Optimization Pipelines	Parallel branch-and-bound, decomposition, distributed local search, GPU/MPI acceleration, batched simulation, benchmarking, and performance metrics.
5	AI for Optimization I: Graph Neural Networks	Learning heuristics for graph optimization, neural combinatorial optimization, learned branching/cutting, embeddings, and search guidance.
6	AI for Optimization II: LLMs and Foundation Models	LLMs for modeling, constraint generation, code synthesis, solver orchestration, debugging, and human-in-the-loop optimization.
7	Quantum Computing Basics for Optimization	Qubits, gates, circuits, measurement, Hamiltonians, noise, transpilation, hardware topology, and observables.
8	Quantum Approximate Optimization Algorithm	QAOA for MaxCut and QUBO, mixers, cost Hamiltonians, parameter landscapes, warm starts, constraints, depth, sampling, and classical outer-loop optimization.
9	Variational and Sampling-Based Quantum Optimization	VQE-style optimization, annealing-inspired algorithms, quantum walks, sampling heuristics, shot noise, and post-processing.
10	Quantum Hardware-Aware Optimization	Problem embedding, transpilation-aware formulations, error mitigation, noise-aware objectives, resource estimation, and comparisons against CPLEX, heuristics, and HPC simulation.
11	AI+Quantum I: Learning to Build Quantum Workflows	GNNs and LLMs for encoding, ansatz selection, mixer design, penalty tuning, parameter initialization, and automated experimental design.
12	AI+Quantum II: Quantum-Centric Supercomputing	Hybrid workflows combining CPUs, GPUs, QPUs, CPLEX, simulators, and AI agents; scheduling, routing, circuit cutting, domain decomposition, and optimization services.
13	Benchmarking, Reproducibility, and Research Frontiers	Fair baselines, instance generation, ablation studies, metrics beyond success probability, benchmark suites, and quantum advantage questions.
14	Student Presentations	Final project presentations on QAOA, QUBO/HUBO, AI-guided solvers, CPLEX-vs-quantum comparisons, HPC simulation, or AI+Quantum pipelines.

Useful Links

Content related to the one presented in this class:

Disclaimer

Any opinions, statements, or conclusions expressed in the above reports do not necessarily reflect the views of the acknowledged funding sponsors or Columbia University.