Heim et al. 2024
paperAuthors
Credibility Rating
Good quality. Reputable source with community review or editorial standards, but less rigorous than peer-reviewed venues.
Rating inherited from publication venue: arXiv
This paper explores quantum algorithms for two-stage stochastic programming under uncertainty, relevant to AI safety as it addresses computational methods for decision-making with uncertain outcomes, potentially applicable to robust AI planning and optimization.
Paper Details
Metadata
Abstract
Two-stage stochastic programming is a problem formulation for decision-making under uncertainty. In the first stage, the actor makes a best "here and now" decision in the presence of uncertain quantities that will be resolved in the future, represented in the objective function as the expected value function. This function is a multi-dimensional integral of the second stage optimization problem, which must be solved over all possible future scenarios. This work uses a quantum algorithm to estimate the expected value function with a polynomial speedup. Our algorithm gains its advantage through the two following observations. First, by encoding the probability distribution as a quantum wavefunction in an auxilliary register, and using this register as control logic for a phase-separation unitary, Digitized Quantum Annealing (DQA) can converge to the minimium of each scenario in the random variable in parallel. Second, Quantum Amplitude Estimation (QAE) on DQA can calculate the expected value of this per-scenario optimized wavefunction, producing an estimate for the expected value function. Quantum optimization is theorized to have a polynomial speedup for combinatorial optimization problems, and estimation error from QAE is known to converge inverse-linear in the number of samples (as opposed to the best case inverse of a square root in classical Monte Carlo). Therefore, assuming the probability distribution wavefunction can be prepared efficiently, we conclude our method has a polynomial speedup (of varying degree, depending on the optimization problem) over classical methods for estimating the expected value function. We conclude by demonstrating this algorithm on a stochastic programming problem inspired by operating the power grid under weather uncertainty.
Summary
This paper presents a quantum algorithm for solving two-stage stochastic programming problems, which involve decision-making under uncertainty. The approach combines Digitized Quantum Annealing (DQA) with Quantum Amplitude Estimation (QAE) to estimate the expected value function—a computationally expensive multi-dimensional integral over all possible future scenarios. By encoding probability distributions as quantum wavefunctions and leveraging quantum parallelism, the algorithm achieves polynomial speedup over classical methods. The authors demonstrate their approach on a power grid operation problem under weather uncertainty, showing practical applicability to real-world stochastic optimization challenges.
Cited by 1 page
| Page | Type | Quality |
|---|---|---|
| AI Governance Coordination Technologies | Approach | 91.0 |
Cached Content Preview
# Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm
Caleb Rotello
caleb.rotello@nrel.gov
Computational Science Center, National Renewable Energy Laboratory, Golden CO, 80401
Peter Graf
Computational Science Center, National Renewable Energy Laboratory, Golden CO, 80401
Matthew Reynolds
Computational Science Center, National Renewable Energy Laboratory, Golden CO, 80401
Cody James Winkleblack
Computational Science Center, National Renewable Energy Laboratory, Golden CO, 80401
Wesley Jones
Computational Science Center, National Renewable Energy Laboratory, Golden CO, 80401
###### Abstract
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.
## 1 Introduction
Two-stage stochastic programming is a problem formulation for decision-making under uncertainty where an actor makes “here and now” decisions in the presence of uncertain quantities that will be resolved at a later time; important problems like energy planning \[ [1](https://ar5iv.labs.arxiv.org/html/2402.15029#bib.bibx1 "")\], traffic routing \[ [2](https://ar5iv.labs.arxiv.org/html/2402.15029#bib.bibx2 "
... (truncated, 98 KB total)8606ccd2aedd5e6b | Stable ID: OWJhYTNhNj