EAGER: Leveraging Quantum Computing for Stochastic Optimization

Many of the most consequential decisions in energy, transportation, and supply chains must be made in the face of uncertainty (e.g., fluctuating demand, disruptions, extreme events), yet the resulting optimization problems can be too large for current methods to solve quickly and reliably. This EArly-concept Grant for Exploratory Research (EAGER) project will provide empirically grounded guidance on when and how quantum computing resources available in the near future can help with these uncertainty-driven decisions, producing practical “guardrails” and open tools that show which problem structures are amenable to these methods. The work advances NSF’s mission by promoting progress of science in quantum-enabled optimization under uncertainty, strengthening national health, prosperity, and welfare through more resilient planning and operations, and informing methods relevant to national defense logistics; it will also train graduate researchers and release open-source benchmarks and software to broaden participation and accelerate impact. The project will develop and validate stochastic formulations for two-stage stochastic programs, emphasizing the common case where uncertainty enters linear terms (e.g., right-hand-side and linear cost uncertainty) to enable compact quadratic unconstrained representations suitable for hybrid quantum–classical workflows. The researchers will implement and evaluate linear vs. logarithmic scenario encodings; design and benchmark soft non-anticipativity enforcement via penalty and relaxation strategies; create incumbent-generation procedures that use quantum (or quantum-simulator) sampling to produce high-quality candidate solutions for classical refinement; and perform systematic scaling and noise-robustness studies across benchmark families to produce phase-diagram style summaries linking instance structure, encoding choice, penalty strength, and achieved solution quality. Deliverables include an open-source code base and benchmark suite, along with evidence-based guidance on where quantum sampling provides measurable value for stochastic optimization. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.