PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical optimization for hybrid quantum-classical algorithms

Gian Giacomo Guerreschi, Mikhail Smelyanskiy

arXiv:1701.01450v1quant-ph

TL;DR

Hybrid variational algorithms must balance optimization quality against the repetition cost of finite-precision quantum estimates. This paper introduces gradient and quasi-Newton optimization in this setting, studies precision and method choices quantitatively for QAOA, and reports conclusions while limiting its numerical study to a QAOA variant.

  • Problem

    The paper addresses how finite estimation precision and optimization-method choice affect the performance and repetition cost of hybrid variational algorithms.

  • Method

    The study extends hybrid-algorithm optimization beyond derivative-free methods to first-order and quasi-Newton approaches, comparing them using experimentally relevant repetition-cost metrics.

  • Results

    The paper presents quantitative optimization-method and precision results for the Quantum Approximate Optimization Algorithm.

  • Takeaways & Limitations

    Repetition cost provides an experimental-feasibility metric for comparing optimization processes in shallow quantum circuits.

  • Takeaways & Limitations

    The numerical study is limited to a QAOA variant.

Abstract

from arXiv · show

A novel class of hybrid quantum-classical algorithms based on the variational approach have recently emerged from separate proposals addressing, for example, quantum chemistry and combinatorial problems. These algorithms provide an approximate solution to the problem at hand by encoding it in the state of a quantum computer. The operations used to prepare the state are not a priori fixed but, quite the opposite, are subjected to a classical optimization procedure that modifies the quantum gates and improves the quality of the approximate solution. While the quantum hardware determines the size of the problem and what states are achievable (limited, respectively, by the number of qubits and by the kind and number of possible quantum gates), it is the classical optimization procedure that determines the way in which the quantum states are explored and whether the best available solution is actually reached. In addition, the quantities required in the optimization, for example the objective function itself, have to be estimated with finite precision in any experimental implementation. While it is desirable to have very precise estimates, this comes at the cost of repeating the state preparation and measurement multiple times. Here we analyze the competing requirements of high precision and low number of repetitions and study how the overall performance of the variational algorithm is affected by the precision level and the choice of the optimization method. Finally, this study introduces quasi-Newton optimization methods in the general context of hybrid variational algorithms and presents quantitative results for the Quantum Approximate Optimization Algorithm.

I. INTRODUCTION

Hybrid variational algorithms combine quantum state preparation with classical optimization, making the optimizer central to how reachable states are explored. This paper studies finite-precision costs and gradient-based alternatives in QAOA.

  • QAOA: QAOA maps binary variable assignments to qubit states and evaluates constraint satisfaction through measurements and averaged outcomes.The algorithm seeks assignments satisfying as many constraints as possible.
  • Motivation: Variational algorithms encode approximate problem solutions in quantum states whose gates are adjusted by classical optimization.The quantum circuit limits reachable states, while optimization selects promising states among them.
  • Optimization challenge: As quantum devices support more gates, parameter-space exploration becomes a bottleneck, increasing the need for effective optimization methods.The introduction describes the parameter count as growing dramatically with available quantum gates.
  • Optimization challenge: Derivative-free methods use recent objective values, whereas gradient-based methods exploit objective smoothness through analytical or finite-difference gradients.The paper introduces advanced gradient-dependent optimization methods for hybrid algorithms.
  • Experimental cost: Finite-precision estimates reduce repetition requirements but can deteriorate optimization effectiveness, creating a precision–cost trade-off.The study compares optimization performance across precision levels using experimental repetition counts.
  • Study scope: Numerical simulations evaluate this trade-off and optimization-method performance for the Quantum Approximate Optimization Algorithm.QAOA is the specific combinatorial hybrid algorithm studied quantitatively.

II. HYBRID QUANTUM-CLASSICAL ALGORITHMS

Hybrid variational algorithms alternate quantum state preparation, measurement-based objective evaluation, and classical parameter updates. Their objective values are expectation estimates requiring repeated experiments.

  • Algorithmic cycle: Hybrid variational algorithms use three steps: state preparation, quantum-state measurement, and classical optimization.The optimization proposes parameter changes that are applied in subsequent state preparations.
  • Objective function: The objective function is the expectation value of an observable for the prepared quantum state.The observable may represent a quantum quantity such as molecular energy or a classical optimization objective.
  • State preparation: A parametrized gate sequence prepares the final state from a reference state, with each gate characterized by a parameter.The gates need not commute, and a parameter can characterize more than one gate.
  • Measurement: Estimating the objective requires repeated state preparations and measurements because one measurement cannot directly provide its expectation value.Outcome statistics are accumulated to construct a finite-precision estimator.
  • Measurement: The repetition count is determined by the desired precision and the variances of the measured observables.The paper frames repetition cost as part of the experimental optimization burden.

III. EXPLOITING THE GRADIENT OF THE OBJECTIVE FUNCTION

Gradient information lets optimization methods use local objective geometry to select search directions, while quasi-Newton methods approximate curvature without evaluating the full Hessian. The benefit must be balanced against derivative-evaluation cost.

  • Gradient information: Derivative-based methods use local function values and derivatives to predict objective behavior beyond the current parameter point.Higher-order derivatives can improve the local model but increase evaluation cost.
  • Search strategies: Line-search methods reduce multidimensional optimization to successive one-dimensional searches along selected directions.The direction-selection rule distinguishes derivative-free, gradient, and higher-order methods.
  • Search strategies: Gradient information identifies the steepest local ascent direction for small parameter changes.Additional curvature information can guide searches toward the expected maximum.
  • Curvature information: Higher-order derivative evaluation has diminishing practical value beyond the Hessian because it is costly and provides no substantial gain.The paper therefore focuses on methods using gradients and approximate Hessians.
  • Quasi-Newton methods: Quasi-Newton methods combine exact gradients with an approximate Hessian, offering a balance between computational cost and performance.BFGS updates an approximate inverse Hessian using objective and gradient differences before and after a move.
  • Quasi-Newton methods: In hybrid algorithms, BFGS requires only the objective function and its gradient, both obtained from averages of quantum measurement outcomes.This connects classical quasi-Newton optimization to experimentally estimated quantities.

IV. GRADIENT EVALUATION AND ITS REPETITION COST

Gradient components are also estimated with finite precision in hybrid algorithms. Their accuracy can be limited by measurement statistics or by approximations such as finite differences.

  • Sources of gradient error: Gradient components inherit finite-precision errors from statistical uncertainty in quantum-observable measurements.The paper treats gradient precision as part of the numerical optimization study.
  • Sources of gradient error: Finite-difference gradients add approximation effects beyond the statistical uncertainty of quantum measurements.The study considers both finite-difference and analytical gradient approaches.

A. Finite difference derivatives

The paper analyzes finite-difference gradient estimates under finite precision, balancing derivative accuracy against measurement repetition cost. It identifies precision conditions that work away from stationary regions but can make gradient-based optimization prohibitively expensive near local maxima.

  • Finite-difference construction: Central finite differences estimate a gradient component by subtracting objective-function evaluations at parameter offsets ±δ/2 and dividing by δ.The estimator uses noisy function estimates with precision ϵ′.
  • Error sources: The derivative estimate combines discretization error O(δ^2) with precision error O(ϵ′/δ).
  • Precision conditions: The required estimator precision should satisfy ϵ′ ≥ δ^3, while the finite-difference increment must separate the two noisy function estimates.These conditions avoid demanding precision higher than the derivative accuracy and ensure distinguishable numerator values.
  • Stationary-region limitation: Near local maxima, vanishing gradient components require very small ϵ′ and therefore a large repetition cost.
  • Optimization trade-off: Gradient-based optimization can lose its advantage when the repetition cost for high-precision finite differences grows by several orders of magnitude.
  • Cost control: A lower bound ϵ′ ≥ 1/10 ϵ limits the extra cost of one gradient component to at most 10^2 times one function evaluation.The factor 1/10 is described as arbitrary but intuitive.

B. Analytical gradient

The paper develops analytical gradient estimators for variational quantum circuits by decomposing generators and observables into measurable unitary contributions. Ancilla-assisted circuits evaluate the required expectation values, with special operator structures reducing the repetition cost.

  • Gradient construction: Analytical gradient estimation replaces finite-difference evaluations with an explicit expression derived from the circuit generators and objective observable.
  • Operator decomposition: Each gradient component can be decomposed into contributions from generator terms and objective-observable terms, with weights determined by their operator expansions.The number of generator terms kG can scale polynomially with the number N of qubits, while one- or two-qubit gates give kG = O(1).
  • Estimator dependence: The estimator and its variance depend on how the objective and generator are decomposed and on how individual terms are measured.Different estimators for the same quantity therefore have different repetition costs.
  • Quantum evaluation: An ancilla-assisted quantum circuit evaluates expectation values for the decomposed terms, and the gradient is obtained by summing those contributions.The circuit prepares a final state and measures an ancilla observable for each relevant term.
  • Cost reduction: Directly measurable observables or unitary generators allow summations over decomposition terms to be avoided, reducing the repetition cost.The simplifications apply when the objective is directly measurable or the generator can be implemented as a unitary gate.
  • QAOA specialization: For QAOA, the objective uses Z-Pauli terms measurable in the computational basis, simplifying analytical-gradient evaluation and repetition-cost expressions.

V. A REPRESENTATIVE QUANTUM-CLASSICAL ALGORITHM: QAOA

QAOA is presented as a representative variational algorithm for constraint-satisfaction problems, with parameterized alternating circuits optimized to maximize the expected number of satisfied clauses. Its structured ansatz is compact and becomes exact in the infinite-depth limit, while small-depth performance remains an open question.

  • Study scope: The paper studies how precision, repetition cost, and optimization performance interact for QAOA within the broader variational-algorithm setting.The QAOA-specific gradient and objective-cost formulas specialize the general expressions developed earlier.
  • Problem encoding: QAOA converts a binary constraint-satisfaction objective into a quantum observable by replacing each variable with a corresponding Z-Pauli operator.The objective counts satisfied clauses, and the quantum version is evaluated through expectation values.
  • State preparation: QAOA prepares trial states by alternating two parameterized quantum operations from the balanced superposition reference state.A depth-p circuit uses 2p parameters (γ, β).
  • Objective evaluation: The objective is estimated by computational-basis measurements, averaging the clause value over repeated measurement outcomes.
  • Ansatz properties: QAOA uses relatively few parameters and has an ansatz whose exact solution is reachable as circuit depth p tends to infinity.The paper notes that performance at small p remains an open question.

VI. NUMERICAL STUDY OF QAOA

The numerical study evaluates QAOA on MAX-CUT instances using gradient-free and quasi-Newton optimizers with finite or analytical gradients under varied precision settings. Because the objective is non-convex, repeated runs from random initial parameters are used to address attraction to local maxima.

  • Optimization methods: The compared optimizers are gradient-free Nelder–Mead and BFGS quasi-Newton methods using either finite-difference or analytical gradients.
  • Convergence limitation: Because the objective is non-convex, the optimizers are not guaranteed to reach the global maximum and may instead converge to a local maximum.The study therefore starts each instance from multiple randomly chosen parameter values.
  • Precision modeling: The simulations vary observable precision ϵ and, when applicable, the finite increment δ or analytical-gradient precision ϵ′′.
  • Simulation setting: All numerical data are computed for N = 16 qubits, with stochastic observable errors drawn uniformly from [−ϵ̃, ϵ̃].

A. Single instance

Single-instance analyses examine how initialization, optimization method, finite precision, and sampling cost shape QAOA performance. Different runs reach distinct states, so practical use selects the run with the highest achieved clause fraction while accounting for all explored runs.

  • Initialization and run selection: Different initial parameter values lead optimization runs to distinct states, motivating selection of the run with the highest achieved R_p(γ, β).The selected run generates the approximated answer, but its repetition cost alone does not represent the full exploration cost.
  • Initialization and run selection: QAOA analyses use multiple initial conditions because good starting values cannot be selected a priori.The study performs N_r = 16 runs per instance and optimization method.
  • Precision and optimization: Finite precision does not always improve performance when ϵ increases, because inaccurate gradient estimates can help escape a local maximum's attraction basin.The paper relates this behavior to stochastic gradient methods.
  • Optimization methods: Gradient-based finite differences require more samples than Nelder-Mead at fixed accuracy ϵ but achieve a higher fraction of satisfied clauses.Increasing the finite-difference increment δ reduces sampling cost with limited effects on optimization effectiveness.
  • Optimization methods: The analytical-gradient cost increase is not supported by considerable optimization improvement.The comparison considers finite-difference and analytical-gradient methods alongside gradient-free optimization.

B. Multiple instances

Across 128 instances, the study compares achieved clause fractions and repetition costs over circuit depths and optimization methods. Deeper QAOA circuits are more powerful but harder to optimize, while quasi-Newton methods consistently outperform Nelder-Mead without greatly increasing repetition cost.

  • Evaluation protocol: The reported sampling cost includes N_r = 16 optimization runs per instance, not only the repetitions of the post-selected best run.The table reports averages, standard deviations, medians, and repetition costs for the highest fraction encountered.
  • Circuit depth: Deeper QAOA circuits are strictly more powerful than shallower ones, while their optimization task becomes more challenging.At small p, different optimization methods converge to nearly the same maximum value.
  • Optimization methods: Quasi-Newton optimization consistently outperforms Nelder-Mead, while repetition cost typically differs by about a factor of 5 for finite differences with δ = 0.1.The comparison covers circuit depths p = 1 through p = 8.
  • Scope and limitations: The study examines only problem size N = 16, leaving the scaling cost of optimization with problem size for future analysis.The realistic form of the stochastic finite-precision term is also deferred to ensuing studies.
  • Finite precision: Finite-precision objective estimates can slow optimization or direct it toward a sub-optimal local maximum.Because the optimization maximizes a stochastically perturbed objective, finite precision can also overestimate the effective maximum; with uniform noise in [−ϵ, ϵ], the absolute bias is at most ϵ.

VII. DISCUSSION AND CONCLUSIONS

The discussion examines optimization choices, measurement costs, stopping criteria, and scope limits for hybrid variational algorithms, with numerical analysis focused on QAOA.

  • Limitations: The numerical study is limited to a QAOA variant and does not establish that gradient or quasi-Newton methods are generally best for hybrid schemes.Nelder–Mead is only one gradient-free solver, and other gradient-free methods may perform better in some contexts.
  • Limitations: The conclusions are not expected to extend directly to p = O(10^3) or larger, including moderately large molecules in the UCC+VQE approach.The paper also notes that quantum hardware noise can increase estimator variance and bias the objective function, with mitigation but not elimination from variational robustness.
  • Optimization methods: The study extends hybrid variational optimization beyond derivative-free approaches by analyzing first-order and quasi-Newton methods, specifically BFGS.The gradient and its computation are presented for hybrid algorithms and QAOA.
  • Experimental relevance: Stopping conditions are experimentally important because they determine when the overall optimization process terminates after each iteration’s repetition cost is incurred.The paper explicitly provides stopping conditions and distinguishes them from the precision determining repetitions per iteration.
  • Experimental relevance: The comparison emphasizes finite precision, estimator bias, and repetition cost as experimentally relevant measures of optimization feasibility.The simulations include finite-precision and finite-difference-gradient bias and relate performance to repetition cost.

Appendix A: Repetition cost for quantum variational algorithms

The appendix formalizes repetition costs for estimating observables and describes the stopping rules and optimization methods used in the study.

  • Repetition cost: Observable estimates are obtained by repeatedly preparing the quantum state, measuring it, and averaging outcomes over independent repetitions.For finite repetitions, the estimator fluctuates around the expectation value, with variance inversely proportional to the number of samples.
  • Repetition cost: The square root of the estimator variance defines its precision, linking desired accuracy to the number of repetitions required.The appendix denotes this precision by ϵ and discusses finite-repetition accuracy.
  • Optimization methods: Nelder–Mead is derivative-free and evaluates the objective at 2p + 1 simplex vertices before updating the associated points.The lowest-objective vertex is updated according to the method’s rules.
  • Optimization methods: BFGS uses line searches based on a quadratic approximation reconstructed from objective values and gradient components.The study considers finite-difference and analytical-gradient variants; analytical gradients do not introduce bias in objective-derivative estimation.
Loading 1701.01450v1…