The key idea behind the proposed algorithm involves constructing two separate local models in each iteration: a model of the objective function, and a model of the variance of the objective function. Exploiting the variance model allows us to both restrict the number of communications with the quantum computer, and also helps navigate the nonconvex objective landscapes typical in the QAOA optimization problems.
The key idea behind the proposed algorithm involves constructing two separate local models in each iteration: a model of the objective function, and a model of the variance of the objective function. Exploiting the variance model allows us to both restrict the number of communications with the quantum computer, and also helps navigate the nonconvex objective landscapes typical in the QAOA optimization problems.
The quantum approximate optimization algorithm (QAOA) has enjoyed increasing attention in noisy, intermediate-scale quantum computing with its application to combinatorial optimization problems. QAOA has the potential to demonstrate a quantum advantage for NP-hard combinatorial optimization problems. As a hybrid quantum-classical algorithm, the classical component of QAOA resembles a simulation optimization problem in which the simulation outcomes are attainable only through a quantum computer. The simulation that derives from QAOA exhibits two unique features that can have a substantial impact on the optimization process: (i) the variance of the stochastic objective values typically decreases in proportion to the optimality gap, and (ii) querying samples from a quantum computer introduces an additional latency overhead. In this paper, we introduce a novel stochastic trust-region method derived from a derivative-free, adaptive sampling trust-region optimization method intended to efficiently solve the classical optimization problem in QAOA by explicitly taking into account the two mentioned characteristics. The key idea behind the proposed algorithm involves constructing two separate local models in each iteration: a model of the objective function and a model of the variance of the objective function. Exploiting the variance model allows us to restrict the number of communications with the quantum computer and also helps navigate the nonconvex objective landscapes typical in QAOA optimization problems. We numerically demonstrate the superiority of our proposed algorithm using the SimOpt library and Qiskit when we consider a metric of computational burden that explicitly accounts for communication costs. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing and Operations Research. Accepted for Special Issue. Funding: This material is based upon work supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers and the Office of Advanced Scientific Computing Research, Accelerated Research for Quantum Computing program under contract number DE-AC02-06CH11357. Y. Ha and S. Shashaani also gratefully acknowledge the U.S. National Science Foundation Division of Civil, Mechanical and Manufacturing Innovation Grant CMMI-2226347 and the U.S. Office of Naval Research [Grant N000142412398]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0575 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0575 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
In this thesis, we develop, analyze, and implement effective and efficient methods for constrained stochastic and derivative-free optimization. For each method, we prove the convergence result under general assumptions. We also conduct numerical experiments to demonstrate the efficiency and efficacy of our proposed methods. In Chapter 2, we develop a model-based derivative-free optimization method. A key component of variational quantum algorithms (VQAs) is the choice of a classical optimizer to update the ansatz parameterization. Quantum algorithms, however, are destined to run on noisy hardware with limited fidelity, leading to objective function evaluations–such as those in the quantum approximate optimization algorithm (QAOA) or the variational quantum eigensolver (VQE)–that are compromised by both stochastic errors and hardware-induced noise. To address these challenges, we adapt recent developments from the noise-aware numerical optimization literature to these commonly used derivative-free model-based methods. We introduce the key defining characteristics of these novel noise-aware derivative-free model-based methods that separate them from standard model-based methods. We study an implementation of such noise-aware derivative-free model-based methods and compare its performance on demonstrative VQA simulations to classical solvers packaged in scikit-quant. Moreover, we propose a series of sequential quadratic programming (SQP) methods tailored for stochastic equality constrained optimization. In Chapter 3, we develop a stochastic method for solving equality constrained problems that utilizes predictive variance reduction within the SQP paradigm, and prove that a measure of first-order stationarity converges to zero in expectation under reasonable assumptions, with practical performance demonstrated on constrained binary classification problems. In Chapter 4, we propose a line search SQP method for general nonlinear equality constrained optimization that employs a modified line search strategy using second-order information to mitigate the Maratos effect, thereby achieving global convergence and local superlinear convergence. We further extend this approach to settings where the objective function is stochastic or represented as a finite sum, and design a practical inexact matrix-free variant and demonstrate the numerical performance empirically. Finally, in Chapter 5, we propose, analyze, and implement an SQP algorithm for minimizing a nonlinear smooth function subject to smooth equality constraints with noisy function and derivative estimates, addressing the challenges posed by bounded noise in the objective and constraint functions as well as potential rank-deficiency in the constraint Jacobians. This algorithm employs a decomposition approach to compute inexact search directions and utilizes adaptive step size selection schemes, which guarantee global convergence of infeasible stationarity error to a neighborhood of zero that is proportional to the noise level.
A key component of variational quantum algorithms (VQAs) is the choice of classical optimizer employed to update the parameterization of an ansatz. It is well recognized that quantum algorithms will, for the foreseeable future, necessarily be run on noisy devices with limited fidelities. Thus, the evaluation of an objective function (e.g., the guiding function in the quantum approximate optimization algorithm (QAOA) or the expectation of the electronic Hamiltonian in variational quantum eigensolver (VQE)) required by a classical optimizer is subject not only to stochastic error from estimating an expected value but also to error resulting from intermittent hardware noise. Model-based derivative-free optimization methods have emerged as popular choices of a classical optimizer in the noisy VQA setting, based on empirical studies. However, these optimization methods were not explicitly designed with the consideration of noise. In this work we adapt recent developments from the “noise-aware numerical optimization” literature to these commonly used derivative-free model-based methods. We introduce the key defining characteristics of these novel noise-aware derivative-free model-based methods that separate them from standard model-based methods. We study an implementation of such noise-aware derivative-free model-based methods and compare its performance on demonstrative VQA simulations to classical solvers packaged in scikit-quant. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing and Operations Research. Accepted for Special Issue. Funding: This material is based upon work supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers and the Office of Advanced Scientific Computing Research, Accelerated Research for Quantum Computing program under contract number DE-AC02-06CH11357. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0578 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0578 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Variational quantum algorithms turn choices of Hamiltonian, ansatz, and parameterization into a classical nonconvex optimization problem. We study how this objective function can be visualized and characterized in ways that help explain optimizer behavior. We distinguish two properties of the objective: the number of local minima encountered along sampled directions and the differences in quality among local-search endpoints. We then ask how a local optimizer, represented by BFGS, compares with adaptive differential evolution, represented by jSO. Rather than comparing jSO with a single local run, we allow BFGS multiple starts within the same function-evaluation budget. This gives local search repeated opportunities to explore different basins and provides a stronger baseline for asking when a global evolutionary solver is useful. We study these questions using VQE and QAOA, focusing on how frustra- tion, circuit depth, parameter tying, mixed locality, and nonlinear repa- rameterization change the Hamiltonian expectation-value objective seen by the classical optimizer. Increasing independent circuit depth raises the sampled local-minimum count without making global search more effective. Parameter tying, by contrast, produces both more repeated local structure and much larger differences in quality among local-search endpoints, and in this regime adaptive differential evolution outperforms function-evaluation-matched multistart BFGS. The comparison shows that the number of local minima alone does not determine whether global search is advantageous: the important distinction is whether different basins lead to similarly good solutions or to substantially different objective values. These results provide a practical workflow for connecting model construction, objective- function geometry, empirical diagnostics, and optimizer choice.