# Towards Efficient Ansatz Architecture for Variational Quantum Algorithms

Anbang Wu
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
&Gushu Li
Department of Electrical & Computer Engineering
University of California, Santa Barbara
<EMAIL_ADDRESS>
Yuke Wang
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
Boyuan Feng
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
Yufei Ding
Department of Computer Science
University of California, Santa Barbara
<EMAIL_ADDRESS>
Yuan Xie
Department of Electrical & Computer Engineering
University of California, Santa Barbara
<EMAIL_ADDRESS>

###### Abstract

Variational quantum algorithms are the quantum analogy of the successful
neural network in classical machine learning. The ansatz architecture design,
which is similar to classical neural network architecture design, is critical
to the performance of a variational quantum algorithm. In this paper, we
explore how to design efficient ansatz and investigate several common design
options in today’s quantum software frameworks. In particular, we study the
number of effective parameters in different ansatz architectures and
theoretically prove that an ansatz with parameterized RX and RZ gates and
alternating two-qubit gate entanglement layers would be more efficient (i.e.,
more effective parameters per two-qubit gate). Such ansatzes are expected to
have stronger expressive power and obtain better solutions. Numerical
experimental results show that our efficient ansatz architecture outperforms
other ansatzes with smaller ansatz size and better optimization results.

##  1 Introduction

Quantum machine learning [8] is an emerging machine learning paradigm due to
its intrinsic large state space and the ability to fast generating
probabilistic distributions that are justifiably hard to sample from a
classical machine [1, 9]. Variational Quantum Algorithms (VQAs), which come
with intrinsic noise resilience [24, 36] and modest computation resource
requirement [11], are expected to tackle machine learning tasks and
demonstrate practical usage on the near-term quantum computing devices. VQA-
based quantum machine learning has been applied on various tasks, including
optimization [16, 20], chemistry simulation [29, 33], quantum program
compilation [26, 36], etc.

VQA can be considered as the quantum version of the classical neural network
(NN) [27]. The structure of the model in VQA, which is often termed as
‘ansatz’ in the quantum computing community, is a parameterized quantum
circuit111the conventional name of quantum program under the well-adopted
quantum circuit model [31] similar to the NN architecture. In a VQA ansatz,
there are some single-qubit gates with parameters applied on different qubits
locally. There are also some two-qubit gates connecting different qubit pairs
and formulating a network structure. The ansatz is executed on a quantum
processor to evaluate a cost function determined by the specific machine
learning task, which is similar to a forward execution of NN. The parameters
in the ansatz are tuned through a classical optimizer to minimize the cost
function, which is the analogy of NN training.

Similar to classical NN, the ansatz architecture is critical to the
performance of VQA and is actively being studied. Some ansatz architectures,
e.g., Quantum CNN [14], Quantum RNN [6], Quantum LSTM [13], and Quantum GNN
[40], are inspired by successful classical NN architectures. Some other ansatz
architectures are inspired by the application, e.g., the Unitary Coupled-
Cluster Singles and Doubles (UCCSD) ansatz [5] for chemistry simulation and
the Quantum Alternating Operator Ansatz [16] for combinatorial problems.
However, such ansatzes have not yet been demonstrated in experiments due to
their relatively high resource requirements and complex structures.

Except for the architectures mentioned above, one type of ansatz architecture
of particular interest is the hardware-efficient ansatz (HEA) employed in
several recent experimental demonstrations of VQAs [3, 4, 25]. HEA usually
employs layers of parameterized single-qubit gates, which can provide linear
transformation (similar to the weight matrix in NN), and layers of two-qubit
gates, which can bring entanglement in the state and enrich the expressive
power (like the non-linear layers in NN). The architectures of HEAs are
regular and easy to be efficiently mapped onto near-term hardware with limited
computation capability. In this paper, we focus on HEA which is probably the
most practical model for QML in the next decade.

One drawback of HEA is that its solution space may not include the desired
solution due to its application-independent design. Today’s quantum computing
software frameworks like Qiskit [2], provide multiple reconfigurable HEA
templates while the best HEA design in practice is not known. One active
research direction to evaluate the quality of HEA designs is to study the
expressive power of different HEA designs [37, 35, 30, 17]. In general, a HEA
with more gates and parameters is more expressive and more likely to capture
the desired solution.

Recall that the original design objective of HEA is to reduce the gate count
for efficiency on hardware. Being more expressive with more gates is clearly
in the opposite direction. For example, the strong expressive power of quantum
states comes from the entanglement among different qubits and the entanglement
must be established by the non-local two-qubit gates. But the two-qubit gates
usually have relatively long latency and high error rates. For example, the
average error rate of two-qubit gates on IBM’s superconducting quantum devices
is $10\times$ higher than that of single-qubit gates.

In this paper, we investigate the efficient ansatz architecture design and our
goal is to provide more expressive power with fewer gates and parameters. We
analyze several common parameterized single-qubit layer designs and two-qubit
entanglement layer designs. In particular, we study the number of effective
parameters (parameters that cannot be combined with other ones) and the number
of the expensive two-qubit gates in different architectures. The efficiency
can then be improved by increase the number of effective parameters per two-
qubit gate.

Our theoretical analysis is based on a widely-used hardware model where the
two-qubit gates are fixed CX gates and single-qubit gates are parameterized
rotation gates along different axes. We made several key observations. First,
if an ansatz consists of a single type of rotation (e.g., rotation along
X-axis, RX) in the entanglement layer, the upper bound of the number of
effective parameters is small. Second, increasing the number of CX gates in
the entanglement layer may not enrich the expressive power. Third, an ansatz
made up of two types of rotation gates (e.g., rotation along X- and Y-axis,
RX-RZ) and an alternating entanglement layer is more efficient. These
observations provide insights about how to get more expressive power with
fewer gates (especially two-qubit gates).

We evaluate our theoretical results by comparing the RX-RZ-CX ansatz with
other common ansatz architectures on various VQA tasks, including molecule
simulation and combinatorial problems. Experiment results show that the
simulation error of RX-RZ-CX ansatz with alternating entanglement is only
around 4.4% of that of the RX-CX ansatz with a linear CX entanglement on
average for molecule simulation tasks. For combinatorial optimization tasks,
all tested ansatz architectures can achieve the optimal solution while the RX-
RZ-CX ansatz has the smallest number of CX gates.

Our major contributions can be summarized as follows:

  1. 1.

We study the expressive power of commonly-used hardware-efficient ansatzes via
calculating the number of effective parameters.

  2. 2.

We propose and examine various common HEA configuration options to help select
efficient architectures for HEA.

  3. 3.

Our numerical experiments demonstrate the effectiveness of the suggested
ansatz design. The proposed RX-RZ-CX ansatz with alternating entanglement can
achieve better solutions comparing with the RX-CX ansatz with linear
entanglement.

###  1.1 Related Work

The architecture of ansatz is one of the key design problems for VQAs [11].
Today’s quantum software frameworks, e.g., IBM’s Qiskit Aqua library [2],
provide various built-in ansatz architectures. The design methodology of VQA
ansatz can be classified into two types. The first type is to design the
ansatz architecture based on the target problem, e.g., the UCCSD ansatz for
the chemistry simulation applications [34]. These ansatzes are in general
easier to converge [41] while they require a large number of gates and are
beyond the computation capability of noisy near-term devices. The second type
of ansatz is usually termed as hardware-efficient ansatz and its architecture
is designed based on the target hardware platform [25]. These ansatzes have
relatively lower gate counts and have been widely employed to experimentally
demonstrate VQAs [3, 4, 25, 28].

It is not yet fully resolved how to optimally construct a hardware-efficient
ansatz. One active research area towards this objective to is study the
expressive power of different ansatz constructions because an ansatz with a
strong expressive power can represent more complicated functions [23] and is
more likely to cover the desired solution. Sim et al. proposed to analyze the
ansatz expressive power from a statistical perspective [37] and the proposed
method is later employed by [35] and [30] to detect redundant parameters and
compare the expressive power of different ansatzes, respectively. [17]
proposed a geometric algorithm that identifies superfluous parameters with
ancilla qubits. In contrast, this paper provides an algebraic analysis of
commonly-used ansatzes. Our analysis directly identifies redundant parameters
and suggests that the RX-RZ-CX ansatz with alternating entanglement is more
efficient in the sense of the number of effective parameters per two-qubit
gate.

It has also been noticed that highly expressive ansatzes are more difficult to
train [22, 32, 39], which is the same with classical machine learning. Various
strategies [35, 17, 30, 19] have been proposed to improve VQA trainability.
How to efficiently train an expressive ansatz is worth further exploring yet
beyond the scope of this paper.

##  2 Preliminary

###  2.1 Quantum Computation Basics

The quantum bit (qubit) is the basic information processing unit in quantum
computing. The state of a qubit can be represented by a unit vector in a
2-dimensional Hilbert space spanned by the computational basis states
$\ket{0}$ and $\ket{1}$ of the qubit. Specifically, the state $\ket{\psi}$ of
a qubit can be expressed by $\ket{\psi}=a\ket{0}+b\ket{1}$ where
$a,b\in\mathbb{C}$ and $\absolutevalue{a}^{2}+\absolutevalue{b}^{2}=1$.
Without ambiguity, $\ket{\psi}$ can be written in the vector form
$\ket{\psi}=(a,b)^{\intercal}$ which is known as the state vector. For a
system with $n$ qubits, its state space is the tensor product of all its
qubits and is a $2^{n}$-dimensional Hilbert space. A state vector in this
space is a vector with $2^{n}$ elements
$\ket{\psi}=(a_{0},\dots,a_{2^{n}-1})^{\intercal}$.

The most popular quantum computation model is the circuit model [31]. In this
model, quantum algorithms are represented by quantum circuits which are
composed of sequences of quantum gates and measurements applied on qubits.
Quantum gates on an $n$-qubit system are unitary operators in the
$2^{n}$-dimensional Hilbert space. For example, the single-qubit bit-flip gate
$\mathrm{X}$ can convert quantum state $\ket{0}$ to quantum state $\ket{1}$:
$\mathrm{X}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\
\mathrm{X}\ket{0}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}\begin{pmatrix}1\\\
0\end{pmatrix}=\begin{pmatrix}0\\\ 1\end{pmatrix}=\ket{1}.$

In this paper, we only consider single-qubit gates and two-qubit gates.
Because they have been proved to be universal [15] and most existing quantum
hardware platforms only support single- and two-qubit gates. We list the
definitions of the $x$-axis rotation gate $\mathrm{RX}$, $z$-axis rotation
gate $\mathrm{RZ}$, a two-qubit gate $\mathrm{CX}$, and their circuit
representation in the following:

$\mathrm{RX}(\theta)=\begin{pmatrix}\cos{\frac{\theta}{2}}&-i\sin{\frac{\theta}{2}}\\\
-i\sin{\frac{\theta}{2}}&\cos{\frac{\theta}{2}}\end{pmatrix},\mathrm{RZ}(\theta)=\begin{pmatrix}e^{-i\frac{\theta}{2}}&0\\\
0&e^{i\frac{\theta}{2}}\end{pmatrix},\mathrm{CX}=\begin{pmatrix}1&0&0&0\\\
0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\\\
\end{pmatrix},\begin{array}[]{c}\includegraphics[width=90.0pt]{fig/basis_gate3.pdf}\end{array}$

The RX and RZ gates are parameterized single-qubit gates. The CX is a fixed
two-qubit gate.

Entanglement: The entanglement is a unique feature in quantum computing and
can be created by two-qubit gates. For example, CX gate can transform quantum
state $\ket{\psi_{0}}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0}$ of qubits
$q_{0}$ and $q_{1}$ to $\ket{\psi_{1}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$:

$\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\\\
\end{pmatrix}\begin{pmatrix}\frac{1}{\sqrt{2}}\\\ 0\\\ \frac{1}{\sqrt{2}}\\\
0\end{pmatrix}=\begin{pmatrix}\frac{1}{\sqrt{2}}\\\ 0\\\ 0\\\
\frac{1}{\sqrt{2}}\end{pmatrix}.$

The state $\ket{\psi_{1}}$ cannot be generated from $\ket{\psi_{0}}$ by only
using single-qubit gates. Such ability of a two-qubit gate to produce
correlations between different qubits can greatly enrich the expressive power
of quantum algorithms [37].

The measurements are not covered in this section since measurement usually
does not appear in the HEA architecture, which is the focus of this paper. We
refer the reader to [31] for details.

###  2.2 VQA Basics and Ansatz Architecture

The quantum circuit of a VQA is a parameterized circuit (a.k.a. ansatz) and
some gates can be tuned to change their functions (e.g., the $\rm RX(\theta)$
gate mentioned above). Therefore, the final state $\ket{\psi(\bm{\theta})}$
after executing the ansatz will depend on the parameters. The solution of the
VQA task is usually encoded in the minimal eigenvalue (or the corresponding
eigenstate) of a Hermitian operator $O$ called observable. On a quantum
processor, we can evaluate $\bra{\psi(\bm{\theta})}O\ket{\psi(\bm{\theta})}$
and then optimize parameters $\bm{\theta}$ to minimize
$\bra{\psi(\bm{\theta})}O\ket{\psi(\bm{\theta})}$. After
$\bra{\psi(\bm{\theta})}O\ket{\psi(\bm{\theta})}$ is minimized,
$\bra{\psi(\bm{\theta})}O\ket{\psi(\bm{\theta})}$ will be the minimal
eigenvalue and $\ket{\psi(\bm{\theta})}$ is the corresponding eigenstate.

One natural question regarding the performance of VQA is that whether the
eigenstate with respect to the smallest eigenvalue of the observable can be
reached or approximated by tuning the parameters in the ansatz. The answer is
highly related to the architecture of the ansatz. In this paper, we focus on
one type of ansatz architecture, namely hardware-efficient ansatz (HEA),
because it is constructed by gates that can be directly executed on the near-
term quantum hardware. A typical HEA has a layered architecture [25] which
consists of two-qubit gate layers to provide entanglement and single-qubit
gate layers with tunable parameters. Figure 1 (a) shows a linear entanglement
layer with CX gates connecting all qubits one by one. The single-qubit gate
layer of hardware-efficient ansatz only contains rotation gates most time.
Figure 2 (a) provides an example of HEA which contains only single-qubit gates
of RX and linear entanglement layer of CX gates. The design space of HEA can
be explored in several directions, including changing the order of two-qubit
gates in the entanglement layer (Figure 1 (b) (c)), applying two-qubit gates
on different qubit pairs (e.g., alternating entanglement in Figure 2 (b)),
modifying the single-qubit gate layer (Figure 2 (c)), etc.

Figure 1: CX gates in an entanglement layer. (a) linear entanglement layer.
(b)(c) examples of changing the order of CX gates in an entanglement layer
Figure 2: RX-CX ansatz with (a) linear entanglement (b) alternating
entanglement, parameters in the RX gates are omitted (c) RX-RZ-CX ansatz with
alternating entanglement

##  3 HEA Expressive Power Analysis

In this section, we analyze the expressive power of commonly-used ansatz forms
from existing quantum software frameworks. We will focus on HEA since this
type of ansatz has relatively low cost and is more likely to be deployed on
near-term devices. In particular, we study two key aspects in ansatz design,
the two-qubit gate connection topology and the selection of single-qubit
rotation gates. We assume that all two-qubit gates are CX gates without
parameters and all single-qubit gates are parameterized rotation gates. This
is a widely used setting in prior research [25, 37] and today’s quantum
software frameworks [2, 7].

###  3.1 Effective Parameters of RX-CX Ansatz

We first study the number of effective parameters since more effective
parameters in an ansatz lead to stronger expressive power. We start from a
simple case with one CX gate and two RX gates placed before and after the CX
gate on the target qubit of the CX gate.. In the following proposition, we
demonstrate an example in which the two parameters of the two RX gates can be
aggregated.

######  Proposition 3.1 (X-rule).

The following two quantum circuits are equivalent.

Proof. The equivalence can be checked immediately by calculation. ∎

Since the two parameters $\theta_{1}$ and $\theta_{2}$ can be combined into
one parameter $\theta=\theta_{1}+\theta_{2}$ in one RX gate in the proposition
above, the circuit above with two parameters only has one effective parameter.
This example suggests that an ansatz may have many parameters but the number
of effective parameters may be smaller since some parameters can be combined.

We then study a more complicated case for RX-CX ansatz. The RX-CX ansatz has a
layered architecture (Figure 2 (a)). In this ansatz, we first have one layer
of RX gates on all qubits. Then we employ an entanglement block, in which the
qubits are connected by CX gates to create entanglement and enhance the
expressive power of the ansatz. We use linear entanglement in this case. In
the following proposition, we show that the number of effective parameters in
an RX-CX ansatz with linear entanglement is very limited even if the ansatz is
deep and has a large number of parameters.

######  Proposition 3.2.

Suppose the number of effective parameters of an n-qubit RX-CX ansatz with
linear entanglement is $K$. We have the following conclusion:
$K\leq\lfloor\frac{3n^{2}+1}{4}\rfloor$ and the parameter combination is
illustrated in Figure 3.

Proof. Postponed to appendix A.1. ∎

This proposition provides an upper bound of the number of effective parameters
in an RX-CX ansatz with linear entanglement. That is, even if such an ansatz
has many layers and many single-qubit gates with parameters, the number of
effective parameters will always be limited by this upper bound. Surprisingly,
the upper bound grows quadratically as the number of qubits increases. For an
$n$-qubit system, the unitary transformation on it is a $2^{n}$-dimensional
linear operator which can be considered as a matrix with $4^{n}$ elements.
Therefore, an ansatz would require an exponentially (with respect to the
number of qubits) large number of effective parameters to become expressive
and cover all possible unitary transformations. However, an RX-CX ansatz with
linear entanglement cannot support such a large number of effective
parameters. Thus, we argue that this ansatz architecture is not effective
since it can only cover a small portion of all possible unitary
transformations.

Figure 3: Parameter combination result for 4-qubit RX-CX ansatz with linear
entanglement. Parameters that can be combined are connected by a curve.

###  3.2 Order of the CX Gates

We then investigate the variants of this RX-CX ansatz and we first modify the
CX gates in the entanglement layer. In the following proposition, we show that
our result in Proposition 3.2 holds when changing the order of the CX gates in
a linear entanglement layer.

######  Proposition 3.3 (CX order does not matter).

An n-qubit RX-CX ansatz with modified linear entanglement has at most
$\lfloor\frac{3n^{2}+1}{4}\rfloor$ effective parameters. The modified linear
entanglement has alternated CX order compared with the original linear
entanglement as shown in Figure 1 (b)(c).

Proof. Postponed to appendix A.2. ∎

Another option to change the CX gates in the entanglement layer is to employ
the so-called alternating entanglement layer. The architecture of RX-CX ansatz
with alternating entanglement layer is shown in Figure 2 (b). In such
architecture, we first have one layer of RX gates followed by one layer of CX
gates applied on qubit pairs $(0,1),(2,3),\dots$. We then have another layer
of RX gates followed by one layer of CX gates applied on qubit pairs
$(1,2),(3,4),\dots$. The CX gates are applied to non-overlapping qubit pairs
in one layer.

Comparing to the RX-CX ansatzes with linear entanglement, the RX-CX ansatzes
with alternating entanglement have more single-qubit gates (or equivalently,
more parameters) per CX gate. Such property would be desirable if all
parameters are effective parameters. Because the CX gate has relatively high
execution overhead (high error rate and long gate latency) and an efficient
ansatz should support more effective parameters with fewer CX gates. However,
a direct corollary of Proposition 3.3 is that employing the alternating
entanglement layer in the RX-CX ansatz cannot improve the upper bound of the
number of effective parameters.

######  Corollary 3.1.

A $(2L)$-layer RX-CX ansatz with alternating entanglement can be reduced to an
$L$-layer RX-CX ansatz with linear entanglement.

Proof. Postponed to appendix A.2. ∎

###  3.3 More CX Gates in the Entanglement Layer

Another direction to change the ansatz architecture is to have more CX gates
in the entanglement layer. We propose the next two propositions to study the
effect of adding CX gates in the entanglement layer. The construction of
entanglement layer, even with CX gates only, is very complex because we can
have many CX gates on arbitrary two qubits in arbitrary order. Here we explore
two approaches to increase the number of CX gates in the entanglement layer.

One direct change is to repeat the entanglement layer multiple times. However,
since the entanglement layer only has CX gates, repeating such a layer may not
yield a high expressive power.

######  Proposition 3.4 (Repetition of entanglement layer).

For any entanglement layer that is purely constructed by CX gates, there
exists an integer $k$, s.t. $E^{k}=I$ where $E$ is the unitary transformation
represented by the entanglement layer and $I$ is the identity operator.

Proof. Postponed to appendix A.3. ∎

This result suggests that repeating an entanglement layer can only yield a
finite number of different unitary transformations. Actually, for any non-
negative integer $t=sk+r$, $E^{t}=(E^{k})^{s}E^{r}=I^{s}E^{r}=E^{r}$ by
Proposition 3.4. Thus, the set of all possible numbers of repetitions is
equivalent to the finite set $\\{I,E,E^{2},\cdots,E^{k-1}\\}$ which forms a
cyclic group of order $k$ under matrix multiplication. Therefore, it may not
be efficient to repeat the entanglement layer since it will significantly
increase the number of expensive CX gates.

We also find that the functionality of the CX-based entanglement layer is
limited and we formulate this statement in the next proposition.

######  Proposition 3.5 (Limitation of CX-based entanglement layer).

For a given n-qubit unitary transformation $U$, $\forall i,j\geq 2$, it is
possible to move $i$-th column of $U$ to $j$-th column of $U$ with a finite
number of CXs, but it is not possible to achieve column swap between two
arbitrary columns when $n\geq 3$.

Proof. Postponed to appendix A.3. ∎

An entanglement layer with CX gates is not universal and it cannot even
implement swapping two columns. As a result, to increase the number of
effective parameters per CX gate, it would be better to have more
parameterized single-qubit gates between the entanglement layers.

###  3.4 An Efficient Ansatz Architecture

Finally, our objective is to have an efficient ansatz architecture design. We
are not going to give the optimal solution since it is a highly complicated
problem and the optimal ansatz might depend on the optimization objective
function. Instead, we aim to give a better ansatz architecture design based on
the propositions above.

We find that an ansatz with two types of single-qubit gates, RX and RZ, and
alternating entanglement would be more efficient as it can give a higher
number of effective parameters per CX gate. The architecture of this RX-RZ-CX
ansatz is shown in Figure 2 (c). The alternating entanglement layers are the
same as those in the RX-CX ansatz. The only difference is that we have two
single-qubit gates RX and RZ on each qubit in each single-qubit layer. We
believe that such RX-RZ-CX ansatz with alternating entanglement will be
efficient since the RZ gate provides rotations along the $z$-axis which is
beyond the rotations along the $x$-axis provided by the RX gates and CX gates.
Also, the alternating entanglement employs relatively few CX gates to support
one single-qubit layer.

######  Theorem 3.1 (Efficiency of the RX-RZ-CX ansatz with alternating
entanglement).

For an $n$-qubit $2L$-layer RX-RZ-CX ansatz with alternating entanglement, the
numbers of effective parameters (w.r.t parameter combination) $w_{xz}$
satisfies $w_{xz}=(4n-3)*L$.

Proof. Postponed to appendix A.4. ∎

######  Corollary 3.2.

Theorem 3.1 can be generalized to other types of HEA such as RY-CX, RX-RY-CX
and RY-RZ-CX. The number of effective parameters of an $n$-qubit $2L$-layer
RY-CX, RX-RY-CX, or RY-RZ-CX ansatz with alternating entanglement is
$w_{y}=(n-1)*2L$, $w_{yz}=(4n-3)*L$, or $w_{xy}=(4n-3)*L$, respectively.

Proof. Postponed to appendix A.4. ∎

The results in Theorem 3.1 shows that the number of effective parameters per
CX gate of an RX-RZ-CX ansatz with alternating entanglement is far larger than
that of an RX-CX ansatz with linear entanglement if they have the same number
of layers. As a result, the RX-RZ-CX ansatzes are expected to outperform the
RX-CX ansatzes in VQA applications because the relative expressive power is
higher and better solutions can possibly be covered by the expressive
ansatzes.

##  4 Evaluation

In this section, we evaluate our major results in the last section by
comparing the RX-RZ-CX ansatz with alternating entanglement and other ansatz
architectures on various VQA benchmarks.

###  4.1 Experimental Setup

Benchmarks: We select seven VQA benchmarks. The first four benchmarks are the
ground state energy simulation of four molecules (${\rm H_{2}}$, ${\rm LiH}$,
${\rm BeH_{2}}$, ${\rm HF}$) using the variational quantum eigensolver (VQE)
[33]. The second three benchmarks are to solve three combinatorial
optimization problems, the graph max-cut problem (MC), the vertex cover
problem (VC), and the traveling salesman problem (TSP) using the quantum
approximate optimization algorithm (QAOA) [16]. The number of qubits and the
minimum (optimal value) of the cost function of the benchmarks are listed in
Table 1.

Table 1: Benchmark information

Name | VQE-${\rm H_{2}}$ | VQE-${\rm LiH}$ | VQE-${\rm BeH_{2}}$ | VQE-${\rm HF}$ | QAOA-MC | QAOA-VC | QAOA-TSP
---|---|---|---|---|---|---|---
# of Qubits | 4 | 6 | 8 | 10 | 4 | 6 | 9
optimal cost $E$ | -1.1373 | -7.8810 | -15.048 | -98.593 | 2.0 | 3.0 | 202.0

Ansatz architectures: We use RX-CX ansatz with linear entanglement, denoted by
‘RX-CX-L’, RX-CX ansatz with alternating entanglement, denoted by ‘RX-CX-A’,
and RX-RZ-CX ansatz with alternating entanglement, denoted by ‘RX-RZ-CX-A’ ,
to illustrate the importance of effective parameters and the effect of the
alternating entanglement. These ansatzes are either generated by Qiskit or
obtained from previous work [12, 30].

Metric: We evaluate the approximation error to compare the performance of
different ansatzes. The approximation error is defined as:
$\epsilon=\absolutevalue{E_{a}-E}$, where $E_{a}$ is the cost function value
optimized by VQA , and $E$ is the minimum cost function value which is the
smallest eigenvalue of the target observable. In our simulation-based
experiments, $E$ can be obtained by applying the eigensolver from Numpy [21]
on the observable of the task to evaluate the performance of the ansatz
architectures. For a practical problem that cannot be simulated classically,
$E$ can be evaluated or cross-validated with other approaches, e.g.,
experiment results for chemistry simulation tasks.

Implementation: All experiments are implemented on IBM’s Qiskit framework [2].
For molecule simulation problems (i.e., VQE tasks), we use the Qiskit
Chemistry module and PySCF [38] driver to generate the Hamiltonian of target
molecules. For combinatorial optimization tasks, we use the Qiskit
Optimization module to generate the Hamiltonian of the simulated combinatorial
optimization problems. We use the COBYLA optimizer [10] to optimize the
parameters. Since today’s public quantum devices cannot accommodate a full VQA
training process, all experiments in this paper are performed in the Qiskit
Simulator running on a server with a 6-core Intel E5-2603v4 CPU and 32GB of
RAM. Parameters are randomly initialized.

###  4.2 Results

Table 2 shows the simulation result of different ansatzes on various VQA
tasks. In general, the RX-RZ-CX-A ansatzes outperform other selected ansatz
architectures with more accurate solutions for VQE chemistry simulation tasks.
For QAOA tasks, the three types of ansatzes have comparable accuracy (all
errors are smaller than $10^{-4}$). This is because the solution state of QAOA
tasks is a computational basis state, which means a highly entangled final
state may not be necessary and a high-quality result may be generated from
simpler ansatzes.

Effect of effective parameters: We first compare RX-CX-L ansatz and RX-RZ-CX-A
ansatz. With the same number of layers, the number of CX gates in an RX-RZ-
CX-A ansatz is half of that in an RX-CX-L ansatz. By Theorem 3.1, RX-RZ-CX-A
ansatz has more effective parameters than the RX-CX-L ansatz. As expected, RX-
RZ-CX-A ansatz can have much more accurate results than RX-CX-L ansatz and the
error is reduced by $95.5\%$ for VQE tasks.

We then compare the RX-CX-L ansatz and RX-CX-A ansatz, both of which only have
parameters in RX gates. When they share the same number of layers, we know
that the RX-CX-L ansatz has twice as many effective parameters as the RX-CX-A
ansatz by Corollary 3.1. The approximation error of the RX-CX-L ansatz is
reduced by $37.5\%$ comparing with the error of the RX-CX-A ansatz (with the
same number of layers) on VQE tasks.

These results indicate that incorporating more effective parameters in the
ansatz can improve the expressive power, and thus reduce the approximation
error of the ansatz. There are mainly two ways to increase the number of
effective parameters without changing the ansatz structure: introducing extra
single-qubit gates or having more layers. However, for the RX-CX ansatz, it is
not possible to boost the number of effective parameters by adding more
layers, as indicated by Proposition 3.2.

Table 2: Simulation results for VQE and QAOA tasks.

name | ansatz | # of params. | # of CXs | # of layers | optimized cost $E_{a}$ | error $\epsilon$
---|---|---|---|---|---|---
| RX-CX-L | 20 | 12 | 4 | -0.83096 | 0.30634
VQE-${\rm H_{2}}$ | RX-CX-A | 20 | 6 | 4 | -0.82081 | 0.31649
|  | 40 | 12 | 8 | -0.83096 | 0.30634
| RX-RZ-CX-A | 40 | 6 | 4 | -1.1170 | 0.02030
| RX-CX-L | 36 | 25 | 5 | -7.6532 | 0.22780
VQE-${\rm LiH}$ | RX-CX-A | 36 | 13 | 5 | -7.5202 | 0.36080
|  | 72 | 25 | 10 | -7.7222 | 0.15880
| RX-RZ-CX-A | 72 | 13 | 5 | -7.8656 | 0.01540
| RX-CX-L | 48 | 35 | 5 | -14.802 | 0.24600
VQE-${\rm BeH_{2}}$ | RX-CX-A | 48 | 18 | 5 | -14.566 | 0.48200
|  | 96 | 35 | 10 | -14.880 | 0.16800
| RX-RZ-CX-A | 96 | 18 | 5 | -15.040 | 0.00800
| RX-CX-L | 60 | 45 | 5 | -97.687 | 0.90600
VQE-${\rm HF}$ | RX-CX-A | 60 | 23 | 5 | -96.756 | 1.8370
|  | 120 | 45 | 10 | -97.969 | 0.62400
| RX-RZ-CX-A | 120 | 23 | 5 | -98.568 | 0.02500
| RX-CX-L | 20 | 12 | 4 | 2.0000 |  $<$ $10^{-4}$
QAOA-MC | RX-CX-A | 20 | 6 | 4 | 2.0000 |  $<$ $10^{-4}$
|  | 40 | 12 | 8 | 2.0000 |  $<$ $10^{-4}$
| RX-RZ-CX-A | 20 | 6 | 4 | 2.0000 |  $<$ $10^{-4}$
| RX-CX-L | 36 | 25 | 5 | 3.0000 |  $<$ $10^{-4}$
QAOA-VC | RX-CX-A | 36 | 13 | 5 | 3.0000 |  $<$ $10^{-4}$
|  | 72 | 25 | 10 | 3.0000 |  $<$ $10^{-4}$
| RX-RZ-CX-A | 72 | 25 | 5 | 3.0000 |  $<$ $10^{-4}$
| RX-CX-L | 54 | 40 | 5 | 202.00 |  $<$ $10^{-4}$
QAOA-TSP | RX-CX-A | 54 | 20 | 5 | 202.00 |  $<$ $10^{-4}$
|  | 108 | 40 | 10 | 202.00 |  $<$ $10^{-4}$
| RX-RZ-CX-A | 108 | 20 | 5 | 202.00 |  $<$ $10^{-4}$

Effect of entanglement layer architecture: Besides the number of effective
parameters, the structure of the entanglement layer may also affect the
performance of the ansatz. With twice the number of layers, the RX-CX-A ansatz
has the same number of effective parameters as the RX-CX-L ansatz by Corollary
3.1. This indicates that the RX-CX-A ansatz needs to have more single-qubit
gates and parameters than the RX-CX-L ansatz if we hope to keep the same
number of effective parameters in the RX-CX-A and the RX-CX-L ansatz. In this
case, many parameters in the RX-CX-A ansatz will be redundant. In general, the
ansatz with a larger number of redundant parameters has lower performance
because of the worse trainability. However, in our experiment, the results of
the RX-CX-A ansatz are slightly better than that of the RX-CX-L ansatz (error
reduced by $22\%$ on average). This may come from the better trainability of
an ansatz with alternating entanglement, as indicated by [30].

##  5 Discussion

The ansatz architecture of VQA can significantly affect the optimization
result quality, trainability, execution overhead, etc. An optimal ansatz
architecture towards all these design objectives is, to the best of our
knowledge, not yet known or may not exist. In this paper, we focused on the
efficiency of different ansatz architectures and studied how to provide more
expressive power with fewer gates (especially two-qubit gates). We believe
that this is critical if we hope to demonstrate some practical usage of VQA on
near-term noisy quantum computing devices. We investigated several common
ansatz design options and found that using the RX-RZ-CX ansatz with
alternating entanglement layer can provide more effective parameters per CX
gate compared with other common architectures discussed in this study. These
results can guide the design of future VQA ansatz and, hopefully, make
progress towards quantum advantage.

Although our conclusion has been evidenced by both theoretical analysis and
experiment results, there is much work left since the design space is
extremely large for VQA ansatz and there are multiple ansatz architecture
optimization objectives. Here we briefly discuss some potential future
research directions.

Application-specific HEA: In this paper, we focus on efficient ansatz design
and try to maintain strong expressive power with fewer CX gates for a smaller
execution overhead. The trainability of HEA is another critical problem of
great interest since generally HEA trades in trainability for efficiency. The
application-specific ansatzes are usually easier to train. It is worth
exploring if trainability and efficiency can be achieved simultaneously if
application information is introduced into HEA architecture design.

Parameter pruning: Our conclusion suggests that deploying single-qubit gates
of different types would increase the number of effective parameters. However,
similar to classical NN, ansatz with a large number of effective parameters
will be inevitably harder to train. One possible solution is to remove
effective parameters that have relatively small effects on ansatz performance.
The parameter pruning techniques in classical NN may be migrated to VQA to
reduce the total number of parameters and improve the trainability.

More efficient entanglement: Our theoretical analysis and experiment results
have verified that the RX-RZ-CX ansatz with alternating entanglement can give
a high-quality solution with relatively few CX gates. However, the alternating
entanglement layer may not be optimal and the efficiency of the entanglement
layer can be further improved. For example, we may not need to fully connect
all qubits in a linear entanglement layer or connect completely different
qubit pairs in successive entanglement layers. Also, the CX gate may not be
the most efficient two-qubit gate to create entanglement and we may
investigate other common two-qubit gates like the $\rm\sqrt{iSWAP}$ and ZZ
gate [18].

##  6 Conclusion

In this paper, we provide an algebraic viewpoint of the expressive power of
ansatz. By analyzing the number of effective parameters, we show that the RX-
CX ansatz with linear entanglement has limited expressive power. We also
examine several common design options that can possibly improve the expressive
power of ansatz. Based on our theoretical analysis, we suggest that the RX-RZ-
CX ansatz with alternating entanglement is more efficient than the RX-CX
ansatz with linear entanglement in terms of the number of effective parameters
per two-qubit gate. Experiment results support our theoretical claim. The
theoretical framework proposed by this paper can be further extended to more
complex ansatz design problems and pave the way to demonstrating near-term
quantum advantage using VQAs.

## References

  * [1] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In 32nd Computational Complexity Conference, page 1, 2017.
  * [2] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Matthew Amy, Eli Arbel, Arijit02, Abraham Asfaw, Artur Avkhadiev, Carlos Azaustre, AzizNgoueya, Abhik Banerjee, Aman Bansal, Panagiotis Barkoutsos, Ashish Barnawal, George Barron, George S. Barron, Luciano Bello, Yael Ben-Haim, Daniel Bevenius, Arjun Bhobe, Lev S. Bishop, Carsten Blank, Sorin Bolos, Samuel Bosch, Brandon, Sergey Bravyi, Bryce-Fuller, David Bucher, Artemiy Burov, Fran Cabrera, Padraic Calpin, Lauren Capelluto, Jorge Carballo, Ginés Carrascal, Adrian Chen, Chun-Fu Chen, Edward Chen, Jielun (Chris) Chen, Richard Chen, Jerry M. Chow, Spencer Churchill, Christian Claus, Christian Clauss, Romilly Cocking, Filipe Correa, Abigail J. Cross, Andrew W. Cross, Simon Cross, Juan Cruz-Benito, Chris Culver, Antonio D. Córcoles-Gonzales, Sean Dague, Tareq El Dandachi, Marcus Daniels, Matthieu Dartiailh, DavideFrr, Abdón Rodríguez Davila, Anton Dekusar, Delton Ding, Jun Doi, Eric Drechsler, Drew, Eugene Dumitrescu, Karel Dumon, Ivan Duran, Kareem EL-Safty, Eric Eastman, Grant Eberle, Pieter Eendebak, Daniel Egger, Mark Everitt, Paco Martín Fernández, Axel Hernández Ferrera, Romain Fouilland, FranckChevallier, Albert Frisch, Andreas Fuhrer, Bryce Fuller, MELVIN GEORGE, Julien Gacon, Borja Godoy Gago, Claudio Gambella, Jay M. Gambetta, Adhisha Gammanpila, Luis Garcia, Tanya Garg, Shelly Garion, Austin Gilliam, Aditya Giridharan, Juan Gomez-Mosquera, Gonzalo, Salvador de la Puente González, Jesse Gorzinski, Ian Gould, Donny Greenberg, Dmitry Grinko, Wen Guan, John A. Gunnels, Mikael Haglund, Isabel Haide, Ikko Hamamura, Omar Costa Hamido, Frank Harkins, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Stefan Hillmich, Hiroshi Horii, Connor Howington, Shaohan Hu, Wei Hu, Junye Huang, Rolf Huisman, Haruki Imai, Takashi Imamichi, Kazuaki Ishizaki, Raban Iten, Toshinari Itoko, JamesSeaward, Ali Javadi, Ali Javadi-Abhari, Wahaj Javed, Jessica, Madhav Jivrajani, Kiran Johns, Scott Johnstun, Jonathan-Shoemaker, Vismai K, Tal Kachmann, Akshay Kale, Naoki Kanazawa, Kang-Bae, Anton Karazeev, Paul Kassebaum, Josh Kelso, Spencer King, Knabberjoe, Yuri Kobayashi, Arseny Kovyrshin, Rajiv Krishnakumar, Vivek Krishnan, Kevin Krsulich, Prasad Kumkar, Gawel Kus, Ryan LaRose, Enrique Lacal, Raphaël Lambert, John Lapeyre, Joe Latone, Scott Lawrence, Christina Lee, Gushu Li, Dennis Liu, Peng Liu, Yunho Maeng, Kahan Majmudar, Aleksei Malyshev, Joshua Manela, Jakub Marecek, Manoel Marques, Dmitri Maslov, Dolph Mathews, Atsushi Matsuo, Douglas T. McClure, Cameron McGarry, David McKay, Dan McPherson, Srujan Meesala, Thomas Metcalfe, Martin Mevissen, Andrew Meyer, Antonio Mezzacapo, Rohit Midha, Zlatko Minev, Abby Mitchell, Nikolaj Moll, Jhon Montanez, Gabriel Monteiro, Michael Duane Mooring, Renier Morales, Niall Moran, Mario Motta, MrF, Prakash Murali, Jan Müggenburg, David Nadlinger, Ken Nakanishi, Giacomo Nannicini, Paul Nation, Edwin Navarro, Yehuda Naveh, Scott Wyman Neagle, Patrick Neuweiler, Johan Nicander, Pradeep Niroula, Hassi Norlen, NuoWenLei, Lee James O’Riordan, Oluwatobi Ogunbayo, Pauline Ollitrault, Raul Otaolea, Steven Oud, Dan Padilha, Hanhee Paik, Soham Pal, Yuchen Pang, Vincent R. Pascuzzi, Simone Perriello, Anna Phan, Francesco Piro, Marco Pistoia, Christophe Piveteau, Pierre Pocreau, Alejandro Pozas-iKerstjens, Milos Prokop, Viktor Prutyanov, Daniel Puzzuoli, Jesús Pérez, Quintiii, Rafey Iqbal Rahman, Arun Raja, Nipun Ramagiri, Anirudh Rao, Rudy Raymond, Rafael Martín-Cuevas Redondo, Max Reuter, Julia Rice, Matt Riedemann, Marcello La Rocca, Diego M. Rodríguez, RohithKarur, Max Rossmannek, Mingi Ryu, Tharrmashastha SAPV, SamFerracin, Martin Sandberg, Hirmay Sandesara, Ritvik Sapra, Hayk Sargsyan, Aniruddha Sarkar, Ninad Sathaye, Bruno Schmitt, Chris Schnabel, Zachary Schoenfeld, Travis L. Scholten, Eddie Schoute, Joachim Schwarm, Ismael Faro Sertage, Kanav Setia, Nathan Shammah, Yunong Shi, Adenilton Silva, Andrea Simonetto, Nick Singstock, Yukio Siraichi, Iskandar Sitdikov, Seyon Sivarajah, Magnus Berg Sletfjerding, John A. Smolin, Mathias Soeken, Igor Olegovich Sokolov, Igor Sokolov, SooluThomas, Starfish, Dominik Steenken, Matt Stypulkoski, Shaojun Sun, Kevin J. Sung, Hitomi Takahashi, Tanvesh Takawale, Ivano Tavernelli, Charles Taylor, Pete Taylour, Soolu Thomas, Mathieu Tillet, Maddy Tod, Miroslav Tomasik, Enrique de la Torre, Kenso Trabing, Matthew Treinish, TrishaPe, Davindra Tulsi, Wes Turner, Yotam Vaknin, Carmen Recio Valcarce, Francois Varchon, Almudena Carrera Vazquez, Victor Villar, Desiree Vogt-Lee, Christophe Vuillot, James Weaver, Johannes Weidenfeller, Rafal Wieczorek, Jonathan A. Wildstrom, Erick Winston, Jack J. Woehr, Stefan Woerner, Ryan Woo, Christopher J. Wood, Ryan Wood, Stephen Wood, Steve Wood, James Wootton, Daniyar Yeralin, David Yonge-Mallo, Richard Young, Jessie Yu, Christopher Zachow, Laura Zdanski, Helena Zhang, Christa Zoufal, and Mantas Čepulkovskis.  Qiskit: An open-source framework for quantum computing, 2019.
  * [3] F. Arute, K. Arya, R. Babbush, D. Bacon, Joseph C. Bardin, R. Barends, S. Boixo, M. Broughton, B. Buckley, David A. Buell, B. Burkett, N. Bushnell, Y. Chen, Zhiqiang Chen, B. Chiaro, R. Collins, W. Courtney, Sean Demura, A. Dunsworth, E. Farhi, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, Steve Habegger, Matthew P. Harrigan, A. Ho, S. Hong, T. Huang, William J. Huggins, L. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, P. Klimov, A. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, Mike Lindmark, E. Lucero, O. Martin, J. M. Martinis, J. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, Wojciech Mruczkiewicz, J. Mutus, O. Naaman, M. Neeley, C. Neill, H. Neven, M. Y. Niu, T. E. O’brien, E. Ostby, A. Petukhov, Harald Putterman, C. Quintana, P. Roushan, N. Rubin, D. Sank, K. Satzinger, V. Smelyanskiy, D. Strain, Kevin J. Sung, M. Szalay, Tyler Y Takeshita, A. Vainsencher, T. White, N. Wiebe, Z. Yao, P. Yeh, and Adam Zalcman.  Hartree-fock on a superconducting qubit quantum computer.  Science, 369:1084 – 1089, 2020.
  * [4] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, David A Buell, et al.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  arXiv preprint arXiv:2004.04197, 2020.
  * [5] P. Barkoutsos, Jérôme F Gonthier, I. Sokolov, N. Moll, G. Salis, Andreas Fuhrer, M. Ganzhorn, D. Egger, M. Troyer, A. Mezzacapo, S. Filipp, and I. Tavernelli.  Quantum algorithms for electronic structure calculations: Particle-hole hamiltonian and optimized wave-function expansions.  Physical Review A, 98:022322, 2018.
  * [6] J. Bausch.  Recurrent quantum neural networks.  ArXiv, abs/2006.14619, 2020.
  * [7] V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, and Nathan Killoran.  Pennylane: Automatic differentiation of hybrid quantum-classical computations.  ArXiv, abs/1811.04968, 2018.
  * [8] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * [9] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, 14(6):595–600, 2018.
  * [10] Joachim Bös.  Numerical optimization of the thickness distribution of three-dimensional structures with respect to their structural acoustic properties.  Structural and Multidisciplinary Optimization, 32(1):12–30, 2006\.
  * [11] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles.  Variational quantum algorithms, 2020.
  * [12] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles.  Cost-function-dependent barren plateaus in shallow quantum neural networks.  arXiv preprint arXiv:2001.00550, 2020.
  * [13] S. Y. Chen, S. Yoo, and Y. Fang.  Quantum long short-term memory.  ArXiv, abs/2009.01783, 2020.
  * [14] Iris Cong, S. Choi, and M. D. Lukin.  Quantum convolutional neural networks.  Nature Physics, pages 1–6, 2018.
  * [15] C. M. Dawson and M. Nielsen.  The solovay-kitaev algorithm.  Quantum Inf. Comput., 6:81–95, 2006.
  * [16] E. Farhi, J. Goldstone, and S. Gutmann.  A quantum approximate optimization algorithm.  arXiv: Quantum Physics, 2014.
  * [17] L. Funcke, T. Hartung, K. Jansen, Stefan Kuhn, and Paolo Stornati.  Dimensional expressivity analysis of parametric quantum circuits.  arXiv: Quantum Physics, 2020.
  * [18] Pranav Gokhale, A. Javadi-Abhari, N. Earnest, Yunong Shi, and F. Chong.  Optimized quantum compilation for near-term algorithms with openpulse.  2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 186–200, 2020.
  * [19] E. Grant, L. Wossnig, M. Ostaszewski, and Marcello Benedetti.  An initialization strategy for addressing barren plateaus in parametrized quantum circuits.  arXiv: Quantum Physics, 2019.
  * [20] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, E. Rieffel, Davide Venturelli, and R. Biswas.  From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.  Algorithms, 12:34, 2019.
  * [21] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, and et al.  Array programming with numpy.  Nature, 585(7825):357–362, Sep 2020.
  * [22] Zoe Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles.  Connecting ansatz expressibility to gradient magnitudes and barren plateaus.  2021\.
  * [23] T. Hubregtsen, Josef Pichlmeier, and K. Bertels.  Evaluation of parameterized quantum circuits: on the design, and the relation between classification accuracy, expressibility and entangling capability.  ArXiv, abs/2003.09887, 2020.
  * [24] JarrodRMcClean, JonathanRomero, RyanBabbush, and andAlánAspuru Guzik.  The theory of variational hybrid quantum-classical algorithms.  2016\.
  * [25] Abhinav Kandala, A. Mezzacapo, K. Temme, Maika Takita, M. Brink, J. Chow, and J. Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  Nature, 549:242–246, 2017.
  * [26] S. Khatri, Ryan LaRose, Alexander Poremba, L. Cincio, A. Sornborger, and Patrick J. Coles.  Quantum assisted quantum compiling.  arXiv: Quantum Physics, 2018.
  * [27] Nathan Killoran, Thomas R. Bromley, J. Arrazola, M. Schuld, N. Quesada, and S. Lloyd.  Continuous-variable quantum neural networks.  ArXiv, abs/1806.06871, 2018.
  * [28] Christian Kokail, Christine Maier, Rick van Bijnen, Tiff Brydges, Manoj K Joshi, Petar Jurcevic, Christine A Muschik, Pietro Silvi, Rainer Blatt, Christian F Roos, and P Zoller.  Self-verifying variational quantum simulation of lattice models.  Nature, 569(7756):355–360, 2019.
  * [29] S. McArdle, Suguru Endo, Alán Aspuru-Guzik, S. Benjamin, and Xiao Yuan.  Quantum computational chemistry.  Reviews of Modern Physics, 92:015003, 2020.
  * [30] Kouhei Nakaji and N. Yamamoto.  Expressibility of the alternating layered ansatz for quantum computation.  arXiv: Quantum Physics, 2020.
  * [31] Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information.  Quantum Computation and Quantum Information, by Michael A. Nielsen, Isaac L. Chuang, Cambridge, UK: Cambridge University Press, 2010, 2010\.
  * [32] T. L. Patti, Khadijeh Najafi, Xun Gao, and S. Yelin.  Entanglement devised barren plateau mitigation.  2020\.
  * [33] A. Peruzzo, J. McClean, Peter Shadbolt, Man-Hong Yung, X. Zhou, P. Love, Alán Aspuru-Guzik, and J. O’Brien.  A variational eigenvalue solver on a photonic quantum processor.  Nature Communications, 5, 2014.
  * [34] 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:4213, 2014.
  * [35] S. E. Rasmussen, N. J. S. Loft, T. Baekkegaard, M. Kues, and N. Zinner.  Reducing the amount of single-qubit rotations in vqe and related algorithms.  arXiv: Quantum Physics, 2020.
  * [36] Kunal Sharma, S. Khatri, M. Cerezo, and Patrick J. Coles.  Noise resilience of variational quantum compiling.  arXiv: Quantum Physics, 2019.
  * [37] Sukin Sim, P. Johnson, and Alán Aspuru-Guzik.  Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms.  arXiv: Quantum Physics, 2019.
  * [38] Qiming Sun, Timothy C. Berkelbach, Nick S. Blunt, George H. Booth, Sheng Guo, Zhendong Li, Junzi Liu, James D. McClain, Elvira R. Sayfutyarova, Sandeep Sharma, Sebastian Wouters, and Garnet Kin-Lic Chan.  Pyscf: the python-based simulations of chemistry framework, 2017.
  * [39] J. Tangpanitanon, Supanut Thanasilp, Ninnat Dangniam, Marc-Antoine Lemonde, and D. Angelakis.  Expressibility and trainability of parameterized analog quantum systems for machine learning applications.  arXiv: Quantum Physics, 2020.
  * [40] Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, V. Singh, Stefan Leichenauer, and J. Hidary.  Quantum graph neural networks.  ArXiv, abs/1909.12264, 2019.
  * [41] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, J. Carrasquilla, Y. Kim, and H. Yuen.  Exploring entanglement and optimization within the hamiltonian variational ansatz.  ArXiv, abs/2008.02941, 2020.

##  Appendix A Proof of the Propositions and Theorems in Section 3

In the following, the qubit indices start from 0.

###  A.1 Proposition 3.2: Effective Parameters of RX-CX Ansatz

######  Lemma A.1.

$\mathrm{CX}\cdot(\mathrm{X}\otimes\mathrm{I})=(\mathrm{X}\otimes\mathrm{X})\cdot\mathrm{CX}=(\mathrm{X}\otimes\mathrm{I})\cdot\mathrm{CX}\cdot(\mathrm{I}\otimes\mathrm{X})$.

###### Proof.

$\mathrm{CX}\cdot(\mathrm{X}\otimes\mathrm{I})=\begin{pmatrix}\mathrm{I}&\bm{0}\\\
\bm{0}&\mathrm{X}\end{pmatrix}\begin{pmatrix}\bm{0}&\mathrm{I}\\\
\mathrm{I}&\bm{0}\end{pmatrix}=\begin{pmatrix}\bm{0}&\mathrm{I}\\\
\mathrm{X}&\bm{0}\end{pmatrix}=\begin{pmatrix}\bm{0}&\mathrm{X}\\\
\mathrm{X}&\bm{0}\end{pmatrix}\begin{pmatrix}\mathrm{I}&\bm{0}\\\
\bm{0}&\mathrm{X}\end{pmatrix}=(\mathrm{X}\otimes\mathrm{X})\cdot\mathrm{CX}$.
On the other hand, with Proposition 3.1, we have
$(\mathrm{X}\otimes\mathrm{X})\cdot\mathrm{CX}=(\mathrm{X}\otimes\mathrm{I})\cdot\mathrm{CX}\cdot(\mathrm{I}\otimes\mathrm{X})$.
∎

Figure 4: Reorganized RX-CX ansatz with linear entanglement by using
Proposition 3.1

######  Lemma A.2.

(Layer unitary of RX-CX ansatz with linear entanglement) Let
$U^{0}(\theta_{0})=\mathrm{RX}(\theta_{0})$. Then the unitary for the first
layer of $(k+1)$-qubit RX-CX ansatz with linear entanglement can be expressed
as:

$U^{k}(\bm{\theta}_{k})=\begin{pmatrix}C_{k}U^{k-1}(\bm{\theta}_{k-1})&-iS_{k}U^{k-1}(\bm{\theta}_{k-1})\\\
-iS_{k}U^{k-1}(\bm{\theta}_{k-1})X_{k-1}&C_{k}U^{k-1}(\bm{\theta}_{k-1})X_{k-1}\end{pmatrix}$
(1)

where $X_{k-1}=\begin{pmatrix}0&\mathrm{I}_{2^{k-1}}\\\
\mathrm{I}_{2^{k-1}}&0\end{pmatrix}$, $C_{k}=\cos(\frac{\theta_{k}}{2})$,
$S_{k}=\sin(\frac{\theta_{k}}{2})$,
$\bm{\theta}_{k}=(\theta_{k},\theta_{k-1},\cdots,0)$.
For simplicity, in the following, we denote $U^{k}(\bm{\theta}_{k+n*j})$ by
$U^{k}_{j}$.

###### Proof.

The first layer of $(k+1)$-qubit RX-CX ansatz with linear entanglement is
$(\mathrm{CX}(1,0)\cdots\mathrm{CX}(k-1,k))(\mathrm{RX}(\theta_{k})\otimes\mathrm{RX}(\theta_{k-1})\otimes\cdots\otimes\mathrm{RX}(\theta_{0}))$.
Since CX gate and RX gate will exchange on the target qubit, we can convert
the unitary to
$\mathrm{RX}({\theta_{0}})(\mathrm{CX}(1,0)\mathrm{RX}({\theta_{1}}))(\mathrm{CX}(2,1)\mathrm{RX}({\theta_{2}}))\cdots(\mathrm{CX}(k,k-1)\mathrm{RX}({\theta_{k}}))$,
as shown in Figure 4.

Let
$U^{k}(\bm{\theta}_{k})=\mathrm{RX}({\theta_{0}})(\mathrm{CX}(1,0)\mathrm{RX}({\theta_{1}}))(\mathrm{CX}(2,1)\mathrm{RX}({\theta_{2}}))\cdots(\mathrm{CX}(k,k-1)\mathrm{RX}({\theta_{k}}))$,
then we have $U^{k}(\bm{\theta}_{k})=\mathrm{I}\otimes
U^{k-1}(\bm{\theta}_{k-1})\mathrm{CX}(k,k-1)\mathrm{RX}({\theta_{k}})\otimes\mathrm{I}=\begin{pmatrix}U^{k-1}(\bm{\theta}_{k-1})&\bm{0}\\\
\bm{0}&U^{k-1}(\bm{\theta}_{k-1})\end{pmatrix}\begin{pmatrix}\mathrm{I}&\bm{0}\\\
\bm{0}&X_{k-1}\end{pmatrix}\begin{pmatrix}C_{k}\mathrm{I}&-iS_{k}\mathrm{I}\\\
-iS_{k}\mathrm{I}&C_{k}\mathrm{I}\end{pmatrix}=\begin{pmatrix}C_{k}U^{k-1}(\bm{\theta}_{k-1})&-iS_{k}U^{k-1}(\bm{\theta}_{k-1})\\\
-iS_{k}U^{k-1}(\bm{\theta}_{k-1})X_{k-1}&C_{k}U^{k-1}(\bm{\theta}_{k-1})X_{k-1}\end{pmatrix}$.
∎

######  Lemma A.3.

For $n$-qubit RX-CX ansatz with linear entanglement, given vector
$\bm{b}\in\\{0,1\\}^{l}$, Let
$G^{k}(\bm{b})=(U^{k}_{l-1}X_{k}^{b_{l-1}})(U^{k}_{l-2}X_{k}^{b_{l-2}})\cdots(U^{k}_{0}X_{k}^{b_{0}})$.
Then,

$\forall k\geq
0,l=2^{\lceil\log_{2}(k+2)\rceil},\forall\bm{b}\in\\{0,1\\}^{l},G^{k}(\bm{b})=G^{k}(\bar{\bm{b}}),$

where $\bar{\bm{b}}=(1-b_{0},1-b_{1},\cdots)$.

###### Proof.

We prove that, $\forall k\in(2^{r}-2,2^{r+1}-2]$,
$G^{k}(\bm{b})=G^{k}(\bar{\bm{b}})$. Note that, $\forall
k\in(2^{r}-2,2^{r+1}-2]$, we have $2^{\lceil\log_{2}(k+2)\rceil}=2^{r+1}$.

It is easy to verify that
$G^{k}(\bm{b})=U^{k}_{l-1}(\theta_{k+n*(l-1)}+b_{l-1}*\pi,\theta_{k-1+n*(l-1)},\cdots)U^{k}_{l-2}(\theta_{k+n*(l-2)}+b_{l-2}*\pi,\theta_{k-1+n*(l-2)},\cdots)\cdots
U^{k}_{0}(\theta_{k}+b_{0}*\pi,\theta_{k-1},\cdots)$, i.e., the effect of
$U^{k}_{j}X_{k}$ is the same as adding a $\mathrm{X}$ gate just before
rotation gate $\mathrm{RX}(\theta_{k+j*n})$.

Example: We consider the case where $r=0$. In this case, $k=0$. Since
$U^{0}_{1}X_{0}U^{0}_{0}=\mathrm{RX}(\theta_{n})\,\mathrm{X}\,\mathrm{RX}(\theta_{0})=\mathrm{RX}(\theta_{n})\,\mathrm{RX}(\theta_{0})\,\mathrm{X}=U^{0}_{1}U^{0}_{0}X_{0}$;
$U^{0}_{1}X_{0}U^{0}_{0}=\mathrm{RX}(\theta_{n})\,\mathrm{X}\,\mathrm{RX}(\theta_{0})\,\mathrm{X}=\mathrm{RX}(\theta_{n})\,\mathrm{RX}(\theta_{0})=U^{0}_{1}U^{0}_{0}$.
Thus, this lemma holds when $r=0$.

$\forall r$, $l=2^{r+1}$, by Lemma A.1, we have
$U^{k}(\bm{\theta}_{k+n})X_{k}U^{k}(\bm{\theta}_{k})=U^{k}(\theta_{n+k}+\pi,\theta_{n+k-1},\cdots,\theta_{n})U^{k}(\bm{\theta}_{k})=U^{k}(\theta_{n+k}+\pi,\theta_{n+k-1},\cdots,\theta_{n})U^{k}(\bm{\theta}_{k})=U^{k}(\theta_{n+k},\theta_{n+k-1}+\pi,\cdots,\theta_{n})U^{k}(\theta_{k}+\pi,\theta_{k-1},\cdots,\theta_{0})$.
Then, by applying Lemma A.1 on every two layers, we can adjust gates on the
$k$-th qubit of $G^{k}(\bm{b})$ exact the same as those of
$G^{k}(\bar{\bm{b}})$.

However, we need to handle the extra $\mathrm{X}$ gate on the $k-1$-th qubit
after applying Lemma A.1.

We extend the notation $G^{k}(\bm{b})$ to
$G^{k}(\bm{b}^{k},\bm{b}^{k-1},\cdots)=U^{k}_{l-1}(\theta_{k+n*(l-1)}+b^{k}_{l-1}*\pi,\theta_{k-1+n*(l-1)}+b^{k-1}_{l-1}*\pi,\cdots)U^{k}_{l-2}(\theta_{k+n*(l-2)}+b^{k}_{l-2}*\pi,\theta_{k-1+n*(l-2)}+b^{k-1}_{l-2}*\pi,\cdots)\cdots$.
And we will omit the term $\bm{b}^{j}$ if $\bm{b}^{j}=0$. Thus,
$G^{k}(\bm{b}^{k})=G^{k}(\bm{b}^{k},\bm{0},\cdots,\bm{0})$. And, after
applying Lemma A.1 on every two layers, we have
$G^{k}(\bm{b}^{k})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{k-1})$, where
$\bm{b}^{k-1}=(b^{k-1}_{l-1},\cdots,b^{k-1}_{0})=(1,0,1,0,\cdots,1,0)$.

We refer to the operation of cancelling every two $\mathrm{X}$ gates
sequentially on the $i$-th qubit by Lemma A.3 and Proposition 3.1 as $P^{i}$.
After apply $P^{k-1}$ on $G^{k}(\bar{\bm{b}^{k}},\bm{b}^{k-1})$, we have
$\bm{b}^{k-1}=\bm{0}$, and
$\bm{b}^{k-2}=(1,1,0,0,1,1,0,0,\cdots)=p(\bm{b}^{k-1})$, here $p$ is the
function induced by $P^{i}$ and obviously, $p$ does not depend on $i$.

We assert if $k=2^{r}-1$, $l=2^{r+1}$,
$p^{k-1}((1,0,1,0,\cdots,1,0))=(1_{l-1},0,0,\cdots,0,1_{\frac{l}{2}-1},0,0,\cdots,0)$,
$p^{2k}=(1,0,\cdots,0)$. The proof is left in the Lemma A.4 below.

Then, if $k=2^{r}-1$, we have
$G^{k}(\bm{b}^{k})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{k-1})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{0})$,
where
$\bm{b}^{0}=p^{k-1}((1,0,1,0,\cdots,1,0))=(1_{l-1},0,0,\cdots,0,1_{\frac{l}{2}-1},0,0,\cdots,0)$.
Then, by applying Proposition 3.1, $\mathrm{X}$ gate can move on the 0-th
qubit, thus we have
$G^{k}(\bar{\bm{b}^{k}},\bm{b}^{0})=G^{k}(\bar{\bm{b}^{k}})$, i.e.,
$G^{k}(\bm{b}^{k})=G^{k}(\bar{\bm{b}^{k}})$.

If $2^{r}-1<k\leq 2^{r+1}-2$, likewise, we have
$G^{k}(\bm{b}^{k})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{k-1})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{0})$,
where $\bm{b}^{0}=p^{k-1}((1,0,1,0,\cdots,1,0))$. Once $i<2^{r+1}-2$, the
$p^{i}((1,0,1,0,\cdots,1,0))$ will have an even number of 1. Thus,
$\bm{b}^{0}$ must have even number of 1 in this case. Then, with Proposition
3.1, we have
$G^{k}(\bm{b}^{k})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{k-1})=G^{k}(\bar{\bm{b}^{k}},\bm{b}^{0})=G^{k}(\bar{\bm{b}^{k}})$
and Lemma A.3 is proved.

∎

######  Corollary A.1.

$\forall k\geq 0,\forall
t\in\mathbb{Z}_{+},l=2^{\lceil\log_{2}(k+2)\rceil},\forall\bm{b}\in\\{0,1\\}^{t*l},G^{k}(\bm{b})=G^{k}(\bar{\bm{b}}).$

###### Proof.

Just divide $\bm{b}$ into $\bm{b}_{1},\cdots\bm{b}_{t}$, then
$G^{k}(\bm{b})=G^{k}(\bm{b}_{t})G^{k}(\bm{b}_{t-1})\cdots
G^{k}(\bm{b}_{1})=G^{k}(\bar{\bm{b}}_{t})G^{k}(\bar{\bm{b}}_{t-1})\cdots
G^{k}(\bar{\bm{b}}_{1})=G^{k}(\bar{\bm{b}})$. ∎

######  Corollary A.2.

(Translation invariance) For
$G^{k}_{i}(\bm{b})=(U^{k}_{l-1+i}X_{k}^{b_{l-1}})(U^{k}_{l-2+i}X_{k}^{b_{l-2}})\cdots(U^{k}_{i}X_{k}^{b_{0}})$,
we still have

$\forall k\geq
0,l=2^{\lceil\log_{2}(k+2)\rceil},\forall\bm{b}\in\\{0,1\\}^{l},G^{k}_{i}(\bm{b})=G^{k}_{i}(\bar{\bm{b}}),$

###### Proof.

$G^{k}_{i}(\bm{b})$ is actually the translation of $G^{k}(\bm{b})$ with $i$
layers shifted. Then this lemma holds because of the translation invariance of
RX-CX ansatz. ∎

######  Lemma A.4.

Let $p$ denote the function induced by the operation of cancelling every two
$\mathrm{X}$ gates sequentially on one qubit by Lemma A.3 and Proposition 3.1.
For $k=2^{r}-1$ and $l=2^{r+1}$,
$p^{k-1}((1,0,1,0,\cdots,1,0))=(1_{l-1},0,0,\cdots,0,1_{\frac{l}{2}-1},0,0,\cdots,0)$,
$p^{2k}((1,0,1,0,\cdots,1,0))=(1,0,\cdots,0)$.

###### Proof.

We prove it by induction.

For $r=1$, i.e., $k=1$. Look at the following sequences:
$p^{0}=\mathrm{id}$
$p((1,0,1,0))=(1,1,0,0)$
$p((1,1,0,0))=(1,0,0,0)$
Thus, this lemma holds when $r=1$. Another example:
$r=2$, i.e., $k=3$. Look at the following sequences:
$p((1,0,1,0,1,0,1,0))=(1,1,0,0,1,1,0,0)$
$p((1,1,0,0,1,1,0,0))=(1,0,0,0,1,0,0,0)$
$p((1,0,0,0,1,0,0,0))=(1,1,1,1,0,0,0,0)$
$p((1,1,1,1,0,0,0,0))=(1,0,1,0,0,0,0,0)$
$p((1,0,1,0,0,0,0,0))=(1,1,0,0,0,0,0,0)$
$p((1,1,0,0,0,0,0,0))=(1,0,0,0,0,0,0,0)$
Thus, this lemma holds when $r=2$.

Suppose this lemma holds for $r=t$. For $r=t+1$, we can divide $\bm{b}$ into
two halves $\bm{b}_{1}$ and $\bm{b}_{2}$. Then with the locality of $p$, we
have
$p^{k-1}(\bm{b})=p^{2^{t+1}-2}(\bm{b})=(p^{2^{t+1}-2}(\bm{b}_{1}),p^{2^{t+1}-2}(\bm{b}_{2}))$.
By induction hypothesis, we have $p^{2^{t+1}-2}(\bm{b}_{1})=(1,0,\cdots,0)$,
thus $p^{k-1}(\bm{b})=(1_{l-1},0,0,\cdots,0,1_{\frac{l}{2}-1},0,0,\cdots,0)$.

Further, $p^{k}(\bm{b})=(1_{l-1},\cdots,1_{\frac{l}{2}},0,\cdots,0)$,
$p^{k+1}(\bm{b})=(1,0,\cdots,0,1_{\frac{3l}{4}-1},0,\cdots,0_{\frac{l}{2}},0,\cdots,0)$.
Then, we again divide $p^{k+1}(\bm{b})$ into two halves $\bm{b}_{1}$ and
$\bm{b}_{2}$. Because $p(\bm{0})=\bm{0}$, thus,
$p^{2k}(\bm{b})=p^{k-1}(p^{k+1}(\bm{b}))=(p^{2^{t+1}-2}(\bm{b}_{1}),\bm{0})=((1,0,\cdots,0),(0,\cdots,0))=(1,0,\cdots,0)$.

Thus, this lemma holds for $r=t+1$.

Therefore, this lemma holds for any $r\geq 1$.

∎

######  Corollary A.3.

For $\bm{a}\in\\{0,1\\}^{l}$,
$p(\bm{0},\bm{a},\bm{0})=(\bm{0},p(\bm{a}),\bm{0})$.

###### Proof.

$p(\bm{0},\bm{a},\bm{0})=(p(\bm{0}),p(\bm{a}),p(\bm{0}))=(\bm{0},p(\bm{a}),\bm{0})$.

Thus the heading ‘0’s and tailing ‘0’s can be ignored. ∎

######  Lemma A.5.

For $n$-qubit RX-CX ansatz with linear entanglement, $\mathrm{CX}(i+1,i)$ will
not affect the parameter combination result on the $i$-th qubit.

###### Proof.

Consider the $i$-th and the $(i+1)$-th qubits in Figure 5. Suppose the state
of the $(i+1)$-th qubit is $\rho_{i+1}=p_{0}{|0\rangle_{i+1}\langle
0|}+p_{1}{|1\rangle_{i+1}\langle 1|}$, then, $\mathrm{CX}(i+1,i)$ on target
qubit $i$ is equivalent to single qubit gate $I$ with probability $p_{0}$ and
gate $X$ with probability $p_{1}$. Since both $I$ and $X$ gate can be combined
into RX gate as a parameter shifting, all $\mathrm{CX}(i+1,i)$ will not affect
the result of parameter combination on the $i$-th qubit. Therefore, we only
need to consider the effect from the $0$-th qubit to the $(i-1)$-th qubit. ∎

Figure 5: Illustration for parameter combination in an RX-CX ansatz with
linear entanglement

######  Lemma A.6.

An $n$-qubit RX-CX ansatz with linear entanglement, the parameters
$\theta_{1+n*j}$ (the parameter in the $j$-th RX gate on the 1st qubit) and
$\theta_{1+n*j+n*2^{\lceil\log_{2}2\rceil}}$ can be combined.

###### Proof.

Without loss of generality, we prove parameters $\theta_{1}$ and
$\theta_{1+n*2^{\lceil\log_{2}2\rceil}}$ can be combined.

From Equation (1) (in Lemma A.2), we have

$U_{1}=\begin{pmatrix}C_{1}U^{0}(\bm{\theta}_{0})&-iS_{1}U^{0}(\bm{\theta}_{0})\\\
-iS_{1}U^{0}(\bm{\theta}_{0})X_{0}&C_{k}U^{0}(\bm{\theta}_{0})X_{0}\end{pmatrix}$

.
Then, we have:

$U^{1}_{1+n}U^{1}_{1}=\begin{pmatrix}C_{1+n}C_{1}U^{0}_{n}U^{0}_{0}-S_{1+n}S_{1}U^{0}_{n}U^{0}_{0}X_{0}&-iC_{1+n}S_{1}U^{0}_{n}U^{0}_{0}-iS_{1+n}C_{1}U^{0}_{n}U^{0}_{0}X_{0}\\\
-iS_{1+n}C_{1}U^{0}_{n}X_{0}U_{0}^{0}-iC_{1+n}S_{1}U^{0}_{n}X_{0}U^{0}_{0}X_{0}&-S_{1+n}S_{1}U_{n}^{0}X_{0}U_{0}^{0}+C_{1+n}C_{1}U_{n}^{0}X_{0}U_{0}^{0}X_{0}\end{pmatrix}$

Without loss of generality, we show $\theta_{1}$ and $\theta_{1+2n}$ can be
combined by consider the first entry of
$U^{1}_{1+n*2^{1}}U^{1}_{1+n}U^{1}_{1}$:

$C_{1+2n}C_{1+n}C_{1}U^{0}_{2n}U^{0}_{n}U^{0}_{0}-S_{1+2n}C_{1+n}S_{1}U^{0}_{2n}U^{0}_{n}X_{0}U^{0}_{0}X_{0}-C_{1+2n}S_{1+n}S_{1}U^{0}_{2n}U^{0}_{n}U^{0}_{0}X_{0}-S_{1+2n}S_{1+n}C_{1}U^{0}_{2n}U^{0}_{n}X_{0}U_{0}^{0}$

For the first two terms, we have:

$C_{1+2n}C_{1+n}C_{1}U^{0}_{2n}U^{0}_{n}U^{0}_{0}-S_{1+2n}C_{1+n}S_{1}U^{0}_{2n}U^{0}_{n}X_{0}U^{0}_{0}X_{0}=C_{1+n}(C_{1+2n}C_{1}U^{0}_{2n}U^{0}_{n}U^{0}_{0}-S_{1+2n}S_{1}U^{0}_{2n}U^{0}_{n}X_{0}U^{0}_{0}X_{0})$

To combine $\theta_{1+2n}$ and $\theta_{1}$ into $\theta_{1+2n}+\theta_{1}$,
we only need to show $U^{0}_{n}X_{0}U^{0}_{n}X_{0}=U^{0}_{n}U^{0}_{0}$. This
can be shown by applying Lemma A.3 immediately.

We also have $U_{n}^{0}U_{0}^{0}X_{0}=U_{n}^{0}X_{0}U_{0}^{0}$ with Lemma A.3.
Thus the remaining two terms can be also combined, and parameter
$\theta_{1+2n}$ and $\theta_{1}$ will be combined into
$\theta_{1+2n}+\theta_{1}$.
Thus, $\theta_{1+2n}$ and $\theta_{1}$ can be combined into
$\theta_{1+2n}+\theta_{1}$ for the first entry of
$U^{1}_{1+n*2^{1}}U^{1}_{1+n}U^{1}_{1}$. The parameter combination for other
entries can be proved similarly.

∎

######  Lemma A.7.

For $n$-qubit RX-CX ansatz with linear entanglement, the two parameters
$\theta_{i+n*j}$ (the parameter in the $j$-th $\rm RX$ gate on the $i$-th
qubit) and $\theta_{i+n*j+n*2^{\lceil\log_{2}(i+1)\rceil}}$ on the $i$-th
qubit can be combined.

###### Proof.

With Lemma A.5, we only need to consider the effect from the 0-th qubit to the
$(i-1)$-th qubit when computing the parameter combination results on $i$-th
qubit.

We prove it by induction. For qubit $i=0$ of $n$-qubit ansatz, we already have
that $\theta_{i}$ and $\theta_{i+n*2^{\lceil\log_{2}(i+1)\rceil}}$ can be
combined by Proposition 3.1.

Assume that when $i=k-1$, the two parameters $\theta_{i+n*j}$ (the parameter
in the $j$-th $\rm RX$ gate on the $i$-th qubit) and
$\theta_{i+n*j+n*2^{\lceil\log_{2}(i+1)\rceil}}$ on the $i$-th qubit can be
combined.

So, for $i=k$, without loss of generality, we only prove that parameters
$\theta_{k}$ and $\theta_{k+n*2^{\lceil\log_{2}(k+1)\rceil}}$ can be combined.

From Lemma A.2, the unitary of the first layer is

$U^{k}(\bm{\theta}_{k})=\begin{pmatrix}C_{k}U^{k-1}(\bm{\theta}_{k-1})&-iS_{k}U^{k-1}(\bm{\theta}_{k-1})\\\
-iS_{k}U^{k-1}(\bm{\theta}_{k-1})X_{k-1}&C_{k}U^{k-1}(\bm{\theta}_{k-1})X_{k-1}\end{pmatrix}$
(2)

Then, consider the composition of the first $l=2^{\lceil\log_{2}(k+1)\rceil}$
layers: $\prod\limits_{i=0}^{l}U^{k}(\bm{\theta}_{n*i+k})$. For simplicity, in
the following, we denote $U^{k}(\bm{\theta}_{n*i+k})$ by $U^{k}_{n*i+k}$.
Without loss of generality, we still consider the (0, 0) entry of
$\prod\limits_{i=0}^{l}U^{k}(\bm{\theta}_{n*i+k})$. The (0, 0) entry is the
sum of many terms during the matrix multiplication. By induction (details are
left in Lemma A.8 below), we know every term of the (0, 0) entry of
$\prod\limits_{i=0}^{l}U^{k}(\bm{\theta}_{n*i+k})$ obeys the following
constraints:
(1) every term is of the form:
$\prod\limits_{i=0}^{l}T_{a_{i}}(\theta_{n*i+k})G_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})$,
where $a_{i}\in\\{0,1\\}$,
$T_{a_{i}}((\theta_{n*i+k}))=(C_{n*i+k})^{1-a_{i}}(-iS_{n*i+k})^{a_{i}}$;
$b_{i}\in\\{0,1\\}$,
$G_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})=(U^{k-1}(\bm{\theta}_{n*i+k-1})X_{k-1})^{b_{i}}(U^{k-1}(\bm{\theta}_{n*i+k-1}))^{1-b_{i}}$.
(2) For every term in the such entry, $\bm{b}=(b_{0},b_{1},\cdots,b_{l})$ is
decided by $\bm{a}=(a_{0},a_{1},\cdots,a_{l})$ by the following process:
$b_{0}=a_{0}$; $b_{i}=\text{XOR}(b_{i-1},a_{i})$ if $i\geq 1$. Thus, we can
represent a term by only using vector $\bm{a}$.

For simplicity, we define some operations on vector $\bm{a}$ or $\bm{b}$:
(1) Complement: $\bar{\bm{a}}=(1-a_{0},\cdots,1-a_{l})$.
(2) Length: $l(\bm{a})$ (or $l(\bm{b})$) refers the number of components in
vector $\bm{a}$ (resp. $\bm{b}$).
(3) Slicing: $\bm{a}(n:m)=(a_{n},a_{n+1},\cdots,a_{m})$.
(4) Indexing: $\bm{a}(i)=a_{i}$.
(5) Index set: $s(\bm{a})$ is the lowest index of vector $\bm{a}$, $u(\bm{a})$
is the highest index of $\bm{a}$.

We denote $\prod\limits_{i=s(\bm{a})}^{u(\bm{a})}$
$T_{a_{i}}(\theta_{n*i+k})G_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})$ by
$R(\bm{a})$; denote
$\prod\limits_{i=s(\bm{b})}^{u(\bm{b})}G_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})$
by $G(\bm{b})$.

Then, we show how terms in the (0, 0) entry combines. Consider a pair of terms
$R(\bm{a}_{1})$ and $R(\bm{a}_{2})$ where $\bm{a}_{1}(0)=1-\bm{a}_{2}(0)$,
$\bm{a}_{1}(l)=1-\bm{a}_{2}(l)$, and $\bm{a}_{1}(i)=\bm{a}_{2}(i)$, $\forall
i\in(0,l)$. We prove that if $R(\bm{a}_{1})$ is in the (0, 0) entry, then
$R(\bm{a}_{2})$ must be also in the (0, 0) entry.
Actually, if $\bm{a}_{1}(l)=0$, since
$\prod\limits_{i=0}^{l}U^{k}(\bm{\theta}_{n*i+k})=U^{k}(\bm{\theta}_{n*l+k})\prod\limits_{i=0}^{l-1}U^{k}(\bm{\theta}_{n*i+k})$,
$R(\bm{a}_{1}(0:l-1))$ must be in the (0,0) entry of
$\prod\limits_{i=0}^{l-1}U^{k}(\bm{\theta}_{n*i+k})$. From Lemma A.9 below, we
know that $R(\bm{a}_{2}(0:l-1))$ is in the (1,0) entry of
$\prod\limits_{i=0}^{l-1}U^{k}(\bm{\theta}_{n*i+k})$. Thus,
$R(\bm{a}_{2})=-iS_{n*l+k}U^{k-1}_{n*l+k-1}R(\bm{a}_{2}(0:l-1))$ is in the (0,
0) entry of $\prod\limits_{i=0}^{l}U^{k}(\bm{\theta}_{n*i+k})$. We can prove
the case $\bm{a}_{1}(l)=1$ similarly. Thus, if $R(\bm{a}_{1})$ is in the (0,
0) entry, then $R(\bm{a}_{2})$ must be also in the (0, 0) entry.
Then,
$R(\bm{a}_{1})+R(\bm{a}_{2})=T_{\bm{a}_{1}(0)}T_{\bm{a}_{1}(l)}\prod\limits_{i=1}^{l-1}T_{\bm{a}_{1}(i)}(\theta_{n*i+k})G(\bm{b}_{1})+T_{\bm{a}_{2}(0)}T_{\bm{a}_{2}(l)}\prod\limits_{i=1}^{l-1}T_{\bm{a}_{2}(i)}(\theta_{n*i+k})G(\bm{b}_{2})$.
Note that
$T_{\bm{a}_{1}(0)}(\theta_{k})T_{\bm{a}_{1}(l)}(\theta_{n*l+k})+T_{\bm{a}_{2}(0)}(\theta_{k})T_{\bm{a}_{2}(l)}(\theta_{n*l+k})=T_{s}(\theta_{k}+\theta_{n*l+k})$,
where $s=\min(\bm{a}_{1}(0)+\bm{a}_{1}(l),\bm{a}_{2}(0)+\bm{a}_{2}(l))$, then
once $G(\bm{b}_{1})=G(\bm{b}_{2})$, for $R(\bm{a}_{1})+R(\bm{a}_{2})$,
$\theta_{k}$ and $\theta_{n*l+k}$ can be combined into
$\theta_{k}+\theta_{n*l+k}$.

Actually, since $\bm{a}_{1}(0)$ and $\bm{a}_{2}(0)$ complements, we have
$\bm{b}_{1}(0:l-1)=\overline{\bm{b}_{2}(0:l-1)}$. Note that
$\bm{b}_{1}(l)=\bm{b}_{2}(l)$, we only need to consider
$G(\bm{b}_{1}(0,l-1))=G(\bm{b}_{2}(0,l-1))$.

Note that $l=2^{\lceil\log_{2}(k+1)\rceil}=2^{\lceil\log_{2}((k-1)+2)\rceil}$,
then with Lemma A.3 and Corollary A.1, we have
$G(\bm{b}_{1}(0:l-1))=G(\bm{b}_{2}(0:l-1))$. This means parameters
$\theta_{n*l+k}$ and $\theta_{k}$ can be combined in the (0, 0) entry. We can
prove this result on other entries similarly.
Therefore, the two parameters $\theta_{i+n*j}$ (the parameter in the $j$-th
$\rm RX$ gate on the $i$-th qubit) and
$\theta_{i+n*j+n*2^{\lceil\log_{2}(i+1)\rceil}}$ on the $i$-th qubit can be
combined. ∎

######  Lemma A.8.

$\forall r\geq 1$, every term of the (0, 0) or (1, 0) entry of
$\prod\limits_{i=0}^{r}U^{k}(\bm{\theta}_{n*i+k})$ obeys the following
constraints:
(1) Every term is of the form:
$\prod\limits_{i=0}^{r}T_{a_{i}}(\theta_{n*i+k})G_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})$,
where $a_{i}\in\\{0,1\\}$,
$T_{a_{i}}((\theta_{n*i+k}))=(C_{n*i+k})^{1-a_{i}}(-iS_{n*i+k})^{a_{i}}$;
$b_{i}\in\\{0,1\\}$,
$G_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})=(U^{k-1}(\bm{\theta}_{n*i+k-1})X_{k-1})^{b_{i}}(U^{k-1}(\bm{\theta}_{n*i+k-1}))^{1-b_{i}}$.
(2) For every term in such entry, $\bm{b}=(b_{0},b_{1},\cdots,b_{r})$ is
decided by $\bm{a}=(a_{0},a_{1},\cdots,a_{r})$ by the following process:
$b_{0}=a_{0}$; $b_{i}=\mathrm{XOR}(b_{i-1},a_{i})$ if $i\geq 1$. For
simplicity, we use $\bm{p}$ to represent this relation, i.e.,
$\bm{b}=\bm{p}(\bm{a})$. Thus, we can represent a term by using only vector
$\bm{a}$.

###### Proof.

The first conclusion of the lemma is obvious and we focus on the second one.
We can prove it by induction.

We first consider $r=1$. The (0, 0) entry is
$C_{k+n}C_{k}U^{k-1}_{n+k-1}U^{k-1}_{k-1}-S_{1+n}S_{1}U^{k-1}_{n+k-1}U^{k-1}_{k-1}X_{k-1}$,
the (1,0) entry is
$-iS_{k+n}C_{k}U^{k-1}_{n+k-1}X_{k-1}U^{k-1}_{k-1}-iC_{1+n}S_{1}U^{k-1}_{n+k-1}X_{k-1}U^{k-1}_{k-1}X_{k-1}$.
It is easy to verify that this lemma holds when $r=1$.

Then we assume this lemma holds when $r=t$.

Then for $r=t+1$, we have
$\prod\limits_{i=0}^{t+1}U^{k}(\bm{\theta}_{n*i+k})=U^{k}(\bm{\theta}_{n*(t+1)+k})\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})=\begin{pmatrix}C_{n*(t+1)+k}U^{k-1}_{n*(t+1)+k}&-iS_{n*(t+1)+k}U^{k-1}_{n*(t+1)+k}\\\
-iS_{n*(t+1)+k}U^{k-1}_{n*(t+1)+k}X_{k-1}&C_{n*(t+1)+k}U^{k-1}_{n*(t+1)+k}X_{k-1}\end{pmatrix}\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$.

Since
$\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})=U^{k}(\bm{\theta}_{n*t+k})\prod\limits_{i=0}^{t-1}U^{k}(\bm{\theta}_{n*i+k})$,
we know that for every term in the (0, 0) entry of
$\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$, we must have $b_{t}=0$
because
$G^{k-1}_{b_{t}}(\bm{\theta}_{n*t+k-1})=U^{k-1}(\bm{\theta}_{n*t+k-1})$.
Likewise, we know that for every term in the (1,0) entry of
$\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$, we must have $b_{t}=1$.

For every term in the (0, 0) entry of
$\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$, denote its $\bm{a}$-vector
by $\bm{a}_{t}$ and its $\bm{b}$-vector by $\bm{b}_{t}$. After multiplying
with $C_{n*(t+1)+k}U^{k-1}_{n*(t+1)+k}$, we have vector
$\bm{a}_{t+1}=(\bm{a}_{t},0)$, $\bm{b}_{t+1}=(\bm{b}_{t},0)$. Thus,
$\bm{b}_{t+1}(t+1)=0=\mathrm{XOR}(\bm{a}_{t+1}(t+1),\bm{b}_{t+1}(t))$. And
since we already know $\bm{b}_{t}=\bm{p}(\bm{a}_{t})$, we now have
$\bm{b}_{t+1}=\bm{p}(\bm{a}_{t+1})$. Likewise, for every term in the (1,0)
entry of $\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$, after multiplying
with $-iS_{n*(t+1)+k}U^{k-1}_{n*(t+1)+k}$, we have vector
$\bm{a}_{t+1}(t+1)=1$. Since $\bm{b}_{t+1}(t)=\bm{b}_{t}(t)=1$, we have
$\bm{b}_{t+1}(t+1)=0=\mathrm{XOR}(\bm{a}_{t+1}(t+1),\bm{b}_{t}(t)=1)$. Thus,
in this case, we still have $\bm{b}_{t+1}=\bm{p}(\bm{a}_{t+1})$. Combining
these two parts, we have terms in (0, 0) entry satisfies the two constraints.

Likewise, we can prove the lemma for (1,0) entry. ∎

######  Lemma A.9.

$\forall r\geq 1$, if
$R(\bm{a}_{1})=\prod\limits_{i=0}^{r}T_{\bm{a}_{1}(i)}(\theta_{n*i+k})G(\bm{b}_{1})$
is in the (0, 0) entry of $\prod\limits_{i=0}^{r}U^{k}(\bm{\theta}_{n*i+k})$,
then $R(\bm{a}_{2})$ must be in the (1, 0) entry, where
$\bm{a}_{2}(0)=1-\bm{a}_{2}(0)$, $\bm{a}_{2}(i)=\bm{a}_{1}(i)$, $\forall
i\in(0,r]$.

###### Proof.

We prove it by induction.
We first consider $r=1$. The (0, 0) entry is
$C_{k+n}C_{k}U^{k-1}_{n+k-1}U^{k-1}_{k-1}+(-iS_{1+n})(-iS_{1})U^{k-1}_{n+k-1}U^{k-1}_{k-1}X_{k-1}$,
the (1,0) entry is
$C_{1+n}(-iS_{1})U^{k-1}_{n+k-1}X_{k-1}+(-iS_{k+n})C_{k}U^{k-1}_{n+k-1}X_{k-1}U^{k-1}_{k-1}U^{k-1}_{k-1}X_{k-1}$.
It is easy to verify that this lemma holds when $r=1$.

Then we assume this lemma holds when $r=t$.
Then, for $r=t+1$, without loss of generality, we assume $\bm{a}_{1}(t+1)=0$.
If
$R(\bm{a}_{1})=\prod\limits_{i=0}^{t+1}T_{\bm{a}_{1}(i)}(\theta_{n*i+k})G(\bm{b}_{1})$
is in the (0, 0) entry of
$\prod\limits_{i=0}^{t+1}U^{k}(\bm{\theta}_{n*i+k})$, then
$R(\bm{a}_{1}(0:t))$ must be in the (0, 0) entry of
$\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$. Then, by inductive
hypothesis, we have $R(\bm{a}_{2}(0:t))$ must be in the (1, 0) entry of
$\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$. Since
$\prod\limits_{i=0}^{t+1}U^{k}(\bm{\theta}_{n*i+k})=U^{k}(\bm{\theta}_{n*(t+1)+k})\prod\limits_{i=0}^{t}U^{k}(\bm{\theta}_{n*i+k})$,
we have
$R(\bm{a}_{2})=C_{n*(t+1)+k}U^{k-1}(\bm{\theta}_{n*(t+1)+k-1})X_{k-1}R(\bm{a}_{2}(0:t))$
being in the (1, 0) entry. Thus this lemma holds when $r=t+1$.

To conclude, this lemma holds for any $r\geq 1$. ∎

Proposition 3.2. Suppose the number of effective parameters of an $n$-qubit
RX-CX ansatz with linear entanglement is $K$. We have the following
conclusion:

$\displaystyle K\leq\lfloor\frac{3n^{2}+1}{4}\rfloor$

###### Proof.

From Lemma A.8, there are at most $2^{\lceil\log_{2}(i+1)\rceil}$ effective
parameters on $i$-th qubit. Assume $2^{r}<n\leq 2^{r+1}$. Then the total
number of effective parameters of linear $n$-qubit RX-CX ansatz is at most

$f(n)=1+\sum_{i=1}^{r}(2^{t-1})2^{t}+(n-2^{r})*2^{r+1}=\frac{1}{3}-\frac{4^{r+1}}{3}+n*2^{r+1}$
(3)

For given $n$, for $r\in[\log_{2}n-1,\log_{2}n)$, the maximum value is
achieved when $2^{r+1}=\frac{3n}{2}$, i.e.,
$f(n)\leq\frac{3}{4}n^{2}+\frac{1}{3}$. Since $f(n)$ is integer, thus we have
$K=f(n)\leq\lfloor\frac{3n^{2}+1}{4}\rfloor$.

∎

###  A.2 Proposition 3.3 and Corollary 3.1: Order of the CX Gates

We can extend the result of Lemma A.3 to a more general case. Consider an
entanglement layer which is same as the linear entanglement layer except that
the order of CX gates may be different. We denote such entanglement layer as
modified linear entanglement layer. Then for any modified linear entanglement
layer, we always have $G^{k}(\bm{b})=G^{k}(\bar{\bm{b}})$.

######  Lemma A.10.

For $n$-qubit RX-CX ansatz with modified linear entanglement, and
$G^{k}(\bm{b})=(U^{k}_{l-1}X_{k}^{b_{l-1}})(U^{k}_{l-2}X_{k}^{b_{l-2}})\cdots(U^{k}_{0}X_{k}^{b_{0}})$
we still have

$\forall k\geq
0,l=2^{\lceil\log_{2}(k+2)\rceil},\forall\bm{b}\in\\{0,1\\}^{l},G^{k}(\bm{b})=G^{k}(\bar{\bm{b}}),$

where $U^{k}_{i}$ is the unitary of one layer from 0-th qubit to $k$-th qubit
with gates involved with other qubits ignored.

###### Proof.

Actually, we only need to consider the following two cases:
1\. $\mathrm{CX}(k,k-1)$ is before $\mathrm{CX}(k-1,k-2)$.

2\. $\mathrm{CX}(k,k-1)$ is after $\mathrm{CX}(k-1,k-2)$.

∎

For case 1, $p((1,1))=(1,0)$; for case 2, $p((1,1))=(0,1)$.

To avoid notation ambiguity, we refer the function induced by the operation of
cancelling every two $\mathrm{X}$ gates sequentially on case 1 (resp. case 2)
by Lemma A.3 and Proposition 3.1 as $p_{1}$ (resp. $p_{2}$).

Likewise, to show $G^{k}(\bm{b})=G^{k}(\bar{\bm{b}})$, we only need to show:
Proposition: for any vector $\bm{x}\in\\{0,1\\}^{l_{1}}$,
$p_{\bm{x}}=p_{x_{0}}\circ p_{x_{1}}\circ\cdots\circ p_{x_{l_{1}-1}}$,
$p_{\bm{x}}((1,0,1,0,\cdots,1,0))$ contains an odd number of $1$ if and only
if $l_{1}=l-2$ ($l$ is the length of input), and in that case,
$p_{\bm{x}}((1,0,1,0,\cdots,1,0))$ contains only one $1$.

Note that $(0,1,\cdots,0,1)$ can be transformed into $(1,0,\cdots,1,0)$ by
Corollary A.3 without changing the conclusion of this proposition. Thus, in
the proposition, we only consider initial vector $(1,0,\cdots,1,0)$.

We can prove the proposition by induction on $l=2^{r+1}$.

We first consider $r=1$. if $l_{1}<l-2=2$, then $l_{1}$ must be $0,1,2,3$.
If $l_{1}=0$, $p_{\bm{x}}=\mathrm{id}$, the proposition already holds. If
$l_{1}=1$, $p_{\bm{x}}$ only produces: $(1,1,0,0)$ and $(0,1,1,0)$, still
holds.
Thus this proposition holds when $r=1$.

Then we assume this proposition holds when $r=t>1$. Then, for $r=t+1$,
$l=2^{t+2}$, if $l_{1}\leq 2^{t+1}-2$, we can cut $(1,0,1,0,\cdots)_{l}$ into
two halves. Then
$p_{\bm{x}}((1,0,1,0,\cdots)_{l})=(p_{\bm{x}}((1,0,1,0,\cdots)_{l/2}),p_{\bm{x}}((1,0,1,0,\cdots)_{l}/2))$
must have even number of ‘1’.

Because for $l_{1}=2^{t+1}-2$, $p_{\bm{x}}((1,0,1,0,\cdots)_{l/2})$ has only
one 1, thus $p_{\bm{x}}((1,0,1,0,\cdots)_{l})$ have two ‘1’ with a distance
$\frac{l}{2}$.
Then, for $l_{1}=2^{t+1}-1$, no matter $x_{l_{1}-1}$ is 0 or 1,
$p_{\bm{x}}((1,0,1,0,\cdots)_{l})$ must contain $\frac{l}{2}$ consecutive ‘1’
and remaining elements is ‘0’. In this case, we still have even number of ‘0’.

Since for both $p_{0}$ and $p_{1}$, heading ‘0’s and tailing ‘0’s can be
ignored (Corollary A.3), thus, we can get vector
$(1,0,1,0,\cdots,1,0,1)_{\frac{l}{2}-1}$ after applying $p_{\bm{x}}$ when
$l_{1}=2^{t+1}$. In this case, we still have an even number of ‘0’.

By Corollary A.3, we can pad $(1,0,1,0,\cdots,1,0,1)_{\frac{l}{2}-1}$ to
$(1,0,1,0,\cdots,1,0,1,0)_{\frac{l}{2}}$ without affecting the proposition
here.

Then, by induction, we need $l_{2}=2^{t+1}-2$,
$\bm{x}_{2}\in\\{0,1\\}^{l_{2}}$, $p_{\bm{x}_{2}}$ to make
$(1,0,1,0,\cdots,1,0,1,0)_{\frac{l}{2}}$ become a vector with only one 1.

Thus, we need $l_{1}=2^{t+1}-2+2^{t+1}=2^{t+2}-2=l-2$ to let
$p_{\bm{x}}((1,0,1,0,\cdots,1,0))$ contain an odd number of ‘1’, i.e., this
proposition holds when $r=t+1$.

Thus, this proposition holds for any $r\geq 1$.

RX-CX ansatz with modified linear entanglement has the same parameter
combination result as the RX-CX ansatz with original linear entanglement,
i.e.,

Proposition 3.3 (CX order does not matter). An $n$-qubit RX-CX ansatz with
modified linear entanglement has at most $\lfloor\frac{3n^{2}+1}{4}\rfloor$
effective parameters. The modified linear entanglement has alternated CX order
compared with the original linear entanglement as shown in Figure 1 (b)(c).

###### Proof.

There are at most two types of form on $k$-th qubit:
$U^{k}(\bm{\theta}_{k})=U^{k-1}(\bm{\theta}_{k-1})\cdot\mathrm{CX}(k,k-1)\cdot\mathrm{RX}(\theta_{k})\otimes\mathrm{I}$
or $U^{k}(\bm{\theta}_{k})=\mathrm{CX}(k,k-1)\cdot
U^{k-1}(\bm{\theta}_{k-1})\cdot\mathrm{RX}(\theta_{k})\otimes\mathrm{I}$.
Since we have already proved the parameter combination of the first form, here
we will focus on the second one, i.e.

$\displaystyle
U^{k}(\bm{\theta}_{k})=\begin{pmatrix}C_{k}U^{k-1}(\bm{\theta}_{k-1})&-iS_{k}U^{k-1}(\bm{\theta}_{k-1})\\\
-iS_{k}X_{k-1}U^{k-1}(\bm{\theta}_{k-1})&C_{k}X_{k-1}U^{k-1}(\bm{\theta}_{k-1})\end{pmatrix}$
(4)

Likewise, we first prove the two parameters $\theta_{k+n*j}$ (the parameter in
the $j$-th $\rm RX$ gate on the $i$-th qubit) and
$\theta_{k+n*j+n*2^{\lceil\log_{2}(k+1)\rceil}}$ on the $k$-th qubit can be
combined.

We follow the notations in the proof of Lemma A.7.

With loss of generality, we only consider the (0, 0) entry. Let
$l=2^{\lceil\log_{2}(k+1)\rceil}$. In this proposition, each term of (0, 0)
entry is like
$\prod\limits_{i=0}^{l}T_{a_{i}}(\theta_{n*i+k})W_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})$,
where $a_{i}\in\\{0,1\\}$,
$T_{a_{i}}((\theta_{n*i+k}))=(C_{n*i+k})^{1-a_{i}}(-iS_{n*i+k})^{a_{i}}$;
$b_{i}\in\\{0,1\\}$,
$W_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})=(X_{k-1}U^{k-1}(\bm{\theta}_{n*i+k-1}))^{b_{i}}(U^{k-1}(\bm{\theta}_{n*i+k-1}))^{1-b_{i}}$.
Denote
$\prod\limits_{i=s(\bm{b})}^{u(\bm{b})}W_{b_{i}}^{k-1}(\bm{\theta}_{n*i+k-1})$
by $W(\bm{b})$.

Similar to the proof of Lemma A.7, to show parameter $\theta_{k}$ and
$\theta_{n*l+k}$ can be combined, we only need to prove:
$U^{k-1}(\bm{\theta}_{n*l+k-1})W(\bm{b}_{1}(0:l-1))=U^{k-1}(\bm{\theta}_{n*l+k-1})W(\overline{\bm{b}_{1}(0:l-1)})$.

We define $\bm{b}_{2}$ as follows:
(1) $\bm{b}_{2}(0)=0$.
(2) $\bm{b}_{2}(i+1)=\bm{b}_{1}(i)$, $\forall i\in(0,l)$.

Then, we have
$U^{k-1}(\bm{\theta}_{n*l+k-1})W(\bm{b}_{1}(0:l-1))=G(\bm{b}_{2}(1:l))U^{k-1}(\bm{\theta}_{k-1})$,
$U^{k-1}(\bm{\theta}_{n*l+k-1})W(\overline{\bm{b}_{1}(0:l-1)})=G(\overline{\bm{b}_{2}(1:l)})U^{k-1}(\bm{\theta}_{k-1})$.

Since $l=2^{\lceil\log_{2}(k+1)\rceil}=2^{\lceil\log_{2}((k-1)+2)\rceil}$,
with Lemma A.10, Corollary A.1 and Corollary A.2, we have
$U^{k-1}(\bm{\theta}_{n*l+k-1})W(\bm{b}_{1}(0:l-1))=G(\bm{b}_{2}(1:l))U^{k-1}(\bm{\theta}_{k-1})=G(\overline{\bm{b}_{2}(1:l)})U^{k-1}(\bm{\theta}_{k-1})=U^{k-1}(\bm{\theta}_{n*l+k-1})W(\overline{\bm{b}_{1}(0:l-1)})$.

Therefore, the two parameters $\theta_{i+n*j}$ (the parameter in the $j$-th
$\rm RX$ gate on the $i$-th qubit) and
$\theta_{i+n*j+n*2^{\lceil\log_{2}(i+1)\rceil}}$ on the $i$-th qubit can be
combined. This means that we have at most $2^{\lceil\log_{2}(i+1)\rceil}$
effective parameters on $i$-th qubit.

Similar to Proposition 3.2, we have that $n$-qubit RX-CX ansatz with modified
linear entanglement has at most $\lfloor\frac{3n^{2}+1}{4}\rfloor$ effective
parameters.

∎

Figure 6: RX-CX ansatz with alternating entanglement

Corollary 3.1. A $(2L)$-layer RX-CX ansatz with alternating entanglement can
be reduced to an $L$-layer RX-CX ansatz with linear entanglement.

###### Proof.

X-rule can directly exchange RX and CX on target qubit.

As shown in Figure 6, by applying the X-rule repeatedly, we can combine
$\theta_{n+i+2k}$ to $\theta_{i+2k}$, $\theta_{n+i+2k+1}$ to
$\theta_{2n+i+2k+1}$, … Then within finite steps, the RX gate between
alternating entanglement layers will be all eliminated, and we get an
entanglement layer that is same as linear entanglement, regardless of the
order of CX.

∎

###  A.3 Proposition 3.4 and Proposition 3.5: More CX Gates in the
Entanglement Layer

Proposition 3.4 (Repetition of entanglement layer). For any entanglement layer
that is purely constructed by CX gates, there exists an integer $k$, s.t.
$E^{k}=I$ where $E$ is the unitary transformation represented by the
entanglement layer and $I$ is the identity operator.

###### Proof.

Because $E$ is just a special permutation matrix, and the number of
$2^{n}$-dimensional permutation matrix is limited. Thus
$\\{E,E^{2},E^{3}\cdots,\\}$ is a cyclic group, i.e., there would be some $k$,
s.t. $E^{k}=I$. ∎

Proposition 3.5 (Limitation of CX-based entanglement layer). For a given
$n$-qubit unitary transformation $U$, $\forall i,j\geq 2$, it is possible to
move $i$-th column of $U$ to $j$-th column of $U$ with a finite number of CXs,
but it is not possible to achieve column swap between two arbitrary columns
when $n\geq 3$.

###### Proof.

Consider the form: $U\cdot E$, where $E$ is the combination of CX gates. We
first prove that we can move second column to another other column except the
first column. We prove it by induction.

When qubit number $n=2$. First consider moving column $2\to 3$. We can do it
by using $E=\text{CX}(0,1)\text{CX}(1,0)$. To move column $2\to 4$, we can do
it by using $E=\text{CX}(0,1)$.

Assume this proposition holds for $n=k$. Then for $n=k+1$, if we want to move
column $2\to i$, $i<2^{k}$, then by hypothesis, we can find $E$ to do it
(ignoring the $k$-th qubit). If we want to move column $2\to i$, where
$i>2^{k}$, then we first apply $CX(0,k)$, then second column will move to the
$2^{k}+1$ column. Then, by induction hypothesis, we can move $2^{k}+1$ column
to any $2^{k}+j$ columns where $j\geq 1$.
Finally we need to show how to move column 2 to column $2^{k}$. We can do it
with only two CX gates: $\text{CX}(0,k)\text{CX}(k,0)$.
Thus this proposition holds for $n=k+1$.

To prove CXs cannot implement arbitrary column swap, we just need to give a
counterexample. Suppose we only want to swap the $(2^{n-1}+1)$-th column and
the $(2^{n-1}+2)$-th column. If $n\geq 3$, this example swap is actually a
controlled-swap operation which cannot be synthesized solely by CX gates. ∎

###  A.4 Theorem 3.1: Effectiveness of RX-RZ-CX ansatz

Now, we will discuss the effectiveness of RX-RZ-CX ansatz together with
several similar ansatzes.

Theorem 3.1 (Efficiency of RX-RZ-CX ansatz with alternating entanglement). For
an $n$-qubit $2L$-layer RX-RZ-CX ansatz with alternating entanglement, the
numbers of effective parameters (w.r.t parameter combination) $w_{xz}$
satisfies $w_{xz}\geq(4n-3)*L$.

###### Proof.

Firstly, we consider the parameter combination of RX-RZ-CX ansatz with linear
entanglement. We first consider the parameter combination of RX gates. In the
RX-RZ-CX ansatz, we make the angles of RZ gate $\lambda_{i}=\frac{\pi}{2}$.
Then, we have
$\mathrm{RX}(\theta_{i})\mathrm{RZ}(\frac{\pi}{2})=\frac{\sqrt{2}}{2}\mathrm{RX}(\theta_{i})+\frac{\sqrt{2}}{2}\mathrm{RX}(\theta_{i})\mathrm{RZ}(\pi)=\frac{\sqrt{2}}{2}\mathrm{RX}(\theta_{i})+\frac{\sqrt{2}}{2}\mathrm{RZ}(\pi)\mathrm{RX}(-\theta_{i})$.
In this case, $\forall i,j$, $\theta_{i}$ and $\theta_{j}$ cannot be combined
because $\theta_{i}+\theta_{j}$ and $\theta_{i}-\theta_{j}$ will
simultaneously appear in the resulted unitary matrix. Similarly, we have
$\mathrm{RX}(\frac{\pi}{2})\mathrm{RZ}(\lambda_{i})=\frac{\sqrt{2}}{2}\mathrm{RZ}(\lambda_{i})+\frac{\sqrt{2}}{2}\mathrm{RX}(\pi)\mathrm{RZ}(\lambda_{i})=\frac{\sqrt{2}}{2}\mathrm{RZ}(\lambda_{i})+\frac{\sqrt{2}}{2}\mathrm{RZ}(-\lambda_{i})\mathrm{RX}(\pi)$.
Thus, by making angles of RX gate $\theta_{i}=\frac{\pi}{2}$, $\forall i,j$,
$\lambda_{i}$ and $\lambda_{j}$ cannot be combined because
$\lambda_{i}+\lambda_{j}$ and $\lambda_{i}-\lambda_{j}$ will simultaneously
appear in the resulted unitary matrix. Thus, there is not parameter
combination in RX-RZ-CX ansatz with linear entanglement.

For RX-RZ-CX ansatz with alternating entanglement, the parameter combination
only happens on qubits without CX gates that single qubit gates can be
combined into one u3 gate (generic single qubit rotation). As shown in Figure
2(c), for every 2 layers of RX-RZ-CX ansatz, at most 3 parameters are combined
on qubits without CX gates. Thus, for a 2L-layer RX-RZ-CX ansatz with
alternating entanglement, we have $w_{xz}\geq(4n-3)L$. ∎

Corollary 3.2. Theorem 3.1 can be generalized to other types of HEA such as
RY-CX, RX-RY-CX and RY-RZ-CX. The number of effective parameters of an
$n$-qubit $2L$-layer RY-CX, RX-RY-CX, or RY-RZ-CX ansatz with alternating
entanglement is $w_{y}\geq(n-1)*2L$, $w_{yz}\geq(4n-3)*L$, or
$w_{xy}\geq(4n-3)*L$, respectively.

###### Proof.

For RY-RZ-CX ansatz and RX-RY-CX ansatz, we can prove this proposition with
the same technique as in Theorem 3.1 by using the following equations:
$\mathrm{RY}(\frac{\pi}{2})\mathrm{RZ}(\lambda_{i})=\frac{\sqrt{2}}{2}\mathrm{RZ}(\lambda_{i})+\frac{\sqrt{2}}{2}\mathrm{RY}(\pi)\mathrm{RZ}(\lambda_{i})=\frac{\sqrt{2}}{2}\mathrm{RZ}(\lambda_{i})+\frac{\sqrt{2}}{2}\mathrm{RZ}(-\lambda_{i})\mathrm{RY}(\pi)$,
$\mathrm{RY}(\beta_{i})\mathrm{RZ}(\frac{\pi}{2})=\frac{\sqrt{2}}{2}\mathrm{RY}(\beta_{i})+\frac{\sqrt{2}}{2}\mathrm{RY}(\beta_{i})\mathrm{RZ}(\pi)=\frac{\sqrt{2}}{2}\mathrm{RY}(\beta_{i})+\frac{\sqrt{2}}{2}\mathrm{RZ}(\pi)\mathrm{RY}(-\beta_{i})$,
$\mathrm{RX}(\frac{\pi}{2})\mathrm{RY}(\beta_{i})=\frac{\sqrt{2}}{2}\mathrm{RY}(\beta_{i})+\frac{\sqrt{2}}{2}\mathrm{RX}(\pi)\mathrm{RY}(\beta_{i})=\frac{\sqrt{2}}{2}\mathrm{RY}(\beta_{i})+\frac{\sqrt{2}}{2}\mathrm{RY}(-\beta_{i})\mathrm{RX}(\pi)$,
$\mathrm{RX}(\theta_{i})\mathrm{RY}(\frac{\pi}{2})=\frac{\sqrt{2}}{2}\mathrm{RX}(\theta_{i})+\frac{\sqrt{2}}{2}\mathrm{RX}(\theta_{i})\mathrm{RY}(\pi)=\frac{\sqrt{2}}{2}\mathrm{RX}(\theta_{i})+\frac{\sqrt{2}}{2}\mathrm{RY}(\pi)\mathrm{RX}(-\theta_{i})$.

For RY-CX ansatz, we prove it with the same technique as in Theorem 3.1 by
using the fact that
$\mathrm{RY}(\theta)=\mathrm{RX}(-\frac{\pi}{2})\mathrm{RZ}(\theta)\mathrm{RX}(\frac{\pi}{2})=\mathrm{RZ}(\frac{\pi}{2})\mathrm{RX}(\theta)\mathrm{RZ}(-\frac{\pi}{2})$.
∎