Seminar: Quantum Optimization for Combinatorial Problems - A Simple Tour via QAOA, Hybrids, and What Works Today

This seminar offers an accessible introduction to quantum optimization through the Quantum Approximate Optimization Algorithm (QAOA). Combinatorial optimization problems arise in many scientific and engineering contexts, and they challenge classical methods as system sizes and complexity grow. QAOA is a near term approach that alternates problem guided and mixing steps on shallow quantum circuits.

We discuss how QAOA targets familiar combinatorial tasks (using Max Cut as a running example), what is known about its behavior on today’s NISQ devices, and where practical limits, such as training instabilities (“barren plateaus”), appear. Throughout, performance is interpreted against strong classical baselines (e.g., the Goemans–Williamson approximation for Max Cut) to keep expectations grounded.

Dr. Kostas Blekos is an Associate Research Scientist in quantum computing at the Computation-based Science & Technology Research Center (CaSToRC) of The Cyprus Institute and a core member of the QUEST ERA Chair team. He earned a Ph.D. in Theoretical & Computational Physics from the University of Patras. His research spans quantum algorithms, especially variational methods and QAOA, quantum information/complexity, and hybrid quantum–classical workflows, often interfacing with machine learning for the physical sciences.

Previously, he served as Head of Research at Quantum Neural Technologies (Athens) and held research posts at NCSR “Demokritos” / Athena RC and the University of Patras.