  Stochastic optimization problems are powerful models for the operation of
systems under uncertainty and are in general computationally intensive to
solve. Two-stage stochastic optimization is one such problem, where the
objective function involves calculating the expected cost of future decisions
to inform the best decision in the present. In general, even approximating this
expectation value is a #P-Hard problem. We provide a quantum algorithm to
estimate the expected value function in a two-stage stochastic optimization
problem in time complexity largely independent from the complexity of the
random variable. Our algorithm works in two steps: (1) By representing the
random variable in a register of qubits and using this register as control
logic for a cost Hamiltonian acting on the primary system of qubits, we use the
quantum alternating operator ansatz (QAOA) with operator angles following an
annealing schedule to converge to the minimal decision for each scenario in
parallel. (2) We then use Quantum Amplitude Estimation (QAE) to approximate the
expected value function of the per-scenario optimized wavefunction. We show
that the annealing time of the procedure in (1) is independent of the number of
scenarios in the probability distribution. Additionally, estimation error in
QAE converges inverse-linear in the number of "repetitions" of the algorithm,
as opposed to converging as the inverse of the square root in traditional Monte
Carlo sampling. Because both QAOA and QAE are expected to have polynomial
advantage over their classical computing counterparts, we expect our algorithm
to have polynomial advantage over classical methods to compute the expected
value function. We implement our algorithms for a simple optimization problem
inspired by operating the power grid with renewable generation and uncertainty
in the weather, and give numerical evidence to support our arguments.
