Where are quantum advantages for discrete optimization hiding?

Although discrete optimization has inspired much quantum algorithmic work, exponential advantages for conventional discrete optimization have remained largely elusive. Why? I’ll offer my perspective on this question using the Max Cut problem as a running example. I’ll talk about approximating Quantum Max Cut, which has very recently has resulted in a new sharp bound for the ground energy of the antiferromagnetic Heisenberg model relating to matchings in the interaction graph. Next, I’ll give an example of an exponential space advantage for approximating the Maximum Directed Cut problem. Finally, I’ll point out some limitations of the recent Decoded Quantum Interferometry (DQI) algorithm for approximating Max Cut.