# Trainability and Expressivity of Hamming-Weight Preserving Quantum Circuits
for Machine Learning

Léo Monbroussou  Laboratoire d’Informatique de Paris 6, CNRS, Sorbonne
Université, 4 Place Jussieu, 75005 Paris, France  CEMIS, Direction Technique,
Naval Group, 83190 Ollioules, France  Jonas Landman  School of Informatics,
University of Edinburgh, 10 Crichton Street, Edinburgh, United Kingdom  QC
Ware, Palo Alto, USA and Paris, France  Alex B. Grilo  Laboratoire
d’Informatique de Paris 6, CNRS, Sorbonne Université, 4 Place Jussieu, 75005
Paris, France  Romain Kukla  CEMIS, Direction Technique, Naval Group, 83190
Ollioules, France  Elham Kashefi  Laboratoire d’Informatique de Paris 6, CNRS,
Sorbonne Université, 4 Place Jussieu, 75005 Paris, France  School of
Informatics, University of Edinburgh, 10 Crichton Street, Edinburgh, United
Kingdom

###### Abstract

Quantum machine learning has become a promising area for real world
applications of quantum computers, but near-term methods and their scalability
are still important research topics. In this context, we analyze the
trainability and controllability of specific Hamming weight preserving quantum
circuits. These circuits use gates that preserve subspaces of the Hilbert
space, spanned by basis states with fixed Hamming weight $k$. They are good
candidates for mimicking neural networks, by both loading classical data and
performing trainable layers. In this work, we first design and prove the
feasibility of new heuristic data loaders, performing quantum amplitude
encoding of $\binom{n}{k}$-dimensional vectors by training a n-qubit quantum
circuit. Then, we analyze more generally the trainability of Hamming weight
preserving circuits, and show that the variance of their gradients is bounded
according to the size of the preserved subspace. This proves the conditions of
existence of Barren Plateaus for these circuits, and highlights a setting
where a recent conjecture on the link between controllability and trainability
of variational quantum circuits does not apply.

##  I Introduction

Variational quantum circuits (VQCs) are promising candidates for near term
quantum computing Cerezo  _et al._ (2020a), but existing and near-term quantum
devices still offer limited resources to implement important tasks for quantum
machine learning (QML), such as encoding and training. Considering fault-
tolerant quantum computation, more advanced QML algorithms that present
potential to achieve a quantum advantage exist. The key step of some of these
“quantum linear algebra” algorithms Harrow  _et al._ (2008); Kerenidis and
Landman (2020); Lloyd  _et al._ (2013) is amplitude encoding, where the input
vector’s components become the quantum amplitudes of the input state in the
computational basis. Amplitude encoding on the entire Hilbert space is
unlikely to be achieved in the near term, and recent work proposed to use
amplitude encoding in small subspaces Johri  _et al._ (2020); Landman  _et
al._ (2022a); Cherrat  _et al._ (2022). In other methods for variational QML,
the data encoding is done by putting directly the vector component as the gate
parameters, which leads to some limitations Schuld  _et al._ (2020); Landman
_et al._ (2022b).

In this work, we propose a method to achieve the amplitude encoding of any
$\binom{n}{k}$-dimensional vector using $n$ qubits by training a VQC made of
Hamming weight (HW) preserving gates. In recent work Johri  _et al._ (2020), a
$n$-qubit quantum data loader using HW preserving gates was presented to
encode any $n$-dimensional vector using a VQC, but without training. HW
preserving quantum circuits allow one to restrict the state created to a
superposition of states of the same HW as the input, i.e., to maintain the
number of qubits in state $\ket{1}$ at the same time. Such subspace invariant
quantum circuits can tackle an important scaling problem with QML methods
called Barren Plateaus (BP) McClean  _et al._ (2018). It has been recently
shown that one can avoid BP while using input data on an invariant subspace of
low dimension under certain conditions on their controllability and
expressivity Larocca  _et al._ (2021a). However, knowing if HW preserving VQCs
are prone to BP without those assumptions is still an open question that we
tackle in this work.

One of our main results can be informally stated as follows: for a $n$-qubit
circuit made of specific HW preserving gates (RBS and FBS), in the subspace
spanned by Hamming weight $k$, the gradient of the cost function vanishes as
$O(1/\binom{n}{k})$. This is neither exponentially decreasing with $n$ (Barren
Plateau), nor quadractically decreasing as one could have expected for the FBS
case, despite its lower controllability.

Figure 1: Representation of a Hamming weight preserving quantum circuit for
Quantum Machine Learning purposes: (1) is the encoding part trained to
represent the classical input, and (2) is the trainable layer or quantum
neural network. The gates represented with B and S signs are RBS.

We first develop in Section II a framework to design a quantum data loader on
any invariant subspace of dimension $\binom{n}{k}$, with a $n$-qubit circuit
and $k$ the chosen HW (see Fig. 1). In addition, we propose a study of the
trainability for HW preserving VQCs in Section III (this concerns both blocks
in Fig. 1). We show that one could avoid BP using HW preserving gates
according to the choice of the subspace used for the encoding without any
hypothesis on the controllability or expressivity of the VQC.

### Related work

The preservation of the HW is a symmetry that we use in this work in order to
propose encoding and trainable layers with theoretical guarantees on their
trainability. Quantum machine learning models that present symmetries have
been proposed as potential more efficiently trainable than common models
Larocca  _et al._ (2022); Meyer  _et al._ (2022); Cohen and Welling (2016);
You  _et al._ (2022); Anschuetz and Kiani (2022). More recently, problem-
inspired ansatz have been study using tools from quantum optimal control to
highlight a link between the dimension of their corresponding dynamical Lie
algebra and their trainability Larocca  _et al._ (2021a) using a certain set
of hypothesis. One main conjecture left open in Larocca  _et al._ (2021a)
concerned the link between trainability and controllability _in a subspace_.
Very recent works just prove that this conjecture applies to many commonly
used ansatzes Ragone  _et al._ (2023); Fontana  _et al._ (2023) such as the
Hamiltonian Variational Ansatz Wecker  _et al._ (2015), Quantum Alternating
Operator Ansatz Farhi  _et al._ (2014); Hadfield  _et al._ (2017), and many
equivariant quantum neural networks. However, in our work, we show that this
conjecture is not respected in the case of HW preserving ansatzes, which
received increasing attention Johri  _et al._ (2020); Landman  _et al._
(2022a); Cherrat  _et al._ (2022); Kerenidis and Prakash (2022). Our results
are consistent and independent of the two works recently released Ragone  _et
al._ (2023); Fontana  _et al._ (2023) as HW preserving ansatzes don’t respect
the assumptions these papers are relying on. One can notice that Fontana  _et
al._ (2023) studies the same ansatzes as we do (see their Appendix C), and
propose an upper-bound on their controlability in a specific setting. In
Section III, we give tighter theoretical guarantees on the trainability of
those ansatzes, using a different analytical proof. See Section V for
discussion.

##  II Space-efficient amplitude encoding.

We first define the Amplitude Encoding and HW preserving quantum data loaders.
Then we show how to achieve it efficiently using HW preserving gates and their
subspace preserving properties.

###  II.1 Hamming weight preserving quantum data loaders

Let us first define the Amplitude Encoding scheme and explain what are HW
preserving quantum data loaders.

######  Definition 1 (Amplitude Encoding).

A data loader is a parameterized $n$-qubit quantum circuit that, given a
classical vector $x=(x_{1},\dots,x_{d})\in\mathbb{R}^{d}$, prepares the
quantum state:

$\ket{x}=\frac{1}{||x||}\sum_{i=1}^{d}x_{i}\ket{e_{i}},$ (1)

where $\ket{e_{i}}$ are $n$-qubit orthogonal quantum states.

######  Definition 2 (Data Loader in a HW preserving subspace).

We define a n-qubit data loader in the subspace of HW $k$, the quantum circuit
that performs amplitude encoding on the basis:

$B_{k}^{n}=\left\\{\ket{e}\middle|e\in\\{0,1\\}^{n}\text{ and
}\text{HW}(e)=k\right\\}$ (2)

with $d_{k}=|B_{k}^{n}|=\binom{n}{k}$.

For example, when considering $n=3$ qubits and a HW $k=2$, the resulting basis
state is:

$B_{2}^{3}=\left\\{\ket{110},\ket{101},\ket{011}\right\\}$

One could use the Reconfigurable Beam Splitter (RBS) gate to perform such an
encoding. This HW preserving gate is easy to implement or native on many
quantum devices. Notice that our results hold for another HW preserving gate
named the Fermionic Beam Splitter (FBS) which was already used for QML
application in Kerenidis and Prakash (2022) but has less good properties in
term of controllability (see Section II.2 and Appendix C).

######  Definition 3 (Reconfigurable Beam Splitter gate).

The Reconfigurable Beam Splitter (RBS) gate is a 2-qubit gate that corresponds
to a $\theta$-planar rotation between the states $\ket{01}$ and $\ket{10}$:

$RBS(\theta)=e^{i\theta H_{RBS}}=\begin{pmatrix}1&0&0&0\\\
0&\cos(\theta)&\sin(\theta)&0\\\ 0&-\sin(\theta)&\cos(\theta)&0\\\ 0&0&0&1\\\
\end{pmatrix}$ (3)

with its corresponding Hamiltonian:

$H_{RBS}=\begin{pmatrix}0&0&0&0\\\ 0&0&-i&0\\\ 0&i&0&0\\\
0&0&0&0\end{pmatrix}$ (4)

######  Definition 4 (Fermionic Beam Splitter).

Let $i,j\in[n]$ be qubits and $S=s_{1}\dots s_{n}\in\\{0,1\\}^{n}$ a binary
word corresponding to a single state $\ket{S}$ with $n$ the total number of
qubits. Then the Fermionic Beam Splitter (FBS) acts on the qubits $i$ and $j$
as the following unitary:

$FBS_{i,j}(\theta)\ket{S}=\begin{pmatrix}1&0&0&0\\\
0&\cos(\theta)&(-1)^{f}\sin(\theta)&0\\\
0&(-1)^{f+1}\sin(\theta)&\cos(\theta)&0\\\ 0&0&0&1\\\ \end{pmatrix}$ (5)

with $f=f_{i,j,S}=\sum_{i<l<j}s_{l}$

The Hilbert space spanned by a subspace preserving VQC can be expressed as a
direct sum of invariant subspaces. By rearranging the order of the
computational basis, we can express the HW preserving VQC unitary as a block
matrix. Each block is an orthogonal matrix $W^{k}$ that corresponds to a
unitary in the subspace of states of a certain Hamming weight $k$.

Figure 2: Block representation of the HW preserving unitaries. $\tilde{W}$ is
the $2^{n}\times 2^{n}$ unitary corresponding to a n-qubit HW preserving
quantum circuit. Each block $k$ is the unitary matrix corresponding to the
preserved subspace of HW $k$, and the state basis $B_{k}^{n}$. Their size are
$d_{k}\times d_{k}$ where $d_{k}=\binom{n}{k}$.

We now explain our data loading scheme. First, we initialize the quantum state
to be $\ket{e_{s}}$, a single state of HW $k$. Then we split off this state
onto the states in $B_{k}^{n}$ using RBS. In Johri  _et al._ (2020), the
authors used a similar method on the unary basis $B_{1}^{n}$. Notice that
achieving an amplitude encoding with such a basis would allow us to encode
many more parameters, namely $\binom{n}{k}\gg n$, in an $n$ qubit state. To
design our quantum data loader, we need to ensure that any
$\binom{n}{k}$-dimensional real vector $x$ can be encoded, i.e., that there
exists a set of RBS gate parameters $\Theta=\\{\theta_{1},\dots,\theta_{D}\\}$
such that:

$W^{k}(\Theta)\ket{e_{s}}-\frac{1}{||x||}\sum_{i=1}^{\binom{n}{k}}x_{i}\ket{e_{i}}=0,$
(6)

Finding the corresponding set of variational parameters or proving their
existence is very hard when $k>1$, and we discuss how one can try to do it
efficiently in future work (see Appendix A). In this work, we focus on the
existence of a solution, and we find the solution by defining an equivalent
optimization problem that can be solved using a gradient descent based method.
Theoretical guarantees to solve the optimization problem easily are described
in Section III.

$\Theta^{\ast}=\arg\min_{\Theta}||\frac{1}{||x||}\sum_{i=1}^{\binom{n}{k}}x_{i}\ket{e_{i}}-W^{k}(\Theta)\ket{e_{s}}||_{2}^{2}$
(7)

Notice that the previous cost function does not induce a Barren Plateaus while
considering a global cost function Cerezo  _et al._ (2020b), as the Hilbert
space described by the state of HW $k$ is not exponentially large for small
choice of $k$. We confirm in Section III that a large choice of $k$ results in
the existence of Barren Plateaus.

Subspace preserving quantum circuits are easier to simulate in small subspaces
than random quantum circuits over the entire Hilbert space Anschuetz  _et al._
(2022). In the case of a HW preserving VQC, the speedup of using a quantum
computer grows with $k$. Classical simulability can be appreciate for the
encoding part when combined with a trainable layer that is hard to simulate.

###  II.2 Existence of Quantum Data Loader

Previously, we proposed the use of HW preserving ansatz such as a n-qubit RBS
based VQC to create a quantum data loader. This circuit will be trained to
perform the amplitude encoding of a $\binom{n}{k}$-dimensional vector with $k$
the chosen HW. In this Section, we give tools to study the existence of a
circuit that always presents a solution for our optimization problem given by
Eq. (7). More precisely, we show how to know if, given a qubit connectivity
and RBS gates, one can design a quantum data loader. If so, we give a method
to design the circuit in Section II.3.

We propose to use quantum optimal control tools to show that, according to the
circuit connectivity, we can prove the existence of a quantum data loader.
This method can be generalized to find quantum data loaders for any subspace
invariant ansatz. We first define an essential tool to study the
controllability of a quantum circuit in the unitary space.

######  Definition 5 (Dynamical Lie Algebra).

Let us consider that we have an Hamiltonian of the form:

$H=H_{0}+\sum_{k\geq 1}^{G}u_{k}(t)H_{k}$ (8)

where each $u_{k}$ is a real function that we can freely choose. We call
$\\{H_{k}\\}_{k\in\llbracket 0,G\rrbracket}$ the set of generators of our
quantum system. The Dynamical Lie algebra is defined as:

$\mathcal{L}=\text{span}\left<iH_{0},\dots,iH_{G}\right>_{\mathcal{L}}\subseteq\mathfrak{su}(d)$
(9)

with $\left<S\right>_{\mathcal{L}}$ the Lie closure, i.e., the set of all Lie
commutators between the elements in $S$.

In the case of RBS based quantum circuits, the generators are given by the
qubit connectivity as we restrict ourselves to the use of a unique 2-qubit
gate (see Fig. 4). We show in Appendix B how to compute the dimension of the
DLA. We can restrict this study of the DLA to a particular subspace of HW $k$.
Then, its dimension indicates the maximal number of coefficients we can
independently fix in $W^{k}$. As this matrix is orthogonal (see Appendix A),
the dimension of the DLA is upper bounded by $\frac{1}{2}d_{k}(d_{k}-1)$.

We can thus compute the DLA corresponding to our circuit 111Hamiltonians in
Fig. 4 do not commute, but the Lie Algebra generated by the sum of those
Hamiltonians is equal to the one given by the global Hamiltonian according to
the Baker-Campbell-Hausdorff formula. in the subspace of the chosen HW $k$.

Figure 3: Evolution of the dimension of the DLA in the subspace of HW
$k=\lfloor\frac{n}{2}\rfloor$ for: (1) the use of RBS gates; (2) the use of
FBS gates with nearest neighbors connectivity; (3) the use of FBS gates with
full connectivity. This plot highlights the difference of controllability
potential between RBS and FBS based quantum circuit. Figure 4: Hamiltonian
representation of a HW preserving VQC: (1) highlights the link between the
qubit connectivity and the generators of the circuit, and (2) represents our
quantum data loader. The bit flips used to prepare the initial state are
represented in green, and RBS are represented red.

If the dimension of the DLA in the subspace of HW $k$ is lower than $d_{k}-1$
(with $d_{k}=\binom{n}{k}$), we cannot control enough coefficients to achieve
the encoding described in Eq. (6). If the dimension is maximal (equal to
$\frac{1}{2}d_{k}(d_{k}-1)$), we can perfectly control $W^{k}$, and thus we
can design a loader. Between those two values, we cannot ensure the existence
of a loader using the DLA dimension as we may control at least $d_{k}-1$
coefficients but not those in the columns corresponding to $\ket{e_{s}}$. In
practice, one could choose to reduce the choice of $k$ to achieve the full
controllability of the subspace or could proceed with our method to find the
data loader given in Section II.3. Indeed, one can use the rank of the Quantum
Fisher Information matrix to ensure this sufficient controlability in the
state space (see Section II.3).

We know that having enough control to design a quantum data loader requires
considering a connected graph in order to reach any state in our encoding
basis. Therefore, the nearest neighbor’s connectivity is the worst as it has a
minimal number of edges, and full connectivity maximizes the dimension of the
DLA. The scaling of the DLA dimension according to a specific type of graph
needs to be tackled in future work, but Fig. 3 gives numerical evidence of
good scaling in terms of controllability for an RBS based quantum circuit.

We observe in the Fig. 3 that the evolution of the DLA dimension in the
nearest neighbors connectivity setting seems to follow the maximum
controllability of the first subspace, which is given by $\frac{1}{2}n(n-1)$.
The DLA dimension for the maximum connectivity seems to evolve according to
the upper bound given by the maximum controllability of a $d_{n/2}\times
d_{n/2}$ orthogonal matrix and equal to $\frac{1}{2}d_{n/2}(d_{n/2}-1)$ when
considering RBS gates. In the case of the FBS gates, we know that each block
$W^{k}$ is perfectly determined by the first one $W^{1}$ Kerenidis and Prakash
(2022) (see Appendix C). As a result, the dimension of the DLA of FBS based
quantum circuit is upper-bounded by $\frac{1}{2}n(n-1)$ as observed in the
previous figure. The limitation of the controllability of FBS gates is
reminded in Appendix C.

In this section we show that the DLA study gives us tools to know if we can
design a quantum data loader from a qubit connectivity and a specific quantum
gate.

###  II.3 Finding the quantum data loader

Using previous results, we know that if we have a quantum hardware such that
the DLA dimension is high enough, there exists a quantum data loader circuit.
A remaining question is how to design the quantum data loader from a given
subspace and the connectivity that induces the existence of such a circuit. In
this Section, we will present two algorithms to design the quantum data loader
based on the study of controllability in the state space.

A subspace preserving circuit’s ability to achieve amplitude encoding on one
of its preserved subspaces is equivalent to saying that this circuit perfectly
controls the state space created by its output. In particular, a RBS based VQC
can achieve amplitude encoding (see Definition 1) on the subspace of HW $k$ if
the output state can be any superposition of states in $B_{k}^{n}$. The state
space spanned by the output of the VQC is thus a sphere of dimension $d_{k}-1$
noted $S^{d_{k}-1}$ and illustrated in Fig. 5.

Figure 5: Representation of the unitary and output state spaces. The DLA is
the tangent space of the unitary space. The possible directions for the
evolution of the output state are given by the Quantum Fisher Information
Matrix eigenvectors.

Now we define an essential tool to study the controllability of a quantum
circuit in the state space.

######  Definition 6 (Quantum Fisher Information Matrix).

Let us consider an initial state $\ket{e_{s}}$ and $U(\Theta)$ the unitary
that represents a quantum circuit with
$\Theta=\\{\theta_{1},\dots,\theta_{D}\\}$ the set of variational parameters.
The Quantum Fisher Information Matrix (QFIM) is a $D\times D$ matrix defined
as:

$\begin{split}[\text{QFIM}_{s}(\Theta)]_{i,j}&=4\text{Re}[\innerproduct{\partial_{\theta_{i}}\psi_{s}(\Theta)}{\partial_{\theta_{j}}\psi_{s}(\Theta)}-\\\
&\innerproduct{\partial_{\theta_{i}}\psi_{s}(\Theta)}{\psi_{s}(\Theta)}\innerproduct{\psi_{s}(\Theta)}{\partial_{\theta_{j}}\psi_{s}(\Theta)}]\end{split}$
(10)

with $\ket{\psi_{s}(\Theta)}=U(\Theta)\ket{e_{s}}$

The maximal rank of the QFIM is a metric of controllability in the state space
Liu  _et al._ (2019), as it gives us the number of independent directions that
can be taken by the state when tuning the gate parameters $\Theta$. For our
encoding method in the subspace of HW $k$, the maximum rank is given by the
topology of the sphere $S^{d_{k}-1}$ :

$\max_{\Theta}\;\rank[QFIM_{s}(\Theta)]\leq d_{k}-1$ (11)

As in Haug  _et al._ (2021), we find numerical evidence (see Fig. 6) that:

$\forall\Theta\in[0,2\pi]^{D}\quad\rank[QFIM_{s}(\Theta)]=\max_{\Theta}\;\rank[QFIM_{s}(\Theta)]$
(12)

Figure 6: Evolution of the rank of the QFIM for a periodic structure ansatz
presented in (1). Each block is represented in (2), and the evolution of the
rank of the corresponding QFIM is given by (3). The derivation of the QFIM
rank is done in the largest subspace ($k=n/2=3$).

By property of the orthogonal group, we know that the unit sphere is a
homogeneous space of the action of the Lie Group that is described by our
encoding method. As a result, we can state the following lemma:

######  Lemma 1.

Let us consider the subspace of HW $k$ of our $n$-qubits encoding method. If
the rank of the QFIM in the subspace is maximal on one point:

$\exists\Theta\in[0,2\pi]^{D}\;|\;\rank[QFIM(\Theta)]=d_{k}-1$ (13)

Then:

$\forall\Theta\in[0,2\pi]^{D},\quad\rank[QFIM(\Theta)]=d_{k}-1$ (14)

Using the QFIM on a given subspace of HW $k$, we propose a first algorithm to
design a quantum data loader in this subspace from an initial state created
using bit-flips, and the possible generators $\mathcal{G}$ given by the qubit
connectivity and the RBS gate Hamiltonian. When the rank of the QFIM of a
quantum data loader circuit is equal to $d_{k}-1$, the state space is
$S^{d_{k}-1}$. It can therefore achieve any superposition of states from
$B_{k}^{n}$, i.e., achieve the amplitude encoding on the subspace of HW $k$.
The Algorithm 1 consists in adding RBS gates and measure the new rank of the
QFIM, until it achieves its maximal value, ensuring the data loader
capability.

Algorithm 1 to design a HW preserving quantum data loader

1:$\mathcal{G}$ the generators, $\ket{e_{s}}$ the initial state

2:circuit = $\emptyset$

3:while $(\max_{\Theta}\rank[QFIM(\text{circuit},\Theta)]<d_{k}-1)$ do

4: for $RBS\in\mathcal{G}$ do

5: $\text{circuit'}=\text{circuit}+RBS$

6: if
($\max_{\Theta^{\prime}}\rank[QFIM(\text{circuit'},\Theta^{\prime})]>\max_{\Theta}\rank[QFIM(\text{circuit},\Theta)]$)
then

7: $\text{circuit}=\text{circuit'}$

8:return circuit

Using the conjecture given by Eq.(12), we can only consider one point of the
state space to derive the maximum rank of the QFIM. To avoid this conjecture,
we propose the Algorithm 2, using overparametrization, a concept introduced in
Larocca  _et al._ (2021a):

######  Definition 7 (Overparametrization).

A VQC overparametrized if the number of parameters $D$ is such that the QFIM,
for all the states in the training set, simultaneously saturate their rank
$R_{s}$:

$\max_{D\geq D_{c},\Theta}\rank[QFIM_{s}(\Theta)]=R_{s}$ (15)

The authors showed that for a general type of periodic-structured VQCs, we
have:

$D_{c}\sim\dim(DLA)$ (16)

The quantum circuit that performs the full rank of the QFIM can be easily
completed using overparametrization according to Eq.(16). Using Theorem 1, we
know that we only need to derive the rank of the QFIM on a single point to
find its maximal value.

Algorithm 2 to design a HW preserving quantum data loader

1:circuit , flag = True

2:while flag do

3: flag = False

4: for $RBS\in\text{circuit}$ do

5: $\text{circuit'}=\text{circuit}-RBS$

6: if
($\max_{\Theta^{\prime}}\rank[QFIM(\text{circuit'},\Theta^{\prime})]=\max_{\Theta}\rank[QFIM(\text{circuit},\Theta)]$)
then

7: circuit, flag $=$ circuit’, True

8: break for

9:return circuit

The reason we can naively increase the rank of the QFIM to its maximal in
Algorithm 1 is because of the results from Larocca  _et al._ (2021a) on the
Theory of Overparametrization, reminded in Definition 7. In practice,
Algorithm 2 is initialized by considering a quantum circuit made of a high
number of gates according to the dimension of its DLA as explained in Eq.(16).
Those gates can be chosen randomly or in such a way to reduce the circuit
depth.

In practice and with both algorithms, one must pay particular attention to the
order of the generators that are tested in the algorithm with regard to the
circuit depth.

##  III Trainability of HW Preserving quantum circuits

In the previous Section, we discussed how to prove the existence of a quantum
data loader using RBS gates and how to design such an encoding circuit for a
specific subspace. In this Section, we show a study of the trainability of HW
preserving quantum circuits that could be used for our encoding but also for
other types of trainable layers, such as represented in Fig. 1. It is known
that some QML proposals suffer from negative optimization landscape properties
McClean  _et al._ (2018) that lead to strong limitation in their trainability.
In this Section, we will give strong results on the gradient of the cost
function for VQC made of RBS or FBS gates. First, we present in Section III.1
the backpropagation formalism applied to RBS and FBS based VQC. Then we
present the resulting theorems on the variance and expectation value of the
cost function gradient in Section III.2.

###  III.1 Backpropagation for gradient calculus

We describe a HW preserving quantum circuit only made of RBS gates. We
decompose the quantum circuit as a set of $\lambda_{max}$ gates. At each time
step $\lambda$, we call the inner layers $\zeta^{\lambda}$ the quantum states
in the circuit, and the inner errors
$\delta^{\lambda}=\partial\mathcal{C}/\partial\zeta^{\lambda}$ . We call
$w^{\lambda}$ the unitary in the considered basis $B_{k}^{n}$ for each RBS.
The cost function is $\mathcal{C}(\Theta)=||z-y||^{2}_{2}$ with $z$ the output
of the quantum circuit, and $y$ the desired output.

Figure 7: Decomposition of the HW preserving quantum circuit for the
backpropagation method.

The equivalent weight matrix of our VQC is $W^{k}=w^{\lambda_{max}}\dots
w^{1}w^{0}$. To train our circuit, we want to update each RBS parameter
$\theta_{i}$ with respect to the gradient of the cost function $\mathcal{C}$.
We derive the gradient by decomposing it using each component, indexed by the
integer $p$, of the inner layer and inner error vectors:

$\frac{\partial\mathcal{C}}{\partial\theta_{i}}=\sum_{p}\frac{\partial\mathcal{C}}{\partial\zeta_{p}^{\lambda+1}}\frac{\partial\zeta_{p}^{\lambda+1}}{\partial\theta_{i}}=\sum_{p}\delta_{p}^{\lambda+1}\frac{\partial(w_{p}^{\lambda}\cdot\zeta^{\lambda})}{\partial\theta_{i}}$
(17)

Each parameter $\theta_{i}$ corresponds to applying a $\theta_{i}$-planar
rotation between two qubits. We call $(l,j)$ the tuples of states affected by
the rotation. Using RBS gates, it comes to:

$\begin{split}\frac{\partial\mathcal{C}}{\partial\theta_{i}}=\sum_{(l,j)}&\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})+\\\
&\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})\end{split}$
(18)

One can decompose the same way a FBS based quantum circuit in a specific
subspace of a given HW:

$\begin{split}\frac{\partial\mathcal{C}}{\partial\theta_{i}}=\sum_{(l,j)}&\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+(-1)^{f(a,b,\zeta_{j}^{\lambda})}\cos(\theta_{i})\zeta_{j}^{\lambda})+\\\
&\delta_{j}^{\lambda}((-1)^{f(a,b,\zeta_{l}^{\lambda})+1}\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})\end{split}$
(19)

With $f(a,b,\zeta_{i}^{\lambda})=\sum_{a<p<b}s_{p}$ where $s\in\\{0,1\\}^{n}$
is the binary word corresponding to the state given by the index $i$:
$\ket{\zeta_{i}}=\ket{s_{1}\cdots s_{n}}$ ($a$ and $b$ are the qubits affected
by the FBS).

###  III.2 Avoiding Barren Plateaus

We can use the backpropagation analytic definition of the cost function
gradient to study the phenomenon of Barren Plateaus, where certain
circumstances lead to exponentially vanishing gradients.

######  Definition 8 (Barren Plateau).

The cost function $\mathcal{C}(\Theta)$ landscape of a n-qubit VQC is said to
exhibit a Barren Plateau (BP) if:

$\forall\theta_{i}\in\Theta,\quad\mathbb{E}_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=0\quad\text{and}\quad\mathbb{V}\text{ar}_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=O(\frac{1}{b^{n}})$
(20)

with $b>1$

It is possible to determine the existence of BP under the hypothesis of
approximate 2-design. This allows to derive the value of
$\mathbb{V}\text{ar}_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]$ using
the integration formulas from Puchala and Miszczak (2011). This results in an
expression of the variance inverse of the size of the Hilbert space. In recent
work Larocca  _et al._ (2021b), authors have shown under this hypothesis, and
the hypothesis of full controllability of the subspace (meaning that the
dimension of the DLA is maximal), that using a subspace invariant quantum
circuit the expression of the variance is inverse of the dimension of the
subspace. As a result, one could avoid BP using a subspace invariant quantum
circuit with a subspace of small dimension.

In the following, we will show that one could avoid BP for subspace invariant
quantum circuits based on RBS or FBS gates by choosing any subspace of HW $k$
with a fixed $k$ without considering the 2-design hypothesis and with any
controllability.

######  Theorem 1 (Evolution of the variance for RBS and FBS based quantum
circuits).

Let us consider a n-qubit HW preserving VQC made of RBS or FBS gates. We
consider here the subspace of HW $k$, i.e., corresponding to the basis
$B_{k}^{n}$. If the initial state and the wanted output are Haar distributed
on the basis $B_{k}^{n}$, we have that:

$\mathbb{E}_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=0\text{,}\quad\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]\approx\frac{k(n-k)}{n(n-1)}\frac{8}{d_{k}}$
(21)

for any $\theta_{i}\in\left\\{\theta_{1},\dots,\theta_{D}\right\\}$, and with
$d_{k}=\binom{n}{k}$.

The complete proof of this Theorem is presented in Appendix D. We use the
hypothesis that the input and the desired output of the RBS quantum circuit
are Haar distributed on the considered state basis. This hypothesis might not
be verified in all cases. In the encoding use case, we may consider a Haar
distributed wanted output but a single input state. In the case of a trainable
layer made of RBS or FBS gates (see Appendix IV.4) we may consider Haar
distributed input, but the desired output may be very concentrated. We
illustrate this result in Fig. 9 in the additional simulations given in
Appendix IV.

######  Theorem 2 (Evolution of the variance for RBS and FBS based quantum
data loader).

Let us consider a n-qubit HW preserving VQC made of RBS or FBS gate. We
consider here the subspace of HW $k$, i.e. corresponding to the basis
$B_{k}^{n}$. If the initial state is a single state $\ket{e_{s}}\in B_{k}^{n}$
and the wanted output is Haar distributed on the basis $B_{k}^{n}$, we have
that:

$\forall
i\geq\lambda_{0},\quad\mathbb{E}_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=0\text{,}\quad\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]\approx\frac{k(n-k)}{n(n-1)}\frac{8}{d_{k}}$
(22)

with $\lambda_{0}$ is such that from the gate with variational parameter
$\theta_{\lambda_{0}}$ every state in $B_{k}^{n}$ can be reached. We recall
that $d_{k}=\binom{n}{k}$.

The complete proof of this Theorem is presented in Appendix E. After a certain
number of gates $\lambda_{0}$, the expectation value is uniformly spread on
the basis states, which is very similar to the situation of Theorem 1. The
same Theorem could be stated for the case where the desired output is included
in a restricted number of states and the input is Haar distributed on the
basis $B_{k}^{n}$, corresponding to the use of a VQC in a subspace of HW $k$
as a neural network. We illustrate this result in Fig. 10 in the additional
simulations given in Appendix IV.

We can conclude from these results that there is no Barren Plateaus for the
subspace invariant RBS and FBS based quantum circuits for a fixed choice of
subspace $k$ according to the scaling of $d_{k}$, the dimension of the
subspace of HW $k$.

###  III.3 Complexity and simulation of subspace preserving RBS circuit

According to its better controllability properties, we focus on RBS gates. In
the subspace of HW $k$, the effect of a RBS gate is a rotation between $k$
couples of states in the basis $B_{k}^{n}$. Therefore, a RBS is easy to
simulate classically in the unary basis but requires an exponential number of
operations when $k$ is close to $n/2$ as $d_{n/2}$ grows exponentially with
$n$ the number of qubits. Nevertheless, using a greater subspace may be a
wrong choice according to the circuit depth. For example, achieving the full
controllability of a larger subspace requires a more significant amount of
gates but the number of qubits is limited. It results in a rise in the circuit
depth. In addition, using a greater subspace results in the apparition of BP,
as shown in III.

Algorithm | Feedforward | Training
---|---|---
Quantum RBS VQCs | $\mathcal{O}(D/(p*\delta^{2}))$ | $\mathcal{O}((D/p)^{2})$
Classical RBS VQCs | $\mathcal{O}(D\binom{n-2}{k-1})$ | $\mathcal{O}((D\binom{n-2}{k-1})^{2})$
Table 1: Running time summary. $n$ is the number of qubits, $k$ the chosen
Hamming weight corresponding to the selected subspace, and $\delta$ is the
error parameter in the quantum implementation. We call $p$ the average number
of gates we can parallelize at the same time (upper-bounded by
$\lfloor\frac{n}{2}\rfloor$).

However, the use of subspace preserving RBS quantum circuits is keen on giving
a speedup advantage for an application that requires to proceed a large amount
of information but with a limited number of degrees of freedom (and thus of
RBS gates). In Section IV.4, we give an example of such an application for a
fully connected orthogonal neural network that is not fully controllable.
Problem-inspired architectures using symmetries are perfect candidates for
this type of application.

##  IV Additional Simulations

In this section, we present additional simulations. We propose to illustrate
the use of Algorithm 1 for an existing hardware and the corresponding
simulations in Section IV.1. In Section IV.2, we propose additional
simulations to illustrate the results in Section III.

###  IV.1 Using our encoding method for an existing hardware

In this part, we propose to use the Algorithm 1 to design a 5-qubit quantum
data loader that fits the Rigetti ASPEN M2 connectivity given in Fig. 8. This
hardware is keen on implementing such a data loader thanks to its high
connectivity and to the fact that the RBS gate is native to this platform (and
called the XY gate).

Figure 8: Rigetti ASPEN M2 connectivity graph and the Quantum Data loader
quantum circuit obtained using our Algorithm 1.

Using the Algorithm 1, we can design a quantum data loader for this
connectivity. To minimize the depth, one can use in practice a variation of
this algorithm that minimizes the depth by testing in priority the gates that
are more likely to parallelize themselves. As a result, the circuit obtained
is given in Fig. 8.

In order to highlight the performance of our quantum data loader, we simulate
our method using python numpy but also using Qiskit, a quantum instruction
language developed as a python library by IBM. We test our data loader for a
well-known data set called the Fashion MNIST dataset.

Simulation tool used | Average Error | Error Variance
---|---|---
Numpy | 0.0097 | 0.00030
Qiskit | 0.0094 | 0.00028
Table 2: Performance of the quantum data loader presented in Fig. 8.

To achieve this simulation, we use our codes after applying a Principal
Component Analysis (PCA) to reduce our dataset to $\binom{n}{k}$-dimensional
vector, with $n=5$ the number of qubits, and $k=2$ the chosen HW. We used 1000
samples to derive those values.

The approximation error is measured using the following cost function between
the real state that we are supposed to have $x^{\ast}$ and the output of our
quantum system given by $x=W^{k}(\theta)\cdot e_{s}$ (with $e_{s}$ the vector
representation of the initial state in our method):

$\mathcal{C}(x)=||W^{k}(\Theta)\cdot e_{s}-x^{\ast}||_{2}^{2}$ (23)

For an actual implementation on a Quantum Processor Unit, one can generalize
the tomography procedure described in Landman  _et al._ (2022a).

###  IV.2 Trainability of Hamming weight preserving quantum circuits

In this part, we illustrate the results obtained from section III on the
trainability of RBS and FBS gate based quantum circuits in a specific subspace
corresponding of a choice of Hamming weight $k$.

In Fig. 9, we plot the average value and the variance of the gradient for
quantum circuits made only of RBS and FBS with a random choice of parameters,
input, and target output. This setting corresponds to the case of Theorem 1.
We observe that the average gradient is close to zero and its variance
corresponds to the theoretical values. In Theorem 1, the result is an average
for a Haar distributed inputs and the target outputs. In our simulation, we
choose to plot the study of the cost function while choosing randomly the
inputs, and the target outputs. To do so, we considered those states as
$\binom{n}{k}$-dimensional vectors with coefficients uniformly distributed in
$[-1,1]$, and we normalized them afterwards. As a result, the distribution of
the input and target states are not exactly Haar distributed.

Figure 9: Gradient study for the same Periodic Structure Ansatz as in Fig. 6.
Using $100$ random choices of input, wanted output, and parameters, we plot
the average value of the gradient for each number of periodic ansatz L in (1).
In (2), we plot the average gradient in the case where the RBS are replaced by
FBS. In (3), we derive the variance of the gradient for the RBS case, and in
(4), the variance for the FBS case. The dotted lines correspond to the
theoretical values from Theorem 1.

In the previous Figure, one can notice that the value of the variance of the
gradient is unchanged with the number of periodic ansatz $L$. As the number of
periodic ansatz increase, the number of gates increase but also the
controllability in the state space. Indeed, Fig. 6 shows the evolution of the
controllability in the state space by presenting the evolution of the QFIM
rank with $L$ (the maximal controllability is achieve with $L=4$). Therefore,
Fig. 9 highlights a in-dependency between the controllability in the state
space and the trainability.

In Fig. 10, we plot the average value and the variance of the gradient for
quantum circuits made only of RBS and FBS with a random choice of parameters
and target output. We fix the choice of the input state to be the initial
state where the $k$ first qubits are initialized in state $\ket{1}$. This
setting corresponds to the case of Theorem 2, very similar to the case of our
encoding described in Section II. This is the reason why the variance of the
gradient is null for some of the first gates that don’t affect the initial
state.

The theoretical variance values in this Theorem is stated for the parameters
corresponding to the gates after a certain rank $\lambda_{0}$. According to
the subspace choice $k$, the rank $\lambda_{0}$ represents the number of gates
necessary to reach any states in the state basis $B_{k}^{n}$. Therefore, we
can see in Fig. 10 that the first points for any subspace $k$ are quite far
from the theoretical values, but as the number of the gate increases, the
points get closer to our theoretical results.

Figure 10: Gradient study for a quantum circuit made of 5 consecutive block
circuits as described in Fig. 6. The plots are numerical evidences of Theorem
2 as the expectation values of the gradient are close to $0$ and the variances
follow the theoretical values given by the doted lines. The initial state is
fixed as a single state in $B_{k}^{n}$ for any subspace choice $k$. We use
$10000$ random target output and set of parameters.

###  IV.3 HW preserving VQC for Neural Networks

In our work, we introduce an encoding method using subspace invariant quantum
circuits with a focus on the HW preserving systems, the RBS, and the FBS
gates. In this particular setting, the capacity of classically simulate such a
circuit is not an issue as one may use our encoding method with an additional
circuit hard to classically simulate. However, the results given in section
III highlights the interest of using such circuit as neural networks. In
addition, the use of Hamming weigh preserving quantum circuits for machine
learning purposes has already been proposed in Johri  _et al._ (2020); Landman
_et al._ (2022a); Cherrat  _et al._ (2022); Kerenidis and Prakash (2022), and
we could generalize those methods for larger subspace with better speedups.

In this Section, we present how to use our results for Neural Networks. First,
we introduce in III.3 the complexity of a RBS based quantum circuit. Then we
present in IV.4 the use of a RBS based VQC for image classification for a toy
example.

###  IV.4 RBS based Quantum Orthogonal Neural Network

In this section, we illustrate the fact that we can use our results for
Quantum Neural Network (QNN) application. In particular, one can consider a
RBS circuit in a particular HW basis $B_{k}^{n}$ in order to design an
orthogonal neural network, as the equivalent unitary in the corresponding
Hilbert space $W^{k}(\Theta)$ is orthogonal according to Theorem 3. In Fig.
11, we plot the training and the testing accuracy for binary classification on
the Fashion MNIST dataset where we use the quantum circuit described in Fig. 8
as a QNN.

Figure 11: Binary classification on the Fashion MNIST data set for $10000$
training samples and $5000$ testing samples. The optimization method is ADAM
with a batch size of $5$, and we used is the Cross Entropy Cost.

We do not claim that this plot exhibits any advantage to use RBS based quantum
circuits as neural networks, but it illustrates that we can easily use such an
architecture. The fact that the testing accuracy is higher than the training
one v Large simulation for more complex HW preserving quantum neural networks
for large value of $k$ must be tackled in future work.

According to the complexity of such RBS models described in Table 1, there is
no exponential advantage in using a quantum orthogonal neural network. In
Landman  _et al._ (2022a), the authors present the use of a specific case of
such a RBS model in the unary basis and show a quadratic advantage for a fully
controllable QNN in the unary basis called the Pyramidal Quantum Neural
Network (PQNN). For specific use cases that require less controllability but
higher-dimensional input data, one can prefer to use a RBS based orthogonal
neural network in a larger Hamming weight basis and can achieve a more
significant speedup.

##  V Discussion

In this work, we study the controllability and the trainability of a subspace-
preserving variational quantum circuit through the prism of designing a
quantum data loader using RBS gates. We show that the encoding capacity is
linked with the controllability of the quantum system and that using only a
certain type of gates, the controllability is linked with the connectivity of
the hardware. In addition, we show how to study mathematical tools such as the
Dynamical Lie Algebra or the Quantum Fisher Information Matrix in order to
design a data loader. Finally, we show how to avoid Barren Plateaus for
variational quantum circuits only made of RBS or FBS gates.

The results we show for the trainability of Hamming weight preserving quantum
circuits must be compared with our results on the controllability. Indeed, it
is now clear that there is a trade-off between the expressivity of a
variational quantum circuit and its trainability. In recent work Larocca  _et
al._ (2021a), authors have shown the connection between the dimension of the
Dynamical Lie Algebra (DLA) and the gradient variance of subspace preserving
variational quantum circuit in the specific setting of the subspace full
controllability and with a 2-design hypothesis on the used ansatz. As a
result, they show that such gradient variance evolves in an inverse manner
with the dimension of the DLA. They also left open Conjecture 1. More
recently, Ragone  _et al._ (2023) and Fontana  _et al._ (2023) have shown that
this evolution is true in a more general setting and hence proved the
Conjecture 1 to be true, under some assumptions on the initial state and the
observable. In Fontana  _et al._ (2023), the authors also claim that RBS and
FBS based quantum circuits are not part of their framework and show a coherent
result to ours by given an upper-bound on the abstract variance of such
circuit. Our results are independent from those papers, and show theoretical
guarantees for RBS and FBS based VQC in a general setting.

######  Conjecture 1 (from Larocca  _et al._ (2021a)).

Let the state $\rho$ belong to a subspace $\mathcal{H}_{k}$ associated with a
subspace DLA $\mathfrak{g}_{k}$ (or sub-DLA, the subrepresentation in
$\mathfrak{g}$ where $\rho$ has support on). Then, the scaling of the cost
function partial derivative is inversely proportional to the scaling of the
dimension of the DLA, i.e.

$\mathbb{V}ar_{\Theta}[\partial_{\mu}\mathcal{C}(\Theta)]\in\mathcal{O}\left(\frac{1}{poly(\dim(\mathfrak{g}_{k}))}\right)$
(24)

In our work, we show that for the specific cases of RBS/FBS circuits and
preserved subspace based on Hamming weight, the cost gradient variance evolves
in an inverse manner with the dimension $d_{k}$ of the subspace, and not as
stated in Conjecture 1. In general, it is very hard to compute the expectation
value and the variance of a subspace preserving variational circuit gradient.
The use of the 2-design hypothesis gives tools to study the gradient Puchala
and Miszczak (2011) but is a huge hypothesis on the expressivity of the
quantum system that often leads to considering that the system is fully
controllable. In the specific case of RBS and FBS gates, the expressions of
those gates are easy to manipulate analytically, and we are able to prevent
the use of use hypothesis.

Although our work give theoretical guarantees on the trainability of a
specific type of VQC, we show that those methods could be useful for near term
QML. In addition, we would like to insist on the fact that one cannot state in
general that the trainability of a VQC is perfectly defined by its
controlability through the dimension of the corresponding DLA. First because
the dimension of the DLA is only an upper-bound on the controlability, but
also because we show an example of a VQC where the previous conjecture from
Larocca  _et al._ (2021a) is refuted. In our setting, only the dimension of
the subspace is involved in the scaling of the cost gradient variance.
Therefore, one needs to be careful to consider the smallest subspace possible.
For example, if you consider a RBS based quantum circuit but where some states
in $B_{k}^{n}$ cannot be reached, you may need to consider a new smaller
subspace more appropriate.

##  VI Acknowledgment

This work is also supported by the H2020-FETOPEN Grant PHOQUSING (GA no.:
899544), the Engineering and Physical Sciences Research Council (grants
EP/T001062/1), and the Naval Group Centre of Excellence for Information Human
factors and Signature Management (CEMIS). ABG is supported by ANR JCJC TCS-
NISQ ANR-22-CE47-0004, and by the PEPR integrated project EPiQ
ANR-22-PETQ-0007 part of Plan France 2030. This work is part of HQI initiative
(www.hqi.fr) and is supported by France 2030 under the French National
Research Agency award number ANR-22-PNCQ-0002.

## References

  * Cerezo  _et al._ (2020a) M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles,  (2020a), 10.1038/s42254-021-00348-9, arXiv:2012.09265 .
  * Harrow  _et al._ (2008) A. W. Harrow, A. Hassidim, and S. Lloyd,  (2008), 10.1103/PhysRevLett.103.150502, arXiv:0811.3171 .
  * Kerenidis and Landman (2020) I. Kerenidis and J. Landman,  (2020), 10.1103/PhysRevA.103.042415, arXiv:2007.00280 .
  * Lloyd  _et al._ (2013) S. Lloyd, M. Mohseni, and P. Rebentrost,  (2013), 10.1038/nphys3029, arXiv:1307.0401 .
  * Johri  _et al._ (2020) S. Johri, S. Debnath, A. Mocherla, A. Singh, A. Prakash, J. Kim, and I. Kerenidis, (2020), arXiv:2012.04145 .
  * Landman  _et al._ (2022a) J. Landman, N. Mathur, Y. Y. Li, M. Strahm, S. Kazdaghli, A. Prakash, and I. Kerenidis,  (2022a), 10.22331/q-2022-12-22-881, arXiv:2212.07389 .
  * Cherrat  _et al._ (2022) E. A. Cherrat, I. Kerenidis, N. Mathur, J. Landman, M. Strahm, and Y. Y. Li, (2022), arXiv:2209.08167 .
  * Schuld  _et al._ (2020) M. Schuld, R. Sweke, and J. J. Meyer,  (2020), 10.1103/PhysRevA.103.032430, arXiv:2008.08605 .
  * Landman  _et al._ (2022b) J. Landman, S. Thabet, C. Dalyac, H. Mhiri, and E. Kashefi, (2022b), arXiv:2210.13200 .
  * McClean  _et al._ (2018) J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven,  (2018), 10.1038/s41467-018-07090-4, arXiv:1803.11173 .
  * Larocca  _et al._ (2021a) M. Larocca, P. Czarnik, K. Sharma, G. Muraleedharan, P. J. Coles, and M. Cerezo,  (2021a), 10.22331/q-2022-09-29-824, arXiv:2105.14377 .
  * Larocca  _et al._ (2022) M. Larocca, F. Sauvage, F. M. Sbahi, G. Verdon, P. J. Coles, and M. Cerezo,  (2022), 10.1103/PRXQuantum.3.030341, arXiv:2205.02261 .
  * Meyer  _et al._ (2022) J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert,  (2022), 10.1103/PRXQuantum.4.010328, arXiv:2205.06217 .
  * Cohen and Welling (2016) T. S. Cohen and M. Welling, (2016), arXiv:1602.07576 .
  * You  _et al._ (2022) X. You, S. Chakrabarti, and X. Wu, “A convergence theory for over-parameterized variational quantum eigensolvers,” (2022), arXiv:2205.12481 .
  * Anschuetz and Kiani (2022) E. R. Anschuetz and B. T. Kiani,  (2022), 10.1038/s41467-022-35364-5, arXiv:2205.05786 .
  * Ragone  _et al._ (2023) M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. O. Marrero, M. Larocca, and M. Cerezo, “A unified theory of barren plateaus for deep parametrized quantum circuits,” (2023), arXiv:2309.09342 .
  * Fontana  _et al._ (2023) E. Fontana, D. Herman, S. Chakrabarti, N. Kumar, R. Yalovetzky, J. Heredge, S. H. Sureshbabu, and M. Pistoia, “The adjoint is all you need: Characterizing barren plateaus in quantum ansätze,” (2023), arXiv:2309.07902 .
  * Wecker  _et al._ (2015) D. Wecker, M. B. Hastings, and M. Troyer,  (2015), 10.1103/PhysRevA.92.042303, arXiv:1507.08969 .
  * Farhi  _et al._ (2014) E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” (2014), arXiv:1411.4028 .
  * Hadfield  _et al._ (2017) S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas,  (2017), 10.3390/a12020034, arXiv:1709.03489 .
  * Kerenidis and Prakash (2022) I. Kerenidis and A. Prakash, (2022), arXiv:2202.00054 .
  * Cerezo  _et al._ (2020b) M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles,  (2020b), 10.1038/s41467-021-21728-w, arXiv:2001.00550 .
  * Anschuetz  _et al._ (2022) E. R. Anschuetz, A. Bauer, B. T. Kiani, and S. Lloyd, (2022), arXiv:2211.16998 .
  * Liu  _et al._ (2019) J. Liu, H. Yuan, X.-M. Lu, and X. Wang,  (2019), 10.1088/1751-8121/ab5d4d, arXiv:1907.08037 .
  * Haug  _et al._ (2021) T. Haug, K. Bharti, and M. S. Kim,  (2021), 10.1103/PRXQuantum.2.040309, arXiv:2102.01659 .
  * Puchala and Miszczak (2011) Z. Puchala and J. A. Miszczak,  (2011), 10.1515/bpasts-2017-0003, arXiv:1109.4244 .
  * Larocca  _et al._ (2021b) M. Larocca, N. Ju, D. García-Martín, P. J. Coles, and M. Cerezo, (2021b), arXiv:2109.11676 .
  * Faugère  _et al._ (1993) J.-C. Faugère, P. Gianni, D. Lazard, and T. Mora, (1993).
  * Faugère  _et al._ (1999) J.-C. Faugère, M. S. E. Din, and P.-J. Spaenlehauer, (1999).
  * Schirmer  _et al._ (2000) S. G. Schirmer, H. Fu, and A. I. Solomon,  (2000), 10.1103/PhysRevA.63.063410, arXiv:quant-ph/0010031 .

##  Appendix A Properties of the RBS gate

In this section, we discuss the properties of the RBS gate. In particular, we
first show in A.1 that any RBS based quantum circuit can be expressed in the
subspace of states of HW $k$, i.e in the state basis $B_{k}^{n}$, as an
orthogonal matrix. Then, we study in A.2 the difficulty to find the good set
of variational parameters to perform the data loading as expressed in Eq.(6)

###  A.1 Orthogonality of RBS equivalent matrix

######  Theorem 3.

Let us consider $\tilde{W}(\Theta)=(\tilde{w}_{i,j}(\Theta))_{i,j\in[2^{n}]}$
the unitary matrix corresponding to a quantum circuit only made of RBS gates.
We call $W^{k}(\Theta)=(w_{i,j}(\Theta))_{i,j\in B_{k}^{n}}$ the
$\binom{n}{k}\times\binom{n}{k}$ equivalent matrix in the basis $B_{k}^{n}$.
The matrix $W^{k}(\Theta)$ is orthogonal.

Proof of Theorem 3:

We call $v_{i}\in\mathbb{R}^{\binom{n}{k}}$ the $i^{th}$ column of
$W^{k}(\Theta)$ and $\tilde{v}_{i}\in\mathbb{R}^{2^{n}}$ the $i^{th}$ column
of $\tilde{W}(\Theta)$. The orthonormality of $W^{k}(\Theta)$ is given by
property on the probability (from each state of the basis, the sum of the
probabilities to reach the other states is equal to one) and by property on
the unitaries:

$\forall i,\quad\innerproduct{v_{i}}{v_{i}}=1$ (25)

To show the orthogonality of the equivalent matrix $W^{k}(\Theta)$, we need to
consider the link between its unitary $\tilde{W}(\Theta)$:

$\forall(i,j)\in B_{k}^{n},\quad\tilde{w}_{i,j}(\Theta)=w_{i,j}(\Theta)$ (26)

By property on unitaries:

$\forall(i,j)\in B_{k}^{n}\;|\;i\neq
j,\quad\innerproduct{\tilde{v}_{i}}{\tilde{v}_{j}}=\sum_{l=0}^{2^{n}-1}\tilde{w}_{i,l}(\Theta)\tilde{w}_{l,j}(\Theta)=0$
(27)

RBS gates maintain the Hamming weight of the states:

$\forall i\in B_{k}^{n},\;\forall j\notin
B_{k}^{n},\quad\tilde{w}_{i,j}(\Theta)=0$ (28)

Thus,

$\forall(i,j)\in B_{k}^{n}\;|\;i\neq
j,\quad\innerproduct{\tilde{v}_{i}}{\tilde{v}_{j}}=\sum_{l\in
B_{k}^{n}}w_{i,l}(\Theta)w_{l,j}(\Theta)=0$ (29)

Finally,

$\forall(i,j)\in B_{k}^{n}\;|\;i\neq
j,\quad\innerproduct{v_{i}}{v_{j}}=0\quad\text{(orthogonality)}$ (30)

###  A.2 Quantum Data Loading equation

We expressed in Eq.(6) the equation that we need to solve to perform the
amplitude encoding of $x\in\mathbb{R}^{d_{k}}$ on the basis $B_{k}^{n}$ of
states of Hamming weight $k$. Notice that we express this problem in the
subspace of HW $k$, which means that we only consider on the states in
$B_{k}^{n}$. We can expressed this encoding equation as the following set of
equations (here, we suppose that the classical vector has been normalized):

$\begin{cases}w_{s,1}(\Theta)-x_{1}=0\\\ \dots\\\
w_{s,\binom{n}{k}}(\Theta)-x_{\binom{n}{k}}=0\end{cases}$ (31)

With $w_{i,j}$ the matrix coefficient from $W^{k}(\Theta)$ corresponding to
the amplitude to go from state $\ket{e_{j}}$ to $\ket{e_{i}}$.

In general, finding the solution (or proving the existence of one solution) of
a parametric set of non-linear equations is very hard. However, according to
the expression of the RBS gate (3), each coefficient $w_{i,j}(\Theta)$ is a
sum of product of cosines and sines of the variational parameters. Thus, using
the change of variables:

$\cos(\theta_{i})=c_{i}\quad\text{and}\quad\sin(\theta_{i})=s_{i}$ (32)

we can express the parametric set of nonlinear equations as a parametric set
of polynomial equations:

$\begin{cases}f_{1}(c_{1},\dots,c_{\binom{n}{k}},s_{1},\dots,s_{\binom{n}{k}})-x_{1}=0\\\
\dots\\\
f_{\binom{n}{k}}(c_{1},\dots,c_{\binom{n}{k}},s_{1},\dots,s_{\binom{n}{k}})-x_{\binom{n}{k}}=0\\\
c_{1}^{2}+s_{1}^{2}-1=0\\\ \dots\\\
c_{\binom{n}{k}}^{2}+s_{\binom{n}{k}}^{2}-1=0\end{cases}$ (33)

Several tools exist to solve such a polynomial system, for example, Gröbner
basis Faugère  _et al._ (1993, 1999), but they may come with a very high
computational cost. This is reason why we prefer focus on an equivalent
optimization problem as defined by Eq (7).

##  Appendix B Dynamical Lie Algebra derivation

In this section, we remind the main properties of the Dynamical Lie Algebra
(DLA). First, we give a more formal definition of the DLA. Then, we highlight
the link between the dimension of the DLA and the dimension of the unitary
equivalent manifold to show the link between the DLA and the degrees of
freedom introduce in Section II.2.

######  Definition 9 (Dynamical Lie Algebra).

Let us consider the question of controllability for the Schrödinger operator
equation in the general form:

$\dot{X}=-iH(u)X,\quad X(0)=\mathbb{1}_{d\times d}$ (34)

The Dynamical Lie algebra is defined as

$\mathcal{L}=span_{u\in\mathcal{U}}\\{-iH(u)\\}\subseteq\mathfrak{su}(d)$ (35)

The set of reachable states from system (34) is the connected Lie group
associated with the DLA and called Dynamical Lie Group:
$\mathcal{R}=e^{\mathcal{L}}$.

In general, the system is said controllable when
$\mathcal{L}=\mathfrak{su}(d)$ (we can achieve any equivalent unitary from the
system considered), which is in general equivalent to having
$\dim(\mathcal{L})=d^{2}-1$ with $d$ the dimension of the Hilbert space. It
tells us that we can choose each coefficient of the equivalent unitary if we
respect the condition that the corresponding matrix is unitary.

The Algorithm 3 Schirmer  _et al._ (2000) allows us to compute the rank of the
Lie Algebra generated by a control system. Basically, this algorithms derive
the dimension of the Lie Algebra by updating a matrix $W$ with potential
generators of the Lie Algebra as columns and derive the rank of this matrix
after every test to ensure that it increases the dimension of the spanned
space.

Algorithm 3 Rank of the Lie Algebra generated by a control system
$\\{\hat{H}_{0},\dots,\hat{H}_{M}\\}$.

1:$W=H_{0}$

2:$r=rank(W)$

3:for $m=1,2,\dots,M+1$ do

4: if $rank([W,H_{m}])>r$ then

5: append $W$ by column vector $H_{m}$

6: r = r + 1

7:$r_{0}=0$

8:$r_{n}=rank(W)$

9:while $r_{n}=r_{0}$ or $r=N^{2}$ do

10: for $l=r_{0}+1,\dots,r_{n}$ do

11: for $j=1,\dots,l-1$ do

12: $\hat{h}=[\hat{W}_{i,l},\hat{W}_{i,j}]$

13: if $rank([W,h])>r$ then

14: append $W$ by column vector $h$

15: $r=r+1$

16: $r_{0}=r_{n}$

17: $r_{n}=rank(W)$

18:return $r_{n}$

##  Appendix C Properties of the FBS gate

In this section, we remind some of the properties of FBS gates introduced in
Kerenidis and Prakash (2022) to show this gate limitation in term of
controllability.

According to Definition 4, the application of a FBS between the qubits $i$ and
$j$, $FBS_{i,j}$, acts as $RBS_{i,j}$ if the parity of the qubits ’between’
$i$ and $j$ is even, and is the conjugate gate $RBS_{i,j}(-\theta)$ otherwise.
The $FBS_{i,j}$ is a non local gate that can be implemented using an RBS gate
together with $\mathcal{O}(|i-j|)$ additional two qubit parity gates with a
circuit of depth $\mathcal{O}(log(|i-j|))$.

Althought similar to the RBS gate, the FBS is less controllable. As a HW
preserving gate, one can express the FBS gate as a block diagonal matrix (see
Fig. 2), where each block $W^{k}$ is an unitary that represents the action of
the FBS in the subspace of state of HW $k$. However, each block $W^{k}$ for
$k>1$ is perfectly determined by $W^{1}$ as it is the k-compound matrix of
$W^{1}$. Therefore, the controllability of the FBS unitary is upper-bounded by
the controllability of the first block that represents the effect of the gate
in the subspace of unitary states, i.e., states of HW 1. In the unitary basis,
the FBS is equivalent of the RBS gate. We can thus conclude that the maximal
dimension of the DLA for the FBS is $\frac{1}{2}n(n-1)$.

######  Definition 10 (Compound matrix).

Given a matrix $A\in\mathbb{R}^{n\times n}$, the compound matrix
$\mathcal{A}^{k}$ for $k\in[n]$ is the $\binom{n}{k}$ dimensional matrix with
entries $\mathcal{A}^{k}_{IJ}=det(A_{IJ})$ where $I$ and $J$ are subsets of
rows and columns of $A$ with size $k$.

The limitation in its controllability is illustrated in Fig. 3, and prevents
the use of FBS for amplitude encoding on a subspace of HW $k$ with $k>1$.
However, FBS can be used to perform Clifford loader, a loader determined on
the entire Hilbert space and restricted to the direct sum of subspace produce
by the FBS. In Kerenidis and Prakash (2022), algorithms for quantum
determinant sampling, singular value estimation for compound matrices, and for
Topological data analysis are presented using FBS gates and Clifford loader.

##  Appendix D Proof of Theorem 1

We recall the Theorem 1:

See 1

To prove this Theorem, we will first consider the unary case in Section D.1,
i.e., the case where the states are in $B^{1}_{n}$. In the unary case, RBS and
FBS are equivalent. Then, we will show how to extend our result to any HW $k$
for RBS in Section D.2. Finally, we will explain in Section D.3 how to adapt
this result to the FBS case.

###  D.1 Unary case

We consider the case of the quadratic cost function. We call $\Delta^{L}$ the
final error:

$\Delta^{L}=2(z^{L}-y)=2[(w^{\lambda_{max}}\cdots w^{\lambda+1})\cdot
w^{\lambda}\cdot\zeta^{\lambda}-y]$ (36)

We consider the case where for each inner layer, there is only one RBS gate
considered. The number of parameters $D$ is equal to the number of inner
layers $\lambda_{max}$. We call $\zeta_{j}$ the amplitude of the
$j^{\text{th}}$ state in the state basis considered of $\zeta$. For each inner
layer, the action of the gate in the state basis $B_{1}^{n}$ results in a
rotation of the amplitudes for two states that we call $(l,j)$:

$\zeta^{\lambda+1}=\overrightarrow{cst}+(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+\sin(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{l}}+(-\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{j}}$
(37)

with
$\overrightarrow{cst}^{t}\cdot\ket{e_{j}}=\overrightarrow{cst}^{t}\cdot\ket{e_{l}}=0$

For example, the action of a RBS with parameter $\theta_{i}$ in $B_{1}^{n}$ on
the two first qubits of a 4-qubit quantum circuit results in the
$\theta_{i}$-planar rotation between the states $\ket{1000}$ and $\ket{0100}$.

We can define the error according to the final error:

$\delta^{\lambda+1}=(w^{\lambda+1})^{-1}\cdots(w^{\lambda_{max}})^{-1}\cdot\Delta^{l}=2[w^{\lambda}\cdot\zeta^{\lambda}-(w^{\lambda+1})^{-1}\cdots(w^{\lambda_{max}})^{-1}\cdot
y]$ (38)

According to Theorem 3:
$\forall\lambda,\quad(w^{\lambda})^{-1}=(w^{\lambda})^{t}$.

We call: $\tilde{y}=(w^{\lambda+1})^{t}\cdots(w^{\lambda_{max}})^{t}\cdot y$
and $\Omega=[0:2\pi]^{D}$

We use the notation $\tilde{y}_{j}$ for the amplitude of the $j^{\text{th}}$
state in the state basis considered of $\tilde{y}$.

According to the backpropagation formalism presented in Section III.1, we have
in the unary case:

$\frac{\partial\mathcal{C}}{\partial\theta_{i}}=\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})+\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})$
(39)

Therefore, we can express the variance of the cost function gradient as:

$\begin{split}\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]&=\mathbb{V}ar_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})+\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\mathbb{V}ar_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]+\mathbb{V}ar_{\Theta}[\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&\;+2\cdot\mathbb{C}ov_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda});\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\end{split}$
(40)

First:

$\begin{split}\mathbb{V}ar_{\Theta}&[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]=\mathbb{V}ar_{\Theta}[2(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+\sin(\theta_{i})\cdot\zeta^{\lambda}_{j}-\tilde{y}_{l}))\cdot(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=4\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})-\mathbb{E}_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})])^{2}d\Theta\end{split}$
(41)

With:

$\begin{split}\mathbb{E}_{\Theta}&[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(2(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+\sin(\theta_{i})\cdot\zeta^{\lambda}_{j}-\tilde{y}_{l}))\cdot(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda}))d\Theta\\\
&=2\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\cos(\theta_{i})\sin(\theta_{i})((\zeta_{j}^{\lambda})^{2}-(\zeta_{l}^{\lambda})^{2})d\Theta+2\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\cos^{2}(\theta_{i})-\sin^{2}(\theta_{i}))\zeta_{j}^{\lambda}\cdot\zeta_{l}^{\lambda}d\Theta\\\
&\quad+2\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\sin(\theta_{i})\cdot\zeta_{l}^{\lambda}-\cos(\theta_{i})\cdot\zeta_{j}^{\lambda})\tilde{y}_{l}d\Theta\end{split}$
(42)

According to our circuit decomposition into inner layers, the previous inner
layer $\zeta^{\lambda}$ does not depend on the parameter $\theta_{i}$ but only
on the previous parameters in the circuit. On the other hand, $\tilde{y}$ does
not depend on the parameter $\theta_{i}$ but only on the following parameters
in the circuit. Thus, we can take out the integral according to $\theta_{i}$:

$\mathbb{E}_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]=2\int_{\Theta\in\Omega\backslash\theta_{i}}(\frac{1}{2\pi})^{D}(\pi-\pi)\zeta_{j}^{\lambda}\cdot\zeta_{l}^{\lambda}d\Theta=0$
(43)

Therefore:

$\begin{split}\mathbb{V}ar_{\Theta}&[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]=4\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda}))^{2}d\Theta\\\
&=4\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\cos^{2}(\theta_{i})\sin^{2}(\theta_{i})\cdot((\zeta_{j}^{\lambda})^{2}-(\zeta_{l}^{\lambda})^{2})^{2}+2\cos^{3}(\theta_{i})\sin(\theta_{i})\zeta_{j}^{\lambda}\zeta_{l}^{\lambda}((\zeta_{j}^{\lambda})^{2}-(\zeta_{l}^{\lambda})^{2})\\\
&-2\cos(\theta_{i})\sin^{3}(\theta_{i})\zeta_{j}^{\lambda}\zeta_{l}^{\lambda}((\zeta_{j}^{\lambda})^{2}-(\zeta_{l}^{\lambda})^{2})+2\cos(\theta_{i})\sin^{3}(\theta_{i})\zeta_{l}^{\lambda}((\zeta_{j}^{\lambda})^{2}-(\zeta_{l}^{\lambda})^{2})\tilde{y}_{l}\\\
&-2\cos^{2}(\theta_{i})\sin(\theta_{i})\zeta_{j}^{\lambda}((\zeta_{j}^{\lambda})^{2}-(\zeta_{l}^{\lambda})^{2})\tilde{y}_{l}+[\cos^{4}(\theta_{i})-2\cos^{2}(\theta_{i})\sin^{2}(\theta_{i})+\sin^{4}(\theta_{i})](\zeta_{l}^{\lambda})^{2}(\zeta_{j}^{\lambda})^{2}\\\
&+2\cos^{2}(\theta_{i})\sin(\theta_{i})(\zeta_{l}^{\lambda})^{2}\zeta_{j}^{\lambda}\tilde{y}_{l}-2\sin^{3}(\theta_{i})(\zeta_{l}^{\lambda})^{2}\zeta_{j}^{\lambda}\tilde{y}_{l}-2\cos^{3}(\theta_{i})\zeta_{l}^{\lambda}(\zeta_{j}^{\lambda})^{2}\tilde{y}_{l}+2\cos(\theta_{i})\sin^{2}(\theta_{i})\zeta_{l}^{\lambda}(\zeta_{j}^{\lambda})^{2}\tilde{y}_{l}\\\
&+\sin^{2}(\theta_{i})(\zeta_{l}^{\lambda})^{2}(\tilde{y}_{l})^{2}-2\cos(\theta_{i})\sin(\theta_{i})\zeta_{l}^{\lambda}\zeta_{j}^{\lambda}(\tilde{y}_{l})^{2}+\cos^{2}(\theta_{i})(\zeta_{j}^{\lambda})^{2}(\tilde{y}_{l})^{2}d\Theta\\\
&=4\int_{\Theta\in\Omega\backslash\theta_{i}}(\frac{1}{2\pi})^{D}[\frac{\pi}{4}(\zeta_{l}^{\lambda})^{4}+\frac{\pi}{2}(\zeta_{l}^{\lambda})^{2}(\zeta_{j}^{\lambda})^{2}+\frac{\pi}{4}(\zeta_{j}^{\lambda})^{4}+\pi(\zeta_{l}^{\lambda})^{2}(\tilde{y}_{l})^{2}+\pi(\zeta_{j}^{\lambda})^{2}(\tilde{y}_{l})^{2}]d\Theta\end{split}$
(44)

Finally, we have:

$\mathbb{V}ar_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}(\zeta_{l}^{\lambda})^{4}+(\zeta_{l}^{\lambda})^{2}(\zeta_{j}^{\lambda})^{2}+\frac{1}{2}(\zeta_{j}^{\lambda})^{4}+2((\zeta_{l}^{\lambda})^{2}+(\zeta_{j}^{\lambda})^{2})(\tilde{y}_{l})^{2}]d\Theta$
(45)

With the same methods, it comes:

$\mathbb{V}ar_{\Theta}[\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}(\zeta_{l}^{\lambda})^{4}+(\zeta_{l}^{\lambda})^{2}(\zeta_{j}^{\lambda})^{2}+\frac{1}{2}(\zeta_{j}^{\lambda})^{4}+2((\zeta_{l}^{\lambda})^{2}+(\zeta_{j}^{\lambda})^{2})(\tilde{y}_{l})^{2}]d\Theta$
(46)

We can decompose the covariance term:

$\begin{split}\mathbb{C}ov_{\Theta}&[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda});\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\mathbb{E}_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})\cdot\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&-\mathbb{E}_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]\cdot\mathbb{E}_{\Theta}[\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\end{split}$
(47)

As shown with Eq.(43):

$\mathbb{E}_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]=\mathbb{E}_{\Theta}[\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]=0$
(48)

Therefore, we have that the expectation value of the cost function gradient is
null. In addition, we have:

$\begin{split}\mathbb{C}ov_{\Theta}&[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda});\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\mathbb{E}_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})\cdot\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})\cdot\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]d\Theta\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\cos^{2}(\theta_{i})\sin^{2}(\theta_{i})(-(\zeta^{\lambda}_{l})^{4}+2(\zeta^{\lambda}_{l})^{2}(\zeta^{\lambda}_{j})^{2}-(\zeta^{\lambda}_{j})^{4})\\\
&+\cos(\theta_{i})\sin(\theta_{i})(\sin^{2}(\theta_{i})-\cos^{2}(\theta_{i}))((\zeta^{\lambda}_{j})^{2}-(\zeta^{\lambda}_{l})^{2})\zeta^{\lambda}_{l}\zeta^{\lambda}_{j}+\cos^{2}(\theta_{i})\sin(\theta_{i})((\zeta^{\lambda}_{j})^{2}-(\zeta^{\lambda}_{l})^{2})\zeta^{\lambda}_{l}\tilde{y}^{\lambda}_{j}\\\
&-\cos(\theta_{i})\sin^{2}(\theta_{i})((\zeta^{\lambda}_{j})^{2}-(\zeta^{\lambda}_{l})^{2})\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{j}+\cos(\theta_{i})\sin(\theta_{i})(\cos^{2}(\theta_{i})-\sin^{2}(\theta_{i}))((\zeta^{\lambda}_{j})^{2}-(\zeta^{\lambda}_{l})^{2})\zeta^{\lambda}_{l}\zeta^{\lambda}_{j}\\\
&-(\cos^{4}(\theta_{i})-2\cos^{2}(\theta_{i})\sin^{2}(\theta_{i})+\sin^{4}(\theta_{i}))(\zeta^{\lambda}_{l}\zeta^{\lambda}_{j})^{2}+\cos(\theta_{i})(\cos^{2}(\theta_{i})-\sin^{2}(\theta_{i}))(\zeta^{\lambda}_{l})^{2}\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{j}\\\
&=-\sin(\theta_{i})(\cos^{2}(\theta_{i})-\sin^{2}(\theta_{i}))\zeta^{\lambda}_{l}(\zeta^{\lambda}_{j})^{2}\tilde{y}^{\lambda}_{j}+\cos(\theta_{i})\sin^{2}(\theta_{i})((\zeta^{\lambda}_{j})^{2}-(\zeta^{\lambda}_{l})^{2})\zeta^{\lambda}_{l}\tilde{y}^{\lambda}_{l}\\\
&+\sin(\theta_{i})(\sin^{2}(\theta_{i})-\cos^{2}(\theta_{i}))(\zeta^{\lambda}_{l})^{2}\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{l}+\cos(\theta_{i})\sin(\theta_{i})(\zeta^{\lambda}_{l})^{2}\tilde{y}^{\lambda}_{l}\tilde{y}^{\lambda}_{j}-\sin^{2}(\theta_{i})\zeta^{\lambda}_{l}\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{l}\tilde{y}^{\lambda}_{j}\\\
&-\cos^{2}(\theta_{i})\sin(\theta_{i})((\zeta^{\lambda}_{l})^{2}-(\zeta^{\lambda}_{j})^{2})\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{l}-\cos(\theta_{i})(\sin^{2}(\theta_{i})-\cos^{2}(\theta_{i}))\zeta^{\lambda}_{l}(\zeta^{\lambda}_{j})^{2}\tilde{y}^{\lambda}_{l}\\\
&+\cos^{2}(\theta_{i})\zeta^{\lambda}_{l}\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{l}\tilde{y}^{\lambda}_{j}+\cos(\theta_{i})\sin(\theta_{i})\zeta^{\lambda}_{j}\tilde{y}^{\lambda}_{l}\tilde{y}^{\lambda}_{j}]d\Theta\\\
&=-\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{4}d\Theta-\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{j})^{4}d\Theta-\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}(\zeta^{\lambda}_{j})^{2}d\Theta\end{split}$
(49)

We can derive the variance of the cost gradient:

$\begin{split}\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=&\mathbb{V}ar_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})]+\mathbb{V}ar_{\Theta}[\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&\;+2\cdot\mathbb{C}ov_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda});\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}(\zeta_{l}^{\lambda})^{4}+(\zeta_{l}^{\lambda})^{2}(\zeta_{j}^{\lambda})^{2}+\frac{1}{2}(\zeta_{j}^{\lambda})^{4}+2((\zeta_{l}^{\lambda})^{2}+(\zeta_{j}^{\lambda})^{2})(\tilde{y}_{l})^{2}]d\Theta\\\
&+\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}(\zeta_{l}^{\lambda})^{4}+(\zeta_{l}^{\lambda})^{2}(\zeta_{j}^{\lambda})^{2}+\frac{1}{2}(\zeta_{j}^{\lambda})^{4}+2((\zeta_{l}^{\lambda})^{2}+(\zeta_{j}^{\lambda})^{2})(\tilde{y}_{l})^{2}]d\Theta\\\
&-\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{4}d\Theta-\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{j})^{4}d\Theta-2\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}(\zeta^{\lambda}_{j})^{2}d\Theta\end{split}$
(50)

We find that:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=2\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)$
(51)

We claim that, if the initial state $\zeta_{0}$ and the wanted output $y$ are
uniformly distributed on the basis $B_{1}^{n}$, we have that:

$\forall\lambda,\forall
r\in[n],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda})^{2}d\Theta=\frac{1}{n}$
(52)

We prove our claim using mathematical induction. First state case:

$\forall
r\in[n],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{0})^{2}d\Theta=(\zeta_{r}^{0})^{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}d\Theta=(\zeta_{r}^{0})^{2}=\frac{1}{n}$
(53)

This result comes from the initial state independence of theta and its uniform
distribution on the unary basis. We now suppose that the property given by
Eq.(52) is true for a given step $\lambda$. Then:

$\forall
r\in[n],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda+1})^{2}d\Theta=\begin{cases}\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r,r^{\prime}}^{\lambda})^{2}d\Theta+\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r^{\prime},r}^{\lambda})^{2}d\Theta\\\
\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda})^{2}d\Theta\end{cases}$
(54)

The first case is when the state $\ket{e_{r}}$ was involved in a rotation by
the application of the RBS between the inner layer $\lambda$ and $\lambda+1$.
The second case correspond to a RBS that does not affect the state $\ket{r}$.
In the two cases, we have:

$\forall
r\in[n],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda+1})^{2}d\Theta=\frac{1}{n}$
(55)

Using the same method we can prove that, if the wanted output is uniformly
distributed on the basis $B_{1}^{n}$, we have:

$\forall\lambda,\forall
r\in[n],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}_{r}^{\lambda})^{2}d\Theta=\frac{1}{n}$
(56)

We can thus conclude that:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=2\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)\approx\frac{8}{n^{2}}$
(57)

We use the approximation sign because we are considering the expectation
according to the input and output vectors.

###  D.2 Extension to any HW for RBS based VQC

We consider once again the case of the quadratic cost function. We call
$\Delta^{L}$ the final error:

$\Delta^{L}=2(z^{L}-y)=2[(w^{\lambda_{max}}\cdots w^{\lambda+1})\cdot
w^{\lambda}\cdot\zeta^{\lambda}-y]$ (58)

We still consider the case where for each inner layer, there is only one RBS
gate considered. For each inner layer, the action of the gate results in a
rotation of the amplitudes between a set of pair of states that we call
$\mathcal{R}_{\lambda}$:

$\zeta^{\lambda+1}=\overrightarrow{cst}+\sum_{(l,j)\in\mathcal{R}_{\lambda}}(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+\sin(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{l}}+(-\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{j}}$
(59)

with
$\forall(l,j)\in\mathcal{R}_{\lambda},\quad\overrightarrow{cst}^{t}\cdot\ket{e_{j}}=\overrightarrow{cst}^{t}\cdot\ket{e_{l}}=0$

For example, the action of a RBS with parameter $\theta_{i}$ in $B_{2}^{n}$ on
the two first qubits of a 4-qubit quantum circuit results in the
$\theta_{i}$-planar rotation between the states $\ket{1010}$ and $\ket{0110}$,
but also in the same $\theta_{i}$-planar rotation between the states
$\ket{1001}$ and $\ket{0101}$.

We can define the error according to the final error:

$\begin{split}\delta^{\lambda+1}&=(w^{\lambda+1})^{-1}\cdots(w^{\lambda_{max}})^{-1}\cdot\Delta^{l}=2[w^{\lambda}\cdot\zeta^{\lambda}-(w^{\lambda+1})^{-1}\cdots(w^{\lambda_{max}})^{-1}\cdot
y]\\\
&=2[\overrightarrow{cst}+\sum_{(l,j)\in\mathcal{R}_{\lambda}}(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+\sin(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{l}}+(-\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{j}}-\tilde{y}^{\lambda}]\end{split}$
(60)

A unique RBS affects $\binom{n-2}{k-1}$ different pairs of states with a
rotation, and all the affected states are different. As before, we have:

$\forall(l,j)\in\mathcal{R}_{\lambda},\quad\delta^{\lambda+1}_{l}=2[\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+\sin(\theta_{i})\cdot\zeta^{\lambda}_{j}-\tilde{y}^{\lambda}_{l}]$
(61)

and,

$\forall(l,j)\in\mathcal{R}_{\lambda},\quad\delta^{\lambda+1}_{j}=2[-\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j}-\tilde{y}^{\lambda}_{j}]$
(62)

According to Theorem 3:
$\forall\lambda,\quad(w^{\lambda})^{-1}=(w^{\lambda})^{t}$.

We call: $\tilde{y}=(w^{\lambda+1})^{t}\cdots(w^{\lambda_{max}})^{t}\cdot y$
and $\Omega=[0:2\pi]^{D}$ In the following, we will omit to note the set
$\mathcal{R}_{\lambda}$.

$\begin{split}\mathbb{V}ar_{\Theta}&[\partial_{\theta_{i}}\mathcal{C}]=\mathbb{V}ar_{\Theta}[\sum_{(l,j)}\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})+\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\sum_{(l,j)}\mathbb{V}ar_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+\cos(\theta_{i})\zeta_{j}^{\lambda})+\delta_{j}^{\lambda}(-\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&+2\sum_{(a,b)\neq(c,d)}\mathbb{C}ov_{\Theta}[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda}),\\\
&\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\end{split}$
(63)

Using previous result from the previous Section D.1, we have:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=2\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)$
(64)

Then,

$\begin{split}\mathbb{C}ov_{\Theta}&[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda}),\\\
&\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=\mathbb{E}_{\Theta}[\left(\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})\right)\cdot\\\
&\left(\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})\right)]\\\
&-\mathbb{E}_{\Theta}[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})]\cdot\\\
&\mathbb{E}_{\Theta}[\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\end{split}$
(65)

Using previous result from the previous Section D.1 we have:

$\begin{split}\mathbb{E}_{\Theta}&[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})]\\\
&=\mathbb{E}_{\Theta}[\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=0\end{split}$ (66)

We can now derive the value of the covariance term:

$\begin{split}\mathbb{C}ov_{\Theta}&[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda}),\\\
&\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=\mathbb{E}_{\Theta}[\left(\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})\right)\cdot\\\
&\left(\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})\right)]\\\
&=\mathbb{E}_{\Theta}[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})]\\\
&+\mathbb{E}_{\Theta}[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&+\mathbb{E}_{\Theta}[\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})]\\\
&+\mathbb{E}_{\Theta}[\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\end{split}$
(67)

Using the integral expression of the expectation value:

$\begin{split}\mathbb{E}_{\Theta}&[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}\left((\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{d})^{2}-(\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{c})^{2}-(\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{d})^{2}+(\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{c})^{2}\right)\\\
&+2\zeta^{\lambda}_{a}\zeta^{\lambda}_{b}\zeta^{\lambda}_{c}\zeta^{\lambda}_{d}+2\zeta^{\lambda}_{a}\zeta^{\lambda}_{c}\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+2\zeta^{\lambda}_{b}\zeta^{\lambda}_{d}\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}]d\Theta\end{split}$
(68)

$\begin{split}\mathbb{E}_{\Theta}&[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}\left((\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{c})^{2}-(\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{c})^{2}-(\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{d})^{2}+(\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{d})^{2}\right)\\\
&-2\zeta^{\lambda}_{a}\zeta^{\lambda}_{b}\zeta^{\lambda}_{c}\zeta^{\lambda}_{d}+2\zeta^{\lambda}_{a}\zeta^{\lambda}_{d}\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}+2\zeta^{\lambda}_{b}\zeta^{\lambda}_{c}\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}]d\Theta\end{split}$
(69)

$\begin{split}\mathbb{E}_{\Theta}&[\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}\left((\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{d})^{2}-(\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{d})^{2}-(\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{c})^{2}+(\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{c})^{2}\right)\\\
&-2\zeta^{\lambda}_{a}\zeta^{\lambda}_{b}\zeta^{\lambda}_{c}\zeta^{\lambda}_{d}+2\zeta^{\lambda}_{a}\zeta^{\lambda}_{d}\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c}+2\zeta^{\lambda}_{b}\zeta^{\lambda}_{c}\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c}]d\Theta\end{split}$
(70)

$\begin{split}\mathbb{E}_{\Theta}&[\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda})\cdot\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[\frac{1}{2}\left((\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{c})^{2}-(\zeta^{\lambda}_{a})^{2}(\zeta^{\lambda}_{d})^{2}-(\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{c})^{2}+(\zeta^{\lambda}_{b})^{2}(\zeta^{\lambda}_{d})^{2}\right)\\\
&-2\zeta^{\lambda}_{a}\zeta^{\lambda}_{b}\zeta^{\lambda}_{c}\zeta^{\lambda}_{d}+2\zeta^{\lambda}_{a}\zeta^{\lambda}_{c}\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d}+2\zeta^{\lambda}_{b}\zeta^{\lambda}_{d}\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d}]d\Theta\end{split}$
(71)

By summing the terms:

$\begin{split}\mathbb{C}ov_{\Theta}&[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}(-\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda}),\\\
&\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}(-\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\\\
&=2\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[(\zeta_{a}^{\lambda}\zeta_{c}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{d}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d})+(\zeta_{a}^{\lambda}\zeta_{d}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{c}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c})]d\Theta\end{split}$
(72)

Finally,

$\begin{split}\mathbb{V}ar_{\Theta}&[\partial_{\theta_{i}}\mathcal{C}]=2\sum_{(l,j)}\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)\\\
&+4\sum_{(a,b)\neq(c,d)}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[(\zeta_{a}^{\lambda}\zeta_{c}^{\lambda}+\zeta_{b}^{\lambda}\zeta_{d}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d})+(\zeta_{a}^{\lambda}\zeta_{d}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{c}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}-\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c})]d\Theta\end{split}$
(73)

We now claim that the covariance term is null. To show this, we are about to
use an induction proof to prove that $\forall\lambda,\forall
a,b\in[d_{k}],\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a}^{\lambda}\zeta_{b}^{\lambda}d\Theta=0$.
First for the basis:

$\forall
a,b\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a}^{0}\zeta_{b}^{0}d\Theta=\zeta_{a}^{0}\zeta_{b}^{0}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}d\Theta=\zeta_{a}^{0}\zeta_{b}^{0}$
(74)

Considering the expectation value on the input vectors $X$, it comes:

$\forall a,b\in[d_{k}],\quad\mathbb{E}_{X}[\zeta_{a}^{0}\zeta_{b}^{0}]=0$ (75)

For the induction part, we just need to use the recursive formula on the
evolution of the inner states. Let us consider the property verified on then
layer $\lambda$:

$\forall
a,b\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a}^{\lambda+1}\zeta_{b}^{\lambda+1}d\Theta=\begin{cases}\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a,a^{\prime}}^{\lambda}\zeta_{b,b^{\prime}}^{\lambda}d\Theta+\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a^{\prime},a}^{\lambda}\zeta_{b^{\prime},b}^{\lambda}d\Theta=0\\\
\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\pm\cos(\theta_{i})\zeta_{a,a^{\prime}}^{\lambda}\pm\sin(\theta_{i})\zeta_{a^{\prime},a}^{\lambda})\zeta_{b}^{\lambda}d\Theta=0\\\
\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a}^{\lambda}(\pm\cos(\theta_{i})\zeta_{b,b^{\prime}}^{\lambda}\pm\sin(\theta_{i})\zeta_{b^{\prime},b}^{\lambda})d\Theta=0\\\
\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a}^{\lambda}\zeta_{b}^{\lambda}d\Theta=0\end{cases}$
(76)

The first case corresponds to the situation where $a$ and $b$ are affected by
a rotation in the previous layer $\lambda$. The second and the third case
refer to situation where only one state between $a$ and $b$ is affected by a
rotation in the previous layer. By integrating over the corresponding
parameter, those value are null. Finally, we consider the case where none of
them are affected by a rotation in the previous layer. In all the cases if
$a\neq b$, the result is null due to the induction hypothesis.

We prove by induction that:

$\forall\lambda,\forall a,b\in[d_{k}],\quad a\neq
b\implies\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\zeta_{a}^{\lambda}\zeta_{b}^{\lambda}d\Theta=0$
(77)

Which implies that the covariance term is equal to $0$:

$\sum_{(a,b)\neq(c,d)}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[(\zeta_{a}^{\lambda}\zeta_{c}^{\lambda}+\zeta_{b}^{\lambda}\zeta_{d}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d})+(\zeta_{a}^{\lambda}\zeta_{d}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{c}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}-\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c})]d\Theta=0$
(78)

Using the expectation of this value over the input and output vectors, we can
show in a similar way as in the previous Section D.1 that:

$\forall
r\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda+1})^{2}d\Theta\approx\frac{1}{d_{k}}$
(79)

and,

$\forall\lambda,\forall
r\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}_{r}^{\lambda})^{2}d\Theta\approx\frac{1}{d_{k}}$
(80)

Using the expectation value on the input and wanted output distribution:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]=2\sum_{(l,j)}\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)=\sum_{(l,j)}\frac{8}{d_{k}^{2}}$
(81)

The sum is over all the rotation induces by the RBS of variational parameter
$\theta_{i}$. The number of rotation between different couple of states is:

$\binom{n-2}{k-1}=\frac{(n-2)!}{(k-1)!(n-1-k)!}=\frac{k(n-k)}{n(n-1)}\binom{n}{k}=\frac{k(n-k)}{n(n-1)}d_{k}$
(82)

We conclude:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]\approx\frac{k(n-k)}{n(n-1)}\frac{8}{d_{k}}$
(83)

We prove Theorem 1 in the specific case of RBS gate. In the following section
we show how to generalize this result for FBS gates.

###  D.3 Generalization for FBS gates

In this section, we explain how to adapt the previous proof given in Section
D.2 to extend our result to FBS based quantum circuits.

We consider once again the case of the quadratic cost function. The
decomposition of the FBS based quantum circuit for the backpropagation method
is very similar to the case of RBS based quantum circuit:

We call $\Delta^{L}$ the final error:

$\Delta^{L}=2(z^{L}-y)=2[(w^{\lambda_{max}}\cdots w^{\lambda+1})\cdot
w^{\lambda}\cdot\zeta^{\lambda}-y]$ (84)

We consider the case where for each inner layer, there is only one FBS gate
considered. For each inner layer, the action of the gate results in a rotation
of the amplitudes between a set of pair of states that we call
$\mathcal{R}_{\lambda}$:

$\zeta^{\lambda+1}=\overrightarrow{cst}+\sum_{(l,j)\in\mathcal{R}_{\lambda}}(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+(-1)^{f(l,j,\zeta^{\lambda}_{j})}\sin(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{l}}+((-1)^{f(l,j,\zeta^{\lambda}_{l})+1}\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{j}}$
(85)

with
$\forall(l,j)\in\mathcal{R}_{\lambda},\quad\overrightarrow{cst}^{t}\cdot\ket{e_{j}}=\overrightarrow{cst}^{t}\cdot\ket{e_{l}}=0$

We can define the error according to the final error:

$\begin{split}\delta^{\lambda+1}&=(w^{\lambda+1})^{-1}\cdots(w^{\lambda_{max}})^{-1}\cdot\Delta^{l}=2[w^{\lambda}\cdot\zeta^{\lambda}-(w^{\lambda+1})^{-1}\cdots(w^{\lambda_{max}})^{-1}\cdot
y]\\\
&=2[\overrightarrow{cst}+\sum_{(l,j)\in\mathcal{R}_{\lambda}}(\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+(-1)^{f(l,j,\zeta^{\lambda}_{j})}\sin(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{l}}\\\
&+((-1)^{f(l,j,\zeta^{\lambda}_{l})+1}\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j})\ket{e_{j}}-\tilde{y}^{\lambda}]\end{split}$
(86)

A unique RBS affects $\binom{n-2}{k-1}$ different pairs of states with a
rotation, and all the affected states are different. A unique FBS applied on
the same qubits affects the same pairs of states. Therefore:

$\forall(l,j)\in\mathcal{R}_{\lambda},\quad\delta^{\lambda+1}_{l}=2[\cos(\theta_{i})\cdot\zeta^{\lambda}_{l}+(-1)^{f(l,j,\zeta^{\lambda}_{j})}\sin(\theta_{i})\cdot\zeta^{\lambda}_{j}-\tilde{y}^{\lambda}_{l}]$
(87)

and,

$\forall(l,j)\in\mathcal{R}_{\lambda},\quad\delta^{\lambda+1}_{j}=2[(-1)^{f(l,j,\zeta^{\lambda}_{l})+1}\sin(\theta_{i})\cdot\zeta^{\lambda}_{l}+\cos(\theta_{i})\cdot\zeta^{\lambda}_{j}-\tilde{y}^{\lambda}_{j}]$
(88)

According to Theorem 3:
$\forall\lambda,\quad(w^{\lambda})^{-1}=(w^{\lambda})^{t}$.

We call: $\tilde{y}=(w^{\lambda+1})^{t}\cdots(w^{\lambda_{max}})^{t}\cdot y$
and $\Omega=[0:2\pi]^{D}$ In the following, we will omit to note the set
$\mathcal{R}_{\lambda}$.

$\begin{split}\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]&=\mathbb{V}ar_{\Theta}[\sum_{(l,j)}\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+(-1)^{f(l,j,\zeta_{j}^{\lambda})}\cos(\theta_{i})\zeta_{j}^{\lambda})+\delta_{j}^{\lambda}((-1)^{f(l,j,\zeta_{l}^{\lambda})}\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&=\sum_{(l,j)}\mathbb{V}ar_{\Theta}[\delta_{l}^{\lambda}(-\sin(\theta_{i})\zeta_{l}^{\lambda}+(-1)^{f(l,j,\zeta_{j}^{\lambda})}\cos(\theta_{i})\zeta_{j}^{\lambda})+\delta_{j}^{\lambda}((-1)^{f(l,j,\zeta_{l}^{\lambda})}\cos(\theta_{i})\zeta_{l}^{\lambda}-\sin(\theta_{i})\zeta_{j}^{\lambda})]\\\
&+2\sum_{(a,b)\neq(c,d)}\mathbb{C}ov_{\Theta}[\delta_{a}^{\lambda}(-\sin(\theta_{i})\zeta_{a}^{\lambda}+(-1)^{f(a,b,\zeta_{b}^{\lambda})}\cos(\theta_{i})\zeta_{b}^{\lambda})+\delta_{b}^{\lambda}((-1)^{f(a,b,\zeta_{a}^{\lambda})}\cos(\theta_{i})\zeta_{a}^{\lambda}-\sin(\theta_{i})\zeta_{b}^{\lambda}),\\\
&\delta_{c}^{\lambda}(-\sin(\theta_{i})\zeta_{c}^{\lambda}+(-1)^{f(c,d,\zeta_{d}^{\lambda})}\cos(\theta_{i})\zeta_{d}^{\lambda})+\delta_{d}^{\lambda}((-1)^{f(c,d,\zeta_{c}^{\lambda})}\cos(\theta_{i})\zeta_{c}^{\lambda}-\sin(\theta_{i})\zeta_{d}^{\lambda})]\end{split}$
(89)

The only change in comparison with the RBS case is with the sign of the sinus
in the previous equations. However, in the proof of Theorem 1 given in the
previous appendix, we derive each term of Eq.(89) by integrating over the
parameter $\theta_{i}$. The sign of the sine does not change the integration
and as a result we find again that:

$\begin{split}\mathbb{V}ar_{\Theta}&[\partial_{\theta_{i}}\mathcal{C}]=2\sum_{(l,j)}\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)\\\
&+4\sum_{(a,b)\neq(c,d)}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[(\zeta_{a}^{\lambda}\zeta_{c}^{\lambda}+\zeta_{b}^{\lambda}\zeta_{d}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d})+(\zeta_{a}^{\lambda}\zeta_{d}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{c}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}-\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c})]d\Theta\end{split}$
(90)

With the FBS, we consider the same induction relation between the inner layers
than in the case of RBS based gates:

$\forall
r\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda+1})^{2}d\Theta=\begin{cases}\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r,r^{\prime}}^{\lambda})^{2}d\Theta+\frac{1}{2}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r^{\prime},r}^{\lambda})^{2}d\Theta\\\
\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda})^{2}d\Theta\end{cases}$
(91)

We can thus consider in a similar way that the covariance term is null. Using
the expectation of this value over the input and output vectors, we can show
in a similar way as in the previous Section D.2, that:

$\forall
r\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta_{r}^{\lambda+1})^{2}d\Theta\approx\frac{1}{d_{k}}$
(92)

and,

$\forall\lambda,\forall
r\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}_{r}^{\lambda})^{2}d\Theta\approx\frac{1}{d_{k}}$
(93)

Using the expectation value on the input and wanted output distribution:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]=2\sum_{(l,j)}\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)=\sum_{(l,j)}\frac{8}{d_{k}^{2}}$
(94)

The sum is over all the rotation induces by the RBS of variational parameter
$\theta_{i}$. The number of rotation between different couple of states is
unchanged:

$\binom{n-2}{k-1}=\frac{(n-2)!}{(k-1)!(n-1-k)!}=\frac{k(n-k)}{n(n-1)}\binom{n}{k}=\frac{k(n-k)}{n(n-1)}d_{k}$
(95)

We conclude:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]\approx\frac{k(n-k)}{n(n-1)}\frac{8}{d_{k}}$
(96)

Therefore, we prove the Theorem 1.

##  Appendix E Proof of Theorem 2

We recall the Theorem 2:

See 2

As in the proof of Theorem 1 presented previously, we can state for RBS or FBS
that:

$\begin{split}\mathbb{V}ar_{\Theta}&[\partial_{\theta_{i}}\mathcal{C}]=2\sum_{(l,j)}\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)\\\
&+4\sum_{(a,b)\neq(c,d)}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[(\zeta_{a}^{\lambda}\zeta_{c}^{\lambda}+\zeta_{b}^{\lambda}\zeta_{d}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d})+(\zeta_{a}^{\lambda}\zeta_{d}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{c}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}-\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c})]d\Theta\end{split}$
(97)

Using the exact same type of induction proof as in D.2, we can prove that:

$\forall\lambda,\forall
a,b\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}\tilde{y}_{a}^{\lambda}\tilde{y}_{b}^{\lambda}d\Theta=0$
(98)

Which implies that the covariance term is equal to $0$ for any inner layer
$\lambda$:

$\sum_{(a,b)\neq(c,d)}\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}[(\zeta_{a}^{\lambda}\zeta_{c}^{\lambda}+\zeta_{b}^{\lambda}\zeta_{d}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{c}+\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{d})+(\zeta_{a}^{\lambda}\zeta_{d}^{\lambda}-\zeta_{b}^{\lambda}\zeta_{c}^{\lambda})(\tilde{y}^{\lambda}_{a}\tilde{y}^{\lambda}_{d}-\tilde{y}^{\lambda}_{b}\tilde{y}^{\lambda}_{c})]d\Theta=0$
(99)

We then just have:

$\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]=2\sum_{(l,j)}\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta\right)\cdot\left(\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}^{\lambda}_{l})^{2}+(\tilde{y}^{\lambda}_{j})^{2}d\Theta\right)$
(100)

By hypothesis on the wanted output distribution, we replace the integral of
the $\tilde{y}$ terms by its expectation value over the wanted output vectors:

$\forall\lambda,\forall
r\in[d_{k}],\quad\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\tilde{y}_{r}^{\lambda})^{2}d\Theta\approx\frac{1}{d_{k}}$
(101)

We now consider a new distribution for our input vector:

$\forall r\in[d_{k}],\quad\zeta_{r}^{0}=\delta_{r,s}\quad\text{with
$\ket{e_{s}}$ the initial state of our quantum circuit and $\delta_{r,s}$ the
Kronecker function}.$ (102)

We notice that we can express the integral for each state as a probability:

$\forall\lambda,\quad\sum_{i\in[d_{k}]}\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{i})^{2}d\Theta=1\quad\text{and}\quad\forall
i\in[d_{k}],\quad\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{i})^{2}d\Theta\in[0,1]$
(103)

If one picks randomly a couple of state in the basis $B_{k}^{n}$, we have in
average (according to the state we choose):

$\int_{\Theta\in\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{l})^{2}+(\zeta^{\lambda}_{j})^{2}d\Theta=\frac{2}{d_{k}}$
(104)

However, we would like to now more about the exact value of

$\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{i})^{2}d\Theta$

For any $i\in[d_{k}]$. Let us consider a given state $\ket{e_{s}}$ and a given
inner layer $\lambda$. If the state $\ket{e_{s}}$ is affected by a rotation
due to the inner layer with another state $\ket{e_{r}}$, we have:

$\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda+1}_{s})^{2}d\Theta=\frac{1}{2}\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{s})^{2}d\Theta+\frac{1}{2}\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{r})^{2}d\Theta$
(105)

and:

$\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda+1}_{r})^{2}d\Theta=\frac{1}{2}\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{s})^{2}d\Theta+\frac{1}{2}\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{r})^{2}d\Theta$
(106)

Therefore, each RBS or FBS is keen to normalize the distribution of
probabilities describe on Eq.(103). Therefore if the circuit has enough gates
that affected all the states in $B_{k}^{n}$, we can consider that:

$\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{i})^{2}d\Theta\approx\frac{1}{d_{k}}$
(107)

We call $\lambda_{0}$ the minimal number of gates (or inner states in the
circuit decomposition) such as every state in $B_{k}^{n}$ can be reached. This
means that:

$\forall\lambda\geq\lambda_{0},\quad\forall
r\in[d_{k}],\;\exists\Theta\in[0,2\pi]^{D}\;\backslash\;\zeta^{\lambda}_{r}\neq
0$ (108)

This implies that:

$\forall\lambda\geq\lambda_{0},\quad\forall
r\in[d_{k}],\int_{\Omega}(\frac{1}{2\pi})^{D}(\zeta^{\lambda}_{i})^{2}d\Theta\neq
0$ (109)

Thus:

$\forall
i\geq\lambda_{0},\quad\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}]\approx
2\sum_{(l,j)}\frac{2}{d_{k}}\cdot\frac{2}{d_{k}}$ (110)

Or the number of couple of states in the sum is $\binom{n-2}{k-1}$ and we have
as shown previously that:

$\binom{n-2}{k-1}=\frac{(n-2)!}{(k-1)!(n-1-k)!}=\frac{k(n-k)}{n(n-1)}\binom{n}{k}=\frac{k(n-k)}{n(n-1)}d_{k}$
(111)

We can thus conclude using the hypothesis from Eq.(107) that:

$\forall
i\geq\lambda_{0},\quad\mathbb{E}_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]=0\text{,}\quad\mathbb{V}ar_{\Theta}[\partial_{\theta_{i}}\mathcal{C}(\Theta)]\approx\frac{k(n-k)}{n(n-1)}\frac{8}{d_{k}}$
(112)