Optimization Problems on Quantum Computers
Course description
The potential of quantum algorithms for solving optimization problems has been explored since the early days of quantum computing. This course introduces some of the key ideas and algorithms developed in this context, along with their fundamental limitations. Depending on the available time, topics covered may include: quantum optimization algorithms inspired by physics (adiabatic algorithms, variational algorithms, QAOA, quantum annealing, etc.), quantum algorithms for convex optimization (acceleration of first- and second-order methods, oracular problems, etc.), applications to combinatorial optimization (graph problems, quadratic binary optimization, etc.).
Instructor: Yassine Hamoudi
Schedule for lectures: Tuesday-Wednesday, 2pm-3:30pm
Schedule for problem session: Thursday, 3:50pm-6pm
Lectures
- Lecture 1: Quantum optimization algorithms inspired by physics [Slides]
- Lecture 2: Quantum optimization algorithms using oracles [Slides]
- Problem session: Solving MAX-3SAT with Grover’s search in Qiskit [File]
Suggested references
- Lectures: R. de Wolf [Lecture notes] (Chapter 19.4) [Video], A. Childs [Lecture notes] (Part VI), A. Montanaro [Video 1] [Video 2]
- Surveys and Textbooks:
- “Challenges and Opportunities in Quantum Optimization”. A. Abbas et al. [Link]
- “Quantum Algorithms: A Survey of Applications and End-to-end Complexities”. A. Dalzell et al. [Link]
- “Quantum Algorithms for Optimizers”. G. Nannicini. [Link]
- “Adiabatic Quantum Computing”. T. Albash, D. Lidar. [Link]
- “Variational Quantum Algorithms”. M. Cerezo et al. [Link]
- Implementation:
- “Qiskit Optimization Tutorials”. [Link]
- Research papers related to Lecture 1:
- “Ising Formulations of Many NP Problems”. A. Lucas. [Paper]
- “A Quantum Approximate Optimization Algorithm”. E. Farhi, J. Goldstone, S. Gutmann. [Paper]
- “Quantum Supremacy through the Quantum Approximate Optimization Algorithm”. E. Farhi, A. Harrow. [Paper]
- “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices”. L. Zhou, S. Wang, S. Choi, H. Pichler, M. Lukin. [Paper]
- “(Sub)Exponential advantage of adiabatic quantum computation with no sign problem”. A. Gilyén, M. Hastings, U. Vazirani [Paper] [Video]
- Research papers related to Lecture 2:
- “Quantum Query Complexity of Some Graph Problems”. C. Durr, M. Heiligman, P. Hoyer, M. Mhalla. [Paper]
- “Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation”. A. Gilyén, S. Arunachalam, N. Wiebe. [Paper] [Video]
- “Quantum Speedups for Exponential-Time Dynamic Programming Algorithms”. A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prūsis, J. Vihrovs. [Paper] [Video]
- “Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving”. S. Apers, R. de Wolf. [Paper] [Video]
- “Quantum Algorithms for Escaping from Saddle Points”. C. Zhang, J. Leng, T. Li. [Paper] [Video]
- “Mind the Gap: Achieving a Super-Grover Quantum Speedup by Jumping to the End”. A. Dalzell, N. Pancotti, E. Campbell, F. Brandão. [Paper] [Video]
- “Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling”. A. Bouland, Y. Getachew, Y. Jin, A. Sidford, K. Tian. [Paper] [Video]
Theme's credit