Quantum optimization is one of the most promising applications of quantum computers, yet significant challenges remain in achieving scalable, fault-tolerant solutions. We will review these challenges and motivate why continued progress is both necessary and within reach. Quantum approximate optimization algorithm (QAOA), with its moderate resource requirements and compelling evidence of speedup, emerges as a leading candidate to address them. We will then introduce regularized warm-started QAOA, a classical-quantum hybrid algorithm combining instance-dependent classical preprocessing with instance-independent shallow quantum evolution. We will demonstrate its superior performance over classical state-of-the-art solvers across hardware experiments, large-scale simulations, and fault-tolerant resource estimation. Finally, we will present results from fully fault-tolerant executions of optimization algorithms using the [[7,1,3]] Steane code on a trapped-ion device. This application-level benchmark will reveal system-level behaviors absent in component-level tests, and its close-to-breakeven performance charts a promising path forward for fault-tolerant quantum computation.