Latency-aware adaptive shot allocation for run-time efficient variational quantum algorithms

As a typical VQA, we focus on problems formulated as the minimization of the cost function

given by the expectation value of a Hermitian operator $H$. In VQE Peruzzo et al. (2014); Bauer et al. (2016); Kandala et al. (2017), we attempt to find a good approximation of the ground state energy of a quantum mechanical Hamiltonian $H$ by minimizing the cost function (1). It is expected that a quantum computer outperforms in computing the expectation value $\bra{\psi(\bm{\theta})}H\ket*{\psi(\bm{\theta})}$ of a quantum mechanical Hamiltonian of some complex systems. Hence, a quantum advantage might be achieved by only using the quantum device to compute the expectation value, while the parameter vector $\bm{\theta}^{(k)}$ is classically optimized. That is why the VQE is a candidate for a practical application of NISQ devices. For a successful VQE, it is important to find an efficient classical optimizer as well as an expressive and trainable ansatz $\ket{\psi(\bm{\theta})}$ which is realizable in a quantum computer. Our focus in this paper is to find an efficient optimizer with respect to the total wall-clock running time and the economic cost as practical figures of merit. Especially, we focus on the gradient descent optimizers.

One possible way to approximately estimate the partial derivative is the numerical differentiation:

where $\bm{e}_{i}$ is the unit vector in the $i$-th direction and $\delta$ is a small number. However, as the finite numbers of measurements for the estimations of the cost function values introduce statistical error, this estimation is not good Harrow and Napp (2021). Instead, we can use an analytic expression of the gradient of the cost function in VQAs. If the ansatz is given by parametric gates in the form of $U_{i}(\theta_{i})=\exp[-i\theta_{i}A_{i}/2]$ with $A_{i}^{2}=I$ and fixed gates, we can use the following so-called parameter shift rule Mitarai et al. (2018); Schuld et al. (2019):

For example, hardware efficient ansatz actually fits in this form. More generally, the partial derivatives may be calculated by general parameter shift rules with some $R_{i}$ number of parameter shifts Wierichs et al. (2022):

Hence, the gradient can be computed by evaluating the cost function at shifted parameters and taking their linear combination. We remark that the statistical error in the estimation of the cost function still remains due to the finiteness of the number of quantum measurements even if we use the analytic form.

The target Hamiltonian $H$ often cannot be measured directly in a quantum computer (e. g. Hamiltonians in quantum chemistry). In such a case, we decompose $H$ into directly measurable operators such as Pauli operators $P_{i}$ as

In general, we cannot measure all the terms simultaneously because this decomposition includes noncommuting Pauli operators. To efficiently measure the observables $P_{i}$, we need to group simultaneously measurable observables. Finding an efficient strategy to choose appropriate measurements is an important problem which have been intensively studied O’Malley et al. (2016); Kandala et al. (2017); Hamamura and Imamichi (2020); Crawford et al. (2021); Hempel et al. (2018); Izmaylov et al. (2020); Vallury et al. (2020); Verteletskyi et al. (2020); Zhao et al. (2020); Wu et al. (2023). We do not go into details regarding the grouping problem in this paper. Once the groups $G_{j}$ of the commuting operators are fixed, another issue is how to allocate the number of shots to each group under a given shot budget $s_{\mathrm{tot}}$. Although this is also a nontrivial problem, we take the weighted random sampling (WRS) strategy Arrasmith et al. (2020) in this paper. In WRS, each $j$-th group is randomly selected with probability $\sum_{i\in G_{j}}|c_{i}|/\sum_{k=1}^{N}|c_{k}|$ in each measurement. We can implement this procedure by sampling the number $s^{(j)}$ of shots for each $j$-th group from the multinomial distribution for $s_{\mathrm{tot}}$ independent trials with probability distribution $p_{j}=\sum_{i\in G_{j}}|c_{i}|/\sum_{k=1}^{N}|c_{k}|$. If we allocate deterministic number of shots, some groups may never be measured for small $s_{\mathrm{tot}}$, which results in the bias in the estimation of the expectation value of $H$. In WRS, we obtain an unbiased estimator of the expectation value of $H$ for any small number of shots $s_{\mathrm{tot}}$.

Gradient descent is a very standard approach to optimization problems. In the gradient descent, we minimize the cost function $f(\bm{\theta})$ by iteratively updating the parameter vector $\bm{\theta}\in\mathbb{R}^{d}$ as

where $\alpha$ is the learning rate which is a hyperparameter. In some problems such as machine learning tasks, $\bm{\nabla}f(\bm{\theta}^{(k)})$ in (6) can be replaced with an estimator $\bm{g}(\bm{\theta}^{(k)})$ of it, which is a random variable. Gradient descent using a random estimator of the gradient is called stochastic gradient descent (SGD). When the estimator is unbiased, rigorous convergence guarantees are available under appropriate conditions Shalev-Shwartz and Ben-David (2014); Karimi et al. (2016); Sweke et al. (2020). Moreover, the stochasticity can rather help to avoid local minima and saddle points Bottou (1991). Thus, SGD is often efficient not only because of saving the resource to compute the gradient.

In VQAs, we have no access to the full gradient $\bm{\nabla}f$ due to the essentially random nature of the quantum measurement. Hence, the gradient descent in VQAs is inevitably stochastic in some extent depending on the number of measurements used to estimate the gradient. Although using large numbers of measurements results in accurate estimation of the full gradient, the accurate estimation of the gradient is not necessarily beneficial, as the stochasticity can be rather advantageous in SGD. In fact, it is reported that using not large numbers of measurements for gradient evaluations effectively results in the implementation of SGD Harrow and Napp (2021), and is actually beneficial in the optimization Sweke et al. (2020); Liu et al. (2022). However, the accuracy of the estimation of the gradients also restricts the final precision of the optimization. Therefore, the numbers of measurements for evaluation of the gradients during the optimization is an important hyperparameter which determines the effectiveness of the optimizer. While the numbers of measurements as well as the learning rate are usually tuned heuristically, some papers propose algorithms to adaptively set the numbers of measurements in SGD as we review later in more detail (Sec. II.5) Kübler et al. (2020); Arrasmith et al. (2020); Gu et al. (2021). The adaptive allocation of appropriate numbers of measurement shots for practically efficient SGD is the main focus of our study.

For the selection of the learning rate $\alpha$, we can make use of the Lipschitz continuity of the gradient of the cost function of the VQE:

where $L$ is called a Lipschitz constant. According to Eq. (7), we can make the change in the gradient per single descent step small by taking small enough $\alpha$ in accordance with the size of $L$. In this way, it is expected that the course of the optimization well follows the gradient. In fact, for the exact gradient descent, the convergence is guaranteed if $\alpha<2/L$ Balles et al. (2017). As seen later, the Lipschitz constant is also used to set the number of shots in our algorithm in a similar manner to Kübler et al. (2020). For the cost function of the VQE, we have access to a Lipschitz constant. Especially, for the case with the parameter shift rule Eq. (3), we see that any order of the partial derivatives of $f$ is upper bounded by the matrix norm $\|H\|$ of $H$ by recursively applying Eq. (3). Then, if the parameter vector is $d$-dimensional, we have the following upper bound of the Lipschitz constant Sweke et al. (2020); Gu et al. (2021)

When $H$ is decomposed as (5), the norm is bounded as $\|H\|\leq\sum_{i=1}^{N}|c_{i}|$. We remark that smaller estimation of $L$ results in good performance of optimizers using $L$ in general. If we need tighter estimation of $L$ than (8), we can search for smaller $L$ in a similar manner to hyperparameter tuning.

Adaptive moment estimation (Adam) Kingma and Ba (2014) is a variation of a modified SGD which adaptively modifies the descent direction and the step size using the estimations of first and the second moments of the gradient. In Adam, we use the exponential moving averages

as the estimations of the moments, where the multiplication of the vector is taken component-wise, $\beta_{1},\beta_{2}$ are the hyperparameters which determines the speed of the reflection of the change in the gradient. Then, we update the parameter according to

where $\alpha_{k}$ is the step size which depends on $k$ in general, and $\epsilon$ is a small constant for the numerical stability. The bias-corrected version of $\bm{m}_{k}$ and $\bm{v}_{k}$ and constant $\alpha_{k}$ are used in the original proposal of Adam, which is equivalent to using $\alpha_{k}=\alpha\sqrt{1-\beta_{2}^{k}}/(1-\beta_{1}^{k})$ with a constant $\alpha$ if we neglect $\epsilon$. A possible advantage of Adam is that the step size for each component is adjusted component-wise, which gives an additional flexibility. In fact, Adam is known to work well for many applications. In this paper, we investigate how to exploit Adam’s power in VQAs by using adaptively determined appropriate number of shots in Sec. III.2.

As explained in Sec. II.3, the number of shots for the estimation of the gradient is an important hyperparameter of SGD for VQE. Using too large number of shots not only results in too expensive optimization, but also loses the benefit from the stochasticity. On the other hand, too small number of shots results in the fail of the accurate optimization due to the statistical errors. In general, the required number of shots tends to be small in the early steps in SGD, and the required number increases as the optimization progresses. Thus, it is hard for SGD to be efficient if we give a fixed number of shots used throughout the optimization process. One option to circumvent this problem is to dynamically increase the number $s$ of shots following a fixed schedule, e. g. $s=\lfloor s_{0}r^{k}\rfloor$ with the initial number $s_{0}$ and a hyperparameter $r$. However, very careful hyperparameter tuning is needed for such a strategy to be efficient Gu et al. (2021). Hence, an adaptive method to determine appropriate numbers of shots step by step in SGD optimizations is desired.

Balles et al. Balles et al. (2017) introduced Coupled Adaptive Batch Size (CABS) method for choosing the sample size in the context of optimizing neural networks by SGD. Inspired by CABS, Kübler et al. Kübler et al. (2020) proposed individual-Coupled Adaptive Number of Shots (iCANS) for choosing the number of shots for SGD optimizations in VQAs. Both algorithms assign the sample size so that the expected gain per single sample is maximized. To do so, the expectation value of a lower bound of the gain is considered based on the following inequality:

where $\bm{g}(\bm{\theta}^{(k)})$ is an estimator of the gradient. For VQAs, when each $i$-th component of the gradient is estimated by $s_{i}$ shots, the expectation value of this lower bound $\mathcal{G}(\bm{s})$ reads

where $\bm{s}$ denotes $(s_{1},s_{2},\cdots,s_{d})$, and $\sigma_{i}$ is the standard deviation of $i$-th component $g_{i}(\bm{\theta}^{(k)})$ of the random estimator of the gradient. We remark that to guarantee that $\mathbb{E}[\mathcal{G}]$ is positive, we need Balles et al. (2017)

The gain $\mathcal{G}(\bm{s})$ can be divided into a sum of the individual contributions $\mathcal{G}_{i}(s_{i})$ from each $i$-th component given as

where $\partial_{i}f:=\frac{\partial f}{\partial\theta_{i}}$. In iCANS, we assign a different number $s_{i}$ of shots for estimating each component of the gradient by individually maximizing $\gamma_{i}:=\mathbb{E}[\mathcal{G}_{i}(s_{i})]/s_{i}$. Then, the maximization of $\gamma_{i}$ yields the suggested number of shots Kübler et al. (2020)

We have to note that this formalism is only valid when $\alpha<2/L$. The suggested number of shots implies that the larger number of shots should be assigned as the statistical noise $\sigma_{i}^{2}$ gets larger compared to the signal $\partial_{i}f(\bm{\theta}^{(k)})$. Hence, $s_{i}$ tends to become large as the optimization progresses. Moreover, a restriction on the number of shots not to exceed that of the highest expected gain is introduced in iCANS for further shot frugality. That is, we impose $s_{i}\leq s_{\max}$ with the number $s_{\max}$ given by

Fortunately, a Lipschitz constant $L$ to calculate $s_{i}$ is accessible in VQAs from Eq. (8). However, the quantities $\sigma_{i}^{2}$ and $\partial_{i}f(\bm{\theta}^{(k)})$ are not accessible because $s_{i}$ must be calculated before we estimate the gradient. Then, in order to implement iCANS, we replace these quantities with accessible quantities calculated from the previous estimations since it is expected that the change in these quantities along the course of SGD is not so large. For increased stability, it is suggested to use bias-corrected exponential moving averages of the previous iterations in place of $\sigma_{i}^{2}$ and $\partial_{i}f(\bm{\theta}^{(k)})$. We also employ this strategy in our algorithm.

Gu et al. Gu et al. (2021) proposed another algorithm global-CANS (gCANS) with a different rule to allocate the number of shots as a variant of CANS. In gCANS, the rate of the expected gain is maximized globally, whereas each individual component is maximized in iCANS. In other words, the number of shots $s_{i}$ is determined so that

is maximized. Then, the suggested rule is

Inaccessible quantities are also replaced by the exponential moving averages in gCANS. Both iCANS and gCANS have shown its efficiency in terms of the total number of shots used as a figure of merit Kübler et al. (2020); Gu et al. (2021), and according to Ref. Gu et al. (2021), gCANS performs better than iCANS. However, in practice, the total time consumption is more important rather than the total number of shots. The latency occurs with circuit-switching and the communication is usually much larger than the single-shot acquisition time Karalekas et al. (2020); Menickelly et al. (2022). As for the economic cost for using a cloud quantum computing service, the task cost is usually much more expensive than a single-shot cost aws . Although Ref. Gu et al. (2021) also showed that gCANS has high frugality of task cost of Amazon braket pricing and the number of the iterations, they does not explicitly consider the performance with respect to the total time or the total economic cost taking into account the latency or task cost.

On the other hand, Menickelly et al. Menickelly et al. (2022) investigated the performance of the optimizers of VQAs in terms of the total time including the latency. They proposed a new optimizer, SHOt-Adaptive Line Search (SHOALS). SHOALS makes use of stochastic line search based on Paquette and Scheinberg (2020); Berahas et al. (2021); Jin et al. (2021) for the better iteration complexity. In SHOALS, the number of shots used for estimating the gradient is adaptively determined so that the error in the estimations will be bounded in such a way that it does not interfere with the gradient descent dynamics. The number of shots used for the cost function evaluations for the line search is also adaptively assigned in a similar manner. The suggested number of shots is also basically proportional to the ratio of the noise to the signal, though the gain is not taken into account. They have shown that SHOALS actually achieves better iteration complexity scaling $O(\epsilon^{-2})$ compared to that of the simple SGD $O(\epsilon^{-4})$, where $\epsilon$ is the precision to be achieved in expectation. In that sense, they suggest SHOALS as a high-performing optimizer in terms of the total time in the presence of the large latency. However, SHOALS does not take into account the explicit value of the latency. To our best knowledge, no optimizer has been proposed in such a way that the value of the latency is explicitly reflected to the optimization strategy. Therefore, a question arises here as to what extent the performance of an optimizer in terms of the total time consumption (or the economic cost) is improved by designing it with an explicit reflection of the latency value.

The simplest idea to take into account the latency is to modify the shot allocation rules of iCANS and gCANS in such a way that we maximize the gain per unit time (or economic cost) including the latency instead of the gain per single shot. In other words, to modify iCANS to take into account the latency overhead, we assign the number of shots $s_{i}$ to estimate $i$-th component of the gradient such that

is maximized, where $m_{i}$ is the number of circuits used to estimate $i$-th component of the gradient. For the case where $m_{i}$ is a random variable as is the case with WRS, we need to replace $m_{i}$ with some available estimated quantity. We deal with this problem in detail in Sec. III.3. Here, we assume that a single round of the communication is enough to estimate all the components of the gradient. This maximization yields the optimal number of shots as

where $R_{i}:=(c_{2}m_{i}+c_{3}/d)/c_{1}$ is the ratio of the overhead per evaluation of each $i$-th component of the gradient to the single-shot acquisition time. All the steps except for the number of shots are the same as the original iCANS. In particular, inaccessible quantities $\sigma_{i}^{2}$ and $\partial_{i}f(\bm{\theta}^{(k)})$ are replaced with the bias-corrected exponential moving averages of the previous iterations. We call this shot allocation strategy Waiting time-Evaluating Coupled Adaptive Number of Shots (weCANS). To distinguish between iCANS-based version and gCANS-based version (introduced below), we call them weCANS(i) and weCANS(g) respectively. In this way, we take the explicit value of the latency into account. Especially, the term proportional to the ratio $R_{i}$ represents the increase in the number of shots to deal with the latency. Indeed, as the latency gets large, taking large iteration number becomes more expensive. Hence, it can be more efficient to take larger number of shots in a single iteration as the latency gets larger compared to $c_{1}$. The shot number (22) concretely suggests how large number of shots is appropriate based on the estimation of the gain. For large ratio $R_{i}$ of the latency, the increase in the number of shots reflecting the latency roughly scales linearly to $\sqrt{R_{i}L\alpha/(2-L\alpha)}\sigma_{i}/\partial_{i}f(\bm{\theta}^{(k)})$, which implies that the effect of the latency tends to be reflected more for later optimization steps as the ratio of the statistical noise to the signal gets larger in general.

A waiting time-evaluating version of gCANS can also be obtained by maximizing

This yields the weCANS(g) shot allocation rule

where $R:=(c_{2}\sum_{i=1}^{d}m_{i}+c_{3})/c_{1}$ is the ratio of the overhead per iteration to the single-shot acquisition time. For weCANS(g), the increase in the number of shots reflecting the latency scales similarly to weCANS(i) as $\sim\sqrt{RL\alpha/(2-L\alpha)}\sigma_{i}/\|\nabla f(\bm{\theta}^{(k)})\|$. Obviously, the leading-order of the gain in the single-shot acquisition time $c_{1}r_{\mathrm{g}}(\bm{s})$ is at most $O(1/R)$ for large $R$. Without latency-aware shot allocation rule in gCANS, the leading-order term of the gain in the single-shot acquisition time is $(\alpha-L\alpha^{2}/2)\|\bm{\nabla}f(\bm{\theta}^{(k)})\|^{2}/(2R)$, whereas using the number of shots of weCANS yields its leading-order term $(\alpha-L\alpha^{2}/2)\|\bm{\nabla}f(\bm{\theta}^{(k)})\|^{2}/R$, which is optimal. A similar estimation also holds for iCANS. Hence, roughly speaking, twice acceleration is expected in large $R$ limit. We remark that subleading-order terms are also maximized in weCANS, although the same leading-order scaling can be obtained by any $s_{i}\propto R^{a}$ $(0<a<1)$. Nevertheless, it turns out that such an improvement by weCANS(i) and weCANS(g) was not observed in our numerical simulations as shown in Sec. IV. That might be due to the limitation of the estimation of the gain using the expectation value of its lower bound even without considering the statistical error. On the other hand, incorporating latency-aware adaptive shot strategy into Adam introduced in the next subsection actually works well as shown in Sec. IV.

In this section, we propose how to incorporate weCANS adaptive shot number allocation strategy into more general stochastic gradient descent optimizers including Adam. We consider the following class of the optimizers such that the parameter is updated according to

where $\bm{X}_{k}(\bm{g}(\bm{\theta}^{(k)}))$ is some analytic function of the gradient estimator. In Adam, this function is given as

where $\bm{m}_{k}(\bm{g}(\bm{\theta}^{(k)}))$ and $\bm{v}_{k}(\bm{g}(\bm{\theta}^{(k)}))$ are given by Eq. (9) and (10) respectively, and we neglect $\epsilon$ in Eq. (11). Here, we only explicitly consider the dependency of $\bm{X}_{k}$ on the gradient estimator of the current step. In particular, $\bm{X}_{k}$ can depend on the quantities calculated in the previous iterations up to $k-1$ as in Adam. The dependency of $\bm{X}_{k}$ except for $\bm{g}(\bm{\theta}^{(k)})$ is included as the change of the form of the function depending on $k$. Under this parameter update rule, we have the following lower bound of the absolute value of the gain

in a similar manner to CANS, where, for clarity, we explicitly denote the dependency on the numbers of shots $\bm{s}$ of the estimator of the gradient

with single-shot estimations $\gamma_{i,k}$. Hence, if we have an estimation of the lower bound $\varphi(\bm{g}(\bm{\theta}^{(k)})[\bm{s}])$, we can determine an appropriate number of shots to maximize the it per unit time. Here, we consider the absolute value of the gain because the expected update direction given by $\bm{X}_{k}(\bm{g}(\bm{\theta}^{(k)}))$ can be opposite to the direction of the gradient $\bm{\nabla}f(\bm{\theta}^{(k)})$. We assume that as large as possible update is beneficial for a given update rule also in such a case.

We remark that the expectation is taken with respect to each single-shot realization $\gamma_{i,k}$ as a random variable. Hence, we can not obtain an analytic expression for the expectation value of this lower bound in general. Then, we approximate it via the Taylor expansion of $\varphi$ around the expectation value $\mathbb{E}[\bm{g}(\bm{\theta}^{(k)})[\bm{s}]]=\bm{\nabla}f(\bm{\theta}^{(k)})$ as

where

Eq. (29) has the same form as the objective function for gCANS, except that $B_{i}$ can be negative. If $B_{i}$ is negative, as small as possible value of $s_{i}$ gives the largest value of our objective function

to be maximized based on the expression Eq. (29). However, choosing $s_{i}=1$ is not appropriate in this case because Eq. (32) is based on the Taylor expansion, which is not accurate for small value of $s_{i}$. Hence, $B_{i}\leq 0$ implies that the optimal $s_{i}$ lies in a region where the Taylor expansion is not accurate. We circumvent this problem by setting a floor value $s_{\min}$, and we substitute $s_{\min}$ for $s_{i}$ with $B_{i}\leq 0$. In other words, we use $\bm{s}$ given by

which yields the shot allocation rule

where $R=(c_{2}\sum_{i=1}^{d}m_{i}+c_{3})/c_{1}$ is the ratio of the overhead per iteration to the single-shot acquisition time and

with $J_{+}:=\{j|B_{j}\geq 0\}$ and $J_{-}:=\{j|B_{j}<0\}$. All the inaccessible quantities are also replaced with the exponential moving average calculated from the previous iterations in the same way as iCANS and gCANS. For Eq. (34) to give valid numbers of shots, $A>0$ is required, which is equivalent to imposing

in accordance with the condition for the lower bound (27) to be positive. We can forcibly impose Eq. (36) by clipping $\alpha_{k}$ by $r$ times this upper limit with a fixed constant $0<r<1$. However, in practice, clipping $\alpha_{k}$ may delay the optimization. Instead, we can use a heuristic strategy to use the original $\alpha_{k}$ for the parameter update while the clipped value is used to calculate the number of shots. We take this strategy in the numerical simulations in Sec. IV.

We also call this adaptive shot allocation strategy weCANS. Especially, we call the Adam optimizer using weCANS strategy we-AdamCANS. For clarity, we describe the detail of we-AdamCANS in Algorithm 1.

We also obtain the shot allocation rule without considering the latency by taking the limit $R\rightarrow 0$. If $|J_{-}|=0$, we have

Especially, we call the Adam optimizer using this adaptive number of shots AdamCANS.

The best expected gain in the single-shot acquisition time of the above generalized weCANS is also twice as large as that of generalized CANS without latency consideration in large $R$ limit, in the same way as the weCANS(g) (weCANS(i)) vs gCANS (iCANS). As shown in numerical simulations in Sec. IV, we-AdamCANS actually achieves fast convergence in wall-clock time, although its acceleration is not always twice in comparison with AdamCANS (sometimes less than twice, sometimes even more faster).

For $H$ composed of multiple noncommuting observables, we allocate the number of shots for each simultaneously measurable group according to WRS as explained in Sec. II.2. In this case, the number of circuits $m_{i}$ used to estimate the gradient is also random because the latency only occurs for the measured groups. Hence, we cannot access $m_{i}$ before we decide the number of shots. Then, we take the following heuristic way to obtain an approximated maximization of the gain per unit time $r_{o}$ $(o=\mathrm{i},\mathrm{g},\mathrm{X})$ by replacing $m_{i}$ with an accessible quantity. For simplicity, we consider the case where the two-point parameter shift rule (3) holds and $s_{i}/2$ shots are used for the evaluation of the cost function at each shifted parameter. It is straightforward to generalize the following prescription to more general case with Eq. (4). We assume that we have obtained a grouping of the Pauli observables in Eq. (5) into $M$ groups of simultaneously measurable observables as

Then, each group $G_{j}$ is measured with probability $p_{j}=\sum_{i\in G_{j}}|c_{i}|/\sum_{k=1}^{N}|c_{k}|$ in WRS. We remark that we can use any probability distribution $p_{j}$ in general. Hence, group $G_{j}$ is not measured with probability $(1-p_{j})^{s_{i}/2}$ in each evaluation of the cost function. Thus, the expectation value of $m_{i}(s_{i})$ when $s_{i}$ shots are used is

However, this value still depends on $s_{i}$. Although it may be possible to numerically solve the maximization problem of $r_{o}$ with $m_{i}$ replaced with its expectation value (39) which we denote by $\tilde{r}_{o}$ from scratch, it might be expensive. In such a case, we instead use the exponential moving average $\tilde{s}_{i}$ of $s_{i}$ calculated from the previous iterations in place of $s_{i}$. We can further neglect the terms $(1-p_{j})^{\tilde{s}_{i}/2}$ below some small value since the probability of no occurrence of such a term is too small, and it is expected to be better to count its latency. Then, we obtain the analytic expressions of $s_{i}$ for weCANS (22) and (24) in the same way. Moreover, we can further implement a full maximization of $\tilde{r}_{o}$ by using the obtained analytic expressions as the initial guess.

As a first benchmark problem, we consider a variational compilation task Nakanishi et al. (2020); Kübler et al. (2020). Our task is to minimize the infidelity of the state $U(\bm{\theta})\ket{\bm{0}}$

with the target state $U(\bm{\theta}^{*})^{\dagger}\ket{\bm{0}}$ given by a randomly selected parameter vector $\bm{\theta}^{*}$ as the cost function. In this way, the ansatz always has the exact solution at the target parameter.

The parameterized quantum circuit $U(\vec{\theta})$ used in the numerical simulation is shown in Fig. 1, where $R_{P_{i,j}}(\theta_{i,j})=\exp[-i\theta_{i,j}P_{i,j}/2]$ with $P_{i,j}$ uniformly and randomly selected from the Pauli operators $X,Y,Z$. Especially, we simulate the optimization with $n=3$ qubits and $D=3$ depth.

The result of our simulation is shown in Fig. 2. We use the latency values $c_{1}=1.0\times 10^{-5}$ s, $c_{2}=0.1$ s, and $c_{3}=4.0$ s following Sung et al. (2020); Menickelly et al. (2022). Adam-$s$ means Adam using $s$ shots for every evaluation of the cost function. The median of the exact values of the cost function $f(\bm{\theta})$ at the optimized parameters of 30 runs is shown as the metric of the performance. Actually, we-AdamCANS outperforms the other optimizers. Especially, we-AdamCANS attains the precision $1.0\times 10^{-3}$ in $773$ s whereas Adam-10000 attains the same precision at 985 s but the error increases again due to the statistical error. The next faster one is iCANS which attains the same precision in 1463 s. Hence, we-AdamCANS is over about 2 times faster than the other optimizers in this problem. However, no improvement can be seen in the median performance by the simple strategies weCANS(i) and weCANS(g). That might be because our estimations are based on the maximization of the expectation value of the lower bound of the gain but not the gain itself. Hence the performance may be improved by using a tighter estimation of the Lipschitz constant $L$ which yields tighter estimation of the lower bound of the gain.

As the next benchmark problem, we consider VQE problems of quantum chemistry. We consider $\mathrm{H}_{2}$ molecule and $\mathrm{H}_{3}^{+}$ chain as examples. The distance between H atoms is set to 0.74Å  for both molecules. For $\mathrm{H}_{2}$ molecule, we use the STO-3G basis to encode the molecular Hamiltonian into the qubit systems via Jordan-Wigner mapping. For a benchmark purpose, we consider the VQE task of $\mathrm{H}_{2}$ encoded in $4$ qubits in this way without any qubit reduction. For $\mathrm{H}_{3}^{+}$ molecule, we also use the STO-3G basis, but apply the parity transform Seeley et al. (2012) as the fermion-to-qubit mapping. We further reduce two qubits via $\mathbb{Z}_{2}$ symmetry. Then, we obtain a 4-qubit Hamiltonian for $\mathrm{H}_{3}^{+}$ molecule. We just use a greedy algorithm to group the Pauli terms into qubit-wise commutable terms, where we use the coefficient of each term as the weight. We use a hardware efficient ansatz shown in Fig. 3 as the ansatz with $D=3$.

Fig. 4 shows the numerical results for the simulation of VQE. Fig. 4(a) and (c) respectively shows the performance of the optimizers for VQE tasks of $\mathrm{H}_{2}$ and $\mathrm{H}_{3}^{+}$ in terms of the elapsed time under the single-shot time $c_{1}=10^{-5}$ s, circuit-switching latency $c_{2}=0.1$ s, and the communication latency $c_{3}=4.0$ s, where $\Delta E$ denotes the difference of the exact energy expectation value evaluated at the parameters obtained by the optimization from the ground-state energy. On the other hand, Fig. 4(b) and (d) respectively shows the performance of the optimizers for VQE tasks of $\mathrm{H}_{2}$ and $\mathrm{H}_{3}^{+}$ in terms of the economic cost for using the Rigetti’s devices in Amazon Braket where $c_{1}=\text{\$}3.5\times 10^{-4}$, $c_{2}=\text{\$}0.3$ and $c_{3}=\text{\$}0.0$. We remark that the economic cost can be relabeled as the elapsed time, which shows the performance without the communication latency. In all the cases, we-AdamCANS considerably outperforms the other optimizers except for AdamCANS. In particular, only we-AdamCANS and AdamCANS attain the chemical accuracy 1.6$\times 10^{-3}$ Ha within the range of the simulation ($2\times 10^{4}$ s and $\text{\$}5\times 10^{4}$ for $H_{2}$, $5\times 10^{4}$ s and $\text{\$}4\times 10^{5}$ for $H_{3}^{+}$). On the other hand, the simple strategies weCANS(i) and weCANS(g) do not work well again in this case.

Except for the VQE performance for $\mathrm{H}_{3}^{+}$ in terms of the economic cost, latency-aware shot allocation strategy of we-AdamCANS actually yields faster convergence than AdamCANS without latency consideration. However, in that exceptional case of $\mathrm{H}_{3}^{+}$ VQE vs the economic cost, we-AdamCANS and AdamCANS attains the chemical accuracy almost with the same cost, though the convergence of we-AdamCANS is more clear and further precision is achieved. That seems because we-AdamCANS sometimes happens to delay by being trapped on a plateau in this problem. In fact, we can verify this observation by looking at some examples of a single run of the optimization shown in Fig. 5. In the case of Fig. 5 (a), we-AdamCANS actually achieves considerably faster convergence than AdamCANS. On the other hand, in the case of Fig. 5 (b), both we-AdamCANS and AdamCANS seems trapped on a plateau. In this case, AdamCANS escapes from the plateau faster than we-AdamCANS. This phenomenon can be understood from the fact that fluctuations can assist to escape from a plateau. Because we-AdamCANS uses larger number of shots to taking into account the latency, AdamCANS can have more chance to escape from a plateau thanks to its larger fluctuations. In the case of the larger ratio of the overhead in Fig. 4 (c), the delay of we-AdamCANS due to the plateau might be compensated by the delay of AdamCANS due to the large latency. It is left for future works to further improve we-AdamCANS shot allocation strategy in such a way that pros and cons of fluctuations are appropriately balanced to avoid such a plateau problem.

Next, let us also see the performance in terms of the number of shots. Fig. 6 shows the performance of the optimizers in terms of the number of shots used. Fig. 6 (a) and (b) are the results for $\mathrm{H}_{2}$ and $\mathrm{H}_{3}^{+}$ respectively. For weCANS optimizers, we used the latency values $c_{1}=3.0\times 10^{-4}$, $c_{2}=0.3$ and $c_{3}=0.0$ for (a), and $c_{1}=10^{-5}$, $c_{2}=0.1$ and $c_{3}=4.0$ for (b) to calculate the number of shots. If we measure the performance in terms of the total expended shots, AdamCANS indeed outperforms the other optimizers in both problems.

Finally, in order to demonstrate the performance of our optimizers in larger system sizes, we consider the VQE task of the 1-dimensional transverse field Ising spin chain with open boundary conditions for the system size $N=6$ and 12, where the Hamiltonian is

We consider the case with $g/J=1.5$. For this problem, we used the ansatz shown in Fig. 7 with $D=3$ following Kübler et al. (2020). The ratio of the number of shots for the measurements of the interaction term to that of the transverse field term is deterministically fixed as $J$ to $g$.

Fig. 4(a) and (b) respectively shows the performance of the optimizers for VQE tasks for $N=6$ and $N=12$ in terms of the elapsed time under the single-shot time $c_{1}=10^{-5}$ s, circuit-switching latency $c_{2}=0.1$ s, and the communication latency $c_{3}=4.0$ s. The results are shown in terms of the precision of the per-site energy $\Delta E/(JN)$, where $\Delta E$ denotes the difference of the exact energy expectation value evaluated at the parameters obtained by the optimization from the ground-state energy. Actually, we-AdamCANS outperforms the other implemented optimizers for both $N=6$ and $N=12$. In particular, we-AdamCANS attains the precision $10^{-2}$ considerably faster than the other optimizers except for Adam-10000 for $N=12$. However, the performance of Adam with a fixed number of shots is sensitive to the choice of the number of shots. In fact, Adam-10000 is too slow for $N=6$. On the other hand, we emphasize that there is no need to tune the number of shots to use in we-AdamCANS, which indeed robustly achieves fast convergence for both systems sizes. Especially, for $N=6$, we-AdamCANS attains $10^{-2}$ in 4044 s whereas the next fastest iCANS attains the same precision in 17455 s. Hence, we-AdamCANS is more than about 4-times faster than the others for the convergence up to this precision in this case.