Where are the exponential quantum advantages for discrete optimization hiding?

Summary:
This seminar examines why exponential quantum advantages for NP-hard discrete optimization remain elusive and explores potential explanations and workarounds through the Maximum Cut problem.

Abstract:
Quantum computing offers hope for realizing exponential advantages over classical computing. Despite over two decades of work studying quantum approaches for discrete optimization, rigorously provable exponential advantages for approximating optimal solutions to NP-hard problems remain scarce. Why? We will discuss a potential explanation and workarounds, using the Maximum Cut problem as a running example.

Speaker Bio:
Ojas Parekh is a theoretical computer scientist who enjoys applying mathematical techniques to practically motivated interdisciplinary problems. He has worked in a variety of fields including discrete optimization, combinatorics, combinatorial scientific computing, and most recently, quantum and neuromorphic computing. A recent passion is helping shape the emerging fields of quantum approximation algorithms and quantum discrete optimization. He co-directs the Quantum Algorithms and Applications Collaboratory (QuAAC) at Sandia National Laboratories and directs the Department of Energy Fundamental Algorithmic Research toward Quantum Utility project (far-qu.sandia.gov), a multi-institutional effort tasked with designing novel quantum algorithms to realize advantages over classical computation, especially for optimization, simulation, and machine learning. Ojas believes the universe loves us because pizza exists.