An Adaptive Optimizer for Measurement-Frugal Variational Algorithms

Jonas M. Kübler; Andrew Arrasmith; Lukasz Cincio; Patrick J. Coles

Source-linked AI summary

An Adaptive Optimizer for Measurement-Frugal Variational Algorithms

Jonas M. Kübler, Andrew Arrasmith, Lukasz Cincio, Patrick J. Coles

arXiv:1909.09083v3Sep 19, 2019quant-ph

TL;DR

VHQCAs may require prohibitively many measurements to converge, motivating more measurement-frugal optimization. The paper introduces iCANS, which adaptively selects shots per iteration and partial derivative, and finds strong performance across tested tasks, especially with realistic noise.

Problem
VHQCAs may require prohibitively many measurements for convergence, particularly in applications requiring chemical accuracy.
Method
The paper introduces iCANS, an adaptive stochastic-gradient optimizer that selects shot counts for each iteration and each partial derivative.
Results
iCANS usually performs best across the tested optimization tasks and compares especially well with other optimizers under realistic hardware noise.
Takeaways & Limitations
iCANS is a measurement-frugal optimizer applicable across VHQCAs, including algorithms with or without Pauli-operator measurement sets.
Takeaways & Limitations
The shot-cap heuristic can remove the guarantee that the expected-gain parameter γ_i is maximized or even positive.

Abstract

from arXiv · show

Variational hybrid quantum-classical algorithms (VHQCAs) have the potential to be useful in the era of near-term quantum computing. However, recently there has been concern regarding the number of measurements needed for convergence of VHQCAs. Here, we address this concern by investigating the classical optimizer in VHQCAs. We introduce a novel optimizer called individual Coupled Adaptive Number of Shots (iCANS). This adaptive optimizer frugally selects the number of measurements (i.e., number of shots) both for a given iteration and for a given partial derivative in a stochastic gradient descent. We numerically simulate the performance of iCANS for the variational quantum eigensolver and for variational quantum compiling, with and without noise. In all cases, and especially in the noisy case, iCANS tends to out-perform state-of-the-art optimizers for VHQCAs. We therefore believe this adaptive optimizer will be useful for realistic VHQCA implementations, where the number of measurements is limited.

1 Introduction

VHQCAs shift much of the computation to classical optimization but face concerns about measurement costs for convergence. iCANS addresses this by adapting shot counts per iteration and partial derivative, and performs strongly across tested applications, especially with noise.

VHQCAs use quantum devices to estimate cost functions while classical optimizers minimize them across applications including ground-state preparation and compiling.
Prohibitively many quantum measurements may be required for VHQCAs to converge, particularly when chemical accuracy is needed.
iCANS frugally adjusts the number of shots both for each optimization iteration and for each partial derivative.
iCANS adapts the CABS optimizer to account for differences in the shot counts needed to estimate individual gradient components.
Across variational quantum eigensolver and compiling implementations, iCANS on average performs best, especially under simulated device noise.
The optimizer can complement Pauli-operator measurement advances and also apply to VHQCAs that do not use Pauli-operator sets.

2 Background

Gradient descent updates parameters downhill, but VHQCAs must estimate noisy gradients from finite measurements or finite differences. These estimation choices create trade-offs among precision, cost, and bias.

2.1 Gradient Descent: Gradient descent updates parameters in a locally downhill direction, with the learning rate controlling step size and progress.
2.1 Gradient Descent: Deterministic gradient descent is guaranteed to converge when the learning rate satisfies α < 2/L for a Lipschitz constant L.
2.2 Gradient Estimation: VHQCAs often require gradient estimation because exact gradients can be expensive to estimate or lack accessible analytic formulas.
2.2.1 Analytic Gradients: For analytic VHQCA gradients, finite measurements and device noise determine precision even when the derivative formula is analytic.
2.2.1 Analytic Gradients: For bounded-eigenspectrum operators, recursive derivative formulas provide a useful upper bound on the Lipschitz constant.
2.2.2 Finite Differencing: Finite-difference gradients introduce statistical noise and systematic error scaling with δ2, motivating possible reductions of δ during optimization.

2.3 Noisy Gradient Descent

Noisy gradient descent must balance estimation cost against update precision, typically using heuristics or adaptive methods. Adam adapts learning rates per gradient component, while CABS selects sample counts to improve expected gain per sample.

2.3.1 Stochastic/Mini-Batch Gradient Descent: Noisy stochastic-gradient methods seek rapid convergence by balancing sample cost, gradient precision, learning rate, and iteration count.
2.3.1 Stochastic/Mini-Batch Gradient Descent: VHQCAs often require rough estimates of unknown, time-varying device-noise bias when choosing stochastic-gradient quantities.
2.3.2 Adam: Adam adapts each search direction using exponential averages of the first and second gradient moments.
2.3.3 CABS: CABS chooses the sample count that maximizes expected gain per sample at each iteration.
2.3.3 CABS: CABS estimates inaccessible covariance and gradient quantities, then selects samples using measurements from the previous point.
2.3.3 CABS: The proposed VH QCA optimizer builds on CABS but differs from it in its adaptation to variational quantum algorithms.

2.4 SPSA

SPSA estimates a descent direction from a randomly sampled perturbation rather than estimating the full gradient. Its learning rate and finite-difference parameters follow decreasing schedules, while quantum implementations may use multiple measurements.

2.4 SPSA: SPSA samples a random direction and estimates the slope along it instead of estimating the full gradient.
2.4 SPSA: The sampled directional slope determines a downhill update in the chosen direction.
2.4 SPSA: The perturbation direction’s element-wise inverse is used in the SPSA slope estimate.
2.4 SPSA: Convergence requires decreasing both the finite-difference parameter c_t and learning rate α_t, commonly through a prefixed schedule.
2.4 SPSA: Quantum implementations may estimate the cost function with more than one measurement rather than SPSA’s original single-measurement formulation.

2.5 Sequential Subspace Search

Sequential subspace-search methods optimize subsets of parameter space independently, with Powell using sequential line searches and SOFF exploiting analytically determined coordinate-axis minima in applicable VHQCAs.

Sequential subspace search: Subspace-search methods iteratively optimize a cost function over a sequence of independently handled parameter subspaces.This decomposes a multivariate minimization problem into simpler subproblems.
Powell method: Powell performs sequential line searches along supplied search vectors, then replaces the vector associated with the greatest displacement.The replacement scheme is intended to accelerate convergence and prevent cyclic behavior.
Powell method: Powell is gradient-free because its scalar displacements can be found with Brent’s method or another gradient-free scalar optimizer.Using gradient-based scalar optimization would remove Powell’s gradient-free character.
SOFF: SOFF fits the cost function along coordinate axes to compute analytic minima and determine optimal displacements when its VHCCA assumptions apply.Its coordinate-axis restriction prevents arbitrary search directions, so it is not quite a special case of Powell’s method.

3 Adaptive Shot Noise optimizer

The paper adapts CABS into CANS and then iCANS, which allocates shots adaptively across iterations and individual gradient components. iCANS estimates per-component gains and shot requirements, with optional safeguards for noisy or unstable updates.

CANS: CANS adapts CABS to VHQCAs by replacing inaccessible quantities with estimates suited to quantum-shot measurements.The construction uses the parameter-shift rule, empirical gradient-component variances, and an estimate of the gradient norm.
iCANS: iCANS extends CANS by allowing each gradient component to receive a different number of shots.The method is motivated by independently estimated partial derivatives and aims to distribute measurements more effectively.
Algorithmic procedure: The algorithm uses a minimum shot count, a total shot budget, a Lipschitz constant, moving-average parameters, and a gradient-norm bias as inputs.It initializes all components at the minimum shot count and iterates while the total budget remains unused.
iCANS: iCANS defines G_i as a lower bound on the gain from updating parameter θ_i and γ_i as the expected gain per shot.The suggested shot count s_i is chosen using these per-component quantities.
iCANS: iCANS caps every component’s shot count at s_max, chosen from the component with the highest expected gain per shot.The cap reflects the empirical observation that near-converged parameters can require many shots, whereas parameters far from convergence can require fewer.
Safeguards: The optional learning-rate check distinguishes iCANS1 from iCANS2 by reducing steps when needed to enforce positive expected gain.The check restores the guarantee that E[G] > 0, while smoothing uses bias-corrected exponential moving averages for noisy problems.

4 Implementations

The implementations evaluate iCANS and comparator optimizers on variational compiling, Heisenberg-chain VQE, and Ising-chain scaling tasks under noiseless and noisy simulation. The studies vary ansatzes, system settings, shot budgets, and optimizer hyperparameters to compare performance.

Benchmark tasks: The study compares iCANS1 and iCANS2 with established optimizers on variational quantum compiling and Heisenberg spin-chain VQE.Both tasks use one hundred random seeds or initial points, with noiseless and noisy simulations.
Optimization settings: The iCANS hyperparameters are α = 0.1, µ = 0.99, and b = 10−6, except for scaling experiments where α = 1/L is used.The alternative scaling choice accounts for the linear growth of the Lipschitz constant with system size.
Optimization settings: Comparator algorithms use fixed shots per operator measurement, denoted A-s, alongside empirically chosen hyperparameters.The reported figures and tables show analytical costs and energies from optimizer output parameters, although optimization used finite statistics and, where indicated, hardware noise.
Performance measures: Figure 2 reports average compiling cost versus total shots, while Figure 3 reports average ∆E versus total shots for Heisenberg VQE.For both figures, panels a and b correspond to noiseless and noisy cases, respectively.
Scaling comparison: The scaling comparison evaluates noiseless VQE on 4, 6, 8, 10, and 12 qubit Ising spin chains using the Fig. 1(b) ansatz with D = 3.The Ising-chain setting uses open boundary conditions and g = 1.5; this ansatz performed significantly better than Fig. 1(a) for the task.

5 Discussion

Across the tested optimization tasks, iCANS usually performed best within the available shot budget, while competing optimizers exhibited task- and hyperparameter-dependent strengths and limitations. The fixed-shot results reflect a trade-off between update precision and the number of iterations affordable under a total shot budget.

SOFF: SOFF trained quickly in low-noise settings but reached a precision floor and struggled more when hardware noise distorted the optimization landscape.SOFF-100 was nevertheless best for some compilation and Heisenberg VQE cases at specific shot budgets.
Adam: Adam showed late optimization instability with the chosen hyperparameters and shot counts, although Adam-100 slightly outperformed iCANS1 for noisy compilation.Adam was usually competitive before reaching the point where it stopped improving.
SPSA: SPSA did not outperform iCANS in the reported cases, but SPSA-100 was the most competitive alternative for noiseless Heisenberg VQE.SPSA was also the most sensitive method to hyperparameter perturbations among those studied.
Overall comparison: iCANS1 or iCANS2 usually provided the best result for each total shot budget, including larger Ising VQE systems.iCANS1 empirically usually outperformed iCANS2, while iCANS2 reduced sensitivity to the input learning rate.
Shot-budget trade-off: Using fewer shots permits more iterations but noisier updates, whereas more shots improve update precision while reducing the number of iterations.This precision-versus-iteration trade-off motivates adaptive shot allocation.

6 Conclusions

The paper addresses the measurement burden of VHQCAs by introducing adaptive optimizers that allocate measurements separately to each partial derivative. Numerical results indicate performance comparable to or better than state-of-the-art optimizers, especially under realistic hardware noise.

Motivation: VHQCAs require measurement-frugal optimizers because preparing and measuring quantum states is likely to limit optimization efficiency.The concern is particularly relevant when convergence requires many shots.
Contribution: iCANS1 and iCANS2 dynamically determine the number of measurements for each partial derivative at every gradient-descent step.iCANS1 keeps a fixed learning rate, whereas iCANS2 limits steps so expected gain remains positive.
Results: The numerical results indicate that iCANS1 and iCANS2 may perform comparably or better than other state-of-the-art optimizers, especially with realistic hardware noise.The paper evaluates these optimizers in the context of measurement-frugal, noise-resilient VHQCAs.
Related evidence: Small shot counts can provide rapid improvement during early training, further motivating an adaptive measurement strategy.This observation was reported in a related study of stochastic-gradient descent for VHQCAs.
Future work: A proposed future direction is extending the frugal adaptive approach to non-gradient methods such as SPSA.The paper identifies this as a potential direction rather than a completed capability.

A The Expected Lower Bound on the Gain per Shot

The derivation develops a lower bound on expected optimization gain per shot and then refines it to a per-partial-derivative expression. It relies on local smoothness and statistical assumptions about gradient estimates.

Derivation: The analysis begins by extending a lower-bound derivation for expected gain per shot to expected gain per shot per partial derivative.This provides the theoretical quantity used to guide individual shot allocation.
Derivation: A quadratic Taylor approximation around the current parameter point is used to approximate the gain after the update θ′ = θ − αg.The gain is interpreted as the change in the cost function expected from the update.
Assumptions: If gradients are Lipschitz continuous, the expected gain can be lower-bounded using the Lipschitz constant L.The Lipschitz condition supplies the smoothness control needed for the bound.
Assumptions: The gradient estimates are assumed to have mean ∇f(θ) and covariance Σ/s, where s is the number of shots.The shot count therefore controls the statistical covariance of the estimate.
Derivation: Dividing the expected-gain bound by the shot count yields an expected lower bound on gain per shot.The derivation then rewrites this expression to obtain the per-partial-derivative form.
Final expression: The final expression defines γ_i = E[G_i]/s_i and replaces the partial derivative and variance with estimators g_i and S_i.These estimated quantities produce the operational bound used by the adaptive method.

B CANS Algorithm

CANS is presented as an adaptation of the CABS algorithm for the VHQCA setting.

Algorithm: CANS adapts the classical Coupled Adaptive Batch Size algorithm to variational hybrid quantum-classical applications.The algorithm is presented in the paper's implementation description.

C Cumulative probability distributions for 3-qubit implementations

The section compares optimizer performance on variational compiling and Heisenberg spin-chain VQE tasks across shot budgets using cumulative probability distributions. It also specifies the stochastic-gradient procedure with CANS, which evaluates gradient estimates and tracks individual derivative variances during optimization.

Cumulative probability distributions: Cumulative probability distributions compare cost values for variational compiling and energy differences from the ground state for Heisenberg spin-chain VQE across shot budgets.The comparisons use one hundred random starts, with separate panels for different total-shot values N.
CANS stochastic-gradient procedure: CANS evaluates each gradient component with s measurements using the parameter-shift rule and returns both the estimated gradient vector and individual derivative variances.These variance estimates are used alongside the gradient during the stochastic-gradient procedure.
CANS stochastic-gradient procedure: The procedure starts from θ0 with a minimum shot count and total budget N, then updates running quantities from the variance vector S and gradient g while the accumulated shots remain below N.The listed inputs include the learning rate α, minimum shots smin, total-shot budget N, Lipschitz constant L, running-average constant µ, and gradient-norm bias b.
Cumulative probability distributions: Curves farther left indicate better optimization because they correspond to lower costs or smaller energies above the ground state.This interpretation applies to the compiling and VQE distributions, respectively.