# Mitigating barren plateaus of variational quantum eigensolvers

Xia Liu  Institute for Quantum Computing, Baidu Research, Beijing 100193,
China  Geng Liu  Institute for Quantum Computing, Baidu Research, Beijing
100193, China  Jiaxin Huang  Institute for Quantum Computing, Baidu Research,
Beijing 100193, China  Xin Wang<EMAIL_ADDRESS>Institute for Quantum
Computing, Baidu Research, Beijing 100193, China

###### Abstract

Variational quantum algorithms (VQAs) are expected to establish valuable
applications on near-term quantum computers. However, recent works have
pointed out that the performance of VQAs greatly relies on the capability of
the ansatzes and is seriously limited by optimization issues such as barren
plateaus (i.e., vanishing gradients). This work proposes the state efficient
ansatz (SEA) for accurate quantum dynamics simulations with improved
trainability. First, we show that SEA can generate an arbitrary pure state
with much fewer parameters than a universal ansatz, making it efficient for
tasks like ground state estimation. It also has the flexibility in adjusting
the entanglement of the prepared state, which could be applied to further
improve the efficiency of simulating weak entanglement. Second, we show that
SEA is not a unitary 2-design even if it has universal wavefunction
expressibility and thus has great potential to improve the trainability by
avoiding the zone of barren plateaus. We further investigate a plethora of
examples in ground state estimation and notably obtain significant
improvements in the variances of derivatives and the overall optimization
behaviors. This result indicates that SEA can mitigate barren plateaus by
sacrificing the redundant expressibility for the target problem.

Introduction.— Quantum computers are expected to achieve quantum advantages
Preskill (2012) in solving valuable problems Lloyd (1996); Harrow  _et al._
(2009); Childs and van Dam (2010); Montanaro (2016). Before arriving at
universal quantum computing, a key direction is to explore the power of Noisy
Intermediate-Scale Quantum (NISQ) Preskill (2018) devices in important fields
such as quantum chemistry Cao  _et al._ (2019); McArdle  _et al._ (2020) and
quantum machine learning Schuld and Petruccione (2021); Biamonte  _et al._
(2017); Huang  _et al._ (2021); Jerbi  _et al._ (2021); Mitarai  _et al._
(2018). Recent results Arute  _et al._ (2019); Wu  _et al._ (2021); Zhong  _et
al._ (2020, 2021); Abbas  _et al._ (2021) have shown that quantum advantages
in specific tasks can be achieved using such devices.

One common paradigm to design quantum solutions using NISQ devices is the
variational quantum algorithms (VQAs) Cerezo  _et al._ (2021a); Bharti  _et
al._ (2021); Endo  _et al._ (2020). VQAs are promising to deliver applications
in many important topics including ground state preparation Peruzzo  _et al._
(2014); Cao  _et al._ (2019); McArdle  _et al._ (2020), quantum data
compression Romero  _et al._ (2017); Wang  _et al._ (2021), machine learning
Cong  _et al._ (2019); Li and Deng (2021); Schuld and Petruccione (2021); Li
_et al._ (2021); Caro  _et al._ (2021); Farhi and Neven (2018), and
combinatorial optimization Farhi  _et al._ (2014a); Zhou  _et al._ (2020).
Combining the advantages of classical computers and quantum devices, VQAs
adopt parameterized quantum circuits (PQCs, also known as ansatzes) Benedetti
_et al._ (2019) and utilize classical computers to optimize the parameters to
minimize the cost functions that are designed for solving target problems.

Among the numerous VQAs, the variational quantum eigensolver (VQE) for ground
state estimation is a central one of both practical and theoretical interests.
For VQE, one common approach is to utilize fixed structure ansatzes, such as
the hardware-efficient ansatz (HEA) Kandala  _et al._ (2017) and the unitary
coupled cluster (UCC) ansatz Hoffmann and Simons (1988); McArdle  _et al._
(2020); Lee  _et al._ (2018), which require a large depth to achieve high
accuracy when the problem scale is large. On the other hand, there are
adaptive structure ansatzes Grimsley  _et al._ ; Tang  _et al._ (2021a);
Ryabinkin  _et al._ (2019); Bharti and Haug (2021); Grimsley  _et al._ (2022),
which usually suffer from relatively high costs of both quantum and classical
resources.

Figure 1: Illustration of our main result. The left column demonstrates the
difficulty in the optimization process of general ansatzes, which have high
expressibility. The optimization process of State Efficient Ansatz (SEA) is
depicted in the right column, with its conceptual framework represented in the
upper right, where $A$ and $B$ are two subsystems. Schmidt coefficient layer
$U_{1}$, entangling layer $V$, and local basis changing layer $U_{2},U_{3}$,
are the three parts of SEA. The key feature of SEA is reducing the optional
range of paths, leading to a more favorable landscape, as shown at the bottom.

Despite the success of VQE, expressibility Haug  _et al._ (2021); Du  _et al._
(2022); Holmes  _et al._ (2022) and trainability McClean  _et al._ (2018);
Zhang  _et al._ (2021, 2022) are still two critical challenges of designing
ansatzes for VQE. To improve the accuracy of the algorithms, ansatzes with
strong expressibility are usually preferred, and they are usually required to
be deep enough to ensure the expressibility for finding the right solutions.
This could be seen in the same spirit of deep neural networks in machine
learning. However, recent works Holmes  _et al._ (2022); Sim  _et al._ (2019);
Nakaji and Yamamoto (2021) have connected the expressibility and trainability
implying that strong expressibility will lead to poor trainability due to the
barren plateau phenomenon McClean  _et al._ (2018); Sharma  _et al._ (2022);
Ortiz Marrero  _et al._ (2021), i.e., the gradients in training will vanish
exponentially in the number of qubits. This technical bottleneck seriously
restricts the scalability of VQE. Despite a plethora of recent attempts to
address the barren plateaus through adjusting initialization Grant  _et al._
(2019); Verdon  _et al._ (2019a), cost functions Cerezo  _et al._ (2021b);
Kieferova  _et al._ (2021), and architectures Pesah  _et al._ (2021), there is
still a strong need for guaranteeing or extending the scalability of VQE by
eliminating this trainability bottleneck while keeping the effectiveness.

To overcome these challenges, we propose the State Efficient Ansatz (SEA) to
mitigate the barren plateaus and extend the scalability of VQE (see Fig. 1).
We first show that SEA is effective and efficient for VQE by theoretically
proving its capability of learning an arbitrary pure quantum state as well as
finding the eigenstates of an arbitrary Hamiltonian. Actually, the SEA is
effective for all the tasks that are essentially learning a quantum state,
which we call the state-oriented tasks. We further show several useful
properties of this ansatz, including its advantages in the parametric degrees
of freedom as well as its flexibility in adjusting the entanglement of the
prepared state. In particular, we show that SEA has the remarkable ability to
mitigate the barren plateaus by removing the part of the expressibility that
is redundant for generating an arbitrary pure state. We further investigate a
plethora of examples in ground state estimation through numerical experiments
and establish evident improvements in both the overall behavior and the
variance of the partial derivatives at the initial stage.

The State Efficient Ansatz.— The intuition of SEA is to prune the redundant
expressibility of an ansatz in the state-oriented tasks by utilizing the
Schmidt representation Nielsen and Chuang (2010) of pure states, which also
inspires the tree tensor network Shi  _et al._ (2006); Nagaj  _et al._ (2008);
Tagliacozzo  _et al._ (2009); Nakatani and Chan (2013). Specifically, the
input system has two subsystems $A$ and $B$, and the ansatz comprises three
parts. The first part is the Schmidt coefficient layer $U_{1}$ acting on
subsystem $A$. The second part is the entangling layer $V$ acting on the whole
system $AB$ to create entanglement between two subsystems. The last part is
the local basis changing layer(LBC layer), which consists of two local
circuits, $U_{2}$ and $U_{3}$, applied to the two subsystems respectively. The
whole structure of SEA is shown in the upper right of Fig. 1 and can be
written as

$S(\bm{\theta})\equiv(U_{2}(\bm{\theta_{2}})\otimes
U_{3}(\bm{\theta_{3}}))V(U_{1}(\bm{\theta_{1}})\otimes I),$ (1)

where $S$ is the unitary representation of SEA,
$\bm{\theta}=\\{\bm{\theta_{1}},\bm{\theta_{2}},\bm{\theta_{3}}\\}$, and each
$\bm{\theta_{i}}(i=1,2,3)$ is a parameter vector.

We here briefly explain the effectiveness of SEA. For simplicity, we assume
both subsystems $A$ and $B$ have $N$ qubits and let $|0\rangle^{\otimes 2N}$
be an initial state sent through SEA. Then $|0\rangle^{\otimes 2N}$ will
evolve into $\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|0\rangle^{\otimes
N}$ ($\lambda_{k}>0$) after the Schmidt coefficient layer with
$U_{1}|0\rangle^{\otimes N}=\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}$ (we
omit $\bm{\theta}$ in writing for simplicity), where
$\\{|k\rangle\\}_{k=0}^{2^{N}-1}$ is the computational basis. At the
entangling layer, we set a composition of $N\operatorname{CNOT}$s controlled
and targeted on the qubit-pairs $\\{(i,N+i)\\}_{i=0}^{N-1}$. After this layer,
we will obtain a pure state in the form of
$\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|k\rangle_{B}$. At the last
layer, we apply $U_{2}$ and $U_{3}$ on subsystems $A$ and $B$, respectively,
such that $U_{2}|k\rangle_{A}=|v_{k}\rangle_{A}$ and
$U_{3}|k\rangle_{B}=|v_{k}\rangle_{B}$. The final output state we obtain is
$\sum_{k=0}^{2^{N}-1}\lambda_{k}|v_{k}\rangle_{A}|v_{k}\rangle_{B}$. Note that
this exactly forms a Schmidt decomposition with tunable Schmidt coefficients
and bases. Since any pure state has a form of Schmidt decomposition, SEA can
evolve an initial state $|0\rangle^{\otimes 2N}$ into an arbitrary $2N$-qubit
pure state if $U_{1}$ can generate an arbitrary $N$-qubit pure state (also
called universal wavefunction expressibility) and $U_{2},U_{3}$ are universal.
The whole process of SEA acting on the initial state $|0\rangle^{\otimes 2N}$
is shown in Fig. 2.

Figure 2: An established case of SEA. Schmidt coefficient layer $U_{1}$ has
universal wavefunction expressibility. The entangling layer consists of N
CNOTs, and the LBC layer comprises two local universal PQCs, $U_{2}$ and
$U_{3}$. The evolution of $|0\rangle^{\otimes 2N}$ under this SEA is as
follows. After Schmidt coefficient layer, we obtain
$\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|0\rangle^{\otimes N}$. Then we
get $\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|k\rangle_{B}$ after
implementing $N$ CNOTs. Finally, we obtain the output state
$\sum_{k=0}^{2^{N}-1}\lambda_{k}|v_{k}\rangle_{A}|v_{k}\rangle_{B}$ after the
LBC layer.

Note that not all SEA can generate an arbitrary pure state as
$\\{U_{i}\\}_{i=1}^{3}$ may not satisfy the conditions specified above. In the
following, we consider different situations with different $U_{1}$. To
simplify the study and better explore the properties of SEA, we fix the
entangling layer as $N$ $\operatorname{CNOT}$s defined before (denote as
$\widetilde{\operatorname{CNOT}}$), and we also assume $U_{2}$ and $U_{3}$ in
the LBC layer are universal. We now elaborate on some useful properties of SEA
with different $U_{1}$:

  1. 1.

A $2N$-qubit SEA can evolve $|0\rangle^{\otimes 2N}$ into an arbitrary
$2N$-qubit pure state $|\phi\rangle$ if $U_{1}$ has universal wavefunction
expressibility, as presented in Property 1.

  2. 2.

The fidelity between the state evolved by SEA and a target state
$|\phi\rangle$ has a lower bound related to Schmidt rank of the target state
when $U_{1}$ does not have universal wavefunction expressibility, as presented
in Property 2.

  3. 3.

SEA has a quadratic advantage in the parametric degrees of freedom over the
universal PQCs, as presented in Property 3.

We further provide detailed statements of these properties as follows, which
imply the effectiveness and efficiency of SEA.

###### Property 1

If $U_{1}$ can generate an arbitrary $N$-qubit pure state, then given any
$2N$-qubit pure state $|\phi\rangle$, a $2N$-qubit SEA can generate
$|\phi\rangle$ with a certain set of parameters
$\bm{\hat{\theta}}=\\{\hat{\bm{\theta}}_{1},\hat{\bm{\theta}}_{2},\hat{\bm{\theta}}_{3}\\}$,
that is, $S(\bm{\hat{\theta}})|0\rangle^{\otimes 2N}=|\phi\rangle$.

Property 1 implies that SEA with a $U_{1}$ of the universal wavefunction
expressibility can accurately solve state-oriented tasks. Note that an
$N$-qubit SEA under property 1 has the universal wavefunction expressibility,
so we can use it as the Schmidt coefficient layer of a $2N$-qubit SEA to
generate an arbitrary $2N$-qubit pure state.

However, universal wavefunction expressibility could be a strong requirement
to some extent. In Property 2, we consider a relaxed condition for $U_{1}$ and
analyze the performance of SEA for generating an arbitrary pure state under
this situation.

###### Property 2

If $U_{1}$ can generate any $N$-qubit pure state that is a superposition of at
most $K$ computational basis states, then for any $|\phi\rangle$, there exists
an SEA output state $|\psi\rangle$ with
$F(|\phi\rangle,|\psi\rangle)\geq\min\left\\{\frac{K}{r},1\right\\}$, where
$F(|\phi\rangle,|\psi\rangle)$ is the fidelity between $|\phi\rangle$ and
$|\psi\rangle$, and $r$ is the Schmidt rank of $|\phi\rangle$.

Property 2 states that if we know the information about entanglement of the
target quantum state, we could adjust $K$ by changing the structure of $U_{1}$
to reduce the cost without sacrificing performance. Property 1 and Property 2
together show that SEA has a strong expressibility for learning a quantum
state.

For a universal $N$-qubit PQC that can generate an arbitrary unitary, it would
have at least $O(4^{N})$ parameters since the dimension of
$\mathcal{U}(2^{N})$ is $4^{N}$ Wybourne (1974). In contrast, the Property 3
will indicate that SEA has a quadratic advantage in the parametric degrees of
freedom compared to universal PQCs.

###### Property 3

Constructing a $2N$-qubit SEA that can generate an arbitrary pure state
requires at most $O(4^{N})$ independent parameters.

A universal $N$-qubit PQC $U_{i}$ has $O(4^{N})$ degree of freedom Biamonte
(2021). Therefore, a $2N$-qubit SEA with universal $U_{i}(i=1,2,3)$ also has
$O(4^{N})$ parametric degrees of freedom. In comparison, a $2N$-qubit
universal PQC has $O(4^{2N})$ parametric degrees of freedom. Meanwhile, the
degree of freedom of an $N$-qubit pure state is $2^{N+1}-2$, so we do not need
a universal unitary with $O(4^{N})$ parameters to generate an arbitrary state.
Combining with Property 1, SEA requires quadratically fewer parameters than a
general PQC of the same dimension while retaining the ability to generate an
arbitrary pure state. In this sense, we call it state efficient ansatz. At the
same time, such improvements in parameters could directly save the cost of
quantum resources for measurement and introduce less noise on near-term
quantum devices.

After showing the useful properties of SEA, we are going to show the validity
of SEA in the variational quantum eigensolver (VQE), which aims to
variationally find the ground state of a given Hamiltonian. This task plays a
key role in the study of the physical and chemical properties of molecules.
Combining with Property 1, we get Property 4, which illustrates the
effectiveness of SEA when used in VQE.

###### Property 4

For any $2N$-qubit Hamiltonian $H$, it holds that

$\displaystyle\min_{S}\langle 0|^{\otimes 2N}S^{\dagger}HS|0\rangle^{\otimes
2N}=E_{0},$ (2)

where $E_{0}$ is the ground state energy of $H$ and the optimization is over
all unitaries reachable by SEA with $U_{1}$ having universal wavefunction
expressibility.

Property 4 implies that SEA could be applied to search the ground state via
VQE. We also note that this usually needs more resources in this situation as
it may require $U_{1}$ to have the universal wavefunction expressibility and
$U_{2},U_{3}$ to be universal. To further investigate the performance in VQE,
in the following parts, we choose alternating layered ansatz (ALT) Cerezo  _et
al._ (2021b) for the Schmidt coefficient layer and the LBC layer. An example
of ALT is shown in Fig. 3.

Applying to chemistry and physics models.— To show the advantages of SEA, we
investigate the performance of SEA and other ansatzes in estimating the ground
state energy of chemistry and physics models by carrying out numerical
experiments. The improvements in effectiveness and efficiency are evident. All
simulations are performed using the Paddle Quantum Pad  toolkit on the
PaddlePaddle Deep Learning Platform Ma  _et al._ (2019).

#### Experiment settings.

Here we use $14$-qubit dinitrogen (N2) molecule and the $14$-qubit Heisenberg
model as examples for numerical simulations of VQE using SEA. As the cost of
implementing a universal unitary is generally high in practice, we choose ALT
as the Schmidt coefficient layer and the LBC layer to construct SEA. The
structure of SEA is shown in Fig. 2, where $U_{1}$, $U_{2}$, and $U_{3}$ are
all $7$-qubit ALTs with $30$ layers. For different Hamiltonian, we could set
different numbers of CNOTs in entangling layer $V$ and different numbers of
qubits of $U_{1}$ in $7$-qubit Schmidt coefficient layer to adjust the $K$ in
Property 2. Detailed design of $U_{1}$ and $V$ are described in Implementation
procedure.

To study the advantages of SEA, we compare $14$-qubit SEA with a $14$-qubit
ALT and a $14$-qubit random circuit McClean  _et al._ (2018) in the task of
VQE with a similar number of parameters by setting different depth for
different ansatzes. The specific calculation methods of parameter numbers are
given in the Sec. V of the Supplemental Material. The reason for choosing an
ALT and a random circuit is that they both have a strong expressibility, and a
random circuit can be regarded as a $2$-design when its depth is large.

$\Qcircuit@C=.7em@R=1em{&\qw\gate{R_{y}}\ctrl{1}\gate{R_{y}}\qw\qw\qw\ctrl{1}\gate{R_{y}}\qw\qw\qw\qw\\\
\qw\gate{R_{y}}\ctrl{0}\gate{R_{y}}\ctrl{1}\gate{R_{y}}\qw\ctrl{0}\gate{R_{y}}\ctrl{1}\gate{R_{y}}\qw\qw\\\
\qw\gate{R_{y}}\ctrl{1}\gate{R_{y}}\ctrl{0}\gate{R_{y}}\qw\ctrl{1}\gate{R_{y}}\ctrl{0}\gate{R_{y}}\qw\qw\\\
\qw\gate{R_{y}}\ctrl{0}\gate{R_{y}}\ctrl{1}\gate{R_{y}}\qw\ctrl{0}\gate{R_{y}}\ctrl{1}\gate{R_{y}}\qw\qw\\\
\qw\gate{R_{y}}\ctrl{1}\gate{R_{y}}\ctrl{0}\gate{R_{y}}\qw\ctrl{1}\gate{R_{y}}\ctrl{0}\gate{R_{y}}\qw\qw\\\
\qw\gate{R_{y}}\ctrl{0}\gate{R_{y}}\qw\qw\qw\ctrl{0}\gate{R_{y}}\qw\qw\qw\qw\gategroup{1}{4}{6}{8}{1.em}{--}\gategroup{1}{9}{6}{13}{1.em}{--}}$
Figure 3: An example of a $6$-qubit ALT with $2$ layers. Each layer is
composed of the rotation operator gate $R_{y}$ and control-Z gate.

#### Implementation procedure.

Considering that the N2 molecule and the Heisenberg model we choose are both
weakly entangled, we use two kinds of SEA named SEA2 and SEA3 to learn these
models’ ground state energies. To be specific, SEA2 is the $14$-qubit SEA of
Schmidt coefficient layer as a $2$-qubit ALT and entangling layer as $2$
CNOTs, which means a composition of $2$ CNOTs controlled and targeted on the
qubit-pairs $\\{(0,7),(1,8)\\}$. SEA3 is the $14$-qubit SEA of Schmidt
coefficient layer as a $3$-qubit ALT and entangling layer as $3$ CNOTs, which
implement on the qubit-pairs $\\{(i,7+i)\\}_{i=0}^{2}$. The reason we show two
types of SEA is that we can implement fewer CNOTs in the entangling layer and
fewer qubits in the Schmidt coefficient layer instead of
$\widetilde{\operatorname{CNOT}}$ and $N$-qubit $U_{1}$ in Fig. 2 to reduce
entanglement. After setting up the ansatzes, we employ a stochastic gradient
descent optimizer to iteratively update parameters for $400$ iterations.

Figure 4: Numerical simulations of VQE on N2 ($14$-qubit). The blue dotted
line is the theoretical ground energy of N2, and the lines from top to bottom
represent the experimental results of ALT, the random circuit, SEA with $2$
CNOTs, and SEA with $3$ CNOTs, respectively. $j$($j=2,3$) CNOTs means that we
set a composition of $j\operatorname{CNOT}$s controlled and targeted on the
qubit-pairs $\\{(i,N+i)\\}_{i=0}^{j-1}$. Figure 5: Numerical simulations of
VQE on Heisenberg model ($14$-qubit). The Hamiltonian is chosen to be the
$14$-qubit $1$-dimensional spin-$1/2$ antiferromagnetic Heisenberg model with
periodical boundary condition, i.e.,
$H=\sum_{i=1}^{14}\left(X_{i}X_{i+1}+Y_{i}Y_{i+1}+Z_{i}Z_{i+1}\right)$. The
blue dotted line is the theoretical ground energy of the Hamiltonian $H$, and
the other lines from top to bottom represent the results of the ALT, random
circuit, SEA with 3 CNOTs and SEA with 2 CNOTs, respectively.

#### Numerical results.

The simulation results of N2 molecule and the Heisenberg model are shown in
Fig. 4 and Fig. 5, respectively. Both figures illustrate the efficiency of SEA
on VQE. We can observe that with a similar number of parameters, there is a
visible gap in the accuracy of estimating the ground energy by different
ansatzes. Both SEA2 and SEA3 converge rapidly and get an approximate value of
ground energy while the results of the other two ansatzes cannot be optimized
in $400$ iterations. In addition, it is also valid to replace the three parts
of SEA with other structures. The Sec. V of the Supplemental Material presents
the result of SEA whose Schmidt coefficient layer is
$R_{y}(\bm{\theta})^{\otimes N}$. We can also see that this kind of SEA has
better performance than ALT and random circuit, which further verifies the
effectiveness of SEA in practical applications.

From the numerical experiment of VQE, we can see that SEA has an advantage in
efficiency. Since we only use $2$ or $3$ CNOTs and adjust the structure of
Schmidt coefficient layer to obtain good results, the experiment results also
support Property 2.

Mitigating Barren Plateaus.— The evident improvement in the above VQE
experiments indeed also indicates that our SEA has a good descent direction at
the beginning of optimization. This fact motivates us to further study the
partial derivatives of parameters at the random initialization and explore the
scalability of SEA.

Trainability is one of the most concerning problems of VQAs, as it has been
proved that the optimization process will be crippled because of the barren
plateaus phenomenon, which means the gradients of the cost function will
vanish exponentially in the number of qubits for a randomly initialized PQC.
In particular, Ref. McClean  _et al._ (2018) has pointed out that if an ansatz
can generate unitaries sufficiently randomly that accord with the Haar
distribution upon unitary group up to the second moment, i.e., forms a
2-design, then the cost will exhibit a barren plateaus phenomenon. In our
context, the alternating layered circuit and random circuit exhibit barren
plateaus phenomenon according to our previous numeric results.

Unlike these two ansatzes that cannot find the proper descent direction, SEA
does not experience a serious trainability issue at the beginning of
optimization. We notably find that one main reason is that the special
structure of SEA ensures it will not form a 2-design, thus mitigating the
barren plateaus caused by this problem. In Theorem 1, we rigorously prove that
SEA will not form a 2-design even if its local structures are 2-design.

###### Theorem 1

SEA with $U_{i}(i=1,2,3)$ being local 2-design and
$\widetilde{\operatorname{CNOT}}$ as entangling layer does not form a 2-design
on the global system.

A large class of random PQCs will end up forming a 2-design when the depth is
large McClean  _et al._ (2018) and this is the usual case in VQAs. However,
this theorem implies that even though the local structures of SEA have strong
expressibility by forming 2-designs, which lead to the universal wavefunction
expressibility of SEA according to Property 1, SEA will still not form a
global 2-design. Thus SEA could avoid the known definite zone of barren
plateaus without losing effectiveness on VQE and will reveal a strong ability
to mitigate the barren plateaus. Moreover, SEA will maintain this property
even if we change the number of CNOTs in the entangling layer. In fact, with
less expressibility, SEA will be farther from being a 2-design.

The main idea of the proof is to focus on the value of $\langle 0|^{\otimes
2N}\int_{\mathbb{U}}U^{\dagger}CU\rho U^{\dagger}DUdU|0\rangle^{\otimes 2N}$
with $C=D=\rho=|0\rangle\\!\langle 0|^{\otimes 2N}$. If a $2N$-qubit SEA forms
a 2-design, it should hold that $\langle 0|^{\otimes
2N}\int_{\mathbb{U}}U^{\dagger}CU\rho U^{\dagger}DUdU|0\rangle^{\otimes 2N}$
is $\frac{2}{d^{2}(d^{2}+1)}$ with $d=2^{N}$ due to the closed form of
integral formula from Emerson  _et al._ (2005). However, using the following
Lemma 2, a key proof ingredient that explores the central structure of SEA, we
find that the actual value of the target term is
$\frac{2d+6}{d^{2}(d+1)^{3}}$. This leads to a direct contradiction as well as
the fact that SEA with $U_{i}(i=1,2,3)$ being local 2-design structures and
$\widetilde{\operatorname{CNOT}}$ entangling layer does not form an exact
2-design. Even if we change the number of CNOTs in entangling layer, we can
still similarly prove that SEA will not form a 2-design. We further provide
the details of Theorem 1 and Lemma 2 in the Supplemental Material.

###### Lemma 2

For any bipartite state $\rho_{AB}$ with $d_{A}=d_{B}=d$ and arbitrary linear
operators $C,D$, we have

$\displaystyle\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)U^{\dagger}CU\rho
U^{\dagger}DU$ (3) $\displaystyle=$ $\displaystyle
t_{0}\rho+t_{1}\frac{\rho_{A}\otimes
I_{B}}{d}+t_{2}\frac{I_{A}\otimes\rho_{B}}{d}+t_{3}I_{AB}\operatorname{Tr}(\rho_{AB}).$
(4)

where $t_{0},t_{1},t_{2},t_{3}$ are decided by $C,D$ and dimension $d$.

Figure 6: Frame potentials of 8-qubit SEA with different Schmidt coefficient
layers and entangling layers. Yellow triangles, black dots, and red diamonds
represent the frame potentials of 8-qubit SEA that change the number of qubits
used in the Schmidt coefficient layer, entangling layer, and both two layers,
respectively. Blue dotted line represents the frame potential of an exactly
2-design circuit. Each value is estimated using an ensemble of 5000 unitaries.

Beyond the exact 2-design, it is natural to consider how far SEA is from being
a 2-design. Here we consider the quantity called frame potential Sim  _et al._
(2019); Holmes  _et al._ (2022); Nakaji and Yamamoto (2021); Roberts and
Yoshida (2017), which is usually used to evaluate the randomness of an
ensemble. It will reach a minimum value if and only if the ensemble is a
2-design. The frame potential of the ensemble $\mathbb{U}$ generated by
$2N$-qubit SEA is denoted by $\mathcal{F}_{\mathbb{U}}$ and the Haar value is
denoted by $\mathcal{F}_{\mathrm{Haar}}$. The $\mathcal{F}_{\mathbb{U}}$ and
$\mathcal{F}_{\mathrm{Haar}}$ are defined as follows

$\displaystyle\mathcal{F}_{\mathbb{U}}$
$\displaystyle=\int_{\mathbb{U}}\int_{\mathbb{U}}dUdV|\langle 0|^{\otimes
2N}(UV^{\dagger})|0\rangle^{\otimes 2N}|^{4},$ (5)
$\displaystyle\mathcal{F}_{\mathrm{Haar}}$
$\displaystyle=\int_{\mathcal{U}(d^{2})}\int_{\mathcal{U}(d^{2})}d\eta(U)d\eta(V)|\langle
0|^{\otimes 2N}(UV^{\dagger})|0\rangle^{\otimes 2N}|^{4}$
$\displaystyle=\frac{1}{(2^{2N}+1)2^{2N-1}},$ (6)

where $U$ and $V$ are elements of the ensemble $\mathbb{U}$, $d\eta(U)$
corresponds to the Haar measure and $dU$, $dV$ correspond to the uniform
distribution over $\mathbb{U}$. By comparing SEA with different
implementations of Schmidt coefficient layer and entangling layer (cf. Fig.
6), we find that the fewer qubits used in the Schmidt coefficient layer and
the fewer CNOTs in the entangling layer, the larger frame potential SEA will
have, thus SEA will be farther away from being a 2-design. Therefore, when the
target state is low-entangled, we can reduce the number of qubits of the
Schmidt coefficient layer and the number of CNOTs in the entangling layer to
further improve the trainability.

As discussed previously, SEA sacrifices some global expressibility without
losing its capability to be effective on VQE. At the same time, as the trade-
off of losing redundant expressibility of representing an arbitrary unitary,
the special structure of SEA makes it avoid forming a 2-design, which can make
it potentially mitigate the influence of barren plateaus. In particular, we
can further mitigate barren plateaus by changing the specific structure of SEA
according to different targets.

Gradient experiments.— To demonstrate that SEA can indeed mitigate the barren
plateaus, we implement two numerical experiments on gradients with different
numbers of qubits. For both experiments, we consider the $1$-dimensional
spin-$1/2$ antiferromagnetic Heisenberg model where the Hamiltonian is
$H=\sum_{i=1}^{2N}(X_{i}X_{i+1}+Y_{i}Y_{i+1}+Z_{i}Z_{i+1})$ with periodic
boundary condition. We use different ansatzes and calculate the gradient of
the cost function $C(\bm{\theta})=\langle 0|^{\otimes
2N}U(\bm{\theta})^{\dagger}HU(\bm{\theta})|0\rangle^{\otimes 2N}$ with respect
to each parameter, where $U(\bm{\theta})$ represents the unitary of the
ansatz.

#### SEA with ALT.

We first conduct experiments with the ansatzes used in the previous numerical
simulations of VQE. The SEAs we chose are SEA1 and SEA⌊N/2⌋, which still adopt
ALT as the Schmidt coefficient layer and the LBC layer. ALT and random circuit
of the same size as SEAs are selected for comparison.

Figure 7: Comparison of the scaling of the average variance of gradients
between different ansatzes on the Heisenberg model. This shows the semi-log
plot of the average value of the variance of each parameters in the circuit.
The depth of each part of SEA is 30 and we ensure different ansatzes have
similar numbers of parameters by setting different depth. The solid part of
the fitted lines represents the range we experiment with, while the dashed
part represents the expected performance on a larger range.

The average variances of parameters of different ansatzes are compared in Fig.
7. We also extract the variance of the largest partial derivative in each
sample, which is shown in the Sec. V of the Supplemental Material. It is
clearly demonstrated that all these variances decay exponentially as the
number of qubits increases. However, the slopes of the red and the blue lines
are nearly half of the slopes of the other lines, which means the SEA has a
much lower rate of decay of variance.

#### SEA with general circuits.

To better illustrate how our structure increases the scaling of variance, we
further inspect the gradient with respect to the parameter in different parts
of SEA. As shown in Fig. 8, we look into the gradients with respect to the
parameters of the $R_{y}$ gates in the Schmidt coefficient layer and the LBC
layer. As a comparison, we also consider a single parameter $R_{y}$ gate in
the middle of a circuit that forms a 2-design with sufficient depth. The
circuit before the gate and the circuit after the gate are both 2-design and
are represented by Haar random unitaries in our experiments. Fig. 9 summarizes
the results of the variance of parameters located in the Schmidt coefficient
layer and the LBC layer, respectively.

Figure 8: The structures of SEA used for studying the scaling of variance of
general circuits Panel (a) shows the $R_{y}$ gate located in Schmidt
coefficient layer. Panel (b) shows the $R_{y}$ gate located in the LBC layer.
Parameter $\theta\in[0,2\pi)$ is uniformly chosen and
$U_{1},U_{11},U_{12},U_{2},U_{21},U_{22},U_{3}$ are Haar randomly chosen from
unitary group in each round of sampling. $CNOTs$ is composed by a number of
CNOTs. Figure 9: Comparison of the scaling of variance between general
structure of SEA and general random circuit. The SEA1-Schmidt and the
SEA⌊N/2⌋-Schmidt show the semi-log plot of the variance of gradient with
respect to the parameter in Schmidt coefficient layer. The SEA1-LBC and the
SEA⌊N/2⌋-LBC show the semi-log plot of the variance of gradient with respect
to the parameter in LBC layer. The markers on the fitted lines represent the
results from our experiments. The dotted part of the lines represents the
expected performance on a larger range.

From Fig. 9, we see that no matter where this parameter is located in SEA, the
variance of its gradient has a decaying speed lower than the decay speed of
variance of the parameter in a sufficiently random circuit that forms a
2-design. This fact indicates that the variance of SEA has significant
improvement compared to using an ansatz that forms a 2-design, indicating an
evident mitigation of barren plateaus. It is also worth noting that the fewer
CNOTs in the entangling layer, the larger variance it will have. Specifically,
in our experiments, if the scale of the problem is larger than 12 qubits, the
variance of the gradients in a 2-design circuit will be less than $10^{-3}$,
which is usually considered too small to be further optimized. However, this
bound of scale can be increased to 18 qubits using SEA with
$\lfloor\frac{N}{2}\rfloor$ CNOTs according to our experiment results. With
the weaker expressibility of SEA, this bound can be further increased. In
other words, we can notably increase the scale of problems with the same
limited scaling of gradients by using SEA instead of a 2-design circuit.
Therefore, SEA is more likely to scale to larger systems on VQE tasks because
of its improvement in trainability by mitigating barren plateaus.

Concluding remarks.— The main contribution of this work is proposing an ansatz
structure SEA to mitigate the barren plateaus in optimizing parameterized
circuits for quantum dynamics simulations. We in particular have provided an
explicit construction of SEA that has enough expressibility to generate
arbitrary pure quantum states while not forming a unitary 2-design. We have
shown that SEA can be applied to approximate the ground state of the N2
molecule and the Heisenberg model, whose numerical results confirm the
effectiveness of SEA. We further compare the scaling of variance in partial
derivatives between different ansatzes and establish that SEA has a much lower
rate of decay of variance, implying that SEA can considerably mitigate the
barren plateaus of VQE. This advantage in trainability mainly comes from the
elimination or sacrifice of redundant expressibility.

We note that SEA is also effective in principle for other tasks with the sole
purpose of generating a pure state, e.g., combinatorial optimization Farhi
_et al._ (2014b) and entanglement detection Wang  _et al._ (2022). It is
natural to explore how to extend our structure by considering multipartite
systems and other possible designs. We also remark that there are other
proposals for dealing with barren plateaus Grimsley  _et al._ (2022); Tang
_et al._ (2021b); Skolik  _et al._ (2021); Volkoff and Coles (2021), and for
using meta-learning to improve efficiency Verdon  _et al._ (2019b); Wilson
_et al._ (2021); Stollenwerk and Hadfield (2022); Chen  _et al._ (2021). The
combination between SEA and other approaches such as adaptive methods may be
worth a future study. Moreover, there are recent works exploiting the symmetry
of VQAs Zheng  _et al._ (2021); Meyer  _et al._ (2022); Larocca  _et al._
(2022), it is also worth studying how to improve the performance of SEA
through the perspective of symmetry.

Acknowledgements. X. L. and G. L. contributed equally to this work. Part of
this work was done when X. L., G. L., and J. H. were interns at Baidu
Research. We would like to thank Runyao Duan, Yin Mo, Chengkai Zhu, and Youle
Wang for helpful discussions.

## References

  * Preskill (2012) J. Preskill, arXiv preprint arXiv:1203.5813 (2012).
  * Lloyd (1996) S. Lloyd, Science 273, 1073 (1996).
  * Harrow  _et al._ (2009) A. W. Harrow, A. Hassidim, and S. Lloyd, Physical review letters 103, 150502 (2009).
  * Childs and van Dam (2010) A. M. Childs and W. van Dam, Reviews of Modern Physics 82, 1 (2010).
  * Montanaro (2016) A. Montanaro, npj Quantum Information 2, 15023 (2016).
  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018).
  * Cao  _et al._ (2019) Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. Sawaya, _et al._ , Chemical reviews 119, 10856 (2019).
  * McArdle  _et al._ (2020) S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Reviews of Modern Physics 92, 015003 (2020).
  * Schuld and Petruccione (2021) M. Schuld and F. Petruccione,  _Machine Learning with Quantum Computers_ (2021).
  * Biamonte  _et al._ (2017) J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Nature 549, 195 (2017).
  * Huang  _et al._ (2021) H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, arXiv:2106.12627 , 1 (2021), arXiv:2106.12627 .
  * Jerbi  _et al._ (2021) S. Jerbi, L. J. Fiderer, H. P. Nautrup, J. M. Kübler, H. J. Briegel, and V. Dunjko, arXiv:2110.13162 , 1 (2021), arXiv:2110.13162 .
  * Mitarai  _et al._ (2018) K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Physical Review A 98, 032309 (2018), arXiv:1803.00745 .
  * Arute  _et al._ (2019) F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Nature 574, 505 (2019).
  * Wu  _et al._ (2021) Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, Q. Zhu, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Physical Review Letters 127, 180501 (2021).
  * Zhong  _et al._ (2020) H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Science 370, 1460 (2020).
  * Zhong  _et al._ (2021) H.-S. Zhong, Y.-H. Deng, J. Qin, H. Wang, M.-C. Chen, L.-C. Peng, Y.-H. Luo, D. Wu, S.-Q. Gong, H. Su, _et al._ , Physical review letters 127, 180502 (2021).
  * Abbas  _et al._ (2021) A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner, Nature Computational Science 1, 403 (2021), arXiv:2011.00027 .
  * Cerezo  _et al._ (2021a) M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, _et al._ , Nature Reviews Physics 3, 625 (2021a).
  * Bharti  _et al._ (2021) K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, arXiv:2101.08448 , 1 (2021), arXiv:2101.08448 .
  * Endo  _et al._ (2020) S. Endo, Z. Cai, S. C. Benjamin, and X. Yuan, arXiv:2011.01382 , 1 (2020), arXiv:2011.01382 .
  * Peruzzo  _et al._ (2014) A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, Nature communications 5, 4213 (2014).
  * Romero  _et al._ (2017) J. Romero, J. P. Olson, and A. Aspuru-Guzik, Quantum Science and Technology 2, 045001 (2017), arXiv:1612.02806 .
  * Wang  _et al._ (2021) X. Wang, Z. Song, and Y. Wang, Quantum 5, 483 (2021), arXiv:2006.02336 .
  * Cong  _et al._ (2019) I. Cong, S. Choi, and M. D. Lukin, Nature Physics 15, 1273 (2019), arXiv:1810.03787 .
  * Li and Deng (2021) W. Li and D.-L. Deng, arXiv:2108.13421 (2021), arXiv:2108.13421 .
  * Li  _et al._ (2021) G. Li, Z. Song, and X. Wang, in  _Proceedings of the AAAI Conference on Artificial Intelligence, 35(9), 8357-8365_ (2021).
  * Caro  _et al._ (2021) M. C. Caro, H.-Y. Huang, M. Cerezo, K. Sharma, A. Sornborger, L. Cincio, and P. J. Coles, arXiv:2111.05292 , 1 (2021), arXiv:2111.05292 .
  * Farhi and Neven (2018) E. Farhi and H. Neven, arXiv:1802.06002 , 1 (2018), arXiv:1802.06002 .
  * Farhi  _et al._ (2014a) E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014a).
  * Zhou  _et al._ (2020) L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X 10, 021067 (2020), arXiv:1812.01041 .
  * Benedetti  _et al._ (2019) M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Quantum Science and Technology 4, 043001 (2019).
  * Kandala  _et al._ (2017) A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Nature 549, 242 (2017).
  * Hoffmann and Simons (1988) M. R. Hoffmann and J. Simons, The Journal of chemical physics 88, 993 (1988).
  * Lee  _et al._ (2018) J. Lee, W. J. Huggins, M. Head-Gordon, and K. B. Whaley, Journal of chemical theory and computation 15, 311 (2018).
  * (36) H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, Nature communications 10, 1.
  * Tang  _et al._ (2021a) H. L. Tang, V. Shkolnikov, G. S. Barron, H. R. Grimsley, N. J. Mayhall, E. Barnes, and S. E. Economou, PRX Quantum 2, 020310 (2021a).
  * Ryabinkin  _et al._ (2019) I. G. Ryabinkin, R. A. Lang, S. N. Genin, and A. F. Izmaylov, “Iterative qubit coupled cluster approach with efficient screening of generators,” (2019), arXiv:1906.11192 [quant-ph] .
  * Bharti and Haug (2021) K. Bharti and T. Haug, Physical Review A 104, L050401 (2021).
  * Grimsley  _et al._ (2022) H. R. Grimsley, G. S. Barron, E. Barnes, S. E. Economou, and N. J. Mayhall, arXiv:2204.07179 (2022), arXiv:2204.07179 .
  * Haug  _et al._ (2021) T. Haug, K. Bharti, and M. S. Kim, PRX Quantum 2, 1 (2021), arXiv:2102.01659 .
  * Du  _et al._ (2022) Y. Du, Z. Tu, X. Yuan, and D. Tao, Physical Review Letters 128, 80506 (2022).
  * Holmes  _et al._ (2022) Z. Holmes, K. Sharma, M. Cerezo, and P. J. Coles, PRX Quantum 3, 010313 (2022).
  * McClean  _et al._ (2018) J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Nature communications 9, 1 (2018).
  * Zhang  _et al._ (2021) K. Zhang, M.-H. Hsieh, L. Liu, and D. Tao, arXiv preprint arXiv:2112.15002 (2021).
  * Zhang  _et al._ (2022) H.-K. Zhang, C. Zhu, G. Liu, and X. Wang, arXiv:2205.05056 , 1 (2022), arXiv:2205.05056 .
  * Sim  _et al._ (2019) S. Sim, P. D. Johnson, and A. Aspuru-Guzik, Advanced Quantum Technologies 2, 1900070 (2019).
  * Nakaji and Yamamoto (2021) K. Nakaji and N. Yamamoto, Quantum 5, 434 (2021).
  * Sharma  _et al._ (2022) K. Sharma, M. Cerezo, L. Cincio, and P. J. Coles, Physical Review Letters 128, 180505 (2022), arXiv:2005.12458 .
  * Ortiz Marrero  _et al._ (2021) C. Ortiz Marrero, M. Kieferová, and N. Wiebe, PRX Quantum 2, 040316 (2021), arXiv:2010.15968 .
  * Grant  _et al._ (2019) E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti, Quantum 3, 214 (2019), arXiv:1903.05076 .
  * Verdon  _et al._ (2019a) G. Verdon, M. Broughton, J. R. McClean, K. J. Sung, R. Babbush, Z. Jiang, H. Neven, and M. Mohseni,  , 1 (2019a), arXiv:1907.05415 .
  * Cerezo  _et al._ (2021b) M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Nature Communications 12 (2021b), 10.1038/s41467-021-21728-w.
  * Kieferova  _et al._ (2021) M. Kieferova, O. M. Carlos, and N. Wiebe, arXiv preprint arXiv:2106.09567 (2021).
  * Pesah  _et al._ (2021) A. Pesah, M. Cerezo, S. Wang, T. Volkoff, A. T. Sornborger, and P. J. Coles, Physical Review X 11, 041011 (2021), arXiv:2011.02966 .
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge university press, 2010).
  * Shi  _et al._ (2006) Y.-Y. Shi, L.-M. Duan, and G. Vidal, Physical review a 74, 022320 (2006).
  * Nagaj  _et al._ (2008) D. Nagaj, E. Farhi, J. Goldstone, P. Shor, and I. Sylvester, Physical Review B 77, 214431 (2008).
  * Tagliacozzo  _et al._ (2009) L. Tagliacozzo, G. Evenbly, and G. Vidal, Physical Review B 80, 235127 (2009).
  * Nakatani and Chan (2013) N. Nakatani and G. K.-L. Chan, The Journal of chemical physics 138, 134113 (2013).
  * Wybourne (1974) B. G. Wybourne,  (1974).
  * Biamonte (2021) J. Biamonte, Phys. Rev. A 103, L030401 (2021).
  * (63) “https://github.com/paddlepaddle/paddle,” .
  * Ma  _et al._ (2019) Y. Ma, D. Yu, T. Wu, and H. Wang, Frontiers of Data and Domputing 1, 105 (2019).
  * Emerson  _et al._ (2005) J. Emerson, R. Alicki, and K. Życzkowski, Journal of Optics B: Quantum and Semiclassical Optics 7, S347 (2005).
  * Roberts and Yoshida (2017) D. A. Roberts and B. Yoshida, Journal of High Energy Physics 2017, 1 (2017).
  * Farhi  _et al._ (2014b) E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028 (2014b), arXiv:1411.4028 .
  * Wang  _et al._ (2022) K. Wang, Z. Song, X. Zhao, Z. Wang, and X. Wang, npj Quantum Information 8, 1 (2022).
  * Tang  _et al._ (2021b) H. L. Tang, V. Shkolnikov, G. S. Barron, H. R. Grimsley, N. J. Mayhall, E. Barnes, and S. E. Economou, PRX Quantum 2, 020310 (2021b).
  * Skolik  _et al._ (2021) A. Skolik, J. R. McClean, M. Mohseni, P. van der Smagt, and M. Leib, Quantum Machine Intelligence 3, 1 (2021).
  * Volkoff and Coles (2021) T. Volkoff and P. J. Coles, Quantum Science and Technology 6, 025008 (2021), arXiv:2005.12200 .
  * Verdon  _et al._ (2019b) G. Verdon, M. Broughton, J. R. McClean, K. J. Sung, R. Babbush, Z. Jiang, H. Neven, and M. Mohseni, arXiv preprint arXiv:1907.05415 (2019b).
  * Wilson  _et al._ (2021) M. Wilson, R. Stromswold, F. Wudarski, S. Hadfield, N. M. Tubman, and E. G. Rieffel, Quantum Machine Intelligence 3, 1 (2021).
  * Stollenwerk and Hadfield (2022) T. Stollenwerk and S. Hadfield, arXiv preprint arXiv:2204.01307 (2022).
  * Chen  _et al._ (2021) C. Chen, Z. He, L. Li, S. Zheng, and H. Situ, arXiv preprint arXiv:2106.06248 (2021).
  * Zheng  _et al._ (2021) H. Zheng, Z. Li, J. Liu, S. Strelchuk, and R. Kondor, arXiv preprint arXiv:2112.07611 (2021).
  * Meyer  _et al._ (2022) J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert, arXiv preprint arXiv:2205.06217 (2022).
  * Larocca  _et al._ (2022) M. Larocca, F. Sauvage, F. M. Sbahi, G. Verdon, P. J. Coles, and M. Cerezo, arXiv preprint arXiv:2205.02261 (2022).
  * Dankert  _et al._ (2009) C. Dankert, R. Cleve, J. Emerson, and E. Livine, Physical Review A 80, 012304 (2009).
  * Feit (1982) W. Feit,  _The representation theory of finite groups_ (Elsevier, 1982).

Supplemental Material for
Mitigating barren plateaus of variational quantum eigensolvers

##  I Preliminaries

Here we present some supplemental lemmas and define some notations to be used
throughout the proof. We write a target quantum state, which is a pure state
to be approximated by a PQC, as $|\phi\rangle$ and let the actual circuit
output be $|\psi(\bm{\theta})\rangle$. We may simply write $|\psi\rangle$ if
the circuit parameters $\bm{\theta}$ are unimportant in the context. Moreover,
let $F(|\phi\rangle,|\psi\rangle)=|\langle\psi|\phi\rangle|^{2}$ be fidelity.
Unless otherwise specified, $\\{|k\rangle\\}_{k=0}^{2^{N}-1}$ are the
$N$-qubit computational bases. We denote
$\widetilde{\operatorname{CNOT}}\equiv\prod_{i=0}^{N-i}\operatorname{CNOT}(i,N+i)$
which is a composition of $N\operatorname{CNOT}$s controlled and targeted on
the pair $(i,N+i)$ for all $i=0,\dots,N-1$. Let $\bar{i}$ be a vector for the
binary expansion of $i$, and therefore $\bar{i}_{j}$, where $0\leq
j<\lceil\log i\rceil$, is the $j$-th leading digit of the expansion.

###  I.1 $t$-design and integration over the unitary group

We firstly recall the definition of a $t$-design. Assume
$\mathcal{U}=\\{U_{k}\\}_{k=1}^{K}$ is a finite of unitary operator on
$\mathbb{C}^{D}$, and $P_{t,t}(U)$ is a polynomial of degree at most $t$ in
the matrix elements of $U$ and at most $t$ in those of $U^{\dagger}$. Then, we
define that $\mathcal{U}$ is a $t$-design if for every polynomial $P_{t,t}(U)$
we have

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}P_{t,t}(U_{k})=\int
P_{t,t}(U)d\eta(U),$ (A1)

where the integrals with respect to the Haar measure over the unitary group.
Particularly, when $t=2$, the definition is equivalent to the following
definition Dankert  _et al._ (2009).

###### Definition S1

$\\{U_{k}\\}_{k=1}^{K}$ forms a unitary $2$-design if and only if for any
linear operators $C,D,\rho\in L(\mathbb{C}^{D})$, we have

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}U_{k}^{\dagger}CU_{k}\rho
U_{k}^{\dagger}DU_{k}$
$\displaystyle=\quad\int_{\mathcal{U}(d)}U^{\dagger}CU\rho
U^{\dagger}DUd\eta(U).$ (A2)

Based on this definition, we can know whether a unitary group is a 2-design by
comparing the both sides of Eq. (A2). Fortunately, according to the Schur’s
lemma Feit (1982) , the RHS of Eq. (A3) has a closed form which is shown in
lemma S1. The proof of lemma S1 can be seen in Emerson  _et al._ (2005).

###### Lemma S1

Let $\\{U_{k}\\}_{k=1}^{K}$ forms a unitary $t$-design with $t\geq 2$, for any
linear operators $C,D,\rho\in L(\mathbb{C}^{D})$. We have

$\displaystyle\quad\int_{\mathcal{U}(d)}U^{\dagger}CU\rho
U^{\dagger}DUd\eta(U)=\frac{\operatorname{Tr}[CD]\operatorname{Tr}[\rho]}{d}\frac{I}{d}+(\frac{d\operatorname{Tr}[C]\operatorname{Tr}[D]-\operatorname{Tr}[CD]}{d(d^{2}-1)})(\rho-\operatorname{Tr}[\rho]\frac{I}{d}).$
(A3)

Furthermore, we present the following lemma so that we can solve the problem
with bipartite system.

###### Lemma 2

For any bipartite state $\rho_{AB}$ ($d_{A}=d_{B}=d$), and arbitrary linear
operators $C,D\in L(\mathbb{C}^{d^{2}})$, we have

$\displaystyle\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)U^{\dagger}CU\rho
U^{\dagger}DU=t_{0}\rho+t_{1}\frac{\rho_{A}\otimes
I_{B}}{d}+t_{2}\frac{I_{A}\otimes\rho_{B}}{d}+t_{3}I_{AB}\operatorname{Tr}(\rho_{AB}),$
(A4)

where $\rho_{A}=\operatorname{Tr}_{B}[\rho_{AB}]$,
$\rho_{B}=\operatorname{Tr}_{A}[\rho_{AB}]$,and $\\{t_{j}\\}_{j=0}^{3}$ can be
computed from the following linear system of equations

$\displaystyle\operatorname{Tr}(CD)$
$\displaystyle=t_{0}d^{2}+t_{1}d^{2}+t_{2}d^{2}+t_{3}d^{4},$ (A5)
$\displaystyle\operatorname{Tr}(C_{A}D_{A})$
$\displaystyle=t_{0}d^{3}+t_{1}d+t_{2}d^{3}+t_{3}d^{3},$ (A6)
$\displaystyle\operatorname{Tr}(C_{B}D_{B})$
$\displaystyle=t_{0}d^{3}+t_{1}d^{3}+t_{2}d+t_{3}d^{3},$ (A7)
$\displaystyle\operatorname{Tr}(C)\operatorname{Tr}(D)$
$\displaystyle=t_{0}d^{4}+t_{1}d^{2}+t_{2}d^{2}+t_{3}d^{2},$ (A8)

that is,

$\left[{\begin{array}[]{*{20}{c}}{t_{0}}\\\ {t_{1}}\\\ t_{2}\\\
t_{3}\end{array}}\right]=\frac{1}{\left(d^{2}-1\right)^{2}}\left[{\begin{array}[]{*{20}{c}}\frac{\operatorname{Tr}[CD]}{d^{2}}-\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}-\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}+\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
-\operatorname{Tr}[CD]+\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}+d\operatorname{Tr}[C_{B}D_{B}]-\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
-\operatorname{Tr}[CD]+d\operatorname{Tr}[C_{A}D_{A}]+\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}-\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
\operatorname{Tr}[CD]-\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}-\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}+\frac{\operatorname{Tr}[C]\operatorname{Tr}[D]}{d^{2}}\end{array}}\right].$
(A9)

###### Proof.

Similar to the proof of Lemma S1, Schur’s lemma implies that the LHS of Eq.
(4) has an explicitly expression, which is denoted as follows:

$\displaystyle\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)U^{\dagger}CU\rho
U^{\dagger}DU=t_{0}\rho+t_{1}\frac{\rho_{A}\otimes
I_{B}}{d}+t_{2}\frac{I_{A}\otimes\rho_{B}}{d}+t_{3}I_{AB}\operatorname{Tr}(\rho_{AB}).$
(A10)

For simplicity, we define the following two functions:

$\displaystyle f^{(1)}(\rho)\equiv t_{0}\rho+t_{1}\rho_{A}\otimes
I_{B}/d+t_{2}I_{A}\otimes\rho_{B}/d+t_{3}I_{AB}\operatorname{Tr}(\rho_{AB}),$
(A11) $\displaystyle
f^{(2)}(\rho)\equiv\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)U^{\dagger}CU\rho
U^{\dagger}DU,$ (A12)

where $f^{(1)}=f^{(2)}$.

Then we only need to consider the coefficients $t_{0},t_{1},t_{2},t_{3}$. To
calculate the coefficients, we defined the following four operators:

$\displaystyle T_{1}(f)\equiv\sum_{i,j}\langle ij|f(I)|ij\rangle,$ (A13)
$\displaystyle T_{2}(f)\equiv\sum_{i,j,k}\langle ik|f(|i\rangle\\!\langle
j|_{A}\otimes I_{B})|jk\rangle,$ (A14) $\displaystyle
T_{3}(f)\equiv\sum_{i,k,l}\langle ik|f(I_{A}\otimes|k\rangle\\!\langle
l|_{B})|il\rangle,$ (A15) $\displaystyle T_{4}(f)\equiv\sum_{i,j,k,l}\langle
ij|f(|ij\rangle\\!\langle kl|)|kl\rangle.$ (A16)

For Eq. (A5), we have

$\displaystyle T_{1}(f^{(1)})$ $\displaystyle=t_{0}\sum_{i,j}\langle
ij|I|ij\rangle+t_{1}\sum_{i,j}\langle ij|I_{A}\otimes
I_{B}|ij\rangle+t_{2}\sum_{i,j}\langle ij|I_{A}\otimes
I_{B}|ij\rangle+t_{3}d^{4}$
$\displaystyle=t_{0}d^{2}+t_{1}d^{2}+t_{2}d^{2}+t_{3}d^{4},$ $\displaystyle
T_{1}(f^{(2)})$ $\displaystyle=\sum_{i,j}\langle
ij|\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)U^{\dagger}CUIU^{\dagger}DU|ij\rangle$
$\displaystyle=\operatorname{Tr}(CD).$

Since $T_{1}(f^{(1)})=T_{1}(f^{(2)})$, then
$\operatorname{Tr}(CD)=t_{0}d^{2}+t_{1}d^{2}+t_{2}d^{2}+t_{3}d^{4}$.

For Eq. (A7), we have

$\displaystyle T_{2}(f^{(1)})$ $\displaystyle=t_{0}\sum_{i,j,k}\langle
ik||i\rangle\\!\langle j|\otimes I_{B}|jk\rangle+t_{1}\sum_{i,j,k}\langle
ik||i\rangle\\!\langle j|\otimes I_{B}|jk\rangle$
$\displaystyle\quad+\frac{t_{2}}{d}\sum_{i,j,k}\langle
ik|I_{A}\otimes\operatorname{Tr}[|i\rangle\\!\langle
j|]I_{B}|jk\rangle+t_{3}\sum_{i,j,k}\langle
ik|I_{AB}\operatorname{Tr}[|i\rangle\\!\langle j|\otimes I_{B}]|jk\rangle$
$\displaystyle=t_{0}d^{3}+t_{1}d^{3}+t_{2}d+t_{3}d^{3},$ $\displaystyle
T_{2}(f^{(2)})$ $\displaystyle=\sum_{i,j,k}\langle
ik|\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)U^{\dagger}CU(|i\rangle\\!\langle
j|_{A}\otimes I_{B})U^{\dagger}DU|jk\rangle$
$\displaystyle=\sum_{i,j,k}\int_{\mathcal{U}(d)\otimes\mathcal{U}(d)}d\eta(U)\langle
ik|U^{\dagger}CU(|i\rangle\\!\langle j|_{A}\otimes
I_{B})U^{\dagger}DU|jk\rangle$ $\displaystyle=\operatorname{Tr}(C_{B}D_{B}).$

Since $T_{2}(f^{(1)})=T_{2}(f^{(2)})$, then
$\operatorname{Tr}(C_{B}D_{B})=t_{0}d^{3}+t_{1}d^{3}+t_{2}d+t_{3}d^{3}$.

Similarly, we have

$\displaystyle T_{3}(f^{(1)})$
$\displaystyle=t_{0}d^{3}+t_{1}d+t_{2}d^{3}+t_{3}d^{3},$ $\displaystyle
T_{3}(f^{(2)})$ $\displaystyle=\operatorname{Tr}(C_{A}D_{A}),$ $\displaystyle
T_{4}(f^{(1)})$ $\displaystyle=t_{0}d^{4}+t_{1}d^{2}+t_{2}d^{2}+t_{3}d^{2},$
$\displaystyle T_{4}(f^{(2)})$
$\displaystyle=\operatorname{Tr}(C)\operatorname{Tr}(D).$

Since

$\displaystyle T_{3}(f^{(1)})$ $\displaystyle=T_{3}(f^{(2)}),$ $\displaystyle
T_{4}(f^{(1)})$ $\displaystyle=T_{4}(f^{(2)}),$

then

$\displaystyle\operatorname{Tr}(C_{A}D_{A})$
$\displaystyle=t_{0}d^{3}+t_{1}d+t_{2}d^{3}+t_{3}d^{3},$
$\displaystyle\operatorname{Tr}(C)\operatorname{Tr}(D)$
$\displaystyle=t_{0}d^{4}+t_{1}d^{2}+t_{2}d^{2}+t_{3}d^{2}.$

Up to now, we have proved Eq. (A5) to Eq. (A8).

Let

$R=\left(\begin{array}[]{llll}d^{2}&d^{2}&d^{2}&d^{4}\\\
d^{3}&d^{1}&d^{3}&d^{3}\\\ d^{3}&d^{3}&d^{1}&d^{3}\\\
d^{4}&d^{2}&d^{2}&d^{2}\end{array}\right).$ (A17)

Then

$R^{-1}=\frac{1}{\left(d^{2}-1\right)^{2}}\left(\begin{array}[]{cccc}\frac{1}{d^{2}}&-\frac{1}{d}&-\frac{1}{d}&1\\\
-1&\frac{1}{d}&d&-1\\\ -1&d&\frac{1}{d}&-1\\\
1&-\frac{1}{d}&-\frac{1}{d}&\frac{1}{d^{2}}\end{array}\right).$ (A18)

Hence, we have

$\left[{\begin{array}[]{*{20}{c}}{t_{0}}\\\ {t_{1}}\\\ t_{2}\\\
t_{3}\end{array}}\right]=R^{-1}\left[{\begin{array}[]{*{20}{c}}\operatorname{Tr}(CD)\\\
\operatorname{Tr}(C_{A}D_{A})\\\ \operatorname{Tr}(C_{B}D_{B})\\\
\operatorname{Tr}(C)\operatorname{Tr}(D)\end{array}}\right]=\frac{1}{\left(d^{2}-1\right)^{2}}\left[{\begin{array}[]{*{20}{c}}\frac{\operatorname{Tr}[CD])}{d^{2}}-\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}-\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}+\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
-\operatorname{Tr}[CD]+\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}+d\operatorname{Tr}[C_{B}D_{B}]-\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
-\operatorname{Tr}[CD]+d\operatorname{Tr}[C_{A}D_{A}]+\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}-\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
\operatorname{Tr}[CD]-\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}-\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}+\frac{\operatorname{Tr}[C]\operatorname{Tr}[D]}{d^{2}}\end{array}}\right],$
(A19)

$\left[{\begin{array}[]{*{20}{c}}{t_{0}}\\\ {t_{1}}\\\ t_{2}\\\
t_{3}\end{array}}\right]=\frac{1}{\left(d^{2}-1\right)^{2}}\left[{\begin{array}[]{*{20}{c}}\frac{\operatorname{Tr}[CD]}{d^{2}}-\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}-\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}+\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
-\operatorname{Tr}[CD]+\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}+d\operatorname{Tr}[C_{B}D_{B}]-\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
-\operatorname{Tr}[CD]+d\operatorname{Tr}[C_{A}D_{A}]+\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}-\operatorname{Tr}[C]\operatorname{Tr}[D]\\\
\operatorname{Tr}[CD]-\frac{\operatorname{Tr}[C_{A}D_{A}]}{d}-\frac{\operatorname{Tr}[C_{B}D_{B}]}{d}+\frac{\operatorname{Tr}[C]\operatorname{Tr}[D]}{d^{2}}\end{array}}\right].$
(A20)

∎

##  II Proof of Theorem 1

###### Lemma S2

$\widetilde{\operatorname{CNOT}}=\sum_{i=0}^{2^{n}-1}|i\rangle\\!\langle
i|_{A}\otimes V_{B_{i}}$, where $A,B$ are subsystems and
$V_{B_{i}}=\bigotimes_{j=0}^{n-1}X_{j}^{\bar{i}_{j}},\bar{i}_{j}\in\\{0,1\\}$,
that is the operator on the subsystem $B$ that represents the binary bit of
$i$ is 1 acting on pauli $X$, and 0 acting on $I$. Then $V_{B_{i}}$ has the
following properties:

  1. 1.

$[V_{B_{i}},V_{B_{j}}]=0$;

  2. 2.

$V_{B_{i}}=V_{B_{i}}^{\dagger}$;

  3. 3.

$\langle 0|^{\otimes n}V_{B_{i}}V_{B_{j}}|0\rangle^{\otimes n}=\delta_{ij}$,

where $\delta_{ij}$ is Kronecker delta.

###### Theorem 1

SEA with $U_{i}(i=1,2,3)$ being local 2-design and
$\widetilde{\operatorname{CNOT}}$ as entangling layer does not form a 2-design
on the global system.

###### Proof.

Without losing generality, we only consider the SEA with $2n$ qubits in this
proof. Lemma S1 says that if an ansatz forms a 2-design, the Eq. (A3) should
hold for any linear operators $C,D,\rho\in L(\mathbb{C}^{d^{2}})$. Assuming
$d=2^{n},C_{0}=D_{0}=\rho=|0\rangle\\!\langle 0|^{\otimes 2n}$, then if SEA
forms a 2-design, we have

$\displaystyle\int_{U(\theta)}\langle 0|^{\otimes 2n}U^{\dagger}C_{0}U\rho
U^{\dagger}D_{0}U|0\rangle^{\otimes 2n}d\eta(U)$ (A21) $\displaystyle=$
$\displaystyle\int_{\mathcal{U}(d^{2})}\langle 0|^{\otimes
2n}U^{\dagger}C_{0}U\rho U^{\dagger}D_{0}U|0\rangle^{\otimes 2n}d\eta(U)$
(A22) $\displaystyle=$ $\displaystyle\frac{2}{d^{2}(d^{2}+1)},$ (A23)

where $U(\theta)$ denotes the subset of unitary group generated by SEA, and
$d\eta(U)$ denotes the Haar measure.

In the following steps, we will explicitly calculate the Eq. (A21) and prove
that it cannot be $\frac{2}{d^{2}(d^{2}+1)}$.

For the SEA with $U_{i}(i=1,2,3)$ being local 2-design and
$\widetilde{\operatorname{CNOT}}=V=\sum_{i=0}^{2^{n}-1}|i\rangle\\!\langle
i|_{A}\otimes V_{B_{i}}$, the unitary of this ansatz is

$\displaystyle U$ $\displaystyle=\sum_{i=0}^{2^{n}-1}(U_{2}\otimes
U_{3})\cdot|i\rangle\\!\langle i|\otimes V_{B_{i}}\cdot(U_{1}\otimes I_{B}).$
(A24)

Therefore,

$\displaystyle U|0\rangle^{\otimes 2n}$
$\displaystyle=\sum_{i=0}^{2^{n}-1}(U_{2}\otimes
U_{3})\cdot|i\rangle\\!\langle i|\otimes V_{B_{i}}\cdot(U_{1}\otimes
I_{B})|0\rangle^{\otimes 2n},$ $\displaystyle\langle 0|^{\otimes
2n}U^{\dagger}$ $\displaystyle=\sum_{i=0}^{2^{n}-1}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot|i\rangle\\!\langle i|\otimes
V_{B_{i}}\cdot(U_{2}^{\dagger}\otimes U_{3}^{\dagger}).$

Then

$\displaystyle\quad\langle 0|^{\otimes 2n}U^{\dagger}C_{0}U\rho
U^{\dagger}D_{0}U|0\rangle^{\otimes 2n}$ $\displaystyle=\langle 0|^{\otimes
2n}U^{\dagger}(|0\rangle\\!\langle 0|)^{\otimes 2n}U(|0\rangle\\!\langle
0|)^{\otimes 2n}U^{\dagger}(|0\rangle\\!\langle 0|)^{\otimes
2n}U|0\rangle^{\otimes 2n}$ $\displaystyle=\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot(U_{2}^{\dagger}\otimes
U_{3}^{\dagger})(|0\rangle\\!\langle 0|)^{\otimes 2n}(U_{2}\otimes U_{3})\cdot
V\cdot(U_{1}\otimes I_{B})(|0\rangle\\!\langle 0|)^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}$
$\displaystyle\quad\cdot(U_{2}^{\dagger}\otimes
U_{3}^{\dagger}))(|0\rangle\\!\langle 0|)^{\otimes 2n}(U_{2}\otimes
U_{3})\cdot V\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}$
$\displaystyle:=\langle 0|^{\otimes 2n}(U_{1}^{\dagger}\otimes I_{B})\cdot
V^{\dagger}\cdot(U_{2}^{\dagger}\otimes U_{3}^{\dagger})\cdot
C_{0}\cdot(U_{2}\otimes U_{3})\cdot\rho_{1}\cdot(U_{2}^{\dagger}\otimes
U_{3}^{\dagger})\cdot D_{0}\cdot(U_{2}\otimes U_{3})\cdot V$
$\displaystyle\quad\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n},$

where

$\displaystyle V$ $\displaystyle=\sum_{i=0}^{2^{n}-1}|i\rangle\\!\langle
i|_{A}\otimes V_{B_{i}},$ $\displaystyle\rho_{1}$
$\displaystyle=V\cdot(U_{1}\otimes I_{B})(|0\rangle\\!\langle 0|)^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}.$

Therefore, we have

$\displaystyle\rho_{1}^{A}$ $\displaystyle=\operatorname{Tr}_{B}[\rho_{1}]$
$\displaystyle=\sum_{k=0}^{d-1}I_{A}\otimes\langle k|_{B}\cdot
V\cdot(U_{1}\otimes I_{B})(|0\rangle\\!\langle 0|)^{\otimes
2n}\cdot(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot
I_{A}\otimes|k\rangle_{B}$ $\displaystyle=\sum_{k=0}^{d-1}I_{A}\otimes\langle
k|_{B}\cdot(\sum_{i=0}^{d-1}|i\rangle\\!\langle i|_{A}\otimes
V_{B_{i}})\cdot(U_{1}\otimes I_{B})(|0\rangle\\!\langle 0|)^{\otimes
2n}\cdot(U_{1}^{\dagger}\otimes
I_{B})\cdot(\sum_{j=0}^{d-1}|j\rangle\\!\langle j|_{A}\otimes
V_{B_{j}}^{\dagger})\cdot I_{A}\otimes|k\rangle_{B}$
$\displaystyle=\sum_{i,j,k=0}^{d-1}I_{A}\otimes\langle
k|_{B}\cdot(|i\rangle\\!\langle i|_{A}\otimes V_{B_{i}})\cdot(U_{1}\otimes
I_{B})(|0\rangle\\!\langle 0|)^{\otimes 2n}\cdot(U_{1}^{\dagger}\otimes
I_{B})\cdot(|j\rangle\\!\langle j|_{A}\otimes V_{B_{j}}^{\dagger})\cdot
I_{A}\otimes|k\rangle_{B}$
$\displaystyle=\sum_{i,j,k=0}^{d-1}|i\rangle\\!\langle
i|_{A}U_{1}(|0\rangle\\!\langle 0|)^{\otimes
n}U_{1}^{\dagger}|j\rangle\\!\langle j|_{A}\otimes\langle
k|_{B}V_{B_{i}}(|0\rangle\\!\langle 0|)^{\otimes
n}V_{B_{j}}^{\dagger}|k\rangle_{B}$
$\displaystyle=\sum_{i,j=0}^{d-1}|i\rangle\\!\langle
i|_{A}U_{1}(|0\rangle\\!\langle 0|)^{\otimes
n}U_{1}^{\dagger}|j\rangle\\!\langle j|_{A}(\sum_{k=0}^{d-1}\langle
k|_{B}V_{B_{i}}(|0\rangle\\!\langle 0|)^{\otimes
n}V_{B_{j}}^{\dagger}|k\rangle_{B})$
$\displaystyle=\sum_{i,j=0}^{d-1}|i\rangle\\!\langle
i|_{A}U_{1}(|0\rangle\\!\langle 0|)^{\otimes
n}U_{1}^{\dagger}|j\rangle\\!\langle
j|_{A}\operatorname{Tr}(V_{B_{i}}(|0\rangle\\!\langle 0|)^{\otimes
n}V_{B_{j}}^{\dagger})$ $\displaystyle=\sum_{i,j=0}^{d-1}|i\rangle\\!\langle
i|_{A}U_{1}(|0\rangle\\!\langle 0|)^{\otimes
n}U_{1}^{\dagger}|j\rangle\\!\langle j|_{A}\operatorname{Tr}(\langle
0|^{\otimes n}V_{B_{i}}V_{B_{j}}^{\dagger}|0\rangle^{\otimes n})$
$\displaystyle=\sum_{i=0}^{d-1}|i\rangle\\!\langle i|U_{1}|0\rangle\\!\langle
0|^{\otimes n}U_{1}^{\dagger}|i\rangle\\!\langle i|,\quad\text{(due to
lemma~{}\ref{lem:cnot})}$ $\displaystyle\rho_{1}^{B}$
$\displaystyle=\operatorname{Tr}_{A}[\rho_{1}]$
$\displaystyle=\sum_{k=0}^{d-1}\langle k|_{A}\otimes I_{B}\cdot
V\cdot(U_{1}\otimes I_{B})(|0\rangle\\!\langle 0|)^{\otimes
2n}\cdot(U_{1}^{\dagger}\otimes I_{B})\cdot
V^{\dagger}\cdot|k\rangle_{A}\otimes I_{B}$
$\displaystyle=\sum_{k=0}^{d-1}\langle k|_{A}\otimes
I_{B}\cdot(\sum_{i=0}^{d-1}|i\rangle\\!\langle i|_{A}\otimes
V_{B_{i}})\cdot(U_{1}\otimes I_{B})(|0\rangle\\!\langle 0|)^{\otimes
2n}\cdot(U_{1}^{\dagger}\otimes
I_{B})\cdot(\sum_{j=0}^{d-1}|j\rangle\\!\langle j|_{A}\otimes
V_{B_{j}}^{\dagger})\cdot|k\rangle_{A}\otimes I_{B}$
$\displaystyle=\sum_{i,j,k=0}^{d-1}\langle k|_{A}|i\rangle\\!\langle
i|_{A}U_{1}(|0\rangle\\!\langle 0|)^{\otimes
n}U_{1}^{\dagger}|j\rangle\\!\langle j|_{A}|k\rangle_{A}\cdot
V_{B_{i}}(|0\rangle\\!\langle 0|)^{\otimes n}V_{B_{j}}$
$\displaystyle=\sum_{k=0}^{d-1}\langle k|U_{1}|0\rangle\\!\langle 0|^{\otimes
n}U_{1}^{\dagger}|k\rangle\cdot V_{B_{k}}|0\rangle\\!\langle 0|^{\otimes
n}V_{B_{k}}.$

Then combining lemma S1 and lemma 2, we have

$\displaystyle\quad\int_{U(\theta)}\langle 0|^{\otimes
2n}U^{\dagger}C_{0}U\rho U^{\dagger}D_{0}U|0\rangle^{\otimes 2n}d\eta(U)$
$\displaystyle=\int_{U(\theta)}\langle 0|^{\otimes 2n}(U_{1}^{\dagger}\otimes
I_{B})\cdot V^{\dagger}\cdot(U_{2}^{\dagger}\otimes U_{3}^{\dagger})\cdot
C_{0}\cdot(U_{2}\otimes U_{3})\cdot\rho_{1}\cdot(U_{2}^{\dagger}\otimes
U_{3}^{\dagger})\cdot D_{0}\cdot(U_{2}\otimes U_{3})\cdot V$
$\displaystyle\quad\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}$ (A25)
$\displaystyle=\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot
V^{\dagger}\cdot(t_{0}\rho_{1}+t_{1}\frac{\rho_{1}^{A}\otimes
I_{B}}{d}+t_{2}\frac{I_{A}\otimes\rho_{1}^{B}}{d}+t_{3}I_{AB}\operatorname{Tr}(\rho_{1}))\cdot
V$ $\displaystyle\quad\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}d\eta(U)$
$\displaystyle:=M_{0}+M_{1}+M_{2}+M_{3},$ (A26)

where

$\displaystyle M_{0}$ $\displaystyle=t_{0}\int_{\mathcal{U}_{1}(d)}\langle
0|^{\otimes 2n}(U_{1}^{\dagger}\otimes I_{B})\cdot
V^{\dagger}\cdot\rho_{1}\cdot V\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes
2n}d\eta(U)$ $\displaystyle=t_{0},$ $\displaystyle M_{1}$
$\displaystyle=\frac{t_{1}}{d}\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot\rho_{1}^{A}\otimes
I_{B}\cdot V\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}d\eta(U),$
$\displaystyle M_{2}$
$\displaystyle=\frac{t_{2}}{d}\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot
I_{A}\otimes\rho_{1}^{B}\cdot V\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes
2n}d\eta(U),$ $\displaystyle M_{3}$
$\displaystyle=t_{3}\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot
I_{AB}\operatorname{Tr}(\rho_{1})\cdot V\cdot(U_{1}\otimes
I_{B})|0\rangle^{\otimes 2n}d\eta(U)$ $\displaystyle=t_{3},$ $\displaystyle
t_{0}$ $\displaystyle=t_{3}=\frac{1}{d^{2}(d+1)^{2}},$ $\displaystyle t_{1}$
$\displaystyle=t_{2}=\frac{1}{d(d+1)^{2}}.$

Now the problem is how do we calculate $M_{1}$ and $M_{2}$. Combine with
$V=\sum_{i=0}^{d-1}|i\rangle\\!\langle i|_{A}\otimes V_{B_{i}}$, there has

$\displaystyle M_{1}$
$\displaystyle=\frac{t_{1}}{d}\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot\rho_{1}^{A}\otimes
I_{B}\cdot V\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}d\eta(U)$
$\displaystyle=\frac{t_{1}}{d}\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})(\sum_{i=0}^{d-1}|i\rangle\\!\langle
i|\otimes V_{B_{i}}^{\dagger})\cdot(\sum_{k=0}^{d-1}|k\rangle\\!\langle
k|U_{1}|0\rangle\\!\langle 0|^{\otimes n}U_{1}^{\dagger}|k\rangle\\!\langle
k|\otimes I_{B})$ $\displaystyle\quad\cdot(\sum_{j=0}^{d-1}|j\rangle\\!\langle
j|\otimes V_{B_{j}})(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}d\eta(U)$
$\displaystyle=\frac{t_{1}}{d}\sum_{i=0}^{d-1}\int_{\mathcal{U}_{1}(d)}\langle
0|^{\otimes n}U_{1}^{\dagger}|i\rangle\\!\langle i|U_{1}(|0\rangle\\!\langle
0|)^{\otimes n}U_{1}^{\dagger}|i\rangle\\!\langle i|U_{1}|0\rangle^{\otimes
n}\cdot(\langle 0|0\rangle)^{\otimes n}d\eta(U)$
$\displaystyle=\frac{2t_{1}}{d(d+1)},$ (A27) $\displaystyle M_{2}$
$\displaystyle=\frac{t_{2}}{d}\int_{\mathcal{U}_{1}(d)}\langle 0|^{\otimes
2n}(U_{1}^{\dagger}\otimes I_{B})\cdot V^{\dagger}\cdot
I_{A}\otimes\rho_{1}^{B}\cdot V\cdot(U_{1}\otimes I_{B})|0\rangle^{\otimes
2n}d\eta(U)$ $\displaystyle=\frac{t_{2}}{d}\int_{\mathcal{U}_{1}(d)}\langle
0|^{\otimes 2n}(U_{1}^{\dagger}\otimes
I_{B})(\sum_{i=0}^{d-1}|i\rangle\\!\langle i|\otimes
V_{B_{i}}^{\dagger})\cdot(I_{A}\otimes\sum_{k=0}^{d-1}\langle
k|U_{1}|0\rangle\\!\langle 0|^{\otimes n}U_{1}^{\dagger}|k\rangle
V_{B_{k}}|0\rangle\\!\langle 0|^{\otimes n}V_{B_{k}})$
$\displaystyle\quad\cdot(\sum_{j=0}^{d-1}|j\rangle\\!\langle j|\otimes
V_{B_{j}})(U_{1}\otimes I_{B})|0\rangle^{\otimes 2n}d\eta(U)$
$\displaystyle=\frac{t_{2}}{d}\sum_{i=0}^{d-1}\int_{\mathcal{U}_{1}(d)}\langle
0|^{\otimes n}U_{1}^{\dagger}|i\rangle\\!\langle i|U_{1}(|0\rangle\\!\langle
0|)^{\otimes n}U_{1}^{\dagger}|i\rangle\\!\langle i|U_{1}|0\rangle^{\otimes
n}\cdot(\langle 0|0\rangle)^{\otimes n}d\eta(U)$
$\displaystyle=\frac{2t_{2}}{d(d+1)}.$ (A28)

Therefore,

$\displaystyle Eq.~{}\eqref{eq:U1U2}$ $\displaystyle=M_{0}+M_{1}+M_{2}+M_{3}$
$\displaystyle=\frac{2d+6}{d^{2}(d+1)^{3}}$
$\displaystyle\neq\frac{2}{d^{2}(d^{2}+1)}(\text{$n\geq 1,d=2^{n}>1$})$
$\displaystyle=Eq.~{}\eqref{eq:2n-qubit}.$ (A29)

Thus, SEA with $U_{i}(i=1,2,3)$ being local 2-design ansatzes and
$\widetilde{\operatorname{CNOT}}$ is not a unitary 2-design. ∎

##  III Proof of Property 1 and Property 2

###### Property 1

If $U_{1}$ can generate an arbitrary $N$-qubit pure state, then given any
$2N$-qubit pure state $|\phi\rangle$, a $2N$-qubit SEA can generate
$|\phi\rangle$ with a certain set of parameters
$\bm{\hat{\theta}}=\\{\hat{\bm{\theta}}_{1},\hat{\bm{\theta}}_{2},\hat{\bm{\theta}}_{3}\\}$,
that is,

$\displaystyle S(\bm{\hat{\theta}})|0\rangle^{\otimes 2N}=|\phi\rangle.$ (A30)

###### Proof.

Beginning with Schmidt decomposition, we can write the target state
$|\phi\rangle$ as

$|\phi\rangle=(\hat{U}_{2}\otimes\hat{U}_{3})\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|k\rangle_{B},$

where $A$ and $B$ are two $N$-qubit subsystems, $\hat{U}_{2}$ and
$\hat{U}_{3}$ are two unitary operators acting on these two subsystems,
$\\{|k\rangle\\}_{k=0}^{2^{N}-1}$ are the $N$-qubit computational bases, and
$\\{\lambda_{k}\\}_{k=0}^{2^{N}-1}$ are Schmidt coefficients.

Because $U_{1}(\bm{\theta_{1}})$ can generate an arbitrary $N$-qubit pure
state, and $U_{2}(\bm{\theta_{2}}),U_{3}(\bm{\theta_{3}})$ are universal, we
can choose a certain set of parameters
$\bm{\hat{\theta}}=\\{\hat{\bm{\theta}}_{1},\hat{\bm{\theta}}_{2},\hat{\bm{\theta}}_{3}\\}$such
that

$\displaystyle U_{1}(\hat{\bm{\theta}}_{1})|0\rangle^{\otimes N}$
$\displaystyle=\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle,$ (A31) $\displaystyle
U_{2}(\hat{\bm{\theta}}_{2})$ $\displaystyle=\hat{U}_{2},$ (A32)
$\displaystyle U_{3}(\hat{\bm{\theta}}_{3})$ $\displaystyle=\hat{U}_{3}.$
(A33)

Combining with $V$, which is a composition of $N\operatorname{CNOT}$s
controlled and targeted on the qubit-pairs $\\{(i,N+1)\\}_{i=0}^{N-1}$, there
has

$\displaystyle V(U_{1}(\bm{\theta_{1}})\otimes I)|0\rangle_{A}^{\otimes
N}|0\rangle_{B}^{\otimes N}=$
$\displaystyle\sum_{k=0}^{2^{N}-1}\lambda_{k}V|k\rangle_{A}|0\rangle_{B}^{\otimes
N}$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|k\rangle_{B}.$

Therefore, we have

$\displaystyle S(\hat{\bm{\theta}})|0\rangle^{\otimes 2N}$
$\displaystyle=(U_{2}(\hat{\bm{\theta}}_{2})\otimes
U_{3}(\hat{\bm{\theta}}_{3}))V(U_{1}(\hat{\bm{\theta}}_{1})\otimes
I)|0\rangle^{\otimes N}|0\rangle^{\otimes N}$
$\displaystyle=(\hat{U}_{2}\otimes\hat{U}_{3})\sum_{k=0}^{2^{N}-1}\lambda_{k}|k\rangle_{A}|k\rangle_{B}.$
$\displaystyle=|\phi\rangle.$

∎

###### Lemma S3

For any descending sequence $\\{x_{i}\\}_{i=1}^{n}(x_{i}\geq x_{i+1})$, and
any $n\geq N\geq M\geq 1$ ($n,N,M\in\mathbb{Z}$), the following is true:

$\frac{1}{M}\sum_{i=1}^{M}x_{i}\geq\frac{1}{N}\sum_{i=1}^{N}x_{i}.$

###### Proof.

Because $N\geq M\geq 1$ and $x_{i}\geq x_{i+1}$, we have the following
formula:

$\displaystyle\quad\frac{1}{M}\sum_{i=1}^{M}x_{i}-\frac{1}{N}\sum_{i=1}^{N}x_{i}$
$\displaystyle=\frac{1}{M}\sum_{i=1}^{M}x_{i}-(\frac{1}{N}\sum_{i=1}^{M}x_{i}+\frac{1}{N}\sum_{i=M+1}^{N}x_{i})$
$\displaystyle=(\frac{1}{M}-\frac{1}{N})\sum_{i=1}^{M}x_{i}-\frac{1}{N}\sum_{i=M+1}^{N}x_{i}$
$\displaystyle=\frac{1}{N}(\frac{N-M}{M}\sum_{i=1}^{M}x_{i}-\sum_{i=M+1}^{N}x_{i})$
$\displaystyle=\frac{N-M}{N}(\frac{1}{M}\sum_{i=1}^{M}x_{i}-\frac{1}{N-M}\sum_{i=M+1}^{N}x_{i})$
$\displaystyle\geq\frac{N-M}{N}(\frac{1}{M}\sum_{i=1}^{M}x_{M}-\frac{1}{N-M}\sum_{i=M+1}^{N}x_{M+1})\quad\text{(because
$x_{i}\geq x_{i+1}$)}$ $\displaystyle=\frac{N-M}{N}(x_{M}-x_{M+1})$
$\displaystyle\geq 0,$

thus, we obtain
$\frac{1}{M}\sum_{i=1}^{M}x_{i}-\frac{1}{N}\sum_{i=1}^{N}x_{i}\geq 0$, that
is, $\frac{1}{M}\sum_{i=1}^{M}x_{i}\geq\frac{1}{N}\sum_{i=1}^{N}x_{i}$. ∎

###### Property 2

If $U_{1}$ can generate any $N$-qubit pure state that is a superposition of at
most $K$ computational basis states, then for any $|\phi\rangle$, there exists
an SEA output state $|\psi\rangle$ with
$F(|\phi\rangle,|\psi\rangle)\geq\min\left\\{\frac{K}{r},1\right\\}$, where
$F(|\phi\rangle,|\psi\rangle)$ is the fidelity between $|\phi\rangle$ and
$|\psi\rangle$, and $r$ is the Schmidt rank of $|\phi\rangle$.

###### Proof.

For any $2N$-qubit target state
$|\phi\rangle=\sum_{k=0}^{r-1}\lambda_{k}|v_{k}\rangle_{A}|v_{k}\rangle_{B}$,
we explicitly construct an SEA, such that
$|\psi\rangle=S(\hat{\bm{\theta}})|0\rangle^{\otimes 2N}$ and
$F(|\phi\rangle,|\psi\rangle)\geq\min\\{\frac{K}{r},1\\}$, where
$\hat{\bm{\theta}}=\\{\hat{\bm{\theta}}_{1},\hat{\bm{\theta}}_{2},\hat{\bm{\theta}}_{3}\\}$
is a certain set of parameters.

Suppose $\\{\lambda_{k}\\}_{k=0}^{r-1}$ is the Schmidt coefficients of
$|\phi\rangle$ sorted in descending order.

Similar to the proof of Property 1, we can choose a certain set of parameters
$\hat{\bm{\theta}}$ such that

$\displaystyle U_{1}(\hat{\bm{\theta}}_{1})|0\rangle_{A}^{\otimes N}$
$\displaystyle=\frac{1}{\sqrt{M}}\sum_{k=0}^{\min\\{K,r\\}-1}\lambda_{k}|k\rangle,$
(A34) $\displaystyle U_{2}(\hat{\bm{\theta}}_{2})|k\rangle_{A}$
$\displaystyle=|v_{k}\rangle_{A},$ (A35) $\displaystyle
U_{3}(\hat{\bm{\theta}}_{3})|k\rangle_{B}$ $\displaystyle=|v_{k}\rangle_{B},$
(A36)

where $M=\sum_{k=0}^{\min\\{K,r\\}-1}\lambda_{k}^{2}$. Then

$|\psi\rangle=S(\hat{\bm{\theta}})|0\rangle^{\otimes
2N}=\frac{1}{\sqrt{M}}\sum_{k=0}^{\min\\{K,r\\}-1}\lambda_{k}|v_{k}\rangle_{A}|v_{k}\rangle_{B}.$

Hence

$\displaystyle F(|\phi\rangle,|\psi\rangle)$
$\displaystyle=|\langle\phi|\psi\rangle|^{2}$
$\displaystyle=\Big{(}\frac{1}{\sqrt{M}}\sum_{k=0}^{\min\\{K,r\\}-1}\lambda_{k}^{2}\Big{)}^{2}$
$\displaystyle=\frac{1}{M}\Big{(}\sum_{k=0}^{\min\\{K,r\\}-1}\lambda_{k}^{2}\Big{)}^{2}$
$\displaystyle=\sum_{k=0}^{\min\\{K,r\\}-1}\lambda_{k}^{2}$
$\displaystyle\geq\frac{\min\\{K,r\\}}{r}\sum_{k=0}^{r-1}\lambda_{k}^{2}\quad(\text{due
to lemma \ref{lemma:average}})$ $\displaystyle=\frac{\min\\{K,r\\}}{r}$
$\displaystyle=\min\\{\frac{K}{r},1\\},$

with equality holds if and only if $\lambda_{i}=\lambda_{j},\forall
i,j=0,\dots,r-1$. ∎

###### Property 3

Constructing a $2N$-qubit SEA that can generate an arbitrary pure state
requires at most $O(4^{N})$ independent parameters.

###### Proof.

As has been proved in property 1, SEA composed of a universal Schmidt layer,
two local universal N-qubit PQCs and $N$ $\operatorname{CNOT}$s, can generate
an arbitrary pure state. Therefore, the number of independent parameters of
this SEA is $f(N)=4^{N}+2\times 4^{N}-1$, that is, $f(N)=O(4^{N})$.

However, the dimension of unitary group of $2N$-qubit is $4^{2N}$. Thus, a
$2N$-qubit universal ansatz needs at least $O(4^{2N})$ independent parameters.
∎

##  IV Proof of Property 4

###### Property 4

For any $2N$-qubit Hamiltonian $H$, it holds that

$\displaystyle\min_{S}\langle 0|^{\otimes 2N}S^{\dagger}HS|0\rangle^{\otimes
2N}=E_{0},$ (A37)

where $E_{0}$ is the ground state energy of $H$ and the optimization is over
all unitaries reachable by SEA with $U_{1}$ having universal wavefunction
expressibility.

###### Proof.

A given $2N$-qubit Hamiltonian $H$ can be written as follows according to
spectral decomposition:

$H=\sum_{i=0}^{m}E_{i}P_{i},$

where $\\{E_{i}\\}_{i=0}^{m}$ are eigenvalues of $H$ such that
$E_{0}<E_{1}<\cdots<E_{m}$ and $P_{i}$ is a projector onto the eigenspace
$V_{i}$ corresponding to the eigenvalue $E_{i}$. Then given an arbitrary pure
state $|\psi\rangle\in V_{0}$, we have

$H|\psi\rangle=E_{0}|\psi\rangle.$

Note that when the optimization is over all unitaries reachable by SEA with
$U_{1}$ having universal wavefunction expressibility, there exists an $S$ such
that $|\psi\rangle=S|0\rangle^{\otimes 2N}$. Therefore,

$\displaystyle\langle 0|^{\otimes 2N}S^{\dagger}HS|0\rangle^{\otimes 2N}$
$\displaystyle=\langle\psi|H|\psi\rangle$ (A38)
$\displaystyle=E_{0}\langle\psi|\psi\rangle$ (A39) $\displaystyle=E_{0}.$
(A40)

Since it is trivial that $\min_{S}\langle 0|^{\otimes
2N}S^{\dagger}HS|0\rangle^{\otimes 2N}\geq E_{0}$, we have

$\displaystyle\min_{S}\langle 0|^{\otimes 2N}S^{\dagger}HS|0\rangle^{\otimes
2N}=E_{0}.$ (A41)

∎

##  V Supplementary Description of Experiments

In this section, we present results from supplementary numerical experiments.
Table S1 shows the specific calculation method for the numbers of parameters.
Fig. S1 displays the results of VQE using the SEA of Schmidt coefficient layer
as $R_{y}(\bm{\theta})^{\otimes 6}$, entangling layer as 6 CNOTs and the LBC
layers as two $6$-qubit ALTs. Fig. S2 shows the variance of the largest
partial derivative in each sample.

Table S1: Comparison of the number of parameters in different ansatzes. $N$ represents qubit number, $l_{i}(i=1,2,3)$ is the number of layer of $U_{i}$. | SEA | ALT | Random
---|---|---|---
parameter number | $3N+6(N-1)l_{1}$ | $2N+2(2N-1)l_{2}$ | $2Nl_{3}$
Figure S1: Numerical experiment of VQE on LiH (12-qubit).The blue dotted line
is the theoretical ground energy of LiH, and the lines from top to bottom
represent the experimental results of ALT, the random circuit, SEA with
$R_{y}(\bm{\theta})$ as $U_{1}$ and two ALTs as $U_{2},U_{3}$ and $6$ CNOTs as
entangling layer, SEA with three ALTs as $U_{i}(i=1,2,3)$ and $3$ CNOTs as
entangling layer, SEA with three ALTs as $U_{i}(i=1,2,3)$ and $6$ CNOTs as
entangling layer, respectively. $j$($j=2,3$) CNOTs means that we set a
composition of $j\operatorname{CNOT}$s controlled and targeted on the qubit-
pairs $\\{(i,N+i)\\}_{i=0}^{j-1}$. Figure S2: Comparison of the scaling of
variance between different ansatzes on the Heisenberg model. It shows the
semi-log plot of the variance of the largest partial derivative among
parameters in each round of sampling. We ensure different ansatzes have
similar number of parameters by setting different depth. The solid part of the
fitted lines represents the range we experimented with, while the dotted part
represents the expected performance on a larger range.