Iteration Complexity of Variational Quantum Algorithms
arXiv:2209.10615 · doi:10.22331/q-2024-10-10-1495
Abstract
There has been much recent interest in near-term applications of quantum computers, i.e., using quantum circuits that have short decoherence times due to hardware limitations. Variational quantum algorithms (VQA), wherein an optimization algorithm implemented on a classical computer evaluates a parametrized quantum circuit as an objective function, are a leading framework in this space. An enormous breadth of algorithms in this framework have been proposed for solving a range of problems in machine learning, forecasting, applied physics, and combinatorial optimization, among others. In this paper, we analyze the iteration complexity of VQA, that is, the number of steps that VQA requires until its iterates satisfy a surrogate measure of optimality. We argue that although VQA procedures incorporate algorithms that can, in the idealized case, be modeled as classic procedures in the optimization literature, the particular nature of noise in near-term devices invalidates the claim of applicability of off-the-shelf analyses of these algorithms. Specifically, noise makes the evaluations of the objective function via quantum circuits biased. Commonly used optimization procedures, such as SPSA and the parameter shift rule, can thus be seen as derivative-free optimization algorithms with biased function evaluations, for which there are currently no iteration complexity guarantees in the literature. We derive the missing guarantees and find that the rate of convergence is unaffected. However, the level of bias contributes unfavorably to both the constant therein, and the asymptotic distance to stationarity, i.e., the more bias, the farther one is guaranteed, at best, to reach a stationary point of the VQA objective.
45 pages, 13 figures
References in corpus (29)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- The theory of variational hybrid quantum-classical algorithms
- Quantum Circuit Learning
- Evaluating analytic gradients on quantum hardware
- Quantum algorithms for quantum chemistry and quantum materials science
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- A programmable two-qubit quantum processor in silicon
- Towards Practical Quantum Variational Algorithms
- Demonstration of Entanglement of Electrostatically Coupled Singlet-Triplet Qubits
- Theory of variational quantum simulation
- Universal Quantum Estimator
- Direct estimations of linear and non-linear functionals of a quantum state
- General parameter-shift rules for quantum gradients
- Hybrid Quantum-Classical Approach to Quantum Optimal Control
- Warm-starting quantum optimization
- Solving nonlinear differential equations with differentiable quantum circuits
- Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
- Estimating the gradient and higher-order derivatives on quantum hardware
- Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
- Performance comparison of optimization methods on variational quantum algorithms
- Quantum Machine Learning for Particle Physics using a Variational Quantum Classifier
- Measuring Analytic Gradients of General Quantum Evolution with the Stochastic Parameter Shift Rule
- A Feasible Approach for Automatically Differentiable Unitary Coupled-Cluster on Quantum Computers
- Analytic gradients in variational quantum algorithms: Algebraic extensions of the parameter-shift rule to general unitary transformations
- Quantum Analytic Descent
- Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space
- Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points