††thanks: Equal contribution to Ze-Tong Li

[1]State Key Laboratory of Millimeter Waves, Southeast University, Nanjing
210096, China [2]National Mobile Communications Research Laboratory, Southeast
University, Nanjing 210096, China. [3]Frontiers Science Center for Mobile
Information Communication and Security, Southeast University, Nanjing 210096,
China. [4]Quantum Information Center, Southeast University, Nanjing 210096,
China. [5]Purple Mountain Lab, Nanjing 211111, China.

# An Efficient Gradient-Sensitive Alternate Framework for VQE with Variable
Ansatz

Ze-Tong Li  Fan-Xu Meng  Han Zeng  Zai-Chen Zhang  Xu-Tao Yu
<EMAIL_ADDRESS>
###### Abstract

Variational quantum eigensolver (VQE), aiming at determining the ground state
energy of a quantum system described by a Hamiltonian on noisy intermediate
scale quantum (NISQ) devices, is among the most significant applications of
variational quantum algorithms (VQAs). However, the accuracy and trainability
of the current VQE algorithm are significantly influenced due to the _barren
plateau_ (BP), the non-negligible gate error and limited coherence time in
NISQ devices. To tackle these issues, a gradient-sensitive alternate framework
with variable ansatz is proposed in this paper to enhance the performance of
the VQE. We first propose a theoretical framework for VA-VQE via alternately
solving a multi-objective optimization problem and the original VQE, where the
multi-objective optimization problem is defined with respect to cost function
values and gradient magnitudes. Then, we propose a novel implementation method
based on the double $\epsilon$-greedy strategy with the candidate tree and
modified multi-objective genetic algorithm. As a result, the local optima are
avoided both in ansatz and parameter perspectives, and the stability of output
ansatz is enhanced. The experimental results indicate that our framework shows
considerably improvement of the error of the found solution by up to 87.9%
compared with the hardware-efficient ansatz. Furthermore, compared with the
full-randomized VA-VQE implementation, our framework is able to obtain the
improvement of the error and the stability by up to 36.0% and 58.7%,
respectively, with similar quantum costs.

##  1 Introduction

Quantum computing, a promising paradigm for solving many classically
intractable problems [1, 2, 3, 4], is confronted with the era of noisy
intermediate scale quantum (NISQ) [5]. NISQ devices, characterized as tiny
quantities and short coherent time of qubits and low fidelity of quantum
gates, seem difficult to efficiently apply the extraordinary quantum
algorithms.

A hybrid quantum-classical scheme kindles the hope of extracting the quantum
advantages from NISQ devices. In this scheme, the quantum computer maintains a
parameterized quantum circuit (aka. ansatz), and the classical computer runs
an optimizer to find the parameters that minimize the cost function of the
ansatz. This novel scheme was first proposed as the variational quantum
eigensolver (VQE) [6] to find the ground-state energy, and generalized for
solving linear systems [7], simulating dynamics [8], decomposing matrix [9,
10], reducing the dimensionality of data [11], and solving problems in the
data science domain [12, 13, 14]. In the following text, the term VQE is used
to indicate all methods that adopt the aforementioned scheme.

The VQE has experimentally shown effectiveness in small-scale problems [15].
The elaborately engineered ansatzes [16] with fixed layer structure and
adjustable cardinality of layers have impressively exhibited high
expressibility, the ability to express the extensive range of quantum states.
However, the performance of VQE with the ansatzes degrades significantly with
the qubit number and circuit depth [17]. The phenomena of the degradation are
generally exhibited as the non-ignorable absolute error between the converged
cost function value and the exact minimum.

One reason for the degradation is that the VQE suffers from the so-called
barren plateau [18] that the gradient magnitudes vanish exponentially with the
system scale. Then, the severity of the BP phenomenon is linked to the number
of entanglements [19, 20, 21, 22] and the expressibility [23]. Another reason
is quantum hardware noise both in quantum gates and qubits. The influence of
the noise accumulates with the number of quantum gates and the circuit depth
[24] and causes the accuracy reduction of the observable estimation. This
significantly impedes the convergence of the cost function since the value of
the cost function and its gradient are inaccurate, which is known as noise-
induced barren plateaus [24].

Recently, the variable ansatz strategy [17, 25, 26, 27, 28, 29, 30] has
emerged as a promising technique to reserve the quantum advantage in large-
scale situations. Unlike the structure fixed ansatz, the layer constraint is
relaxed in variable ansatz, and gates can be added anywhere in the ansatz as
required. As a result, both the size and the depth of the constructed anzatz
can be effectively reduced, and thus better solutions can be found.
Nevertheless, implementing the VQE with variable ansatz (VA-VQE) exists a
significant space overhead for the ansatz layout optimization procedure, and
consequently requires substantially more computing resources than that with
the structure fixed ansatz.

To further improve efficiency, several techniques from intelligent algorithms
have also been introduced. Several methods based on the complete training are
proposed [25, 27, 28, 31]. In these methods, the performance estimation of an
ansatz requires VQE training until the cost function converges to obtain the
lowest cost function value of the ansatz. As a result, high precision of the
optimal selection among sampled ansatzes is achieved but undesirably
introduces tremendous cost function determinations which are time-consuming
because each determination of cost function requires substantial quantum
measurements. Therefore, the range of sampled ansatzes is narrow when the
quantity of quantum measurements is limited. This may result in local optimum
from the ansatz perspective.

Attempting to overcome this hurdle, several methods based on the highly shared
parameter pool are proposed [17, 30]. These methods construct ansatzes layer-
wisely and maintain parameter pools from which values of parameters are
exploited to calculate the cost function value as the performance predictor.
Introducing the weight-sharing policy [32], parameters are shared among layers
with similar structures. Thus, the number of parameters in the parameter pool
required to be trained is effectively reduced. These methods first train the
parameter pools iteratively. In each iteration, several ansatzes are sampled
based on the sampling strategy. Then, the parameters corresponding to the
ansatzes are updated in specified steps (especially one step) by an optimizer.
After training the parameter pools, the optimal ansatz selection procedure is
processed. Quantities of ansatzes are sampled and evaluated by the performance
predictor. Finally, the ansatz with the best performance, generally the lowest
cost function value, is selected as the optimal ansatz.

This kind of method gains the efficiency in finding optimal ansatz by avoiding
complete training of ansatzes. However, since the parameters are highly shared
and the training step of each ansatz is insufficient to converge, the current
cost function values may not express the actual performances of the ansatzes,
and hence the output suffers from high variance. This may result from two
issues. The first is the training competitions that values of parameters in
‘good’ ansatzes with promising layouts may be disturbed by the training of
‘bad’ ansatzes incurred by the weight-sharing policy. The second issue is that
the policy for ansatz layout optimization exploits the cost function value
only as the benchmark to find the optimal ansatz structure. The mediocre
ansatz whose cost function value is currently the lowest and cannot be further
decreased may be selected as the optimum. Contrarily, the promising ansatzes
may be discarded because of their temporarily high cost function values.

In this paper, addressing these issues, we propose a gradient-sensitive
alternate framework (GSA) for VA-VQE. The GSA alternately optimizes the
structure of the ansatz and corresponding parameters by emphasizing the
gradient magnitudes. Contributions are listed below:

  * •

We first propose a theoretical framework solving VA-VQE via alternately for
solving a gradient magnitudes related multi-objective optimization problem and
the original VQE, so that local optima can be avoided from the ansatz
perspective and the stability is enhanced compared to other VA-VQE methods.

  * •

To mitigate training competitions in training the parameter pool for the
initialization of parameters, we first exploit the double $\epsilon$-greedy
strategy based on the candidate tree to differentiate ansatzes by their cost
function values and the gradient magnitudes, so that local optima can be
evaded from the parameter perspective.

  * •

We further reduce the size of the search space of the ansatz via applying gate
commutation rules and establishing a bijection between the search space and
the practical implementations of ansatzes to boost the time efficiency of the
optimal ansatz and parameter determination.

  * •

We adopt relatively fair criteria for measuring the performance of VA-VQE so
that the transverse comparison among methods of VA-VQE can be conducted. As a
result, the GSA shows conspicuously better performance on average compared to
the structure fixed HEA up to 87.9% improvement in terms of absolute error,
and to the full-randomized VA-VQE method up to 36.0% and 58.7% improvement in
terms of absolute error and stability (mean square error), respectively, with
similar quantum costs (the number of calculations of the cost function).

This paper is structured as follows: In Sec. 2, we give a brief introduction
to the basic knowledge. Then, the gradient-sensitive theoretical framework
based on the alternate optimization is proposed in Sec. 3. The detail of the
practical implementation of GSA is proposed in Sec. 4. Subsequently, we
conduct numerical simulations with relatively fair criteria in Sec. 5 to show
the advantages of our proposed method. Finally, we conclude this work in Sec.
6. Notice that the examples and pseudocodes of algorithms are summarized in
Appendix A and F, respectively.

##  2 Background

###  2.1 Variational Quantum Eigensolver

In this work, we address the variational quantum eigensolver (VQE) tasks
identified by sets of tuples
$\mathbb{T}=\left\\{\left(O_{i},\rho_{i},f_{i}\right)\right\\}$ aiming at
minimizing a cost function

$C(\bm{\theta})=\sum_{i}f_{i}({\rm
Tr}\left[O_{i}U(\bm{\theta})\rho_{i}U^{\dagger}(\bm{\theta})\right]),$ (1)

where $\\{\rho_{i}\\}$ is the training set formed as n-qubit quantum states,
$U(\bm{\theta})$ is a specified parameterized quantum circuit (aka. ansatz)
with parameters $\bm{\theta}$, $O_{i}$ are observables and $f_{i}$ are bounded
second-order differentiable functions that encode the problem with respect to
the operand observable $O_{i}$ and state $\rho_{i}$. Generally, while
implementing the VQE, the quantum computer applies the ansatz $U(\bm{\theta})$
and processes the quantum measurements to determine expectations ${\rm
Tr}\left[O_{i}U(\bm{\theta})\rho_{i}U^{\dagger}(\bm{\theta})\right],\forall
i$. The classical computer computes the cost function value and runs an
optimization algorithm to find the optimal parameters $\bm{\theta}^{*}$ that
minimize the cost function. We provide an example finding the ground state
energy of a quantum system described by a Hamiltonian in Eg. 1.

###  2.2 Quantum Gradient

In the optimization procedure of large-scale VQE, the gradient-based methods
(e.g., gradient descent) are generally more preferred than gradient-free
methods (e.g., Nelder-Mead) [33]. In the gradient-based methods, the gradient
of the cost function with respect to the parameters is essentially estimated
in each optimization iteration.

Without loss of generality, an ansatz can be mathematically defined by

$U(\bm{\theta}):=\prod_{l=1}^{N_{l}}U_{l}(\theta_{l})W_{l},$ (2)

where $U_{l}(\theta_{l})=\exp(-i\theta_{l}V_{l})$, $V_{l}$ is a Hermitian
operator, and $W_{l}$ is a non-parametrized quantum gate. Then, the partial
derivative of an expectation $E(\bm{\theta})={\rm Tr}(OU(\bm{\theta})\rho
U^{\dagger}(\bm{\theta}))$ with respect to the $k$th parameter $\theta_{k}$ is

$\displaystyle\partial_{k}E(\bm{\theta})$ $\displaystyle\equiv\frac{\partial
E(\bm{\theta})}{\partial\theta_{k}}=i{\rm
Tr}\left(\left[V_{k},U_{L}^{\dagger}OU_{L}\right]U_{R}\rho
U_{R}^{\dagger}\right),$ (3)

where we use the notations

$\displaystyle
U_{R}\equiv\prod_{l=1}^{k-1}U_{l}(\theta_{l})W_{l},\leavevmode\nobreak\
U_{L}\equiv\prod_{l=k}^{N_{l}}U_{l}(\theta_{l})W_{l}.$ (4)

In this paper, we apply the parameter-shift rule [33] for gradient estimating.
We assume that all parameterized quantum gates are Pauli rotations. Therefore,
the partial derivative of $E(\bm{\theta})$ with respect to $\theta_{k}$ is

$\partial_{k}E(\bm{\theta})=\frac{1}{2}\left[E(\bm{\theta}+\frac{\pi}{2}\bm{e}_{k})-E(\bm{\theta}-\frac{\pi}{2}\bm{e}_{k})\right],$
(5)

where $\bm{e}_{k}$ is a vector whose $k$th element is $1$ and others are $0$.

###  2.3 Gradient Descent

Gradient descent is literately a gradient-based optimizer that has been
generally used in training VQE [7, 8, 11, 12]. The kernel process of the
gradient descent can be mathematically represented as

$\bm{\theta}\leftarrow\bm{\theta}-\alpha\nabla C(\bm{\theta}),$ (6)

where $\alpha$ is the step size.

In this paper, we exploit a line search to estimate the step size $\alpha$
instead of a fixed one. In each optimization step, $\alpha$ satisfies the
Wolfe conditions [34]

$\displaystyle C(\bm{\theta}-\alpha\bm{g})\leq
C(\bm{\theta})-c_{1}\alpha\left\|\bm{g}\right\|_{2}^{2},$ (7)
$\displaystyle\nabla C(\bm{\theta}-\alpha\bm{g})^{T}\bm{g}\geq
c_{2}\left\|\bm{g}\right\|_{2}^{2},$ (8)

where $\bm{g}=\nabla C(\bm{\theta})$ and $0<c_{1}<c_{2}<1$. To facilitate the
$\alpha$ determination, given a reference step size $\alpha_{0}$, we gradually
decrease $\alpha$ from $\alpha_{0}$ by repeating $\alpha\leftarrow\rho\alpha$
until Eq. (7) establishes, where $\rho<0$. In this paper, we empirically set
$c_{1}=10^{-4}$ and $\rho=0.618$.

###  2.4 Expressibility

In the absence of prior knowledge about the solution unitaries
$\mathbb{U}_{s}$ of a VQE task, the ability of ansatz to generate a wide range
of unitaries $\mathbb{U}$ to guarantee
$\mathbb{U}_{s}\cap\mathbb{U}\neq\emptyset$ is required. The expressibility of
an ansatz describes the degree to which it uniformly explores the unitary
group $\mathcal{U}(2^{n})$, and can be simply considered as the range of
unitaries the ansatz can generate. By comparing the uniform distribution of
unitaries obtained from $\mathbb{U}$ to the Haar distribution of unitaries
from $\mathcal{U}$, the expressibility of an ansatz can be defined by the
superoperator [35, 36]:

$\displaystyle\mathcal{A}_{u}^{(t)}:=$
$\displaystyle\int_{\mathcal{U}(2^{n})}d\mu(V)V^{\otimes
t}(\,\cdot\,)(V^{\dagger})^{\otimes t}-\int_{\mathbb{U}}dU\,U^{\otimes
t}(\,\cdot\,)(U^{\dagger})^{\otimes t},$ (9)

where $d\mu(V)$ is the volume element of the Haar measure and $dU$ is the
volume element corresponding to the uniform distribution over $\mathbb{U}$.
Here we are especially interested in the expressibility of the ansatz with
respect to the input quantum state $\rho$ and the observable $O$

$\displaystyle\epsilon_{\mathbb{U}}^{\rho}:=\left\|\mathcal{A}^{(2)}_{\mathbb{U}}(\rho^{\otimes
2})\right\|_{2},\leavevmode\nobreak\
\epsilon_{\mathbb{U}}^{O}:=\left\|\mathcal{A}^{(2)}_{\mathbb{U}}(O^{\otimes
2})\right\|_{2}.$ (10)

Small values of $\epsilon_{\mathbb{U}}^{\rho}$ and $\epsilon_{\mathbb{U}}^{O}$
indicate the high expressibility of the ansatz.

###  2.5 Barren Plateau and Trainability

As one of the key challenges of VQE, the barren plateau phenomenon exhibited
the exponential decrement of the gradient magnitudes with respect to the
system size $n$ [18] and was generalized that the ansatzes’ expressibility
[23] and the amount of entanglement [19, 20, 21, 22] play significant roles in
leading to barren plateaus. We highlight the severity of the BP phenomenon
with respect to $n$ and the expressibility of the ansatz by the limited
variance of gradient magnitudes

$\displaystyle{\rm
Var}[\partial_{k}C(\bm{\theta})]\leq\frac{g(\rho,O,U)}{2^{2n}-1}+f\left(\epsilon_{\mathbb{U}_{L}}^{O},\epsilon_{\mathbb{U}_{L}}^{\rho}\right),$
(11)

where $g(\rho,O,U)$ is the prefactor in $O(2^{n})$,

$f(x,t)=4xy+\frac{2^{n+2}\left(x\left\|O\right\|^{2}_{2}+y\left\|\rho\right\|^{2}_{2}\right)}{2^{2n}-1},$
(12)

and $\mathbb{U}_{L}$ and $\mathbb{U}_{R}$ are ensembles of $U_{L}$ and
$U_{R}$, respectively [23]. The first term on the right in Eq. (11) indicates
the variance of 2-design ansatz and is in $O(1/2^{n})$, and the second term is
the expressibility-dependent correction. From the Chebyshev’s inequality, the
trainability of an ansatz can be described by

$\displaystyle{\rm
Pr}\left[\left|{\partial_{k}C(\bm{\theta})}\right|\geq\delta\right]\leq\frac{{\rm
Var}[\,\partial_{k}C(\bm{\theta})]}{\delta^{2}},\,\forall\delta>0.$ (13)

When the ansatz exhibits the BP phenomenon, the probability decreases
exponentially with respect to $n$, which indicates that the precision to
determine a cost-minimizing direction is exponentially large to $n$ [28, 37,
38]. Notably, an ansatz with higher expressibility suffers lower trainability
since it exhibits a more severe BP phenomenon.

Remarkably, there exists another kind of barren plateaus, the noise-induced
barren plateaus [24], caused by the imperfect quantum hardware. The cost
function value concentrates exponentially around its average as the influence
of noise accumulates, since the noise models acting throughout the ansatz map
the input state toward the fixed point of the noise model [24, 39].

This challenging phenomenon cannot simply be escaped by changing the optimizer
[38]. While several attempts have been made to mitigate the severity of the
barren plateau [40, 41, 42, 43, 44], it is widely accepted that the variable
ansatz strategy is promising to address this issue via automatically balancing
the expressibility, the influence of noise, and the trainability.

###  2.6 Hardware Constraints

Generally, only a limited number of gates are available on a practical quantum
computer and the two-qubit gates are only allowed to be applied on a specific
set of qubit pairs. These available gates are known as native gates of the
quantum hardware. In this paper, we assume the native gates on an $n$-qubit
quantum system to be $R_{y}$, $R_{z}$ and CNOT mathematically represented as

$\displaystyle
R^{q}_{y}(\theta)=e^{-i\frac{\theta}{2}\sigma_{y}}=\begin{bmatrix}\cos\frac{\theta}{2}&-\sin\frac{\theta}{2}\\\
\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{bmatrix},$ (14) $\displaystyle
R^{q}_{z}(\theta)=e^{-i\frac{\theta}{2}\sigma_{z}}=\begin{bmatrix}e^{-i{\theta}/{2}}&0\\\
0&e^{i{\theta}/{2}}\end{bmatrix},$ (15)
$\displaystyle\mathrm{CNOT}^{q_{a},q_{b}}=\left|0\right>\left<0\right|^{q_{a}}\otimes
I^{q_{b}}+\left|1\right>\left<1\right|^{q_{a}}\otimes X^{q_{b}},$ (16)

where superscript $q$, $q_{a}$, and $q_{b}$ indicate the qubits on which the
quantum gates act, $\sigma_{y}$ and $\sigma_{z}$ are Pauli operators
mathematically represented as

$\displaystyle\sigma_{y}=\begin{bmatrix}0&-i\\\
i&0\end{bmatrix},\sigma_{z}=\begin{bmatrix}-1&0\\\ 0&1\end{bmatrix},$ (17)

$I$ is the identity quantum operation and $X$ is the quantum _not_ gate
mathematically represented as

$I=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},X=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}.$ (18)

Moreover, $R^{q}_{z}$ and $R^{q}_{y}$ can be applied for all
$q\in\\{1,2,\ldots,n\\}$, while CNOT gates $\mathrm{CNOT}^{q_{a},q_{b}}$ are
unidirectionally available on adjacent qubit pairs, i.e., $q_{b}=(q_{a}+1)\mod
n$. Note that the proposed framework can be easily adjusted for different
native gate sets.

##  3 Theoretical Framework

In this section, we introduce the theoretical framework derived from the
problem of VQE. Then, we equivalently transform the solving procedure into
solving a series of multi-objective optimization problems related to gradient
magnitudes.

Recall that a VQE task can be considered as minimizing a cost function, which
is summarized in Prob. 1.

######  Problem 1 (VQE).

Given an ansatz $U(\bm{\theta})$ and a task $\mathbb{T}$, the problem of VQE
is to find parameters that minimize the cost function $C(\bm{\theta})$, i.e.,

$\min_{\bm{\theta}\in\mathbb{D}^{N_{p}}}C(\bm{\theta})=\sum_{i}f_{i}({\rm
Tr}\left[O_{i}U(\bm{\theta})\rho_{i}U^{\dagger}(\bm{\theta})\right]),$ (19)

where $\mathbb{D}\subset\mathbb{R}$, $N_{p}$ is the cardinality of trainable
parameters $\bm{\theta}$.

While introducing the VA-VQE framework as summarized in Prob. 2, the structure
of ansatz $U$ is treated as a variable that needs to be optimized in the cost
function

$C(U,\bm{\theta})=\sum_{i}f_{i}({\rm
Tr}\left[O_{i}U(\bm{\theta})\rho_{i}U^{\dagger}(\bm{\theta})\right]).$ (20)

######  Problem 2 (VA-VQE).

Given a search space of ansatz $\mathbb{S}$ and a task $\mathbb{T}$, the
problem of VA-VQE is to find ansatzes and corresponding parameters that
minimize the cost function $C(U,\bm{\theta})$, i.e.,

$\displaystyle\min_{U\in\mathbb{S},\leavevmode\nobreak\
\bm{\theta}\in\mathbb{D}^{N_{p}}}C(U,\bm{\theta}),$ (21)

where $C(U,\bm{\theta})$ forms as Eq. (20), $\mathbb{D}\subset\mathbb{R}$, and
$N_{p}$ is the cardinality of trainable parameters $\bm{\theta}$.

Practically, the VA-VQE methods automatically construct ansatzes by quantum
gates from a given gate set $\mathbb{G}$, i.e.
$\mathbb{S}=\mathbb{G}^{\infty}$, and find ones with trained parameters that
minimize the cost function. The search space of ansatz actually scales
infinitely since the depth of ansatz circuits can be infinitely large.
However, the trainability of the ansatz is substantially limited by the number
of quantum gates because the expressibility and the impact of noise of the
ansatz may increase with respect to the number of quantum gates, which
aggravates the BP phenomenon. On the other hand, it is intractable to search
for solutions with enormous (even infinite) search space of ansatz. Therefore,
a fixed or gradually increased maximum number $n_{g}$ of quantum gates is
introduced as $\mathbb{S}=\mathbb{G}^{N_{g}}$, where $N_{g}$ is sufficiently
large that $\exists U\in\mathbb{G}^{N_{g}}$ such that
$\mathbb{U}\cap\mathbb{U}_{s}\neq\emptyset$. Nevertheless, determining exact
solutions requires solving combinatorial optimization in an exponentially
large search space, which conceals the efficiency of VQE. Most methods [17,
26, 28, 30, 31] attempt to provide approximate solutions in polynomial
complexity with respect to $g$. Although the gradient is generally estimated
for the optimization of parameters, its magnitude is neglected to provide a
guideline for the optimization of the structure of ansatz. Therefore, several
undesirable phenomena listed below may occur:

  1. 1.

The ansatz which exhibits severe barren plateau, and thus the gradient
magnitude is highly close to $0$, is selected to test the cost function value
multiple times.

  2. 2.

The trivial ansatz whose parameters are completely trained, i.e. the gradient
magnitude is highly close to $0$, is selected as the optimal ansatz since it
temporarily cost less than potentially better ansatz with incompletely trained
parameters, i.e. the gradient magnitude is significantly larger than $0$.

These phenomena result in the local optimal of the VA-VQE from the ansatz
perspective and instability of optimal ansatz and cost function value outputs.

Here we first introduce the gradient magnitude in solving the VA-VQE problem
to explicitly supervise the severity of the BP phenomenon and the completeness
of parameter training of ansatzes. We define a subproblem the gradient-related
ansatz multi-objective optimization (GRAMO) in Prob. 3.

######  Problem 3 (GRAMO).

Given a search space of ansatzes $\mathbb{S}$, a task $\mathbb{T}$, and a set
of parameters $\mathbb{P}$ such that $\exists!\bm{\theta}_{U}\in\mathbb{P}$,
$\forall U\in\mathbb{S}$, the problem of GRAMO is to find ansatzes that
minimize the cost function $C(U,\bm{\theta}_{U})$ and maximize the gradient
magnitude of the cost function, i.e.,

$\displaystyle\min_{U\in\mathbb{S}}C(U,\bm{\theta}_{U}),\leavevmode\nobreak\
\max_{U\in\mathbb{S}}\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}$ (22)

where $C(U,\bm{\theta}_{U})$ forms as Eq. (20), $\nabla C(U,\bm{\theta}_{U})$
is the gradient of $C(U,\bm{\theta}_{U})$ with respect to $\bm{\theta}_{U}$,
$\bm{\theta}_{U}\in\mathbb{P}$, and $|\bm{\theta}_{U}|$ is the cardinality of
parameters in $\bm{\theta}_{U}$.

The (1-rank) solution of Prob. 3 is defined as the non-dominated set
$\mathbb{U}_{n}$ consisting of all $U$ such that no $V\in\mathbb{S}$
simultaneously establishes inequalities

$\displaystyle C(V,\bm{\theta}_{V})$ $\displaystyle<C(U,\bm{\theta}_{U}),$
(23) $\displaystyle\frac{\left\|\nabla
C({V},\bm{\theta}_{V})\right\|_{2}}{|\bm{\theta}_{V}|}$
$\displaystyle\geq\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}.$ (24)

As a result, structures of ansatzes with low cost function values or large
gradient magnitudes, in other words, high absolute performance or high
potentiality, are selected as solutions. Furthermore, the $k$-rank solution
$\mathbb{U}_{n}(k)$ of the problem is defined by
$\mathbb{U}_{n}(k):=\mathbb{U}_{n}({k-1})\cap\mathbb{U}_{n}^{\prime}$, where
$\mathbb{U}_{n}^{\prime}$ is the 1-rank solution of Prob. 3 with search space
$\mathbb{S}\setminus\mathbb{U}_{n}^{k-1}$.

We solve the VA-VQE problem by alternately solving Prob. 1 and Prob. 3 as
summarized in Alg. 1. When the gate set $\mathbb{G}$ and the task $\mathbb{T}$
are specified, for any initialization of $\mathbb{P}$, the VA-VQE can be
solved iteratively. At each iteration, the non-dominated set $\mathbb{U}_{n}$
is determined by solving Prob. 3 the GRAMO with $\mathbb{P}$. Then, the
optimal parameters $\theta_{U}\in\mathbb{P}$ are updated via solving Prob. 1
the VQE, $\forall U\in\mathbb{U}_{n}$. The alternate optimization procedure
terminates until $\mathbb{U}_{n}$ and $\mathbb{P}$ are converged.

######  Theorem 1 (Convergence).

$\mathbb{U}_{n}$ and $\mathbb{P}$ in Alg. 1 converge such that
$\forall\left(U\in\mathbb{U}_{n},\bm{\theta}_{U}\in\mathbb{P}\right)$ are
solutions of Prob. 2 for all $\mathbb{P}_{0}$ satisfied that $\exists
V\in\mathbb{S}$ such that

$\displaystyle\exists\bm{\theta}^{*},\leavevmode\nobreak\
C(V,\bm{\theta}^{*})=\min_{U,\bm{\theta}}C(U,\bm{\theta}),$ (25)
$\displaystyle\forall\delta>0,\leavevmode\nobreak\
C(V,\bm{\theta}_{V}\in\mathbb{P}_{0})\neq\max_{\bm{\theta}\in\Theta_{V,\delta}}C(V,\bm{\theta}),$
(26)

where

$\Theta_{V,\delta}=\\{\bm{\theta}\left|\|\bm{\theta}-\bm{\theta}_{V}\|_{2}<\delta\right.\\}.$
(27)

Theorem 1 (c.f. Appendix C for the proof) indicates that solutions of VA-VQE
can be determined by Alg. 1.

##  4 Solving VQE Tasks with Gradient Sensitive Variable Ansatz

In this section, the gradient-sensitive alternate framework (GSA) for VA-VQE
is proposed in detail. As the VA-VQE problem described, GSA takes the gate set
$\mathbb{G}$ and the task $\mathbb{T}$ as inputs. Based on the gate
commutation rules, the search space of ansatz $\mathbb{S}(N_{l})$ under the
maximum number of layers $N_{l}$ is reduced to boost the time efficiency of
the optimal ansatz and parameters determination. Then, the quasi-optimal
ansatz and corresponding trained parameters are output through three stages:
_pool training_ , _alternate training_ , and _VQE retraining_. In the stage of
_pool training_ , a candidate tree $T$ is constructed for double
$\epsilon$-greedy sampling and a parameter pool in which parameters are shared
among ansatzes with similar structures is trained via exploiting the double
$\epsilon$-greedy strategy based on the candidate tree. As a result, a
reasonable set of parameters $\mathbb{P}_{0}$ is generated as the
initialization of parameters for the next stage. Based on the multi-objective
genetic algorithm, the _alternate training_ applies the framework described in
Alg. 1 to solve the VA-VQE problem via alternately solving the GRAMO in Prob.
3 and the VQE in Prob. 1. Since the evolutionary algorithm is applied, the
output ansatz is quasi-optimal and corresponding parameters may be
incompletely trained. Therefore, the third stage _VQE retraining_ is required
to guarantee the completion of parameter training of the quasi-optimal ansatz.
We summarize the GSA as Alg. 2.

Besides, there are several parameters needed to be defined before actually
running (c.f. Tab. 4 in Appendix D for the summarizing). For the entire
proposed framework, they are, respectively, the maximum number of layers
$N_{l}$, the reference step size $\alpha_{0}$, the convergence threshold
$\xi$, and the probabilities of greedy selection for the double
$\epsilon$-greedy strategy $\epsilon_{1}$ and $\epsilon_{2}$. In the _pool
training_ , they are, respectively, the number of sampled ansatzes $N_{s1}$,
the maximum number of ranks of ansatzes whose corresponding parameters are
updated $N_{r1}$, the stable threshold for terminating the main process
$N_{t1}$, the maximum iteration times in the prethermalization $N_{i0}$, and
the maximum iteration times in the main process $N_{i1}$. In the _alternate
training_ , they are, respectively, the population size $N_{s2}$, the maximum
number of ranks of ansatzes whose corresponding parameters are updated
$N_{r2}$, the stable threshold $N_{t2}$, the optimization step in a generation
$N_{o}$, and the maximum iteration times $N_{i2}$. In the _VQE retraining_ ,
they include the maximum iteration times $N_{i3}$.

This section is organized as follows: In Sec. 4.1, we concretely propose the
structure of the search space of ansatz for the GSAand conduct the size
reduction to the search space based on the gate commutation rules.
Subsequently, the _pool training_ , _alternate training_ , and _VQE
retraining_ stages are explained in Sec. 4.2, 4.3 and 4.4, respectively.

Figure 1:  The layer-by-layer ansatz (a) with each layer being decomposed into
two sublayers, i.e., (b) a single-qubit gate layer and a CNOT layer; and (c)
four exemplary constructions of layers.

###  4.1 Search Space of Ansatz

Without violation of Eq. 2, we compose an ansatz in a layer-by-layer fashion
as shown in Fig. 1. To be specific, each layer consists of a set of native
disjoint single-qubit gates followed by a set of hardware-compliant disjoint
CNOT gates. It can be easily derived that the number of all possible
structures $N_{s}$ of a layer is exponentially large with respect to the
number of qubits $n$. We use the term state denoted by ${\mathbf{s}}_{j}$ to
indicate the $j$th structure is used. Then, an ansatz can be identified by a
tuple of states

$\left({\mathbf{s}}^{1},{\mathbf{s}}^{2},\ldots,{\mathbf{s}}^{N_{l}}\right),$

where ${\mathbf{s}}^{l}\in
S:=\left\\{{\mathbf{s}}_{1},{\mathbf{s}}_{2},\ldots,{\mathbf{s}}_{N_{s}}\right\\}$.
As a result, the search space of ansatz $\mathbb{S}(N_{l})$ can be
specifically represented by a tree with $N_{l}+1$ layers (from layer $0$ to
$N_{l}$). A node at the layer $l>0$ in the tree is uniquely identified by its
parent node and the state, i.e.,
${\mathbf{v}}^{l}:=({\mathbf{v}}^{l-1},{\mathbf{s}}^{l})$, and linked to its
child nodes. In layer $0$, the root node of the tree is defined with no parent
node and the state ${\mathbf{s}}^{0}$ in which no layer information is stored.
Furthermore, we call the nodes in layer $N_{l}$ linked to no child nodes the
leaf nodes. Finally, a path from the root node to a leaf node
$\left({\mathbf{v}}^{0},{\mathbf{v}}^{1},\ldots,{\mathbf{v}}^{N_{l}}\right)$
represents an ansatz
$\left({\mathbf{s}}^{1},{\mathbf{s}}^{2},\ldots,{\mathbf{s}}^{N_{l}}\right)$.

The unrefined $\mathbb{S}(N_{l})$ is intuitively a full $N_{s}$-ary tree with
$(N_{s})^{N_{l}}$ leaf nodes. However, this simple-minded construction can not
establish the bijection between practical implementations of ansatzes and
paths (c.f. Eg. 2). Moreover, gates in distinct layers may be deletable or
mergeable (c.f. Eg. 3). To further eliminate the redundant ansatzes and
improve the efficiency, the paths violating the following cross-layer
constraints based on gate commutation rules will be pruned.

#### Constraints:

For node ${\mathbf{v}}^{l}:=({\mathbf{v}}^{l-1},{\mathbf{s}}^{l})$ in the path
$({\mathbf{v}}^{0},{\mathbf{v}}^{1},\ldots,{\mathbf{v}}^{l})$:

  1. 1.

$R_{z}^{q},\mathrm{CNOT}^{q,q^{\prime}}\notin{\mathbf{s}}^{l}$, if $R_{y}^{q}$
and $\mathrm{CNOT}^{q^{\prime\prime},q}$ $\notin{\mathbf{s}}^{k}$, $\forall q$
with $\left|0\right>$ initialization, $q^{\prime}$ and $q^{\prime\prime}$,
$l>k>0$;

  2. 2.

$\mathrm{CNOT}^{q_{1},q_{2}}\notin{\mathbf{s}}^{l}$, if
$\exists\mathrm{CNOT}^{q_{1},q_{2}}\in{\mathbf{s}}^{k}$ such that
$R_{y}^{q_{1}}$, $R_{y}^{q_{2}}$, $R_{z}^{q_{2}}$,
$\mathrm{CNOT}^{q^{\prime},q_{1}}$, $\mathrm{CNOT}^{q_{2},q^{\prime}}$, and
$\mathrm{CNOT}^{q^{\prime},q_{2}}$ $\notin{\mathbf{s}}^{m}$, $\forall
q,q^{\prime}$, $k<m<l<0$;

  3. 3.

$R_{z}^{q}\notin{\mathbf{s}}^{l}$, if $R_{y}^{q}$ and
$\mathrm{CNOT}^{q^{\prime},q}$ $\notin{\mathbf{s}}^{l-1}$, $\forall
q,q^{\prime}$, $l>0$;

  4. 4.

$R_{y}^{q}\notin{\mathbf{s}}^{l}$, if $R_{z}^{q}$,
$\mathrm{CNOT}^{q,q^{\prime}}$, and
$\mathrm{CNOT}^{q^{\prime},q}\notin{\mathbf{s}}^{l-1}$, $\forall
q,q^{\prime}$, $l>1$.

  5. 5.

${\mathbf{s}}^{l}$ is empty if ${\mathbf{s}}^{l-1}$ is empty, $l>1$.

The first constraint follows the fact that $R_{z}^{q}$ and
$\mathrm{CNOT}^{q,q\prime}$ preserve the state of the quantum system when the
quantum state of $q$ is $\left|0\right>$. The second constraint avoids two
consecutive CNOT gates with identical control and target qubits. As a result,
the first two constraints eliminate deletable combinations of quantum gates.
The mergeable combinations are extinguished by constraints 3 and 4 by
prohibiting consecutive $R_{z}$ and $R_{y}$, respectively. Finally, the
bijection between practical implementations of ansatzes and paths is
established by the conjunction of constraints 3 to 5. Consequently, the size
of the search space $\left|\mathbb{S}(N_{l})\right|$ is significantly reduced.
We provide an example Eg. 4 to demonstrate the efficiency obtained from our
constraints.

###  4.2 Pool training

In this subsection, the _pool training_ stage is presented in detail. Based on
the weight-sharing policy, the number of parameters required to be trained is
reduced to $\mathcal{O}(N_{l})$. Moreover, the double $\epsilon$-greedy
strategy is exploited accompanied by a candidate tree to mitigate the training
competitions among ansatzes. We treat the _pool training_ as a one-shot
training program. At each iteration, several ansatzes are randomly sampled and
estimated. According to the estimated performance, several temporarily
outstanding ansatzes are selected to update parameters in specified steps
(typically one step) via a gradient-based optimizer.

Recall that solving VQ-VQE in the framework as described in Alg. 1 requires
the initialization of $\mathbb{P}_{0}$ in which each structure of ansatz links
to an independent set of parameters. Intuitively, that parameters
$\bm{\theta}_{U}\in\mathbb{P}_{0}$ substantially reflect the actual
performance of ansatz $U$, i.e.,
$\bm{\theta}_{U}\approx\arg\min_{\bm{\theta}}C(U,\bm{\theta})$, facilitates
the optimal ansatz determination. Therefore, we conduct a pre-training of
parameters before the alternate optimization solving VA-VQE instead of random
initialization. Unfortunately, the size of $\mathbb{P}_{0}$ is exponentially
large with respect to $n$ and $N_{l}$ resulting from the exponentially large
$\mathbb{S}(N_{l})$. It is impractical to adequately train $\mathbb{P}_{0}$
efficiently.

Instead, we construct a parameter pool with linear size with respect to
$N_{l}$ via applying the weight-sharing policy and train the pool to
eventually derive $\mathbb{P}_{0}$. The parameter pool can be matrix-like
defined as

$P:=\begin{bmatrix}\bm{\theta}_{{\mathbf{s}}_{1},1}&\bm{\theta}_{{\mathbf{s}}_{1},2}&\ldots&\bm{\theta}_{{\mathbf{s}}_{1},N_{l}}\\\
\bm{\theta}_{{\mathbf{s}}_{2},1}&\bm{\theta}_{{\mathbf{s}}_{2},2}&\ldots&\bm{\theta}_{{\mathbf{s}}_{2},N_{l}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\bm{\theta}_{{\mathbf{s}}_{N_{s}},1}&\bm{\theta}_{{\mathbf{s}}_{N_{s}},2}&\ldots&\bm{\theta}_{{\mathbf{s}}_{N_{s}},N_{l}}\\\
\end{bmatrix},$ (28)

where $\bm{\theta}_{k,l}$ represents the parameters at the $l$th layer
corresponding to the state ${\mathbf{s}}_{k}$. Then, parameters of an ansatz
$\left({\mathbf{v}}^{0},{\mathbf{v}}^{1},\ldots,{\mathbf{v}}^{N_{l}}\right)$
is

$\bm{\theta}:=\bm{\theta}_{{\mathbf{s}}^{1},1}\oplus\bm{\theta}_{{\mathbf{s}}^{2},2}\oplus\ldots\oplus\bm{\theta}_{{\mathbf{s}}^{N_{l}},N_{l}},$
(29)

where $\oplus$ indicates the direct sum such that

$\begin{bmatrix}a_{1}\\\ a_{2}\\\ \vdots\\\
a_{N}\end{bmatrix}\oplus\begin{bmatrix}b_{1}\\\ b_{2}\\\ \vdots\\\
b_{N}\end{bmatrix}=\begin{bmatrix}a_{1}\\\ \vdots\\\ a_{N}\\\ b_{1}\\\
\vdots\\\ b_{N}\end{bmatrix}.$

It can be simply derived that parameters in identical layers and states are
shared among ansatzes, which is the direct effect of applying the weight-
sharing policy. Then, the number of trainable parameters is in
$\mathcal{O}({N_{s}N_{l}})$, which is linear with respect to $N_{l}$. The
exponentially reduction significantly boosts the efficiency of parameter
training. However, the training competitions are therefore introduced.

Inspired by the $\epsilon$-greedy strategy from traditional machine learning
[45], we propose the double $\epsilon$-greedy strategy based on the candidate
tree to mitigate the training competitions. Remarkably, our proposed method
not only differentiates ‘good’ and ‘bad’ ansatzes but also ansatzes among the
two categories.

Recall that the search space $\mathbb{S}(N_{l})$ can be represented by a tree.
It is intuitive that constructing a tree to save potentially ‘good’ ansatzes
and discarding potentially ‘bad’ ansatzes are reasonable for the
differentiation. The tree spanned by paths representing potentially ‘good’
ansatzes is named the candidate tree. Each node ${\mathbf{v}}$ in the tree
maintains a leaf count $c_{l}({\mathbf{v}})$ to indicate the number of leaf
nodes below ${\mathbf{v}}$ and a training count $c_{t}({\mathbf{v}})$ to
record the total times of training of the node. At each path sampling
procedure, the GSA samples a path from the candidate tree with the probability
$\epsilon_{1}$ and the $\mathbb{S}(N_{l})$ uniformly with the probability
$1-\epsilon_{1}$. While sampling from the candidate tree, nodes are
successively sampled from the root to a leaf. Since only potentially ‘good’
ansatzes are appended to the candidate tree and recorded the training count of
nodes via the one-shot training scheme, nodes in the candidate tree with a
large training count may intuitively have more probability to construct
potentially ‘good’ ansatzes. Let the last selected node be
${\mathbf{v}}^{l-1}$, $1\leq l\leq N_{l}$, linked to child nodes
${\mathbf{v}}_{1}^{l},{\mathbf{v}}_{2}^{l},\ldots,{\mathbf{v}}_{N_{\mathbf{v}}}^{l}$.
Then, the next node is sampled as ${\mathbf{v}}_{k}^{l}$ with the probability

${\rm Pr}({\mathbf{v}}^{l}_{k};\eta)=\frac{c_{l}({\mathbf{v}}^{l}_{k})+\eta
c_{t}({\mathbf{v}}^{l}_{k})}{\sum_{i=1}^{N_{{\mathbf{v}}}}c_{l}({\mathbf{v}}^{l}_{i})+\eta
c_{t}({\mathbf{v}}^{l}_{i})},$ (30)

where $\eta=1$ with the probability $\epsilon_{2}$ representing the greedy
sampling and $\eta=0$ with the probability $1-\epsilon_{2}$ representing the
uniform sampling. The ansatz sampling procedure is summarized as Alg. 3.

As depicted in Fig. 2, at each main process iteration of the _pool training_ ,
the GSA samples $N_{s1}$ paths exploiting the double $\epsilon$-greedy
strategy. Then, the cost function values and gradients of sampled ansatzes are
estimated with corresponding parameters from the parameter pool. Subsequently,
the $N_{r1}$-rank solution $\mathbb{U}_{n}({N_{r1}})$ of Prob. 3 is determined
among the sampled ansatzes. For each ansatz $U\in\mathbb{U}_{n}({N_{r1}})$,
corresponding parameters in the parameter pool are updated in one step via
gradient descent optimizer. The main process terminates at iteration $N_{i1}$
or when $c_{l}({\mathbf{v}}^{0})$ is stable that the value has been preserved
for $N_{t1}$ iterations which means there is no new path appended on the tree.
As a result, the main process of the _pool training_ is summarized as Alg. 4.

Figure 2:  Single iteration of _pool training_ with $N_{l}=3$.

For the stability of _pool training_ , we provide a prethermalization before
the main process. Given an $N_{i0}$, at iteration $i$, the GSA processes as
the main process iteration with
$\epsilon_{1}^{\prime}={(i-1)\epsilon_{1}}/{N_{i0}}$ instead of
$\epsilon_{1}$. The prethermalization of _pool training_ is summarized as Alg.
5.

Finally, the _pool training_ can be described by Alg. 6. After the
initialization of $P$ and $T$, the prethermalization and the main process are
conducted to train $P$ as well as $T$. Subsequently, the set of parameters
$\mathbb{P}_{0}$ can be constructed by expanding $P$ that $\bm{\theta}_{U}$ is
generated by Eq. (28) for any ansatz $U\in\mathbb{S}(N_{l})$. The
$\mathbb{P}_{0}$ and $T$ are output for the next stage.

###  4.3 Alternate training

Recall that the VA-VQE can be solved via alternately solving Prob. 3 and Prob.
1. We exploit the multi-objective genetic algorithm with novel modification.
The set of parameters $\mathbb{P}$ is initialized as $\mathbb{P}_{0}$. The
individuals in the first generation are sampled independently via the double
$\epsilon$-greedy strategy as described in Sec. 4.2 to compose the initial
population.

Figure 3:  Single generation of _alternate training_.

As shown in Fig. 3, at each generation (iteration), ansatzes in
$\mathbb{U}_{n}(N_{r2})$ from solving Prob. 3 with respect to the population
are trained to update $\mathbb{P}$ in $N_{o}$ steps via gradient descent
optimizer. Note that the number of ansatzes in $\mathbb{U}_{n}(N_{r2})$ should
be less than $N_{s2}/2$. Similar to the traditional genetic algorithm NGSA-II,
$N_{s2}/2$ ansatzes are survived. Specifically, the GSA finds an
$N_{r}^{\prime}$ such that

$\left|\mathbb{U}_{n}(N_{r}^{\prime})\right|<N_{s2}/2\leq\left|\mathbb{U}_{n}(N_{r}^{\prime}+1)\right|.$

Then, ansatzes are sequentially inserted to survivals in increasing order of
the cost function value from
$\mathbb{U}_{n}(N_{r}^{\prime}+1)\setminus\mathbb{U}_{n}(N_{r}^{\prime})$.
Subsequently, new ansatzes are generated by applying asexual genetic operators
on survivals to fill the population. We leave the description of asexual
genetic operators in Appendix E. Besides, we introduce the explicit
elimination to the near-completely trained survivals $U$ satisfying
$\alpha\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}<\xi$, where $\alpha$ is
the step size. The eliminated ansatz is recorded if it has the temporarily
lowest cost function value and is erased if there exists an ansatz with a
lower cost function value. Notice that the elimination is conducted after the
application of genetic operators. Therefore, the sampling based on the double
$\epsilon$-greedy is required to refill the population.

The _alternate training_ terminates at the generation $N_{i2}$ or when the
record eliminated ansatz is preserved for $N_{t2}$ generations. As a result,
the ansatz $U^{*}$ with the temporarily lowest cost function value is output
as the quasi-optimal ansatz. Meanwhile, the corresponding parameters
$\bm{\theta}_{U^{*}}$ are output for the next stage as the parameter
initialization. We summarize the _alternate training_ in Alg. 7.

###  4.4 VQE retraining

The final stage of _VQE retraining_ inherits the quasi-optimal ansatz $U^{*}$
and corresponding parameters $\bm{\theta}_{U^{*}}$ output from the _alternate
training_ and provides a guarantee of the sufficiency of the parameter
training of $\bm{\theta}_{U^{*}}$. As traditional VQE training does, this
stage simply trains the parameters of $\bm{\theta}_{U^{*}}$ with the
initialization $\bm{\theta}_{U^{*}}$ until the cost function value converges
or the iteration count reaches $N_{i3}$. We summarize this stage as Alg. 8 for
completeness.

##  5 Numerical Simulations

(a) Ground State Energy

(b) Absolute Error

(c) Quantum Cost

Figure 4:  The average result of determining ground state energy of
$\mathrm{H}_{2}$ in various bond lengths among 100 running times.

(a) Ground State Energy

(b) Absolute Error

(c) Quantum Cost

Figure 5:  The best result of determining ground state energy of
$\mathrm{H}_{2}$ in various bond lengths among 100 running times.

In this section, we conduct numerical simulations on VQE tasks for finding
ground state energies of $\mathrm{H}_{2}$ and $\mathrm{H}_{4}$ molecules to
show the improvement of the proposed framework. Moreover, to demonstrate the
flexibility, we implement a modified version of the proposed framework for
meta-VQE [46] learning energy profiles of parameterized Hamiltonians.

###  5.1 Finding ground state energies

To showcase the improvement of the proposed framework, we compare it with
structure fixed hardware efficient ansatz (HEA) [16] and a fully randomized
(RND) baseline algorithm. To make a fair comparison, we use Python with the
_Pennylane_ package [47] to implement both our and the two compared methods.
The technical details for algorithms to be compared are elaborated as follows:

  * •

HEA. HEA utilizes a fixed layer pattern to construct the whole circuit. The
layer construction used in this implementation is depicted in Appendix B. Note
that this kind of ansatzes is also widely used in other implementations, e.g.,
[10, 11];

  * •

RND. We sample $N_{Rs}$ circuits with $N_{l}$ layers and unique random
parameters, then process the VQE retraining and output the circuit with the
minimum cost function value.

We assume that depolarization dominates the quantum error in the quantum
hardware. Then, the noise operator (depolarizing channel) is

$\begin{gathered}\Phi(p,\sigma)=\sum_{i=0}^{3}K_{i}(p)\sigma
K_{i}^{\dagger}(p),\\\ K_{0}=\sqrt{1-p}\left[\begin{matrix}1&0\\\
0&1\end{matrix}\right],K_{1}=\sqrt{\frac{p}{3}}\left[\begin{matrix}0&1\\\
1&0\end{matrix}\right],K_{2}=\sqrt{\frac{p}{3}}\left[\begin{matrix}0&-i\\\
i&0\end{matrix}\right],K_{3}=\sqrt{\frac{p}{3}}\left[\begin{matrix}1&0\\\
0&-1\end{matrix}\right],\end{gathered}$

where $p\in[0,1]$ is the depolarization probability and $\sigma$ is a density
matrix of a single qubit [47]. In our configuration, a depolarizing channel
with depolarization probability $p=0.001$ is applied after a single-qubit
gate. We simultaneously apply two depolarizing channels with depolarization
probability $p=0.01$ after a CNOT, i.e., apply one on the control qubit, and
one on the target qubit.

Figure 6:  Mean square error among 100 running times.

The criteria used for all methods are absolute error between the obtained and
exact optimal cost function values, and the invoking times for the calculation
of the cost function (termed _quantum cost_ henceforth), respectively. For VA-
VQE, we analyze the distribution of performances of output ansatzes and
calculate the mean square error (MSE) mathematically represented by

$MSE=\frac{1}{M}\sum_{i=1}^{M}(\hat{C}^{*}_{i}-C_{exact}^{*})^{2}$ (31)

to indicate the stability to obtain the quasi-optimal cost function values,
where $M$ is the total running time, $\hat{C}^{*}$ is the output quasi-optimal
cost function value and $C_{exact}^{*}$ is the exact optimal cost function
value.

Figure 7:  Detail of cost function values with respect to quantum cost in
solving the ground state energy of $\mathrm{H}_{2}$ in bond length $0.7$Å
among 100 running times. (a) The average cost function values with respect to
quantum cost. (b) The cost function values among 100 running times with
respect to quantum cost in the running time which output the ansatz with the
lowest cost function value among 100 running times. The $\blacktriangle$,
$\blacktriangledown$, and $\times$ represent the termination of _pool
training_ ’s prethermalization, _pool training_ ’s main process, and
_alternate training_ , respectively.

(a) $\mathrm{H}_{2}$ in bond length $0.7$Å

(b) $\mathrm{H}_{4}$ in bond length $0.7$Å

Figure 8:  Output quasi-optimal cost function values with respect to the
quantum cost of 100 running times in solving the ground state energy. Dashed
lines present cost function values on average.

We first conduct numerical simulations on determining the ground state
energies of Hamiltonians of $\mathrm{H}_{2}$ in various bond lengths. The
quantum device is assumed to have 4 qubits with ring connectives and
depolarization error being imposed by the classical simulator. For the
proposed framework, we empirical set $N_{l}=3$, $\alpha_{0}=5$, $\xi=0.003$,
$\epsilon_{1}=\epsilon_{2}=0.8$, $N_{s1}=N_{s2}=16$, $N_{r1}=1$, $N_{r2}=2$,
$N_{i0}=N_{i1}=2$, $N_{i2}=100$, $N_{i3}=10$, $N_{t1}=1$, $N_{t2}=4$, and
$N_{o}=5$; for HEA, we exploit 2-layer HEA as HEA-2 and 3-layer HEA as HEA-3;
for RND, we set $N_{l}=3$ and $N_{Rs}=6000$ such that the quantum costs of GSA
and RND are approximately equal.

For each bond length, we conduct the GSA and comparison methods $100$ times,
respectively. The results on average are shown in Fig. 4. It can be found that
our algorithm can determine ground state energy with consistently lower
absolute error on average than the compared algorithms in terms of the
absolute error in various bond lengths, and with lower quantum cost compared
to RND. This conclusion holds while considering the ansatzes with the lowest
cost function values among the $100$ running times as depicted in Fig. 5.
Moreover, GSA exhibits outstanding stability as shown in Fig. 6. Remarkably,
VA-VQE methods performs better in terms of absolute error at a cost of quantum
cost than HEA in most bond lengths.

For bond length $0.7$Å, we also record the quantum cost and absolute error for
each running time in Fig. 7 and Fig. 8(a) when the algorithm converges to the
final output result. It can be concluded that our algorithm can obtain the
best solution on average with a rather small quantum cost (about 6107.49)
which is conspicuously better than HEA (up to 87.9% improvement in terms of
error) and RND (up to 36.0% and 58.7% improvement in terms of error and
stability, respectively). Remarkably, GSA can asymptotically reach the best
ansatz among the training, which means that a temporarily quasi-optimal ansatz
can be output at any generation of _alternate training_. However, our
framework shows large variance of the quantum cost. This may result from the
termination conditions of the three stages. It can be concluded that the
termination conditions prevent the redundant iterations which can not
significantly benefit the training, and thus the performance of our framework
may not be sensitive to hyperparameters $N_{i0}$, $N_{i1}$, $N_{i2}$, and
$N_{i3}$ when they are sufficiently large.

Table 1: The result of determining the ground state energy of $\mathrm{H}_{4}$ in bond length $0.7$Å. Data outside and inside brackets represent the average and the best values among 100 running times, respectively. | GSA | RND | HEA-2 | HEA-3
---|---|---|---|---
energy [$\mathrm{Ha}$] | -5.762(-5.828) | -5.728(-5.793) | -5.350(-5.487) | -5.230(-5.439)
absolute error [$\mathrm{Ha}$] | 0.134(0.068) | 0.167(0.103) | 0.546(0.408) | 0.666(0.457)
error improvement | - | 20.1%(34.1%) | 75.5%(83.4%) | 79.9%(85.2%)
quantum cost | 8579(6301) | 8811(8741) | 2665(2695) | 3865(3887)
stability | 0.020 | 0.029 | - | -

We also conduct 6-qubit simulations for $\mathrm{H}_{4}$ in bond length
$0.7$Å. Configurations of GSA and HEA are set as them for $\mathrm{H}_{2}$. As
for RND, we set $N_{Rs}=8600$. Results of the simulations are shown in Tab. 1
and Fig. 8(b). Remarkably, the proposed method still shows significant
improvements in terms of absolute error by up to 75.5% on average compared to
HEA and both the absolute error and stability by up to 20.1% and 29.5%,
respectively, compared to RND.

###  5.2 Learning energy profiles

To showcase the flexibility, we implement a modified version of the proposed
framework for Meta-VQE [46]. Let the parameterized Hamiltonian be $H(\Delta)$.
Then, sample $M$ available values of $\Delta$ denoted by $\Delta_{1}$,
$\Delta_{2}$, $\ldots$, $\Delta_{M}$ as training bonds. Hence, the cost
function for training Meta-VQE is defined by

$C_{\mathrm{Meta}}(\bm{\theta})=\sum_{i=1}^{M}{\rm
Tr}\left[H(\Delta_{i})U(\bm{f}(\Delta_{i};\bm{\theta}))\rho_{i}U^{\dagger}(\bm{f}(\Delta_{i};\bm{\theta}))\right],$
(32)

where $\bm{f}(\Delta_{i};\cdot)$ represents the encoding function of the
parameter of the Hamiltonian with respect to operand trainable parameters.
After parameter training, the landscape of

$V_{\mathrm{Meta}}(\Delta)={\rm
Tr}\left[H(\Delta)U(\bm{f}(\Delta_{i};\bm{\theta}))\rho_{i}U^{\dagger}(\bm{f}(\Delta;\bm{\theta}))\right]$
(33)

exhibits the energy profile of the parameterized Hamiltonian.

We implement the Meta-VQE adapted GSA by simply identifying each state
${\mathbf{s}}$ by both the structure and the encoding function of each single-
qubit gate in the structure to enable the auto-decision of the encoding
methods. Here we provide 3 encoding functions for parameters of single-qubit
gates. They are, respectively,

$\displaystyle f_{1}(\Delta;\theta)=\theta,$ (34) $\displaystyle
f_{2}(\Delta;\theta,\gamma)=\theta\Delta+\gamma,$ (35) $\displaystyle
f_{3}(\Delta;\theta,\gamma)=\theta e^{\Delta}+\gamma.$ (36)

We compare our framework with the HEA implementation. Each HEA consists of
$N_{le}$ encoding layers and $N_{lp}$ processing layers and is denoted by
HEA-$N_{le}$-$N_{lp}$. Specifically, $f_{2}$ and $f_{1}$ are applied on each
single-qubit gate in encoding layers and processing layers, respectively.

(a) Energy Profile

(b) Absolute Error

Figure 9:  The result of determining the energy profile of $\mathrm{H}_{2}$. Table 2: The variance of absolute error and corresponding improvement. | GSA | HEA-1-1 | HEA-2-2 | HEA-3-1 | HEA-4-0
---|---|---|---|---|---
variance | 0.001 | 0.078 | 0.024 | 0.020 | 0.033
improvement | - | 98.8% | 96.1% | 95.4% | 97.2%

Simulations are conducted for $\mathrm{H}_{2}$, where $\Delta$ in $H(\Delta)$
represents the bond length. Training bonds are set as 0.5, 0.9, 1.3, 1.7, 2.1,
2.5 and 2.9. We set $N_{l}=4$ and other configurations as that for the VQE
task of $\mathrm{H}_{2}$. Results are shown in Fig. 9 and Tab. 2. It can be
concluded that our framework learns the energy profile with the conspicuously
lower variance of absolute error, which indicates more information on chemical
properties.

##  6 Conclusion

In this paper, addressing the issues in mitigating the BP phenomenon in VQE,
we propose a gradient-sensitive alternate framework for VQE with the variable
ansatz strategy. We propose a theoretical framework that highlights the
magnitude of gradient and exploits the alternate optimization scheme so that
the local optimum can be avoided from the ansatz perspective. It can be
theoretically proved that the result of the proposed theoretical framework is
a subset of the results of the original VA-VQE.

Then, based on the theoretical framework, a novel implementation named GSA is
proposed with three stages. We reduce the size of the search space of the
ansatz via applying gate commutation rules and establishing a bijection
between the search space and the practical implementations of ansatzes to
boost the time efficiency of the optimal ansatz and parameter determination.
Exploiting the double $\epsilon$-greedy strategy based on the candidate tree,
an initialization of parameters is determined, so that the training
competitions are mitigated and the local optimal can be evaded from the
parameter perspective. Based on the initialization of parameters, the GSA
follows the framework with an elaborately modified genetic algorithm to find
and train a quasi-optimal ansatz.

Finally, we conduct numerical simulations on quantum chemistry to find the
ground state energy of a quantum system. We adopt relatively fair criteria for
measuring the performance of VA-VQE so that the transverse comparison among
methods of VA-VQE can be clearly conducted. As a result, the GSA shows
conspicuously better performance on average compared to the structure fixed
HEA up to 87.9% improvement in terms of absolute error. Furthermore, compared
to the full-randomized RND, our framework obtains up to 36.0% and 58.7%
improvement in terms of error and stability, respectively, with similar
quantum costs. Moreover, we implement a modified version of our proposed
framework for meta-VQE learning the energy profile of parameterized
Hamiltonians to show the flexibility.

Although the proposed method obtained better results, further research is
required to be conducted. For example, GSA requires a large number of
hyperparameters to be adjusted such as $N_{l}$. Research on automatic
hyperparameter adjustment may be meaningful for the VA-VQE.

## Acknowledgements

This work was supported by the National Science Foundation of China (No.
61871111 and No. 61960206005) and the Fundamental Research Funds for the
Central Universities (No. 2242022k30006 and No. 2242022k30001).

## References

  * [1] Lov K Grover.  “Quantum computers can search arbitrarily large databases by a single query”.  Physical review letters 79, 4709 (1997).
  * [2] Peter W Shor.  “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”.  In SIAM Review.  Volume 41, pages 303–332.  SIAM (1999).
  * [3] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  “Quantum algorithm for linear systems of equations”.  Physical review letters 103, 150502 (2009).
  * [4] Guang Hao Low and Isaac L. Chuang.  “Hamiltonian simulation by qubitization”.  Quantum 3, 163 (2019).
  * [5] John Preskill.  “Quantum computing in the NISQ era and beyond”.  Quantum 2, 79 (2018).
  * [6] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’brien.  “A variational eigenvalue solver on a photonic quantum processor”.  Nature communications 5, 1–7 (2014).
  * [7] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles.  “Variational Quantum Linear Solver” (2020).  arXiv:1909.05820.
  * [8] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C. Benjamin.  “Theory of variational quantum simulation”.  Quantum 3, 191 (2019).
  * [9] Xin Wang, Zhixin Song, and Youle Wang.  “Variational quantum singular value decomposition”.  Quantum 5, 483 (2021).
  * [10] Fan-Xu Meng, Ze-Tong Li, Xutao Yu, and Zaichen Zhang.  “Quantum algorithm for MUSIC-based DOA estimation in hybrid MIMO systems”.  Quantum Science and Technology (2021).
  * [11] Ze-Tong Li, Fan-Xu Meng, Xu-Tao Yu, and Zai-Chen Zhang.  “Quantum algorithm for Laplacian eigenmap via Rayleigh quotient iteration”.  Quantum Information Processing 21, 1–20 (2022).
  * [12] Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J. Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf.  “Training deep quantum neural networks”.  Nature Communications 11, 808 (2020).
  * [13] Amira Abbas, David Sutter, Christa Zoufal, Aurelien Lucchi, Alessio Figalli, and Stefan Woerner.  “The power of quantum neural networks”.  Nature Computational Science 1, 403–409 (2021).
  * [14] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  “Quantum machine learning”.  Nature 549, 195–202 (2017).
  * [15] Vojtěch Havlíček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta.  “Supervised learning with quantum-enhanced feature spaces”.  Nature 567, 209–212 (2019).
  * [16] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta.  “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets”.  Nature 549, 242–246 (2017).
  * [17] Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao.  “Quantum circuit architecture search: Error mitigation and trainability enhancement for variational quantum solvers” (2020).  arXiv:2010.10217.
  * [18] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven.  “Barren plateaus in quantum neural network training landscapes”.  Nature communications 9, 1–6 (2018).
  * [19] Taylor L. Patti, Khadijeh Najafi, Xun Gao, and Susanne F. Yelin.  “Entanglement devised barren plateau mitigation”.  Physical Review Research 3, 033090 (2021).
  * [20] Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe.  “Entanglement-Induced Barren Plateaus”.  PRX Quantum 2, 040316 (2021).
  * [21] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles.  “Cost function dependent barren plateaus in shallow parametrized quantum circuits”.  Nature communications 12, 1–12 (2021).
  * [22] Stefan H. Sack, Raimel A. Medina, Alexios A. Michailidis, Richard Kueng, and Maksym Serbyn.  “Avoiding barren plateaus using classical shadows” (2022).  arXiv:2201.08194.
  * [23] Zoë Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles.  “Connecting ansatz expressibility to gradient magnitudes and barren plateaus”.  PRX Quantum 3, 010313 (2022).  arXiv:2101.02138.
  * [24] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J. Coles.  “Noise-induced barren plateaus in variational quantum algorithms”.  Nature communications 12, 1–11 (2021).
  * [25] Arthur G. Rattew, Shaohan Hu, Marco Pistoia, Richard Chen, and Steve Wood.  “A Domain-agnostic, Noise-resistant, Hardware-efficient Evolutionary Variational Quantum Eigensolver” (2020).  arXiv:1910.09694.
  * [26] Shi-Xin Zhang, Chang-Yu Hsieh, Shengyu Zhang, and Hong Yao.  “Differentiable Quantum Architecture Search” (2021).  arXiv:2010.08561.
  * [27] Mateusz Ostaszewski, Lea M. Trenkwalder, Wojciech Masarczyk, Eleanor Scerri, and Vedran Dunjko.  “Reinforcement learning for optimization of variational quantum circuit architectures”.  In Advances in Neural Information Processing Systems.  Volume 34, pages 18182–18194.  Curran Associates, Inc. (2021).
  * [28] M. Bilkis, M. Cerezo, Guillaume Verdon, Patrick J. Coles, and Lukasz Cincio.  “A semi-agnostic ansatz with variable structure for quantum machine learning” (2022).  arXiv:2103.06712.
  * [29] Zi-Jian Zhang, Thi Ha Kyaw, Jakob Kottmann, Matthias Degroote, and Alan Aspuru-Guzik.  “Mutual information-assisted adaptive variational quantum eigensolver”.  Quantum Science and Technology (2021).
  * [30] Fanxu Meng, Ze-Tong Li, Xu-Tao Yu, and Zai-Chen Zhang.  “Quantum Circuit Architecture Optimization for Variational Quantum Eigensolver via Monto-Carlo Tree Search”.  IEEE Transactions on Quantum Engineering (2021).
  * [31] D. Chivilikhin, A. Samarin, V. Ulyantsev, I. Iorsh, A. R. Oganov, and O. Kyriienko.  “MoG-VQE: Multiobjective genetic variational quantum eigensolver” (2020).  arXiv:2007.04424.
  * [32] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter.  “Neural Architecture Search: A Survey” (2019).  arXiv:1808.05377.
  * [33] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii.  “Quantum circuit learning”.  Physical Review A 98, 032309 (2018).
  * [34] Philip Wolfe.  “Convergence conditions for ascent methods”.  SIAM review 11, 226–235 (1969).
  * [35] Sukin Sim, Peter D. Johnson, and Alán Aspuru-Guzik.  “Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms”.  Advanced Quantum Technologies 2, 1900070 (2019).
  * [36] Kouhei Nakaji and Naoki Yamamoto.  “Expressibility of the alternating layered ansatz for quantum computation”.  Quantum 5, 434 (2021).
  * [37] Marco Cerezo and Patrick J. Coles.  “Higher order derivatives of quantum neural networks with barren plateaus”.  Quantum Science and Technology 6, 035006 (2021).
  * [38] Andrew Arrasmith, M. Cerezo, Piotr Czarnik, Lukasz Cincio, and Patrick J. Coles.  “Effect of barren plateaus on gradient-free optimization”.  Quantum 5, 558 (2021).
  * [39] Daniel Stilck França and Raul Garcia-Patron.  “Limitations of optimization algorithms on noisy quantum devices”.  Nature Physics 17, 1221–1227 (2021).
  * [40] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger, and Patrick J. Coles.  “Absence of barren plateaus in quantum convolutional neural networks”.  Physical Review X 11, 041011 (2021).
  * [41] Tyler Volkoff and Patrick J. Coles.  “Large gradients via correlation in random parameterized quantum circuits”.  Quantum Science and Technology 6, 025008 (2021).
  * [42] Andrea Skolik, Jarrod R. McClean, Masoud Mohseni, Patrick van der Smagt, and Martin Leib.  “Layerwise learning for quantum neural networks”.  Quantum Machine Intelligence 3, 1–11 (2021).
  * [43] Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti.  “An initialization strategy for addressing barren plateaus in parametrized quantum circuits”.  Quantum 3, 214 (2019).
  * [44] Guillaume Verdon, Michael Broughton, Jarrod R. McClean, Kevin J. Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, and Masoud Mohseni.  “Learning to learn with quantum neural networks via classical neural networks” (2019).  arXiv:1907.05415.
  * [45] Shan You, Tao Huang, Mingmin Yang, Fei Wang, Chen Qian, and Changshui Zhang.  “Greedynas: Towards fast one-shot nas with greedy supernet”.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition.  Pages 1999–2008.  IEEE (2020).
  * [46] Alba Cervera-Lierta, Jakob S. Kottmann, and Alán Aspuru-Guzik.  “Meta-variational quantum eigensolver: Learning energy profiles of parameterized hamiltonians for quantum simulation”.  PRX Quantum 2, 020329 (2021).
  * [47] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M. Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, Keri McKiernan, Johannes Jakob Meyer, Zeyue Niu, Antal Száva, and Nathan Killoran.  “PennyLane: Automatic differentiation of hybrid quantum-classical computations” (2020).  arXiv:1811.04968.

##  Appendix A Examples

######  Example 1 (A VQE Task).

The VQE is to find the ground state energy of a quantum system where the
dynamic can be described by a Hamiltonian $H$. Setting the observable $O=H$,
the function $f(x)=x$, the input state $\rho=\left|0\right>\left<0\right|$
,and the ansatz $U(\bm{\theta})$ as the hardware efficient ansatz (c.f.
Appendix B), where $\bm{\theta}\in\left(-\pi,\pi\right]^{d}$ and $d$ is the
number of parameters, the problem is

$\min_{\bm{\theta}\in\left(-\pi,\pi\right]^{d}}C(\bm{\theta})={\rm
Tr}\left[HU(\bm{\theta})\left|0\right>\left<0\right|U^{\dagger}(\bm{\theta})\right].$
(37)

######  Example 2 (Not Bijection).

For a $2$-qubit quantum system, $N_{l}=2$, define ${\mathbf{s}}_{1}$ and
${\mathbf{s}}_{2}$ as $(I^{q_{1}},R_{y}^{q_{2}})$ and
$(R_{y}^{q_{1}},I^{q_{2}})$, respectively. Then, the practical implementations
of two ansatzes described by paths

$\displaystyle{\mathbf{p}}_{1}$
$\displaystyle=({\mathbf{v}}^{0},{\mathbf{v}}_{1}^{1}:=({\mathbf{v}}^{0},{\mathbf{s}}_{1}),{\mathbf{v}}_{1}^{2}:=({\mathbf{v}}^{1},{\mathbf{s}}_{2})),$
$\displaystyle{\mathbf{p}}_{2}$
$\displaystyle=({\mathbf{v}}^{0},{\mathbf{v}}_{2}^{1}:=({\mathbf{v}}^{0},{\mathbf{s}}_{2}),{\mathbf{v}}_{2}^{2}:=({\mathbf{v}}^{1},{\mathbf{s}}_{1}))$

are identical.

######  Example 3 (Mergeable & Deletable).

For a $4$-qubit quantum system, $N_{l}=2$, define

$\displaystyle{\mathbf{s}}_{1}$
$\displaystyle:=(I^{q_{1}},R_{y}^{q_{2}},\mathrm{CNOT}^{q_{3},q_{4}}),$
$\displaystyle{\mathbf{s}}_{2}$
$\displaystyle:=(R_{z}^{q_{1}},R_{y}^{q_{2}},\mathrm{CNOT}^{q_{3},q_{4}}),$
$\displaystyle{\mathbf{s}}_{3}$
$\displaystyle:=(R_{z}^{q_{1}},R_{y}^{q_{2}}).$

Then, the practical implementations of two ansatzes described by paths

$\displaystyle{\mathbf{p}}_{1}$
$\displaystyle=({\mathbf{v}}^{0},{\mathbf{v}}_{1}^{1}:=({\mathbf{v}}^{0},{\mathbf{s}}_{1}),{\mathbf{v}}_{1}^{2}:=({\mathbf{v}}^{1},{\mathbf{s}}_{2})),$
$\displaystyle{\mathbf{p}}_{2}$
$\displaystyle=({\mathbf{v}}^{0},{\mathbf{v}}_{2}^{1}:=({\mathbf{v}}^{0},{\mathbf{s}}_{3}),{\mathbf{v}}_{2}^{2}:=({\mathbf{v}}^{1},(\leavevmode\nobreak\
))),$

are equivalent.

######  Example 4 (Size of Search Space).

The number of possible paths in a $4$-qubit quantum system under the setting
as described in Sec. 2.6 with and without the gates commutation rules $N_{w/}$
and $N_{w/o}$ with respect to $N_{l}$ are demonstrated in Tab.3

Table 3: The number of possible paths with respect to $N_{l}$. $N_{l}$ | $N_{w/}$ | $N_{w/o}$ | $\frac{N_{w/}}{N_{w/o}}$
---|---|---|---
1 | 56 | 567 | 9.88%
2 | 11768 | 321489 | 3.66%
3 | 2859977 | 182284263 | 1.57%

##  Appendix B Hardware efficient ansatz

The hardware efficient ansatz (HEA) was first proposed in [16] to conduct VQE
for small molecules and quantum magnets. It is constructed in a layer-by-layer
fashion in which each layer has an identical structure. Specifically, a layer
is organized by native single-qubit gates on all qubits and naturally
available entangling interactions. In our setting, based on the native gates
as described in Sec. 2.6, we exploit the HEA with layers as depicted in Fig.
10.

Figure 10: Layer construction used in HEA.

##  Appendix C Proof of Theorem 1

Solution of Prob. 1 is a set of parameters

$\Theta^{*}=\\{\bm{\theta}^{*}|C(\bm{\theta}^{*})=\min_{\bm{\theta}\in\mathbb{D}^{d}}C(\bm{\theta})\\}.$
(38)

$\left\\{(U^{*},\Theta^{*})\left|\begin{gathered}C(U^{*},\bm{\theta}^{*})=\min_{U,\bm{\theta}}C(U,\bm{\theta}),\\\
\forall\bm{\theta}^{*}\in\Theta^{*}\end{gathered}\right.\right\\}.$ (39)

Given an arbitrary valid $\mathbb{P}$, we divide $\mathbb{S}$ into four
disjoint sets

$\mathbb{U}_{+}^{*}\equiv\left\\{U\left|C(U,\bm{\theta}_{U})=\min_{U,\bm{\theta}}C(U,\bm{\theta})\right.\right\\},$
(40)
$\mathbb{U}_{+}\equiv\left\\{U\left|\exists\bm{\theta}^{\prime},C(U,\bm{\theta}^{\prime})=\min_{U,\bm{\theta}}C(U,\bm{\theta}),\leavevmode\nobreak\
C(U,\bm{\theta}_{U})>\min_{\bm{\theta}}C(U,\bm{\theta})\right.\right\\},$ (41)
$\mathbb{U}_{-}^{*}\equiv\left\\{U\left|\forall\bm{\theta}^{\prime},C(U,\bm{\theta}^{\prime})>\min_{U,\bm{\theta}}C(U,\bm{\theta}),\leavevmode\nobreak\
C(U,\bm{\theta}_{U})=\min_{\bm{\theta}}C(U,\bm{\theta})\right.\right\\},$ (42)
$\mathbb{U}_{-}\equiv\left\\{U\left|\forall\bm{\theta}^{\prime},C(U,\bm{\theta}^{\prime})>\min_{U,\bm{\theta}}C(U,\bm{\theta}),\leavevmode\nobreak\
C(U,\bm{\theta}_{U})>\min_{\bm{\theta}}C(U,\bm{\theta})\right.\right\\}.$ (43)

Note that
$\mathbb{U}_{+}^{*}\cup\mathbb{U}_{+}\cup\mathbb{U}_{-}^{*}\cup\mathbb{U}_{-}=\mathbb{S}$.
We prove the theorem by proving

$\displaystyle\lim_{t\to\infty}\mathbb{U}_{n}\cap\left(\mathbb{U}_{-}^{*}\cup\mathbb{U}_{-}\right)=\emptyset,$
(44)
$\displaystyle\lim_{t\to\infty}\mathbb{U}_{n}=\lim_{t\to\infty}\mathbb{U}_{+}^{*},$
(45)

where $t$ indicates the iteration of the alternate optimization loop.

######  Lemma 1.

$U\in\lim_{t\to\infty}\mathbb{U}_{+}^{*}\cup\mathbb{U}_{-}^{*}$, $\forall
U\in\mathbb{U}_{+}\cup\mathbb{U}_{-}$ such that $\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}>0$.

###### Proof.

By solving the Prob. 3, all ansatzes $U\in\mathbb{U}_{+}\cup\mathbb{U}_{-}$
such that

$\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}=\max_{\bm{\theta}}\frac{\left\|\nabla
C(U,\bm{\theta})\right\|_{2}}{|\bm{\theta}|}>0$

are included in $\mathbb{U}_{n}$. For any $U\in\mathbb{U}_{n}$,
$\bm{\theta}_{U}\in\mathbb{P}$ is updated by $\bm{\theta}^{*}$ such that
$C(U,\bm{\theta}^{*})=\min_{\bm{\theta}}C(U,\bm{\theta})$, which means any
$U\in\mathbb{U}_{n}$ is an element of
$U\in\mathbb{U}_{+}^{*}\cup\mathbb{U}_{-}^{*}$ in the next iteration.
Therefore, any $U\in\mathbb{U}_{+}\cup\mathbb{U}_{-}$ such that
$\frac{\left\|\nabla C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}>0$
will be selected as an element in $\mathbb{U}_{n}$ if $t\to\infty$. Then, we
have $U\in\lim_{t\to\infty}\mathbb{U}_{+}^{*}\cup\mathbb{U}_{-}^{*}$, $\forall
U\in\mathbb{U}_{+}\cup\mathbb{U}_{-}$ such that $\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}>0$. ∎

Further, it is straightforward that $U\in\lim_{t\to\infty}\mathbb{U}_{+}^{*}$,
$\forall U\in\mathbb{U}_{+}$ such that $\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}>0$ and
$V\in\lim_{t\to\infty}\mathbb{U}_{-}^{*}$, $\forall V\in\mathbb{U}_{-}$ such
that $\frac{\left\|\nabla
C(V,\bm{\theta}_{V})\right\|_{2}}{|\bm{\theta}_{V}|}>0$. Since
$C(U,\bm{\theta}_{U})=\min_{\bm{\theta}}C(U,\bm{\theta})$ for all
$U\in\mathbb{U}_{+}^{*}\cup\mathbb{U}_{-}^{*}$, we have that

$\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|}=0,\leavevmode\nobreak\
\forall U\in\mathbb{U}_{+}^{*}\cup\mathbb{U}_{-}^{*}.$ (46)

Therefore, if $\mathbb{U}_{+}^{*}$ is not empty, then inequalities Eq. (23)
and Eq. (24) are simultaneously established for all $U\in\mathbb{U}_{-}^{*}$,
$V\in\mathbb{U}_{+}^{*}$, which means
$\mathbb{U}_{n}\cap\mathbb{U}_{-}^{*}=\emptyset$. Then, we have that

$\lim_{t\to\infty}\mathbb{U}_{n}\cap(\mathbb{U}_{-}^{*}\cup\mathbb{{U}_{-}})=\emptyset,$
(47)

if $\lim_{t\to\infty}U_{+}^{*}\neq\emptyset$.

The simultaneous establishment of Eq. (25) and Eq. (26) of $V$ implies that
$V\in\mathbb{U}_{+}$ with $\frac{\left\|\nabla
C(V,\bm{\theta}_{V})\right\|_{2}}{|\bm{\theta}_{V}|}>0$ or
$V\in\mathbb{U}_{+}^{*}$, which indicates

$\lim_{t\to\infty}U_{+}^{*}\neq\emptyset.$ (48)

It is obvious that $\mathbb{U}_{+}^{*}\subset\mathbb{U}_{n}$ and
$\mathbb{U}_{n}\subset\mathbb{U}_{+}^{*}\cup\mathbb{U}_{+}$. Since

$\lim_{t\to\infty}U_{+}\equiv\left\\{U\left|\begin{gathered}\exists\bm{\theta}^{\prime},C(U,\bm{\theta}^{\prime})=\min_{U,\bm{\theta}}C(U,\bm{\theta}),\\\
\forall\delta>0,\leavevmode\nobreak\
C(U,\bm{\theta}_{U}\in\lim_{t\to\infty}\mathbb{P})=\max_{\bm{\theta}\in\Theta_{U,\delta}}C(U,\bm{\theta})\end{gathered}\right.\right\\},$
(49)

where
$\Theta_{U,\delta}=\\{\bm{\theta}\left|\|\bm{\theta}-\bm{\theta}_{U}\|_{2}<\delta\right.\\}$,
we have that $\lim_{t\to\infty}(\mathbb{U}_{n}\cup\mathbb{U}_{+})=\emptyset$.
Therefore, Eq. (44) and Eq. (45) are established.

##  Appendix D Hyperparameters

Table 4: Hyperparameters. scope | name | notation
---|---|---
global | maximum number of layers | $N_{l}$
reference step size | $\alpha_{0}$
convergence threshold | $\xi$
probabilities for double $\epsilon$-greedy strategy |  $\epsilon_{1}$, $\epsilon_{2}$
pool training | number of sampled ansatzes | $N_{s1}$
maximum number of ranks for updating parameters | $N_{r1}$
stable threshold for terminating | $N_{t1}$
maximum iteration times in the prethermalization | $N_{i0}$
maximum iteration times in the main process | $N_{i1}$
alternate training | population size | $N_{s2}$
maximum number of ranks for updating parameters | $N_{r2}$
stable threshold for terminating | $N_{t2}$
optimization step per generation | $N_{o}$
maximum iteration times | $N_{i2}$
VQE retraining | maximum iteration times | $N_{i3}$

##  Appendix E Genetic Operators

In this appendix, we provide genetic operators the GSA applied in detail. We
only consider the asexual genetic operators for simplicity. Consequently, only
one ansatz is generated from each survival ansatz. All genetic operators
comply with the same structure. First, a new practical implementation of
ansatz is randomly generated. Then, the implementation is refined by the gate
commutation rule. Since the bijection between the search space and the
practical implementations of ansatzes is established, the path representation
of the new implementation is finally output. We introduce the genetic
operators identified in the first step.

#### Mutation:

The mutation operator randomly selects a node ${\mathbf{v}}$ in the survival
ansatz. Then, a child node ${\mathbf{v}}_{new}$ of the parent node of
${\mathbf{v}}$ is randomly sampled. Therefore, a new implementation of ansatz
substituting ${\mathbf{v}}$ by ${\mathbf{v}}_{new}$ is generated.

#### Deletion:

The deletion operator randomly deletes a node in the survival ansatz and
connects its parent node and child node. Then, a new implementation is
generated.

#### Amplification:

The amplification operator randomly selects a node ${\mathbf{v}}$ in the
survival ansatz. Then, a child node of ${\mathbf{v}}$ is inserted into the
ansatz, and therefore a new implementation is generated.

##  Appendix F Pseudocodes for Algorithms

In this appendix, we list the pseudocodes for algorithms. Note that the task
$\mathbb{T}$ is generally omitted as the input parameters of algorithms
without confusion.

Input: $\mathbb{S}$, $\mathbb{P}_{0}$

begin

$\mathbb{P}\leftarrow\mathbb{P}_{0}$; // Initialize $\mathbb{P}$

$\mathbb{U}_{n}\leftarrow\left\\{\,\right\\}$; // Initialize $\mathbb{U}_{n}$

while  _$\mathbb{U}_{n}$ and $\mathbb{P}$ are not converged_ do

$\mathbb{U}_{n}\leftarrow\mathbf{SolveProb\ref{prob:multi_obj}}(\mathbb{S},\mathbb{P})$;

foreach  _$U\in\mathbb{U}_{n}$_ do

$\bm{\theta}_{U}\in\mathbb{P}\leftarrow\mathbf{SolveProb\ref{prob:vqe}}(U)$;

end foreach

end while

end

return _$\mathbb{U}_{n}$ , $\mathbb{P}$._

Algorithm 1 alternate VA-VQE

Input: $\mathbb{G}$

begin

$\mathbb{S}(N_{l})\leftarrow$ Construct search space by $\mathbb{G}$;

$\mathbb{P}_{0},T\leftarrow\mathbf{PoolTraining}(\mathbb{S}(N_{l}))$;

$U^{*},\bm{\theta}_{U^{*}}\leftarrow\mathbf{AlternateTraining}(\mathbb{S}(N_{l}),\mathbb{P}_{0},T)$;

$U^{*},\bm{\theta}^{*}\leftarrow\mathbf{VQETraining}(U^{*},\bm{\theta}_{U^{*}})$;

end

return _$U^{*}$ , $\bm{\theta}^{*}$._

Algorithm 2 GSA

Input: $\mathbb{S}(N_{l})$, $T$, $\epsilon_{1}$, $\epsilon_{2}$

begin

$J_{1}\sim\left\\{(True,\epsilon_{1}),(False,1-\epsilon_{1})\right\\};$

if  _$J_{1}$ is $True$_ then

${\mathbf{v}}\leftarrow{\mathbf{v}}^{0}\in T$;

$U\leftarrow({\mathbf{v}})$;

$\eta\sim\left\\{(1,\epsilon_{2}),(0,1-\epsilon_{2})\right\\}$;

for  _${\mathbf{v}}$ is not a leaf node_ do

$\mathbb{V}_{c}\leftarrow\mathbf{GetChildNodes({\mathbf{v}})}$;

${\mathbf{v}}^{\prime}\sim\left\\{({\mathbf{v}}^{\prime}_{k}\in\mathbb{V}_{c},{\rm
Pr}({\mathbf{v}}^{\prime}_{k};\eta))\right\\}$;

$U\leftarrow U\oplus({\mathbf{v}}^{\prime})$;

${\mathbf{v}}\leftarrow{\mathbf{v}}^{\prime}$;

end for

else

$U\sim\mathbb{S}(N_{l})$;

end if

end

return _$U$._

Algorithm 3 USampling

Input: $\mathbb{S}(N_{l})$, $P$, $T$

begin

$\mathbb{S}\leftarrow\mathbb{S}(N_{l})$;

$t\leftarrow 0$;

$c_{l}^{\prime}\leftarrow 1;$

$i\leftarrow 1$;

for  _$i\leq N_{i1}$_ do

$\mathbb{U}_{s}\leftarrow\left\\{\right\\}$;

for  _$\left|\mathbb{U}_{s}\right| <N_{s1}$_ do

$U\leftarrow\mathbf{USampling}(\mathbb{S},T,\epsilon_{1},\epsilon_{2})$;

$\mathbb{U}_{s}\leftarrow\mathbb{U}_{s}\cup\left\\{U\right\\}$;

end for

$\mathbb{U}_{n}(N_{r1})\leftarrow\mathbf{SolveProb\ref{prob:multi_obj}}(\mathbb{U}_{s},P)$;

foreach  _$U\in\mathbb{U}_{n}(N_{r1})$_ do

$\bm{\theta}\leftarrow\mathbf{GetParameters}(U,P)$;

$\alpha\leftarrow\mathbf{GetStepSize}(\alpha_{0})$;

$\bm{\theta}\leftarrow\bm{\theta}-\alpha\nabla C(U,\bm{\theta})$;

$P\leftarrow\mathbf{UpdatePool}(\bm{\theta},P)$;

$T\leftarrow$ Append $U$ on the candidate tree $T$;

end foreach

if  _$c_{l}({\mathbf{v}}^{0})=c_{l}^{\prime}$_ then

$t\leftarrow t+1$;

if  _$t=N_{t1}$_ then

$\mathbf{break}$;

end if

else

$t\leftarrow 0$;

$c_{l}^{\prime}\leftarrow c_{l}({\mathbf{v}}^{0})$;

end if

$i\leftarrow i+1$;

end for

end

return _$P$ , $T$._

Algorithm 4 PoolTrainingMainProcess

Input: $\mathbb{S}(N_{l})$, $P$, $T$

begin

$\mathbb{S}\leftarrow\mathbb{S}(N_{l})$;

$i\leftarrow 1$

$\epsilon_{1}^{\prime}={(i-1)\epsilon_{1}}/{N_{i0}}$;

for  _$i\leq N_{i1}$_ do

$\mathbb{U}_{s}\leftarrow\left\\{\right\\}$;

for  _$\left|\mathbb{U}_{s}\right| <N_{s1}$_ do

$U\leftarrow\mathbf{USampling}(\mathbb{S},T,\epsilon_{1}^{\prime},\epsilon_{2})$;

$\mathbb{U}_{s}\leftarrow\mathbb{U}_{s}\cup\left\\{U\right\\}$;

$j\leftarrow j+1$;

end for

$\mathbb{U}_{n}(N_{r1})\leftarrow\mathbf{SolveProb\ref{prob:multi_obj}}(\mathbb{U}_{s},P)$;

foreach  _$U\in\mathbb{U}_{n}(N_{r1})$_ do

$\bm{\theta}\leftarrow\mathbf{GetParameters}(U,P)$;

$\alpha\leftarrow\mathbf{GetStepSize}(\alpha_{0})$;

$\bm{\theta}\leftarrow\bm{\theta}-\alpha\nabla C(U,\bm{\theta})$;

$P\leftarrow\mathbf{UpdatePool}(\bm{\theta},P)$;

$T\leftarrow$ Append $U$ on the candidate tree $T$;

end foreach

$i\leftarrow i+1$;

end for

$\mathbb{P}_{0}\leftarrow\mathbf{Expand}(P)$;

end

return _$P$ , $T$._

Algorithm 5 PoolTrainingPrethermalization

Input: $\mathbb{S}(N_{l})$

begin

$P\leftarrow$ Construct parameter pool with $\bm{0}$ initialization;

$T\leftarrow\\{{\mathbf{v}}^{0}\\}$;

$P,T\leftarrow\mathbf{PoolTrainingPrethermalization}(\mathbb{S}(N_{l}),P,T)$;

$P,T\leftarrow\mathbf{PoolTrainingMainProcess}(\mathbb{S}(N_{l}),P,T)$;

$\mathbb{P}_{0}\leftarrow\mathbf{Expand}(P)$;

end

return _$\mathbb{P}_{0}$ , $T$._

Algorithm 6 PoolTraining

Input: $\mathbb{S}(N_{l})$, $\mathbb{P}_{0}$, $T$

begin

$\mathbb{P}\leftarrow\mathbb{P}_{0}$

$\mathbb{U}_{s}\leftarrow\left\\{\right\\}$;

$U_{best}\leftarrow\mathbf{None}$;

for  _$\left|\mathbb{U}_{s}\right|\leq N_{s2}$_ do

$U\leftarrow\mathbf{USampling}(\mathbb{S},T,\epsilon_{1},\epsilon_{2})$;

$\mathbb{U}_{s}\leftarrow\mathbb{U}_{s}\cup\left\\{U\right\\}$;

end for

$i\leftarrow 1$;

for  _$i\leq N_{i2}$_ do

$\mathbb{U}_{n}(N_{r2}),\mathbb{U}_{n}(N_{r}^{\prime}),\mathbb{U}_{n}(N_{r}^{\prime}+1)\leftarrow\mathbf{SolveProb\ref{prob:multi_obj}}(\mathbb{U}_{s},\mathbb{P})$;

foreach  _$U\in\mathbb{U}_{n}(N_{r2})$_ do

$j\leftarrow 1$;

for  _$j\leq N_{o}$_ do

$\alpha\leftarrow\mathbf{GetStepSize}(\alpha_{0})$;

$\bm{\theta}_{U}\leftarrow\bm{\theta}_{U}-\alpha\nabla C(U,\bm{\theta}_{U})$;

$j\leftarrow j+1$;

end for

end foreach

$\mathbb{U}_{survival}\leftarrow\mathbf{GetSurvivals}(\mathbb{U}_{n}(N_{r}^{\prime}),\mathbb{U}_{n}(N_{r}^{\prime}+1))$;

if  _$\exists U\in\mathbb{U}_{survival}$ such that
$C(U,\bm{\theta}_{U})<C(U_{best},\bm{\theta}_{U_{best}})$_ then

$U_{best}\leftarrow\mathbf{None}$;

end if

$\mathbb{U}_{new}\leftarrow\\{\\}$;

foreach  _$U\in\mathbb{U}_{survival}$_ do

$U_{new}\leftarrow\mathbf{RandomGeneticOperator}(U)$;

$\mathbb{U}_{new}\leftarrow\mathbb{U}_{new}\cup\\{U_{new}\\}$;

$\alpha\leftarrow\mathbf{GetStepSize}(\alpha_{0})$;

if  _$\alpha\frac{\left\|\nabla
C(U,\bm{\theta}_{U})\right\|_{2}}{|\bm{\theta}_{U}|} <\xi$_ then

$\mathbb{U}_{survival}\leftarrow\mathbb{U}_{survival}\setminus\\{U\\}$;

if  _$C(U,\bm{\theta}_{U}) <C(U_{best},\bm{\theta}_{U_{best}})$_ then

$U_{best}\leftarrow U$;

end if

end if

end foreach

$U_{s}\leftarrow\mathbb{U}_{survival}\cap\mathbb{U}_{new}$;

for  _$\left|\mathbb{U}_{s}\right|\leq N_{s2}$_ do

$U\leftarrow\mathbf{USampling}(\mathbb{S},T,\epsilon_{1},\epsilon_{2})$;

$\mathbb{U}_{s}\leftarrow\mathbb{U}_{s}\cup\left\\{U\right\\}$;

end for

if  _$U_{best}$ has been preserved for $N_{t2}$ generations_ then

$\mathbf{break}$;

end if

end for

$U^{*}\leftarrow\arg\min_{U\in\mathbb{U}_{s}\cup\\{U_{best}\\}}C(U,\bm{\theta}_{U})$;

end

return _$U^{*}$ , $\bm{\theta}_{U^{*}}$._

Algorithm 7 AlternateTraining

Input: $U$, $\bm{\theta}_{0}$

begin

$\bm{\theta}\leftarrow\bm{\theta}_{0}$;

$i\leftarrow 1$

for  _$i\leq N_{i3}$_ do

$\alpha\leftarrow\mathbf{GetStepSize}(\alpha_{0})$;

$\bm{\theta}\leftarrow\bm{\theta}-\alpha\nabla C(U,\bm{\theta})$;

$i\leftarrow i+1$;

if  _$\alpha\frac{\left\|\nabla C(U,\bm{\theta})\right\|_{2}}{|\bm{\theta}|}
<\xi$_ then

$\mathbf{break}$;

end if

end for

$U^{*}\leftarrow U,\bm{\theta}^{*}\leftarrow\bm{\theta}$;

end

return _$U^{*}$ , $\bm{\theta}^{*}$._

Algorithm 8 VQERetraining