Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm

• URL: http://arxiv.org/abs/2402.15029v1
• Date: Fri, 23 Feb 2024 00:07:34 GMT
• Title: Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm
• Authors: Caleb Rotello, Peter Graf, Matthew Reynolds, Cody James Winkleblack, Wesley Jones
• Abstract summary: Two-stage optimization involves calculating the expected cost of future decisions to inform the best decision in the present. We provide a quantum algorithm to estimate the expected value function in a two-stage optimization problem in time largely independent from the complexity of the random variable.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Non-linear Quantum Monte Carlo [1.237454174824584]
  Quantum computing provides a quadratic speedup over classical Monte Carlo methods for mean estimation. We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems.
  arXiv  Detail & Related papers  (2025-02-07T17:13:27Z)
• Mixed State Variational Quantum Eigensolver for the Estimation of Expectation Values at Finite Temperature [0.0]
  We introduce a novel hybrid quantum-classical algorithm for the near-term computation of expectation values in quantum systems at finite temperatures. This is based on two stages: on the first one, a mixed state approximating a fiducial truncated density matrix is prepared through Variational Quantum Eigensolving (VQE) techniques. This is then followed by a reweighting stage where the expectation values for observables of interest are computed.
  arXiv  Detail & Related papers  (2024-01-30T17:29:58Z)
• Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games [31.554420227087043]
  We propose a two-timescale smoothed $Q$-learning algorithm with function approximation that is payoff-based, convergent, rational, and symmetric between the two players. In two-timescale $Q$-learning, the fast-timescales are updated in spirit to the gradient descent and the slow-timescales are updated by taking a convex combination between its previous and the latest fast-timescale. The key novelty lies in constructing a valid Lyapunov function to capture the evolution of the slow-timescales.
  arXiv  Detail & Related papers  (2023-12-08T08:39:36Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
  We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time. This is the first speed-up of this type to be obtained over the seminal nearly-linear time of vStefankovivc, Vempala and Vigoda.
  arXiv  Detail & Related papers  (2022-07-18T14:41:48Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• Quantum algorithms for numerical differentiation of expected values with respect to parameters [0.0]
  We consider an expected value of a function of a variable and a real-valued parameter, and how to calculate derivatives of the expectation of the parameter. Based on QMCI and the general-order central difference formula for numerical differentiation, we propose two quantum methods for this problem. We see that, depending on the smoothness of the function and the number of qubits available, either of two methods is better than the other.
  arXiv  Detail & Related papers  (2021-11-22T06:50:25Z)
• Continuous black-box optimization with quantum annealing and random subspace coding [2.839269856680851]
  A black-box optimization algorithm such as Bayesian optimization finds extremum of an unknown function by alternating inference of the underlying function and optimization of an acquisition function. In a high-dimensional space, such algorithms perform poorly due to the difficulty of acquisition function optimization. We apply quantum annealing to overcome the difficulty in the continuous black-box optimization.
  arXiv  Detail & Related papers  (2021-04-30T06:19:07Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.