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.
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.
Within the context of hybrid quantum-classical optimization, gradient descent based optimizers typically require the evaluation of expectation values with respect to the outcome of parameterized quantum circuits. In this work, we explore the consequences of the prior observation that estimation of these quantities on quantum hardware results in a form of stochastic gradient descent optimization. We formalize this notion, which allows us to show that in many relevant cases, including VQE, QAOA and certain quantum classifiers, estimating expectation values with k measurement outcomes results in optimization algorithms whose convergence properties can be rigorously well understood, for any value of k. In fact, even using single measurement outcomes for the estimation of expectation values is sufficient. Moreover, in many settings the required gradients can be expressed as linear combinations of expectation values - originating, e.g., from a sum over local terms of a Hamiltonian, a parameter shift rule, or a sum over data-set instances - and we show that in these cases k-shot expectation value estimation can be combined with sampling over terms of the linear combination, to obtain "doubly stochastic" gradient descent optimizers. For all algorithms we prove convergence guarantees, providing a framework for the derivation of rigorous optimization results in the context of near-term quantum devices. Additionally, we explore numerically these methods on benchmark VQE, QAOA and quantum-enhanced machine learning tasks and show that treating the stochastic settings as hyper-parameters allows for state-of-the-art results with significantly fewer circuit executions and measurements.
Within the context of hybrid quantum-classical optimization, gradient descent based optimizers typically require the evaluation of expectation values with respect to the outcome of parameterized quantum circuits. In this work, we explore the consequences of the prior observation that estimation of these quantities on quantum hardware results in a form of s t o c h a s t i c gradient descent optimization. We formalize this notion, which allows us to show that in many relevant cases, including VQE, QAOA and certain quantum classifiers, estimating expectation values with k measurement outcomes results in optimization algorithms whose convergence properties can be rigorously well understood, for any value of k . In fact, even using single measurement outcomes for the estimation of expectation values is sufficient. Moreover, in many settings the required gradients can be expressed as linear combinations of expectation values -- originating, e.g., from a sum over local terms of a Hamiltonian, a parameter shift rule, or a sum over data-set instances -- and we show that in these cases k -shot expectation value estimation can be combined with sampling over terms of the linear combination, to obtain ``doubly stochastic'' gradient descent optimizers. For all algorithms we prove convergence guarantees, providing a framework for the derivation of rigorous optimization results in the context of near-term quantum devices. Additionally, we explore numerically these methods on benchmark VQE, QAOA and quantum-enhanced machine learning tasks and show that treating the stochastic settings as hyper-parameters allows for state-of-the-art results with significantly fewer circuit executions and measurements.
Abstract Portfolio optimization plays a central role in finance to obtain optimal portfolio allocationsthat aim to achieve certain investment goals. Over the years, many works have investigateddifferent variants of portfolio optimization. Portfolio optimization also provides a rich area tostudy the application of quantum computers to obtain advantages over classical computers.In this work, we give a sampling version of an existing classical online portfolio optimizationalgorithm by Helmbold et al., for which we in turn develop a quantum version. The quantumadvantage is achieved by using techniques such as quantum state preparation, inner productestimation and multi-sampling. Our quantum algorithm provides a quadratic speedup inthe time complexity, in terms of n, where n is the number of assets in the portfolio. Thetransaction cost of both of our classical and quantum algorithms is independent of n whichis especially useful for practical applications with a large number of assets.
Variational quantum eigensolvers have recently received increased attention, as they enable the use of quantum computing devices to find solutions to complex problems, such as the ground energy and ground state of strongly-correlated quantum many-body systems. In many applications, it is the optimization of both continuous and discrete parameters that poses a formidable challenge. Using reinforcement learning (RL), we present a hybrid policy gradient algorithm capable of simultaneously optimizing continuous and discrete degrees of freedom in an uncertainty-resilient way. The hybrid policy is modeled by a deep autoregressive neural network to capture causality. We employ the algorithm to prepare the ground state of the nonintegrable quantum Ising model in a unitary process, parametrized by a generalized quantum approximate optimization ansatz: the RL agent solves the discrete combinatorial problem of constructing the optimal sequences of unitaries out of a predefined set and, at the same time, it optimizes the continuous durations for which these unitaries are applied. We demonstrate the noise-robust features of the agent by considering three sources of uncertainty: classical and quantum measurement noise, and errors in the control unitary durations. Our work exhibits the beneficial synergy between reinforcement learning and quantum control.
The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations. For two core problems, namely general convex optimization and volume estimation of convex bodies, we give quantum algorithms as well as quantum lower bounds that constitute the quantum speedups of both problems to be polynomial compared to their classical counterparts. We then consider machine learning and optimization problems with input data stored explicitly as matrices. We first look at semidefinite programs and provide quantum algorithms with polynomial speedup compared to the classical state-of-the-art. We then move to machine learning and give the optimal quantum algorithms for linear and kernel-based classifications. To complement with our quantum algorithms, we also introduce a framework for quantum-inspired classical algorithms, showing that for low-rank matrix arithmetics there can only be polynomial quantum speedup. Finally, we study statistical problems on quantum computers, with the focus on testing properties of probability distributions. We show that for testing various properties including L1-distance, L2-distance, Shannon and Renyi entropies, etc., there are polynomial quantum speedups compared to their classical counterparts. We also extend these results to testing properties of quantum states.
We consider the problem of minimizing a continuous function given quantum access to a stochastic gradient oracle. We provide two new methods for the special case of minimizing a Lipschitz convex function. Each method obtains a dimension versus accuracy trade-off which is provably unachievable classically and we prove that one method is asymptotically optimal in low-dimensional settings. Additionally, we provide quantum algorithms for computing a critical point of a smooth non-convex function at rates not known to be achievable classically. To obtain these results we build upon the quantum multivariate mean estimation result of Cornelissen et al. 2022 and provide a general quantum-variance reduction technique of independent interest.