Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
arXiv:2304.02262 · doi:10.1007/s42484-026-00363-y
Abstract
Optimization theory has been widely studied in academia and finds a large variety of applications in industry. The different optimization models in their discrete and/or continuous settings have catered to a rich source of research problems. Robust convex optimization is a branch of optimization theory in which the variables or parameters involved have a certain level of uncertainty. In this work, we consider the online robust optimization meta-algorithm by Ben-Tal et al. and show that for a large range of stochastic subgradients, this algorithm has the same guarantee as the original non-stochastic version. We develop a hybrid quantum-classical version of this algorithm and show that an at most quadratic improvement in terms of the dimension can be achieved. The speedup is due to the use of quantum state preparation, quantum norm estimation, and quantum multi-sampling. We apply our quantum meta-algorithm to examples such as robust linear programs and robust semidefinite programs and give applications of these robust optimization problems in finance and engineering.
31 pages
References in corpus (16)
- Quantum algorithm for solving linear systems of equations
- Quantum random access memory
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- Architectures for a quantum random access memory
- Exponential improvement in precision for simulating sparse Hamiltonians
- On the robustness of bucket brigade quantum RAM
- Quantum SDP-Solvers: Better upper and lower bounds
- Randomized Block Coordinate Descent for Online and Stochastic Optimization
- An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance
- Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
- Quantum Algorithms for the Pathwise Lasso
- Improved Quantum Boosting
- A quantum random access memory (QRAM) using a polynomial encoding of binary strings
- Preparing Many Copies of a Quantum State in the Black-Box Model