# How Much Entanglement Do Quantum Optimization Algorithms Require?

Yanzhu Chen  Center for Quantum Information Science & Engineering, Virginia
Tech, Blacksburg, VA 24061, U.S.A.  Department of Physics, Virginia Tech,
Blacksburg, VA 24061, U.S.A.  Linghua Zhu  Department of Chemistry, University
of Washington, Seattle, WA 98195, U.S.A.  Chenxu Liu  Center for Quantum
Information Science & Engineering, Virginia Tech, Blacksburg, VA 24061, U.S.A.
Department of Physics, Virginia Tech, Blacksburg, VA 24061, U.S.A.  Nicholas
J. Mayhall  Center for Quantum Information Science & Engineering, Virginia
Tech, Blacksburg, VA 24061, U.S.A.  Department of Chemistry, Virginia Tech,
Blacksburg, VA 24061, U.S.A.  Edwin Barnes  Center for Quantum Information
Science & Engineering, Virginia Tech, Blacksburg, VA 24061, U.S.A.  Department
of Physics, Virginia Tech, Blacksburg, VA 24061, U.S.A.  Sophia E. Economou
Center for Quantum Information Science & Engineering, Virginia Tech,
Blacksburg, VA 24061, U.S.A.  Department of Physics, Virginia Tech,
Blacksburg, VA 24061, U.S.A.

(July 9, 2023)

###### Abstract

Many classical optimization problems can be mapped to finding the ground
states of diagonal Ising Hamiltonians, for which variational quantum
algorithms such as the Quantum Approximate Optimization Algorithm (QAOA)
provide heuristic methods. Because the solutions of such classical
optimization problems are necessarily product states, it is unclear how
entanglement affects their performance. An Adaptive Derivative-Assembled
Problem-Tailored (ADAPT) variation of QAOA improves the convergence rate by
allowing entangling operations in the mixer layers whereas it requires fewer
CNOT gates in the entire circuit. In this work, we study the entanglement
generated during the execution of ADAPT-QAOA. Through simulations of the
weighted Max-Cut problem, we show that ADAPT-QAOA exhibits substantial
flexibility in entangling and disentangling qubits. By incrementally
restricting this flexibility, we find that a larger amount of entanglement
entropy at earlier stages coincides with faster convergence at later stages.
In contrast, while the standard QAOA quickly generates entanglement within a
few layers, it cannot remove excess entanglement efficiently. Our results
demonstrate that the role of entanglement in quantum optimization is subtle
and provide guidance for building favorable features into quantum optimization
algorithms.

##  1 Introduction

In today’s quantum devices, decoherence sets limits on the circuit depth.
Quantum-classical hybrid variational algorithms, which bypass the need for
deep quantum circuits, show promise for providing advantage over purely
classical computing [1, 2, 3, 4, 5]. In these algorithms, a parametrized
ansatz state is realized through a parametrized quantum circuit, on which
suitable measurements are carried out to provide information for classical
optimization. A suitably chosen ansatz is the key to ensure the correct
solution is reached or well approximated. Some approaches, such as the
hardware-efficient ansatz, allow the ansatz the capacity of realizing any
possible unitary operator in the Hilbert space [6, 7]. On the other hand, a
highly expressive ansatz may lead to difficulty in optimization [8, 9, 10,
11]. This has prompted a search for more problem-specific algorithms [12, 13,
14, 15]. To this end, an Adaptive Derivative-Assembled Problem-Tailored
(ADAPT) protocol has been developed [13, 16, 17]. First proposed to find the
ground state energies of molecules, the ADAPT protocol constructs the ansatz
iteratively, leading to a shallow quantum circuit and fast convergence. Its
flexibility also allows one to incorporate some information about the hardware
into the ansatz.

The application of hybrid variational algorithms extends beyond simulating
physical and chemical systems. In general, optimization problems are of
paramount importance to essentially every industry. While it is not yet clear
whether quantum computers will offer significant speedups to optimization
problems, the huge economic and technological repercussions of such an
achievement have motivated the community to explore quantum advantage in the
context of optimization. Entanglement has long been considered to play an
essential role in quantum computing, although a precise statement in each
specific context demands caution [18, 19, 20]. The role of entanglement is
especially mysterious in quantum optimization algorithms, where both the
initial state and the target state are unentangled. Nevertheless, it is often
believed that creating some entanglement can provide an advantage to such
algorithms. Many classical optimization problems, such as graph coloring and
traveling time optimization, can be mapped to finding the ground state of an
Ising Hamiltonian, where hybrid variational algorithms can be naturally
applied [21, 22, 23, 24, 25, 26, 27, 28].

A well-known heuristic algorithm for these problems is the Quantum Approximate
Optimization Algorithm (QAOA) [2]. It seeks the solution by optimizing the
expectation value of the problem Hamiltonian with respect to an ansatz that
alternates between a unitary evolution of the problem Hamiltonian and another
unitary that amounts to a simultaneous $X$ rotation of all the qubits. The
generator of the latter is called a mixer operator. Although the ansatz shares
similarities with a trotterized version of an adiabatic evolution, its
performance is limited by problem features, locality, and symmetry [29, 30,
31, 32, 33]. Moreover, analyses of computational resources and experimental
requirements for QAOA point out difficulties in its near-term application [34,
35, 36].

To improve the performance of QAOA, one can modify it with the ADAPT approach
[37, 38]. This algorithm, dubbed ADAPT-QAOA, builds up the ansatz layer by
layer. While preserving the alternating structure of QAOA, it replaces the
mixer at each step with an operator selected based on the energy gradient. It
was observed that convergence was drastically improved in the Max-Cut problem
when two-qubit operators were included in the mixer operator pool [37]. Such
two-qubit operators provide additional entangling operations in the ansatz.
The possibility of having them in the mixer layers lends ADAPT-QAOA more
freedom in entanglement production while the standard QAOA can only entangle
the qubits through the unitary generated by the Hamiltonian. Despite the fact
that ADAPT-QAOA is free to insert more entangling operations in the ansatz,
somewhat counterintuitively the final ansatz it produces requires fewer CNOT
gates overall compared to the standard QAOA for a given convergence threshold
[37]. This indicates that the role of entanglement in quantum optimization
algorithms is subtle and raises the question of how much entanglement is
really needed to improve convergence.

Depending on the formalism chosen for the computation, entanglement can be
seen as the key feature that sets quantum computing apart from classically
simulable processes [39, 18]. On the other hand, excessive entanglement in
certain settings can make classical optimization harder [40, 41]. Examining
entanglement in the context of optimization problems can shed light on the
efficiency and favorable features of hybrid variational algorithms. After
simulating non-interacting fermions with the hardware efficient ansatz, Ref.
[20] concluded that entanglement of an undesirable type can be a hindrance
rather than a resource. In the Hamiltonian variational ansatz, entanglement
entropy is observed to be between the level required in the ground state and
the level in a random state [42]. In classical optimization problems, however,
the target states do not intrinsically require a finite amount of
entanglement. This makes such problems great testing grounds for studying
whether existence of entanglement helps accelerate the optimization process.
Ref. [43] suggests that for quadratic unconstrained binary optimization
problems a product state ansatz may outperform entangled ones under certain
conditions.

In this work, we investigate the role entanglement plays in the performance of
ADAPT-QAOA for the weighted Max-Cut problem, which falls in the family of
quadratic unconstrained binary optimization problems. The amount of
entanglement entropy at each layer of the algorithm is calculated and compared
to that produced by the standard QAOA. From this we find that a larger amount
of entanglement entropy does not guarantee a higher convergence rate. Our
simulations reveal that ADAPT-QAOA has substantial flexibility in entangling
and disentangling qubits. By comparing its performance across different levels
of flexibility, we find that a larger amount of entanglement entropy at
earlier stages of ADAPT-QAOA can lead to faster convergence at later stages.
We also find that ADAPT-QAOA favoring entangling mixer operators converges
faster on average, although the first few optimized states doe not generate
more entanglement in this case. The rest of the paper is organized as follows.
In Sec. 2 we describe the details of our simulations, with the results
summarized in Sec. 3. We conclude and discuss the implications of our work in
Sec. 4.

##  2 Numerical simulation

To study the entanglement generated in the process of variational algorithms,
we consider the problem of finding the ground state of the Hamiltonian

$H_{\rm MaxCut}=\frac{1}{2}\sum_{i<j}w_{ij}(Z_{i}Z_{j}-I),$ (1)

where $\\{w_{ij}\\}$ are the edge weights of a graph, $Z_{i}$ is the Pauli $Z$
operator acting on the qubit labelled by $i$, and $i,j$ run from $0$ to $n-1$.
This is equivalent to the weighted Max-Cut problem. Since the identity term in
$H_{\rm MaxCut}$ only contributes a constant shift to the objective function
and a global phase to the ansatz, we drop it and use the cost Hamiltonian

$H=\frac{1}{2}\sum_{i<j}w_{ij}Z_{i}Z_{j}$ (2)

both as the objective function and in the ansatz. All the computational states
are eigenstates of $H$. Since any two states related by the symmetry
$F=\otimes_{i}X_{i}$ share the same energy, there are at least two degenerate
ground states. In the standard QAOA, with the reference state, the
Hamiltonian, and the mixer operator all respecting the symmetry $F$, the
solution will always be a symmetric superposition of computational basis
states. In ADAPT-QAOA, the selection criterion that determines the mixer
operator at each layer ensures that only symmetric operators get selected
[37]. Consequently, the solution is also a symmetric superposition. In this
work, we focus on the role of entanglement in the performance of the
algorithm. To eliminate the effect caused by the entanglement required in the
target state, we take either of the following two approaches. In the first we
measure one of the qubits before calculating the entanglement entropy, which
corresponds to projecting the state of the qubit to $0$ or $1$ in the
simulation. We refer to this as the symmetry-preserving case. The second is
directly breaking the symmetry of the Hamiltonian by adding to $H$ a small
perturbation $fZ_{0}$, where $f$ is a small positive constant. The 2-fold
ground space degeneracy is lifted, and the target ground state is a unique
product state unless an accidental degeneracy is present. In this approach the
Hamiltonian is

$\tilde{H}=fZ_{0}+\frac{1}{2}\sum_{i<j}w_{ij}Z_{i}Z_{j},$ (3)

which we refer to as the symmetry-breaking case.

We simulate the performance of both the standard QAOA and ADAPT-QAOA for
6-vertex degree-5 and 8-vertex degree-7 weighted regular graphs. In each case,
512 instances are generated in which the edge weights are randomly drawn from
the discrete set $\\{0.1,0.2,\dots,0.9\\}$. We set $f=0.05$ so that the
symmetry breaking term is always smaller than the energy gaps. To accommodate
the symmetry-breaking setting, we choose a symmetry-breaking reference state
in ADAPT-QAOA. Specifically, the state of qubit $0$ is initialized to
$|1\rangle$ while the other qubits are initially in the state $|+\rangle$.

The pool $\mathcal{P}$ from which the mixer operators are selected for ADAPT-
QAOA contains more options than the original mixer operator $M$ for the
standard QAOA. For a $n$-qubit system, the pool is

$\displaystyle\mathcal{P}=$
$\displaystyle\\{M=\sum_{i=0}^{n-1}X_{i},N=\sum_{i=0}^{n-1}Y_{i}\\}$
$\displaystyle\cup\\{X_{j},Y_{j}\\}_{j=0,\dots,n-1}$
$\displaystyle\cup\\{X_{j}X_{k},Y_{j}Y_{k},X_{j}Y_{k},X_{j}Z_{k},Y_{j}Z_{k}\\}_{j,k=0,\dots,n-1,j\neq
k}.$ (4)

This is a complete pool, according to Ref. [16], in that the ADAPT-QAOA ansatz
built from this pool can approximate any unitary to arbitrary precision given
sufficiently many layers. In Ref. [37], a significant improvement in
performance is observed for ADAPT-QAOA with this pool compared to standard
QAOA. Note that in the symmetry-breaking case we restore the operators that
anticommute with the operator $F$. At the $l$-th layer, the operator
$e^{-i\beta_{l}A_{l}}e^{-i\gamma_{l}\tilde{H}}$ is added to the optimal state
at the $(l-1)$-th layer, where the mixer operator $A_{l}$ is chosen from
$\mathcal{P}$ after initializing $\gamma_{l}$ to some small non-zero value
$\gamma_{0}$ and $\beta_{l}$ to $0$ [37]. In this work we set
$\gamma_{0}=0.01$. The selection of the mixer operators takes a greedy
approach and follows the ADAPT criterion: Among the operators in the pool,
choose the one that maximizes the magnitude of the derivative of the energy
(or more generally, the objective function) with respect to the new
variational parameter $\beta_{l}$ [13, 16, 37]. With the $l$-th mixer fixed,
all the $2l$ variational parameters in the current ansatz are then
(re-)optimized, where the previous $2(l-1)$ parameters are initialized to the
optimal values obtained in the previous layer. We set the total number of
layers to $p=15$ for the 6-vertex graphs and to $p=20$ for the 8-vertex
graphs.

There have been various strategies for initializing the variational parameters
in the standard QAOA [25, 29, 44, 45, 46], and an initialization strategy
based on optimal parameters for fewer layers has been shown to outperform
random initialization [46]. Here, we take an initialization strategy similar
to that for ADAPT-QAOA: At the $l$-th layer, the $2(l-1)$ parameters that
appear in the $(l-1)$-layer ansatz are initialized to the previously optimized
values, while the two new parameters in front of $\tilde{H}$ and $M$ are
initialized to $\gamma_{0}$ and $0$, respectively.

In summary, the ansatze in ADAPT-QAOA, ADAPT-QAOA in the symmetry breaking
setting, and the standard QAOA are, respectively,

$\displaystyle|\psi_{\rm
AQ}\rangle=\left(\prod_{l=1}^{p}e^{-i\beta_{l}A_{l}}e^{-i\gamma_{l}\tilde{H}}\right)\otimes\overset{n}{\underset{i=1}{\bigotimes}}|{+}\rangle_{i},$
(5) $\displaystyle|\psi_{\rm
AQsb}\rangle=\left(\prod_{l=1}^{p}e^{-i\beta_{l}A_{l}}e^{-i\gamma_{l}\tilde{H}}\right)|{1}\rangle_{0}\otimes\overset{n-1}{\underset{i=1}{\bigotimes}}|{+}\rangle_{i},$
(6) $\displaystyle|\psi_{\rm
QAOA}\rangle=\left(\prod_{l=1}^{p}e^{-i\beta_{l}M}e^{-i\gamma_{l}\tilde{H}}\right)\overset{n-1}{\underset{i=0}{\bigotimes}}|{+}\rangle_{i},$
(7)

For the optimal state produced at each layer, we calculate the entanglement
entropy for two types of bipartitions. One is the entanglement entropy across
a middle cut separating half of the qubits from the rest. This measure
overlooks the entanglement within either set of qubits, but any possible bias
introduced by this particular bipartition will be mitigated after averaging
over graphs with randomly generated edge weights. The other is the
entanglement entropy between each qubit and the remaining qubits, averaged
over all qubits. This measure is $0$ if and only if the system is in a product
state. By taking the entanglement entropy as the measure, we do not
distinguish different entanglement classes [47, 48, 49, 50, 51].

To see if entanglement is favorable when the ansatz is adaptive, we examine
the behavior of ADAPT-QAOA in different settings. Since ADAPT-QAOA has better
performance in the symmetry-preserving case than in the symmetry-breaking
case, we take the former for this simulation. First we vary the level of
flexibility for ADAPT-QAOA. If a quantum device has limited connectivity, it
is costly to realize an entangling gate between the qubits that are not
directly connected. This is common in quantum processors such as
superconducting devices, where one can adjust the mixer operator pool
accordingly. We compare the full pool with two restricted pools containing
two-qubit operators for the nearest neighbors on a ladder configuration (a
$2\times 3$ grid for the $6$-qubit case and $2\times 4$ grid for the $8$-qubit
case) and on a linear configuration, respectively.

Then we rescale the magnitude of the energy gradient in each ADAPT step to
increase (decrease) the chance that ADAPT-QAOA adds an entangling mixer
operator to the ansatz. Specifically, for the two-qubit operators in the pool,
we multiply the energy gradient by a factor of $1-\delta$ where
$0\leq\delta<1$. Compared with the previous case where extra entangling
operations are introduced as a byproduct of the gradient-based adaptive
procedure, this rescaling directly influences the ansatz construction based on
the entangling feature. We choose four values $\delta\in\\{\pm 0.1,\pm 0.5\\}$
in our simulation.

In addition to entanglement entropy, we also calculate the entanglement
spectrum, which reveals more information about a state [52]. We know that
$\mathcal{P}$ is a complete pool for ADAPT-QAOA, and the controllability of
the standard QAOA can be quantified by the dimension of the dynamical Lie
algebra generated by $\tilde{H}$ and $M$ [53, 46]. With a number of layers
that does not grow with the system size, neither ansatz has the capacity to
reach all possible states in the Hilbert space. This is a desired feature,
since one would face the challenge of barren plateaus in optimizing a
sufficiently generic ansatz [8, 9, 53]. To numerically test how close the
distribution of ansatz circuits is to that of random unitaries, we turn to the
entanglement spectrum, which has been employed to study the properties of the
Hamiltonian variational ansatz [42]. For a state $|{\psi}\rangle$ describing a
system partitioned into subsystems A and B, it is defined as the spectrum of
the operator $-\log(\rho_{\rm A})$, where

$\rho_{\rm A}={\rm Tr}_{\rm B}(|\psi\rangle\langle\psi|).$ (8)

At each layer, it is calculated for the ansatz state with the variational
parameters taking random values.

Throughout this work, the minimization is implemented with the Nelder-Mead
method in the SciPy library [54]. The codes are derived from those in Refs.
[13, 37] and are available here.

##  3 Results

###  3.1 Comparing ADAPT-QAOA with the standard QAOA

Figure 1: Energy error normalized to the MaxCut value (a, d), entanglement
entropy across a middle cut (b, e), and the average entanglement entropy
across 1-qubit cuts (c, f) for the optimized state with each number of QAOA
layers, in the symmetry-preserving case. The panels on the left (a, b, c) and
right (e, f, g) are for the 6-qubit and 8-qubit graphs, respectively. The
performance of ADAPT-QAOA (magenta) is compared to that generated by the
standard QAOA (blue). The scattered short lines are from different graph
instances while the solid and dashed lines are the mean and the median of
them, respectively. Figure 2: Energy error normalized to the MaxCut value (a,
d), entanglement entropy across a middle cut (b, e), and the average
entanglement entropy across 1-qubit cuts (c, f) for the optimized state with
each number of QAOA layers, in the symmetry-breaking case. The panels on the
left (a, b, c) and right (d, e, f) are for the 6-qubit and 8-qubit graphs,
respectively. The performance of ADAPT-QAOA (magenta) is compared to that
generated by the standard QAOA (blue). The scattered short lines are from
different graph instances while the solid and dashed lines are the mean and
the median of them, respectively. Figure 3: Maximum entanglement entropy in
the intermediate optimized states as a function of the final energy error in
the symmetry-preserving case (a, b, c, d) and the symmetry-breaking case (e,
f, g, h). The performance of ADAPT-QAOA (magenta dot) is compared to that
generated by the standard QAOA (blue cross). Each point is from one graph
instance. Figure 4: Number of CNOT gates (left, blue) and number of
variational parameters (right, orange) required by ADAPT-QAOA and the standard
QAOA with a symmetric reference state, when the energy error normalized to the
MaxCut value reaches the threshold $0.05$ in the symmetry-preserving case. The
error bars show the standard deviation. Panels (a) and (b) are for the 6-qubit
and 8-qubit graphs, respectively. The numbers are undercounted due to the
cutoff at 15 (20) layers for the 6-qubit (8-qubit) graphs.

As shown in Figures 1 and 2, with very few layers ADAPT-QAOA finds an
entangled optimized state. As the number of layers increases, the entanglement
entropy in the solution drops down close to zero as required for the ground
state. In contrast, the entanglement entropy of the optimal state found by the
standard QAOA increases fast in the first few layers but decreases more slowly
in the later layers. As shown in Fig. 1, the ADAPT-QAOA ansatz can generate
more entanglement at early stages than the standard QAOA ansatz for some graph
instances, with the effect of symmetry removed. As shown in Fig. 2, the
entanglement in the standard QAOA ansatz remains high throughout the
algorithm, largely due to the symmetry. In this case, the symmetry-breaking
ADAPT-QAOA generates less entanglement while still outperforming it as the
number of layers increases.

Fig. 3 shows the final energy error as a function of the maximum entanglement
entropy generated by the optimal state at any layer. We observe that there is
no definite relation between the achieved accuracy and the maximum
entanglement. In other words, creating more entanglement does not necessarily
accelerate the optimization process in generic quantum optimization
algorithms.

Both cases demonstrate that the additional flexibility in ADAPT-QAOA allows it
to control the rise and fall of entanglement to its advantage. With few
layers, both algorithms are capable of finding solutions with more
entanglement than required. With more layers, however, ADAPT-QAOA can remove
the excess entanglement far more efficiently than the standard QAOA. We
attribute this to the two-qubit mixer operators in the ADAPT-QAOA ansatz.
Their presence helps with both the production and the removal of entanglement
in the state whereas the Hamiltonian is the only operation in the standard
QAOA ansatz that can do so.

Fig. 4 shows the number of CNOT gates and the number of variational parameters
required in the ansatz circuit when the energy error gets below some
threshold. It has been shown that for classical approximate algorithms it hard
to get an approximation ratio better than $16/17\approx 94.1\%$ [55]. We set
the threshold to be $0.05$, below this value. Among the 512 graph instances,
the energy error has not reached the threshold at the last layer of ADAPT-QAOA
for 29 (16) instances of the $6$-qubit ($8$-qubit) graphs. These corresponds
to the cases where ADAPT-QAOA converges to an excited state and increasing the
number of layers does not lower the energy further. We exclude these cases
when calculating the average resources.

###  3.2 Comparing different levels of flexibility in ADAPT-QAOA

Figure 5: Energy error normalized to the MaxCut value (a, d), entanglement
entropy across a middle cut (b, e), and the average entanglement entropy
across 1-qubit cuts (c, f) for the optimized state with each number of QAOA
layers, in the symmetry-preserving case. The panels on the left (a, b, c) and
right (d, e, f) are for the 6-qubit and 8-qubit graphs, respectively. The
performance of ADAPT-QAOA with a full operator pool (magenta) is compared to
that with potential mixer operators are restricted to the nearest neighbors on
a ladder configuration (olive) or a linear configuration (teal). The scattered
short lines are from different graph instances while the solid and dashed
lines are the mean and the median of them, respectively.

The observation that ADAPT-QAOA is able to generate an appropriate amount of
entanglement can be reinforced by examining its performance as we constrain
its flexibility to varying degrees. With fewer options for entangling
operations, ADAPT-QAOA exhibits slower convergence when averaging over graphs
with different edge weights. One feature accompanying slower convergence is
less efficient entanglement generation, as shown in Fig. 5. In the first few
layers, the energy expectation values of the optimal states are close to each
other regardless of the operator pool. Despite similar energies, ADAPT-QAOA
with full connectivity produces more entanglement entropy than with reduced
connectivity. With more layers, it is able to disentangle more quickly and get
close to the target state whereas reduced connectivity leads to a solution
with more entanglement entropy than needed. In this case, better overall
performance coincides with more entanglement entropy at earlier stages of the
algorithm, an indication that more entanglement than required in the target
state can be helpful.

###  3.3 Comparing ansatze favoring or penalizing entanglement

Figure 6: Difference between the ADAPT-QAOA optimized state with a penalty
$\delta$ and that without the penalty, in energy error (a, d), entanglement
entropy across a middle cut (b, e), and the average entanglement entropy
across 1-qubit cuts (c, f) at each number of QAOA layers in the symmetry-
preserving case. The panels on the left (a, b, c) and right (d, e, f) are for
the 6-qubit and 8-qubit graphs, respectively. We omit the individual graph
instances but retain the mean (solid line) and the median (dashed line) only.

Having seen that ADAPT-QAOA, given a higher level of flexibility, tends to
generate more entanglement at early stages, we now explore whether manually
boosting entanglement is beneficial. We focus on the difference between the
values obtained by ADAPT-QAOA with a penalty term $\delta$ and those obtained
without the penalty, averaged over different graph instances, as shown in Fig.
6. In the first 3-4 layers ADAPT-QAOA reaches similar energy errors across
different $\delta$’s. As the number of layers increases further, a negative
$\delta$ favoring entangling operators outperforms a positive $\delta$
penalizing entangling operators on average. At these layers, the optimized
states associated with $\delta<0$ has less entanglement entropy than those
associated with $\delta>0$. This again underlines the importance of the
ability to disentangle the state. We remark that the reward or penalty
introduced by rescaling the energy gradient is different from adding fixed
entangling operations to the ansatz. It still compares different entangling
operations based on the energy gradient criterion while it is unclear which
entangling operations would be useful in the latter case.

###  3.4 Entanglement spectrum

Figure 7: Entanglement spectrum, entanglement entropy across a middle cut, and
the average entanglement entropy across 1-qubit cuts for the ADAPT-QAOA ansatz
(a, b) and the standard QAOA ansatz (c, d), respectively, with the variational
parameters randomly sampled between $0$ and $20\pi$ in the symmetry-preserving
case. We average over 50 $6$-qubit graph instances and the error bars on the
entanglement entropy represent the standard deviation among the graph
instances.

With the ability to take any operators from the pool $\mathcal{P}$, ADAPT-QAOA
can in principle generate all possible unitaries if there are no restrictions
on the number of layers. For each problem, the operator selection process
ensures that the ansatz is specific. As the number of layers increases, the
ansatz becomes more expressive. We compare the ansatze produced at each layer
by ADAPT-QAOA and the standard QAOA. In both cases, we replace the optimized
variational parameters in the ansatz with values randomly drawn from
$[0,20\pi)$, and average over $1000$ such states for the ansatz associated
with one graph instance. This offers an indirect probe into how general the
possible states for a chosen ansatz can be.

In Fig. 7, we present the entanglement spectrum across a middle cut given each
number of layers, averaged over 50 $6$-qubit graph instances since the
simulation is costly. Qualitatively, the entanglement spectrum becomes more
similar to that produced by random unitaries as the number of layers increases
for both ADAPT-QAOA and the standard QAOA. Interestingly, in terms of the
average entanglement spectrum produced, the standard QAOA ansatz approaches
the random unitary more quickly. This suggests that the ADAPT-QAOA ansatz is
less generic, leading to easier optimization of the variational parameters.

##  4 Conclusion and discussion

In this work we investigate the role of entanglement in solving MaxCut
problems with quantum optimization algorithms, where a finite amount of
entanglement is not required in the target state. In the context of QAOA and
its adaptive variation ADAPT-QAOA, we find that the algorithm performance can
benefit from entanglement generation in the process. On the other hand, the
relation between the convergence speed and the amount of entanglement in the
intermediate state is not a simple positive correlation and it can be
counterproductive to create too much entanglement.

In particular, by comparing the entanglement generated by ADAPT-QAOA at
various stages of the algorithm to that generated by the standard QAOA, we
observe that although the standard QAOA can quickly generate more entanglement
entropy with only a few layers in the ansatz, it is inefficient in removing
excess entanglement as the number of layers increases. Consequently, at later
stages it does not perform as well as ADAPT-QAOA, in which both the
Hamiltonian and the selected two-qubit mixer operators contribute to
entanglement generation and removal. By examining ADAPT-QAOA with different
mixer operator pools, we find that given the largest degree of flexibility, it
produces more entanglement entropy at earlier stages and converges faster at
later stages. This hints at the promise of entangled ansatze in quantum
optimization algorithms. We stress that more entanglement entropy by itself
does not imply faster convergence in the entire process. Rather, it is
important to have suitable entangling operations. We also find that in ADAPT-
QAOA, manually favoring entangling mixer operators in the ansatz improves the
convergence on average. Finally, the average entanglement spectrum of the
possible states for each ansatz suggests that with a given number of layers,
ADAPT-QAOA is less expressive than the standard QAOA, which can reduce the
difficulty in the classical optimization component of the variational
algorithm.

These observations provide qualitative guidance in designing quantum
optimization algorithms. Specifically, variational algorithms equipped with
flexibility in entangling operations can outperform the algorithms with
limited entangling operations. From this perspective, ADAPT-QAOA and the ADAPT
approach in general demonstrate great potential in generating a suitable
amount of entanglement for the optimization task. To offer better flexibility,
the mixer operator pool should include multiqubit operators beyond those
supported on nearest neighbors. It will thus be easier to demonstrate ADAPT-
QAOA on platforms with less limitation on entangling operations between
arbitrary pairs of qubits, such as trapped ion systems [56, 57, 58] and
Rydberg atoms [59, 60, 61].

In our work, entanglement is quantified by the entanglement entropy associated
with a bipartition, which does not reveal the many-body structure of the
entanglement. Multipartite entanglement, where the number of parties grows
with the system size, is necessary if the quantum algorithm is exponentially
hard to simulate classically [18]. It thus remains to be investigated whether
the heuristic quantum optimization algorithms studied here offer any advantage
over classical algorithms.

## Acknowledgements

S. E. E. acknowledges support from the US Department of Energy (Award No. DE-
SC0019318). E.B. and N.J.M. acknowledge support from the US Department of
Energy (Award No. DE-SC0019199).

## References

  * Peruzzo et al. [2014] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien.  A variational eigenvalue solver on a photonic quantum processor.  _Nat. Phys._ , 5:4213, 2014.  doi: 10.1038/ncomms5213.
  * Farhi et al. [2014] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A Quantum Approximate Optimization Algorithm.  _arXiv e-prints_ , art. arXiv:1411.4028, November 2014.  doi: 10.48550/arXiv.1411.4028.
  * Farhi and Harrow [2016] Edward Farhi and Aram W Harrow.  Quantum Supremacy through the Quantum Approximate Optimization Algorithm.  _arXiv e-prints_ , art. arXiv:1602.07674, February 2016.  doi: 10.48550/arXiv.1602.07674.
  * McClean et al. [2016] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik.  The theory of variational hybrid quantum-classical algorithms.  _New J. Phys._ , 18:023023, 2016.  doi: 10.1088/1367-2630/18/2/023023.
  * Cerezo et al. [2021a] M. Cerezo, Andrew Arrasmith, and et al. Ryan Babbush.  Variational quantum algorithms.  _Nat. Rev. Phys._ , 3:625–644, 2021a.  doi: 10.1038/s42254-021-00348-9.
  * Kandala et al. [2017] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  _Nature_ , 549:242–246, 2017.  doi: 10.1038/nature23879.
  * Sim et al. [2019] S. Sim, P.D. Johnson, and A. Aspuru-Guzik.  Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms.  _Adv. Quantum Technol._ , 2:1900070, 2019.  doi: 10.1002/qute.201900070.
  * McClean et al. [2018] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  _Nat. Commun._ , 9:4812, Nov 2018.  doi: 10.1038/s41467-018-07090-4.
  * Cerezo et al. [2021b] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles.  Cost function dependent barren plateaus in shallow parametrized quantum circuits.  _Nat. Commun._ , 12:1791, Mar 2021b.  doi: 10.1038/s41467-021-21728-w.
  * Arrasmith et al. [2022] Andrew Arrasmith, Zoë Holmes, M. Cerezo, and Patrick J. Coles.  Equivalence of quantum barren plateaus to cost concentration and narrow gorges, 2022.
  * Holmes et al. [2022] Zoë Holmes, Kunal Sharma, M. Cerezo, and Patrick J. Coles.  Connecting ansatz expressibility to gradient magnitudes and barren plateaus.  _PRX Quantum_ , 3:010313, Jan 2022.  doi: 10.1103/PRXQuantum.3.010313.
  * Wecker et al. [2015] Dave Wecker, Matthew B. Hastings, and Matthias Troyer.  Progress towards practical quantum variational algorithms.  _Phys. Rev. A_ , 92:042303, Oct 2015.  doi: 10.1103/PhysRevA.92.042303.
  * Grimsley et al. [2019] Harper R. Grimsley, Edwin Barnes, Sophia E. Economou, and Nicholas J. Mayhall.  An adaptive variational algorithm for exact molecular simulations on a quantum computer.  _Nat. Commun._ , 10:3007, July 2019.  doi: 10.1038/s41467-019-10988-2.
  * Hadfield et al. [2019] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas.  From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.  _Algorithms_ , 12(2), 2019.  ISSN 1999-4893.  doi: 10.3390/a12020034.
  * Choquette et al. [2021] Alexandre Choquette, Agustin Di Paolo, Panagiotis Kl. Barkoutsos, David Sénéchal, Ivano Tavernelli, and Alexandre Blais.  Quantum-optimal-control-inspired ansatz for variational quantum algorithms.  _Phys. Rev. Research_ , 3:023092, May 2021.  doi: 10.1103/PhysRevResearch.3.023092.
  * Tang et al. [2021] Ho Lun Tang, V.O. Shkolnikov, George S. Barron, Harper R. Grimsley, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou.  Qubit-adapt-vqe: An adaptive algorithm for constructing hardware-efficient ansätze on a quantum processor.  _PRX Quantum_ , 2:020310, Apr 2021.  doi: 10.1103/PRXQuantum.2.020310.
  * Shkolnikov et al. [2023] V. O. Shkolnikov, Nicholas J. Mayhall, Sophia E. Economou, and Edwin Barnes.  Avoiding symmetry roadblocks and minimizing the measurement overhead of adaptive variational quantum eigensolvers.  _Quantum_ , 7, 2023.  doi: 10.22331/q-2023-06-12-1040.
  * Jozsa and Linden [2003] Richard Jozsa and Noah Linden.  On the role of entanglement in quantum-computational speed-up.  _Proc. R. Soc. Lond. A._ , 459:2011–2032, 2003.  doi: 10.1098/rspa.2002.1097.
  * Gross et al. [2009] D. Gross, S. T. Flammia, and J. Eisert.  Most quantum states are too entangled to be useful as computational resources.  _Phys. Rev. Lett._ , 102:190501, May 2009.  doi: 10.1103/PhysRevLett.102.190501.
  * Woitzik et al. [2020] Andreas J. C. Woitzik, Panagiotis Kl. Barkoutsos, Filip Wudarski, Andreas Buchleitner, and Ivano Tavernelli.  Entanglement production and convergence properties of the variational quantum eigensolver.  _Phys. Rev. A_ , 102:042402, Oct 2020.  doi: 10.1103/PhysRevA.102.042402.
  * Lucas [2014] Andrew Lucas.  Ising formulations of many np problems.  _Frontiers in Physics_ , 2:5, 2014.  doi: 10.3389/fphy.2014.00005.
  * Kochenberger et al. [2014] Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng L u, Haibo Wang, and Yang Wang.  The unconstrained binary quadratic programming problem: a survey.  _J. Comb. Optim._ , 28:58–81, 2014.  doi: 10.1007/s10878-014-9734-0.
  * Hadfield et al. [2017] Stuart Hadfield, Zhihui Wang, Eleanor G. Rieffel, Bryan O’Gorman, Davide Venturelli, and Rupak Biswas.  Quantum approximate optimization with hard and soft constraints.  In _Proceedings of the Second International Workshop on Post Moores Era Supercomputing_ , PMES’17, page 15–21, New York, NY, USA, 2017. Association for Computing Machinery.  ISBN 9781450351263.  doi: 10.1145/3149526.3149530.
  * Oh et al. [2019] Young-Hyun Oh, Hamed Mohammadbagherpoor, Patrick Dreher, Anand Singh, Xianqing Yu, and Andy J. Rindos.  Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms.  _arXiv e-prints_ , art. arXiv:1911.00595, November 2019.  doi: 10.48550/arXiv.1911.00595.
  * Shaydulin et al. [2019] Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson.  Multistart methods for quantum approximate optimization.  In _2019 IEEE High Performance Extreme Computing Conference (HPEC)_ , pages 1–8, 2019.  doi: 10.1109/HPEC.2019.8916288.
  * Tabi et al. [2020] Zsolt Tabi, Kareem H. El-Safty, Zsófia Kallus, Péter Hága, Tamás Kozsik, Adam Glos, and Zoltán Zimborás.  Quantum optimization for the graph coloring problem with space-efficient embedding.  In _2020 IEEE International Conference on Quantum Computing and Engineering (QCE)_ , pages 56–62, 2020.  doi: 10.1109/QCE49297.2020.00018.
  * Bravyi et al. [2022] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang.  Hybrid quantum-classical algorithms for approximate graph coloring.  _Quantum_ , 6:678, 2022.  doi: 10.22331/q-2022-03-30-678.
  * Weggemans et al. [2022] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman.  Solving correlation clustering with qaoa and a rydberg qudit system: a full-stack approach.  _Quantum_ , 6:687, 2022.  doi: 10.22331/q-2022-04-13-687.
  * Zhou et al. [2020] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin.  Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices.  _Phys. Rev. X_ , 10:021067, Jun 2020.  doi: 10.1103/PhysRevX.10.021067.
  * Akshay et al. [2020] V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte.  Reachability deficits in quantum approximate optimization.  _Phys. Rev. Lett._ , 124:090504, Mar 2020.  doi: 10.1103/PhysRevLett.124.090504.
  * Bravyi et al. [2020] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang.  Obstacles to variational quantum optimization from symmetry protection.  _Phys. Rev. Lett._ , 125:260505, Dec 2020.  doi: 10.1103/PhysRevLett.125.260505.
  * Farhi et al. [2020a] Edward Farhi, David Gamarnik, and Sam Gutmann.  The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case.  _arXiv e-prints_ , art. arXiv:2004.09002, April 2020a.  doi: 10.48550/arXiv.2004.09002.
  * Farhi et al. [2020b] Edward Farhi, David Gamarnik, and Sam Gutmann.  The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples.  _arXiv e-prints_ , art. arXiv:2005.08747, May 2020b.  doi: 10.48550/arXiv.2005.08747.
  * Guerreschi and Matsuura [2019] G. G. Guerreschi and A. Y. Matsuura.  Qaoa for max-cut requires hundreds of qubits for quantum speed-up.  _Sci. Rep._ , 9:6903, 2019.  doi: 10.1038/s41598-019-43176-9.
  * Harrigan et al. [2021] Matthew P. Harrigan, Kevin J. Sung, and et al Matthew Neeley.  Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.  _Nat. Phys._ , 17:332–336, 2021.  doi: 10.1038/s41567-020-01105-y.
  * Weidenfeller et al. [2022] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J. Egger.  Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware.  _Quantum_ , 6, 2022.  doi: 10.22331/q-2022-12-07-870.
  * Zhu et al. [2022] Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou.  Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer.  _Phys. Rev. Res._ , 4:033029, Jul 2022.  doi: 10.1103/PhysRevResearch.4.033029.  URL https://link.aps.org/doi/10.1103/PhysRevResearch.4.033029.
  * Warren et al. [2022] Ada Warren, Linghua Zhu, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou.  Adaptive variational algorithms for quantum Gibbs state preparation.  _arXiv e-prints_ , art. arXiv:2203.12757, March 2022.  doi: 10.48550/arXiv.2203.12757.
  * Ekert and Jozsa [1998] Artur Ekert and Richard Jozsa.  Quantum algorithms: entanglement–enhanced information processing.  _Phil. Trans. R. Soc. A._ , 356:1769–1782, 1998.  doi: https://doi.org/10.1098/rsta.1998.0248.
  * Patti et al. [2021] Taylor L. Patti, Khadijeh Najafi, Xun Gao, and Susanne F. Yelin.  Entanglement devised barren plateau mitigation.  _Phys. Rev. Research_ , 3:033090, Jul 2021.  doi: 10.1103/PhysRevResearch.3.033090.
  * Ortiz Marrero et al. [2021] Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe.  Entanglement-induced barren plateaus.  _PRX Quantum_ , 2:040316, Oct 2021.  doi: 10.1103/PRXQuantum.2.040316.
  * Wiersema et al. [2020] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen.  Exploring entanglement and optimization within the hamiltonian variational ansatz.  _PRX Quantum_ , 1:020319, Dec 2020.  doi: 10.1103/PRXQuantum.1.020319.
  * Díez-Valle et al. [2021] Pablo Díez-Valle, Diego Porras, and Juan José García-Ripoll.  Quantum variational optimization: The role of entanglement and problem hardness.  _Phys. Rev. A_ , 104:062426, Dec 2021.  doi: 10.1103/PhysRevA.104.062426.
  * Sack and Serbyn [2021] Stefan H. Sack and Maksym Serbyn.  Quantum annealing initialization of the quantum approximate optimization algorithm.  _Quantum_ , 5:491, jul 2021.  doi: 10.22331/q-2021-07-01-491.
  * Li et al. [2023] Junde Li, Mahabubul Alam, and Swaroop Ghosh.  Large-scale quantum approximate optimization via divide-and-conquer.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 42(6):1852–1860, 2023.  doi: 10.1109/TCAD.2022.3212196.
  * Zhang et al. [2022] Bingzhi Zhang, Akira Sone, and Quntao Zhuang.  Quantum computational phase transition in combinatorial problems.  _npj Quantum Inf_ , 8, 2022.  doi: 10.1038/s41534-022-00596-2.
  * Coffman et al. [2000] Valerie Coffman, Joydip Kundu, and William K. Wootters.  Distributed entanglement.  _Phys. Rev. A_ , 61:052306, Apr 2000.  doi: 10.1103/PhysRevA.61.052306.
  * Wei and Goldbart [2003] Tzu-Chieh Wei and Paul M. Goldbart.  Geometric measure of entanglement and applications to bipartite and multipartite quantum states.  _Phys. Rev. A_ , 68:042307, Oct 2003.  doi: 10.1103/PhysRevA.68.042307.
  * Virmani et al. [2001] S Virmani, M.F Sacchi, M.B Plenio, and D Markham.  Optimal local discrimination of two multipartite pure states.  _Physics Letters A_ , 288(2):62–68, 2001.  doi: https://doi.org/10.1016/S0375-9601(01)00484-4.
  * Plenio and Virmani [2007] Martin B. Plenio and Shashank Virmani.  An introduction to entanglement measures.  _Quantum Inf. Comput._ , 7(1):1–51, 2007.  doi: 10.26421/QIC7.1-2-1.
  * Horodecki et al. [2009] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki.  Quantum entanglement.  _Rev. Mod. Phys._ , 81:865–942, Jun 2009.  doi: 10.1103/RevModPhys.81.865.
  * Li and Haldane [2008] Hui Li and F. D. M. Haldane.  Entanglement spectrum as a generalization of entanglement entropy: Identification of topological order in non-abelian fractional quantum hall effect states.  _Phys. Rev. Lett._ , 101:010504, Jul 2008.  doi: 10.1103/PhysRevLett.101.010504.
  * Larocca et al. [2022] Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J. Coles, and M. Cerezo.  Diagnosing barren plateaus with tools from quantum optimal control.  _Quantum_ , 6, 2022.  doi: 10.22331/q-2022-09-29-824.
  * Virtanen et al. [2020] Pauli Virtanen, Ralf Gommers, and et al Travis E. Oliphant.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  _Nature Methods_ , 17:261–272, 2020.  doi: 10.1038/s41592-019-0686-2.
  * Håstad [2001] Johan Håstad.  Some optimal inapproximability results.  _Journal of the ACM_ , 48(4):798–859, July 2001\.  doi: 10.1145/502090.502098.
  * Landsman et al. [2019] K. A. Landsman, Y. Wu, P. H. Leung, D. Zhu, N. M. Linke, K. R. Brown, L. Duan, and C. Monroe.  Two-qubit entangling gates within arbitrarily long chains of trapped ions.  _Phys. Rev. A_ , 100:022332, Aug 2019.  doi: 10.1103/PhysRevA.100.022332.
  * Zhang et al. [2020] Chi Zhang, Fabian Pokorny, Weibin Li, Gerard Higgins, Andreas Pöschl, Igor Lesanovsky, and Markus Hennrich.  Submicrosecond entangling gate between trapped ions via rydberg interaction.  _Nature_ , 580:345–349, 2020.  doi: 10.1038/s41586-020-2152-9.
  * Blümel et al. [2021] Reinhold Blümel, Nikodem Grzesiak, Neal Pisenti, Kenneth Wright, and Yunseong Nam.  Power-optimal, stabilized entangling gate between trapped-ion qubits.  _npj Quantum Inf_ , 7:147, 2021.  doi: 10.1038/s41534-021-00489-w.
  * Levine et al. [2019] Harry Levine, Alexander Keesling, Giulia Semeghini, et al.  Parallel implementation of high-fidelity multiqubit gates with neutral atoms.  _Phys. Rev. Lett._ , 123:170503, Oct 2019.  doi: 10.1103/PhysRevLett.123.170503.
  * Graham et al. [2019] T. M. Graham, M. Kwon, B. Grinkemeyer, Z. Marra, X. Jiang, M. T. Lichtman, Y. Sun, M. Ebert, and M. Saffman.  Rydberg-mediated entanglement in a two-dimensional neutral atom qubit array.  _Phys. Rev. Lett._ , 123:230501, Dec 2019.  doi: 10.1103/PhysRevLett.123.230501.
  * Graham et al. [2022] T.M. Graham, Y. Song, J. Scott, et al.  Multi-qubit entanglement and algorithms on a neutral-atom quantum computer.  _Nature_ , 604:457–462, 2022.  doi: 10.1038/s41586-022-04603-6.


# Generative Adversarial Stacked Autoencoders

Ariel Ruiz-Garcia
LatinX in AI and SeeChange.ai
Manchester, United Kingdom
&Ibrahim Almakky, Vasile Palade, Luke Hicks
Coventry University
Coventry, United Kingdom
<EMAIL_ADDRESS>Most of this work was done while at Coventry
University.ibrahimalmakky@gmail.comvasile.palade<EMAIL_ADDRESS>
##  1 Introduction

Generative Adversarial Networks (GANs) [1], [2] have become predominant in
image generation tasks. Their success is attributed to the training regime
which employs two models: a generator $G$ and discriminator $D$ that compete
in a minimax zero sum game. Nonetheless, GANs are difficult to train due to
their sensitivity to hyperparameter and parameter initialisation, which often
leads to vanishing gradients, non-convergence, or mode collapse, where the
generator is unable to create samples with different variations.

In this work, we propose a novel Generative Adversarial Stacked Convolutional
Autoencoder (GASCA) model and a generative adversarial gradual greedy layer-
wise learning algorithm designed to train Adversarial Autoencoders in an
efficient and incremental manner. Our training approach produces images with
significantly lower reconstruction error than vanilla joint training.

##  2 Generative Adversarial Stacked Convolutional Autoencoders

Let $x_{\varphi}$ be a sample from the data distribution $p_{d}(x_{\varphi})$
and $x_{\mu}$ the sample from the data distribution $p_{d}(x_{\mu})$ used as
the desired target reconstruction. The autoencoder $G$ model in a GASCA learns
to map $x_{\varphi}$ to a latent space $z$ and back to a reconstruction $y$
that resembles $x_{\mu}$ and lies in the distribution $q(y)$. The
discriminator $D$ attempts to differentiate between $y$ and $x_{\mu}$.

In the conventional adversarial autoencoder framework [2], a distribution
$p(z)$ —often a Gaussian distribution—is imposed on $q(z)$ by estimating the
divergence between $q$ and $p$. This imposition can be used to produce
reconstructions with specific features. However, in order to produce
reconstructions that are as close as possible to the desired target image
$x_{\mu}$, instead of imposing random noise on the hidden representation
vector, the GASCA model imposes $p_{d}(x_{\mu})$ on $q(y)$ in the following
manner: $q(y)=\mathbb{R}_{x_{\mu}}q(y|x_{\mu})p_{d}(x_{\varphi})dx_{\mu}$.
With this formulation, the discriminator model $D$ is optimised to rate
samples from $p_{d}(x_{\mu})$ with a higher probability, and samples from
$q(y)$ with a low probability. Formally, this is defined as:
$\nabla_{\theta_{d}}\frac{1}{m}\sum_{i=1}^{m}\Big{[}\log
D(x^{(i)}_{\mu})+\log\big{(}1-D(G(y^{(i)}))\big{)}\Big{]}$ where $x_{\mu}$ is
an input image and $x_{\varphi}$ is the target reconstruction image and $m$ is
the number of samples. Note that since $(x_{\varphi}=x_{\mu})$ is not
necessarily true, the discriminator $D$ is not guaranteed to see the input to
$G$.

The objective of the autoencoder model $G$ is to convince the discriminator
model $D$ that a sample reconstruction $y$ was drawn from the data
distribution $p_{d}(x_{\mu})$ and not from $q(y)$. This optimisation is done
according to:
$\nabla_{\theta_{g}}\frac{1}{m}\sum_{i=1}^{m}\log\Big{(}1-D\big{(}G(y^{(i)})\big{)}\Big{)}$.
Furthermore, since GANs are known to be difficult to train due to their
sensitivity to hyper-parameters and parameters initialisation, which often
leads to mode collapse, we propose training the GASCA model in a Greedy Layer
Wise (GLW) [3] fashion. However, since the greedy nature of GLW leads to error
accumulation as individual layers are trained and stacked [4], we build on the
gradual greedy layer-wise training algorithm from [4] and adapt it for
adversarial autoencoders. We introduce the GAN gradual greedy layer-wise
(GANGGLW) training framework and formally define it in Algorithm 1.

Algorithm 1 Given a training set $X$ and validation set $\tilde{X}$ each
containing input images $x_{\varphi}$ and target images $x_{\mu}$, $m$ shallow
autoencoders, an unsupervised feature learning algorithm $\mathcal{L}$ which
returns a trained shallow autoencoder and a discriminator model, and a fine-
tuning algorithm $\mathcal{T}$: train $D^{1}$ and $G^{1}$ jointly with raw
data and add them to their corresponding stacks $G$ and $D$. For the remaining
autoencoders and generator models: encode $X$ and $\tilde{X}$ using the
encoder layers $\xi$ from the stack $G$. Create a new discriminator $D^{k}$
and train together with the new autoencoder $G^{k}$ and add them to their
corresponding stacks. Fine-tune $G$ on raw pixel data. Forward propagate
$x_{\varphi}\subset X$ through $G$ and use the resulting features, along with
$x_{\mu}$, to fine-tune $D$ for binary classification.

1:$[G^{1},D^{1}]\leftarrow\mathcal{L}(G^{1},D^{1},X,\tilde{X})$

2:$G\leftarrow G\circ G^{1}$

3:$D\leftarrow D\circ D^{1}$

4:for $k=2$, …, $m$ do

5: $[\xi,\delta]\leftarrow D$

6: $[X_{g},\tilde{X}_{g}]\leftarrow\xi(X,\tilde{X})$

7: $[G^{k},D^{k}]\leftarrow\mathcal{L}(G^{k},D^{k},X_{d},\tilde{X}_{d})$

8: $G\leftarrow G^{(k)}\circ G$

9: $D\leftarrow D^{(k)}\circ D$

10: $G\leftarrow\mathcal{T}(G,X,\tilde{X})$

11: $X_{\varphi}\leftarrow G(x_{\varphi})$

12: $D\leftarrow\mathcal{T}(D,\\{X_{\varphi},x_{\mu}\subset X\\})$

13:end for

14:return $G,D$

By fine-tuning $G$ and $D$ in Algorithm 1 we avoid error accumulation from one
layer to the next and reduce the required number of fine-tuning steps for
deeper layers.

The key difference in GANGGLW as opposed to conventional GLW is that each time
a new layer or shallow autoencoder is trained, the entire model is fine-tuned
on raw data. This allows for stronger inter-layer connections and
significantly decreased error accumulation. Moreover, both the discriminator
and generator are trained in an incremental manner where layers are added one
by one.

This formulation of GAN autoencoder also allows for the target reconstructions
to be different than the input image as in conventional autoencoders. Figure 1
shows a sample reconstruction of facial images with different poses (up to
$60$ degrees), where the same image (at $0$ degrees, top right) is used as
target reconstruction. Our GANGGLW training approach has also proven to be
effective when used a as a pre-training approach for supervised tasks such as
classification, where it produces state-of-the-art accuracy. An extended
version of this work has been published in [5].

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Figure 1: Sample reconstructions produced by a GASCA model on face images from
[6].

## List of References

  * [1] J. Schmidhuber, “Generative adversarial networks are special cases of artificial curiosity (1990) and also closely related to predictability minimization (1991),” Neural Networks, vol. 127, pp. 58 – 66, 2020.
  * [2] A. Makhzani, J. Shlens, N. Jaitly, I. Goodfellow, and B. Frey, “Adversarial Autoencoders,” 2015.
  * [3] Y. Bengio, P. Lamblin, D. Popovici, and H. Larochelle, “Greedy layer-wise training of deep networks,” in Proceedings of the 19th International Conference on Neural Information Processing Systems, NIPS’06, (Cambridge, MA, USA), p. 153–160, MIT Press, 2006.
  * [4] A. Ruiz-Garcia, V. Palade, M. Elshaw, and I. Almakky, “Deep Learning for Illumination Invariant Facial Expression Recognition,” in Proceedings of the International Joint Conference on Neural Networks, (Rio de Janeiro), IEEE, 2018.
  * [5] A. Ruiz-Garcia, V. Palade, M. Elshaw, and M. Awad, “Generative adversarial stacked autoencoders for facial pose normalization and emotion recognition,” in 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1–8, 2020.
  * [6] R. Gross, I. Matthews, J. Cohn, T. Kanade, and S. Baker, “Multi-pie,” in 2008 8th IEEE International Conference on Automatic Face Gesture Recognition, pp. 1–8, 2008.


# Real-time Timbre Transfer and Sound Synthesis using DDSP

Francesco Ganis, Erik Frej Knudesn, Søren V. K. Lyster, Robin Otterbein, David
Südholt and Cumhur Erkut
Department of Architecture, Design, and Media Technology
Aalborg University Copenhagen, Denmark
https://www.smc.aau.dk/

###### Abstract

Neural audio synthesis is an actively researched topic, having yielded a wide
range of techniques that leverages machine learning architectures. Google
Magenta elaborated a novel approach called Differential Digital Signal
Processing (DDSP) that incorporates deep neural networks with preconditioned
digital signal processing techniques, reaching state-of-the-art results
especially in timbre transfer applications. However, most of these techniques,
including the DDSP, are generally not applicable in real-time constraints,
making them ineligible in a musical workflow. In this paper, we present a
real-time implementation of the DDSP library embedded in a virtual synthesizer
as a plug-in that can be used in a Digital Audio Workstation. We focused on
timbre transfer from learned representations of real instruments to arbitrary
sound inputs as well as controlling these models by MIDI. Furthermore, we
developed a GUI for intuitive high-level controls which can be used for post-
processing and manipulating the parameters estimated by the neural network. We
have conducted a user experience test with seven participants online. The
results indicated that our users found the interface appealing, easy to
understand, and worth exploring further. At the same time, we have identified
issues in the timbre transfer quality, in some components we did not
implement, and in installation and distribution of our plugin. The next
iteration of our design will address these issues. Our real-time MATLAB and
JUCE implementations are available at https://github.com/SMC704/juce-ddsp and
https://github.com/SMC704/matlab-ddsp, respectively.

##  1 Introduction

Sound synthesizers have been widely used in music production since the late
50s. Because of their inner complexity, many musicians and producers polish
presets’ parameters until they reach the desired sound. This procedure is
time-consuming and sometimes results in failed attempts to achieve a desired
sound.

Much research has been done in the area of automating the generation of these
sounds through the aid of machine learning and neural networks. Common
approaches included directly generating the waveform in the time domain [1] or
predicting synthesis parameters based on hand-picked analysis features [2]. In
their 2020 paper on Differentiable Digital Signal Processing (DDSP)[3], Engel
et al. proposed a novel approach to neural audio synthesis. Rather than
generating signals directly in the time or frequency domain, DDSP offers a
complete end-to-end toolbox consisting of a synthesizer based on Spectral
Modeling Synthesis (SMS) [4], and an autoencoder neural network architecture
that takes care of both extracting analysis features and predicting synthesis
parameters.

The authors of the DDSP paper released a public demonstration of ”tone
transfer”111https://sites.research.google/tonetransfer, last accessed on
2020-11-30, allowing the user to upload their own recordings, select from a
list of models trained on various instruments and ”transfer” their recorded
melodies to the sound of a trumpet, a violin etc.

Figure 1: Our real-time DDSP Synthesizer GUI.

We implemented the DDSP back-end as a virtual instrument playable in real-
time. Figure 1 shows the GUI of our synthesizer. This paper documents the
background, our requirement-driven design and implementation approach,
including model compenents and training, the GUI design, and user experience
evaluation. The structure of this paper follows these main topics in order.

Besides our contribution to the real-time neural audio synthesis, we release
our real-time MATLAB and JUCE implementations at
https://github.com/SMC704/juce-ddsp and https://github.com/SMC704/matlab-ddsp,
respectively.

##  2 Background

In addition to the DDSP paper [3], our work is inspired by the commercially
produced additive synthesizer called _Razor_ by Native Instruments[5]. Razor’s
core consists of a powerful additive synthesizer and features various
modulation options for manipulating the sound output. What is especially
interesting about Razor is that every modulation option (e.g. filters, stereo
imaging, reverbs and delays) is actually modulating individual partial
harmonics (non-integer multiples of the fundamental frequency) in the additive
synthesis engine. Furthermore, Razor enables musicians and producers to
intuitively control partials via different parameters while relying on a
visual representation of partial manipulation. We therefore focused on the
harmonic and the stochastic components of the DDSP.

###  2.1 Harmonic Oscillator / Additive Synthesizer

The additive synthesizer is the main core of the whole synthesis and is
responsible for generating all the harmonic components of the reconstructed
sound. The output is characterized by the sum of several harmonic integer
multiples of the fundamental frequency $f_{0}$:

$f_{k}=k\cdot f_{0}(n).$ (1)

In order to generate the harmonics, we can implement $k$ oscillators in the
discrete time:

$x(n)=\sum_{k=1}^{K}A_{k}(n)\cdot sin(\phi_{k}(n)),$ (2)

where $A_{k}(n)$ is the time-varying amplitude of the $k_{th}$ sinusoidal
component and $\phi_{k}(n)$ is its instantaneous phase. $\phi_{k}(n)$ is
obtained using equation 3.

$\phi_{k}(n)=2\pi\sum_{m=0}^{n}f_{k}(m)+\phi_{0,k}.$ (3)

The only two parameters necessary to control the synthesizer are the frequency
$f_{0}(n)$ and the harmonic amplitudes $A_{k}(n)$. These are retrieved
directly from the input sound using the encoder contained in the autoencoder
network. As reported in [3], the network outputs are scaled and normalized to
fall within an interpretable value range for the synthesizer

###  2.2 Filtered Noise / Subtractive Synthesizer

The subtractive synthesis is used to recreate the non-harmonic part of natural
sounds. The parameters necessary to obtain a frequency-domain transfer
function of a linear time-variant finite impulse response (LTV-FIR) filter are
retrieved from the neural network in frames that are subsets of the input
signal. The corresponding impulse responses (IRs) are calculated and a
windowing function is applied. The windowed IRs are then convolved with white
noise via transformation to and multiplication in the frequency domain.

###  2.3 Reverb

In addition to the SMS model, the sound is also given a sense of space using a
reverberation algorithm performed in the frequency domain. Thus, the operation
of convolution between the impulse response of the reverb and the synthesized
signal is a more efficient multiplication.

###  2.4 Research question

Based on this background we have formulated the following research question:
How can we develop a playable software instrument, based on the DDSP library,
that would: a) allow customization of model-estimated synth parameters through
top-level macro controls, b) enable existing workflow-integration in Digital
Audio Workstations (DAWs), and c) facilitate a simple approach for beginners
without limiting usability for expert music producers?

To sum up the design requirements, we aim to build a software instrument
plugin that is playable in real-time. The instrument must support different
composition techniques, thus having a line and MIDI input mode. The instrument
must include at least four pre-trained models which serve the purpose of
estimating synthesizer parameters to output a desired sound. Finally, the
instrument must include graphical user interface components that provide
intuitive controls for the manipulation of synthesizer and effect parameters.

##  3 Design & Implementation

Based on this research question, we have identified five user needs [6], and
matched them with a solution, reformulating them as a concrete measurable
design requirement. The design requirements are thus documented on Table 1.

# |  User Obj. |  Solution |  Design Requirement
---|---|---|---
1 |  Provide a new playable instrument for unique sound generation and inspiration |  Real-time implementation |  _Must work in real-time as a playable software instrument._
2 |  Conveniently integrate into existing workflows |  Plugin format application |  _Must be implemented as a software plugin._
3 |  Adapt to different composition methods |  Allow line and MIDI input |  _Must allow switching between Line and MIDI input._
4 |  Easy fast unique sound generation |  Choose models for sound generation |  _Must implement at least four pre-trained models._
5 |  Convenient customizability of sounds |  Tweakable parameters that effects the audio output |  _Must include GUI components for intuitive manipulation of synth and effects parameters._
Table 1: Documentation of Design Requirements

###  3.1 Architecture overview

Figure 2: Schematic overview of the project architecture.

To meet our criteria of creating a real-time software instrument, we decided
to build the plugin in C++ using the JUCE application
framework222https://juce.com/, last accessed on 2020-12-15. With JUCE, we had
a multi-platform supported audio plugin template that was handling MIDI and
audio inputs and outputs. This allowed us to mainly focus on the audio
processing and GUI.

Creating a real-time implementation of the non-real-time DDSP library posed
some immediate challenges. To analyze and understand these challenges we
decided to start by doing a direct translation of the additive and subtractive
synthesizers from the DDSP library into MATLAB. The synthesizers could then be
changed into real-time implementations and tested. In order to use our MATLAB
implementation in the JUCE framework, we used inbuilt MATLAB tools to generate
C++ code.

We transformed the autoencoder models pretrained by Google into models that
could be used to estimate synthesizer parameters directly from our plugin’s
user input.

A general overview of this architecture can be seen in figure 2. The following
sections will discuss each component in more detail.

####  3.1.1 Synth in MATLAB

MATLAB’s environment and visualization tools gave us access to quick
prototyping and testing. This allowed us to do the implementation over
multiple iterations. We tested our synthesizers’ compatibility with the
predicted parameters from the DDSP models by invoking the encoders and
decoders in isolation through MATLAB’s Python interface.

At first we implemented the non-real-time synthesis algorithms of the DDSP
library. Then the synthesizers were changed to real-time, i.e., synthesizing a
single frame at a time. Using the MATLAB Audio Test Bench, we could then test
the functionality of the synthesizer components and parameters with real-time
audio and varying sample rate and buffer size. The last iterations consisted
of optimizing the code with the constraints of real-time audio processing on
CPUs.

####  3.1.2 MATLAB to C++

Using the MATLAB coder tool333https://se.mathworks.com/products/matlab-
coder.html, last accessed on 2020-12-15 we were able to generate C++ functions
from the MATLAB code. For the simplest integration between the generated C++
functions and the JUCE plugin we chose to limit the function inputs and
outputs to built-in and derived C++ data types. This required our MATLAB
functions to have fixed-sized inputs and outputs. We decided on a maximum
input/output size of 4096 double-precision floating point numbers, this being
the maximum buffer size the plugin would be able to work with.

A helper file was created to ensure code consistency, allowing the user and
MATLAB coder to verify the functions with different inputs. Having this setup
made it easy to go back to the MATLAB code and generate updated C++ functions
without breaking the JUCE plugin.

####  3.1.3 TensorFlow in C++

Running the DDSP TensorFlow implementation in a real-time audio application is
a heavy computational challenge. Moving from TensorFlow in Python to the
TensorFlow C API444https://www.tensorflow.org/install/lang_c, last accessed on
2020-12-15 allowed us to integrate the models into the C++ codebase. By moving
the TensorFlow computations to a separate thread, we can load the models, set
the inputs, run the parameter estimation and save the outputs, without
experiencing buffer underruns in the main audio processing thread.

####  3.1.4 Input signals

The DDSP autoencoder needs the input values _fundamental frequency_ ($f_{0}$)
and _loudness_ ($ld$). Since we allow both MIDI and line-in audio, two
separate implementations are needed to calculate these values. Functions for
this were created in MATLAB, but in the C++ implementation we chose to use the
implementation of the YIN pitch tracking algorithm [7] from the C library
Aubio[8], since it yielded more precise results.

###  3.2 Training models

####  3.2.1 Pre-trained models

Next to the _tone transfer_ website mentioned in the introduction, the authors
of the DDSP paper also published a Jupyter Notebook Demo on Google Colab
called _timbre transfer._
555https://colab.research.google.com/github/magenta/ddsp/blob/master/ddsp/colab/demos/timbre_transfer.ipynb,
last accessed on 2020-12-15 We accessed the available checkpoint files for
violin, flute, tenor saxophone and trumpet from this notebook for our real-
time implementation of the timbre transfer. However, we were not immediately
able to use them in the JUCE plugin. The DDSP models are trained using
TensorFlow’s _eager execution mode_ , while the TensorFlow C API is
constructed around _graph mode_. Additionally, since we required the models to
be controllable by MIDI input, we needed direct access to the decoder part of
the model instead of supplying audio to the encoder.

The convert_models.py script from the Python folder of the plugin code
repository deals with these requirements by loading the eager model from the
downloaded checkpoint file, constructing a graph-based model only containing
the decoder and then copying all weights from the old model to the new one.
The resulting checkpoint now contains a graph that can be loaded by the
TensorFlow C API.

####  3.2.2 Custom models

In order to make use of the DDSP training library and extend the synthesizer
with additional models, we created four custom models trained on:

  * •

Bass sounds of the Moog One, Moog Minimoog and Moog Minitaur synthesizers

  * •

Studio recordings of Middle Eastern instruments, the Hammered Dulcimer and
Santoor

  * •

Studio recordings of a Handpan (also known as Hang Drum)

  * •

Nature field recordings of birds chirping

For training we used the official DDSP (version 0.14.0) Jupyter notebook on
Google Colab called _train autoencoder_
666https://colab.research.google.com/github/magenta/ddsp/blob/master/ddsp/colab/demos/train_autoencoder.ipynb,
last accessed on 2020-12-15 which allows training on a Google Cloud GPU using
own data. We chose the recordings listed above in order to obtain interesting
sounds that differ from the more traditional pre-trained DDSP models.
According to the recommendations of the DDSP authors given in the notebook,
trained models perform best using recordings of a single, monophonic sound
source, in one acoustic environment, in .wav or .mp3 format with a total
duration of 10 to 20 minutes. Since the DDSP Autoencoder is conditioned on the
loudness $A$ and the fundamental frequency $f_{0}$, i.e., the model learns to
associate different synthesizer configurations to specific value pairs of
$(A,f_{0})$, training on multiple instruments, acoustic environments or
polyphonic sounds prevents the autoencoder to learn a unified representation.
However, these thereby introduced artifacts can also be used in a musical
context, that is why we decided to challenge the autoencoder with less conform
training data and eventually achieved interesting timbres.

The training process is performed as follows. The first step is comprised of
data generation and pre-processing of the training data. The raw audio is
split into short parts of a few seconds, each analyzed on the specified
features, i.e., the fundamental frequency and loudness, and finally saved in
the TensorFlow _TFRecord_ format. The fundamental frequency is thereby
estimated by using the state-of-the-art pitch tracking technique, called
_CREPE_ by Kim et al. [9] that applies a deep convolutional neural network on
time-domain audio. The second step is the actual training, using a Python
based configuration framework for dependency injection by Google, called _Gin_
777https://github.com/google/gin-config, last accessed on 2020-12-15. In this
way, all available training hyperparameters can be defined in a gin config
file that is passed to the training function. The training process does not
include any optimization techniques, such as a hyperparameter search or early
stopping, the authors just recommend in the code documentation to train for
5,000 to 30,000 steps until a spectral loss of about 4.5-5 is reached for an
optimal learning representation without overfitting. The third and last step
is a short evaluation based on resynthesis. That means, a training sample is
randomly picked, passed to the autoencoder that encodes and decodes, i.e.,
reconstructs the input sample based on the learned features.

We successfully conducted training of all four models and validated their
performance in the previously mentioned timbre transfer demo. While validation
using the DDSP library went smoothly and showed musically interesting results,
we ran into issues during inference using the TensorFlow C API within our
plugin. We monitored a much higher loudness of the custom models compared to
the pre-trained models, resulting in a distorted, clipping sound. Furthermore,
we detected a constant harmonic distribution independent of the incoming pitch
and loudness while the pre-trained models adapt harmonics and frequency
response according to these inputs. The overall experience with the training
script provided by the DDSP authors is that it works without problems for
standard parameters, but as soon as own hyperparameters within the gin
framework are chosen, a lot of side-effects appear. For the mentioned reasons,
integrating and possibly adapting the custom-trained models to make them work
in the DDSP synthesizer will be a part of future work.

####  3.2.3 Real-time implementation of the models

The DDSP non-real-time implementation synthesizes several frames before
processing them into one output. Reading through the DDSP code base we
experienced the number of frames (time steps) to be defined by the size of the
input audio and a hop size defined by constants in the gin config file of the
selected pre-trained model.

For our real-time implementation we wanted to calculate one frame with a size
of the input buffer each time the buffer is ready. Given the static nature of
our TensorFlow model implementation we were not able to change the number of
time steps on the run. Therefore, we set the number of time steps to one. Each
run of the TensorFlow model would then return a set of values for one time
step, independent of the buffer size.

###  3.3 Additive synthesizer

The implementation of the additive synthesizer can be found in the additive.m
MATLAB code file. During the development of the DDSP synthesizer we went from
a re-implementation of the DDSP equivalent to an adapted real-time optimized
version with additional parameters for high-level control. While the original
DDSP library provides two different implementations of the additive synthesis,
the harmonic and sinusoidal approach, this work focuses on the harmonic
synthesis that models a signal by adding only integer multiples of the
fundamental frequency.

In the following, the initial implementation as well as the main modifications
in its final state are clarified. As already explained in 2.1, the additive
synthesizer models audio using a bank of harmonic sinusoidal oscillators. The
synthesis algorithm takes amplitudes, harmonic distribution and fundamental
frequencies for a specified number of frames as input and computes the sample-
wise audio signal as output. The harmonic distribution provides frame-wise
amplitudes of the harmonics. The additive synthesis as implemented in the DDSP
library is performed in two main steps:

  * •

Translation of neural network outputs to the parameter space of the
synthesizer controls

  * •

Computing the output signal from synthesizer controls

In order to make the output of the neural network usable for controlling the
synthesizer, it needs to be transformed accordingly. In detail, that means the
amplitudes are scaled and the harmonic distribution is scaled, bandlimited and
normalized while the fundamental frequencies remain unchanged. Bandlimiting
the harmonic distribution means removing the harmonics that exceed Nyquist in
order to avoid artifacts.

After retrieving valid synthesizer controls, the harmonic synthesis is
performed. Since the DDSP approach works frame-based while the output needs to
be delivered sample-based, the synthesizer controls need to be upsampled. This
is done by linearly interpolating the frequency envelopes and windowing the
amplitude envelopes by using 50% overlapping Hann windows. Having calculated
all controls on a sample basis, the signal can be synthesized by accumulative
summation of the corresponding phases, i.e., adding the calculated sinusoids
together, sample by sample.

The following changes were made to optimize the algorithm for a real-time
application and to add additional high-level control for the synthesis.

  * •

Since the frame-based calculation was computationally too heavy, we adapted
the code so that the input is always one frame (equivalent to the buffer size)
and all computations are sample-based. Therefore, no resampling or windowing
is needed.

  * •

Each time the function is called, the phases of all harmonics are saved and
returned along with the signal and added as offset in the next call to avoid
artifacts caused by phase jumps.

  * •

In order to be able to optionally introduce non-harmonic partials to the
signal, a stretch parameter was added that transforms the distance between the
integer multiples while maintaining the fundamental frequency. An additional
shift parameter adds the functionality to modify the fundamental frequency
from one octave below to one octave above the current pitch in a continuous
scale.

###  3.4 Subtractive synthesizer

This component is responsible for the non-harmonic parts of instrument sounds,
such as the audible non-pitched flow of air that accompanies the harmonic part
of a flute sound. Our implementation, which can be found in the subtractive.m
MATLAB code file, generates a frame of random noise and then filters it
according to a given frequency response.

The function’s parameters are the frame length (number of samples), noise
color (see below) and the frequency response, which is given as a vector of
$N$ magnitudes $m_{0},\ldots,m_{N-1}$, where $m_{0}$ corresponds to the DC
component and $m_{i}$ to frequency $f_{\text{nyquist}}/(N-i)$ with
$f_{\text{nyquist}}=f_{s}/2$ and samplerate $f_{s}$.

While we started with a direct re-implementation of the DDSP FilteredNoise
approach described in 2.2, we made the following adaptations over the course
of the project:

  * •

Simplified filtering calculation. The DDSP synthesizer processes multiple
frames at once. For the sake of a real-time implementation, we removed the
step of calculating the impulse response for each frame and applying a
windowing function. Instead, we simply perform a Fourier transform on the
generated noise and multiply the result with the filter magnitude response
that the model predicted for the single current frame.

  * •

Noise color. We provide functionality to shape the frequency distribution of
the generated noise. Noise color generally refers to the frequency $f$ being
emphasized proportionally to $1/f^{\alpha}$ for some exponent $\alpha$ [10].
$\alpha<1$ results in higher frequencies becoming more prominent, while
$\alpha>1$ increases the energy of the lower frequencies. Uniform white noise
is achieved by setting $\alpha=1$.

###  3.5 Graphical User Interface

After the development of all the features of our synthesizer, we focused our
attention on designing an interface with high-level controls for the additive
and the subtractive synthesis, the reverb, the modulation and the models. Our
process started from a list of all the parameters we wanted to manipulate. We
also looked for some inspiration from well-known VST synthesizers, comparing
them in terms of usability and trying to understand what their best
interaction features were. Later we organized the controls of our synthesizer
in different modules and displayed them in a rectangular interface, trying to
find a layout that was pleasant but also respectful of the instrument’s
architecture logic. In table 2, we list all the controls for each module of
our synthesizer. Because of the particular choice of a graphic control for the
harmonics’ amplitude, the team opted for a spectrogram representing the output
of our plugin. In this way, the user is able to clearly see which harmonics
are being played.

Module |  Feature controls
---|---
Input selector |  MIDI/line selector
Models selector |  Violin
Flute
Saxophone
Trumpet
Moog Bass (not included)
Dulcimer (not included)
Handpan (not included)
Chirps (not included)
Additive synthesis |  Graphic harmonics editor
$f_{0}$ shift
Harmonics stretching
Global amplitude
Subtractive synthesis |  Noise color
Global amplitude
Modulation |  Modulation rate
Delay control
Amount
Reverb |  Dry/wet mix
Size
Glow
Output |  Master gain
Spectrogram |  Clear visualization of the output
Table 2: List of GUI’s features

Once we defined the layout and the parameters that we wanted to control, we
moved to the software development in JUCE. In order to customize the
appearance of knobs, we used the ”Custom LookandFeel” objects while we
designed ad hoc images for the buttons and background texture using a vector
graphics software. Figure 1 previously presented the GUI of our synthesizer.

###  3.6 Plugin setup

The synthesizer ended up being built as a standalone executable and a DAW
plugin using Steinberg’s VST3 format.

Using JUCE’s AudioProcessorValueTreeState class we are exposing the different
controllable parameters to the DAW, allowing control and automation of the
plugin. Using this class we will also be able to easily store and read plugin
states, enabling generation of presets, though this has not been implemented
yet.

The synthesizer is configured to load the models from a given path with
subfolders containing the individual models, as well as configuration files
containing key-value pairs such as number of harmonics and scaling values.

##  4 Evaluation

In order to understand the strengths and weaknesses of our product to improve
it, we designed an evaluation strategy for both User Experience (UX) and sound
output. Our target users are musicians and music producers. Accordingly, we
shared a release of our VST plugin with selected sound engineers, musicians
and producers to collect opinions and user insights. Moreover, we designed two
different questionnaires and asked participants to evaluate the UX and the
sound accuracy of our software. The DDSP Synthesizer as well as the two
questionnaires have been distributed online and the participants received an
email with all the indications to properly conduct the test.

In the next two sub-sections we will describe each evaluation in detail,
including approach, desired outcome, survey design and results.

###  4.1 User Experience Evaluation

####  4.1.1 Approach

The aim of this evaluation is to collect feedback about the user interface
from people with experience on synthesizers and music production. One of the
goals of our project was to design a simple and efficient interface able to
control several parameters with a single gesture without giving up
functionality in the pursuit of simplicity. After a trial period where the
participants had the chance to familiarize themselves with the software, we
asked them to compile a form.

####  4.1.2 Survey structure

Google Forms was chosen as a platform because of its simplicity and wide
spread. We designed the survey with different sections to group the questions
by theme. We included an experiment in order to ask each participant to load
and perform some changes to a model and export the result in an audio file. In
this way, we are sure that every participant had at least used and interacted
with the plugin for a while. Moreover we are able to compare each audio export
to understand if some of the instructions were not clear or if the UX itself
was not effective.

Four usage questions have been asked to collect information about the user’s
DAW and for how much time they used the plugin. In the next sections we asked
the participants to report their experience during the experiment and evaluate
the user interface rating 9 different statements with a Likert-scale, a widely
used bipolar symmetric scaling method in questionnaires. In this way, users
were able to express their agreement/disagreement related to each sentence.
Furthermore, we asked 4 open questions to let the participants express their
opinion about the overall UX. Finally we added 8 questions to locate
demographics and musical-related personal experiences. Table 3 summarizes the
content of each section.

# |  Section |  Content
---|---|---
1 |  Introduction |  Aim of the questionnaire
2 |  Experiment |  Task instructions
3 |  Usage |  4 mixed questions
4 |  UX evaluation |  9 Likert scale evaluations
5 |  UX experience |  4 open questions
5 |  Demographics |  8 mixed questions
Table 3: Content of the UX survey

####  4.1.3 Expected results

In this section we want to express a projection of the feedback regarding the
User Experience. Considering that the software is still under development, we
are expecting reports about compatibility issues with different DAWs as well
as some stability problems. Moreover, because of the VST’s instability in the
first release, it is possible that some users will not be able to conduct the
small experiment that requires the plugin to be embedded in a DAW track.
Considering the whole interface, one of the main points of our design
requirements was the simplicity and thus our hope is to facilitate the user’s
interaction.

####  4.1.4 Results

We received 7 answers. Five participants identified as males, 1 female and one
preferred not to say. The age average is 28.57 years (STD 8.42). Six of them
declared that sound production is their hobby while one said music production
is related to their job. The mean experience in the music production field is
7.43 years (STD 4.87). Six users do not have experience with machine learning
VST plugins and only one of them does not know if she/he ever used one. Each
user spent an average of 23.57 minutes using our synthesizer (STD 17.74). We
suppose that some mistake has been made reporting the usage time for at least
one user. In table 4 we report the number of user tests per different software
environment.

# users |  Environment
---|---
3 |  Reaper
2 |  Ableton Live
1 |  Cubase
1 |  Standalone version
Table 4: List of used DAWs in the evaluation.

In general, the experiment has been rated a medium difficult task with a mean
rating of 3.43 in a scale from 1 to 5 being 1 ”easy to accomplish” and 5 ”hard
to accomplish”. In figure 3 we summarize the answers obtained from the
questions with an associated likert scale. The users were asked to rate each
sentence from 1 to 5 with 1 corresponding to ”strongly disagree” and 5 to
”strongly agree”. We can observe that the graphical user interface has been
really appreciated with a 4.43 mean value while the interface’s controls seem
not to let the participants easily reach the wanted results. The other
statements reported in the likert section obtained a medium rating between 3
and 3.86 which might mean that the GUI is in general appreciated.

Figure 3: User experience evaluation - Likert scale

As expected, some of the participants encountered difficulties in the
installation procedure of the VST3 plugin in both Windows and macOS
environments while the standalone version seems to be more stable.
Furthermore, three users reported an unsatisfactory audio result related to
the presets obtained from models. Here we report part of one of the feedback:
”[…] It’s possible to get some cool sounds but the default sound when you just
start it is not so nice.”. On the other hand, the audio input feature was
appreciated: ”[…] I think the audio input feature has a lot of potential and I
caught myself experimenting with this a lot and loosing track of time.”. Two
participants reported that the possible interaction with the interface for the
additive synthesizer was not immediate to spot and they realized its features
after a while. For this reason they suggest a graphical indication to guide
the user to the interaction with the harmonic sliders. A significant outcome
is the unexpected audio results that participants reported. Even though they
described output sounds as ”awkward”, they highlighted the new creative way of
producing unexpected sounds, finding the whole synthesizer experience
engaging.

###  4.2 Real-time timbre transfer

We found the quality of the timbre transfer in our real-time implementation
below that of the demonstrations published by the Magenta team. Our converted
models preserve some characteristics of the original ones, such as wind noises
in the flute model, but do not accurately reproduce the timbre overall. We
confirmed that on the level of a single frame, our models produce the same
output as their original counterparts; will investigate and improve the
quality in the future. Additionally, we would like to further investigate why
we were unable to perform the timbre transfer with models that we trained both
within the framework provided by Magenta, and within custom environments.

A recently released realtime reimplementation of DDSP in
PyTorch888https://github.com/acids-ircam/ddsp_pytorch provides a possibly more
seamless way of interfacing with DDSP models in C++ that proved compatible
with our plugin and JUCE. Extending that API to allow the user some control
over the synthesis parameters seems a promising avenue to improve the sound
quality of our timbre transfer.

###  4.3 Distribution as a VST3 plugin

When it came to distributing our project to users, we encountered some
difficulties in packaging the required libraries and model files together with
the generated VST3 plugin. Some of the DAWs that users tested on, like Ableton
or Reaper, did not recognize the plugin or experienced stability issues during
its usage. Although the core functionality could still be accessed via the
standalone application generated by JUCE, the project was designed first and
foremost as a plugin. Functionality like handling of external audio sources
and wet/dry mixing was expected to be handled by the host DAW. Users who had
to resort to the standalone when their DAW did not recognize or stably run the
plugin reported those features as missing.

Thus, we would like to improve the distribution process in the future,
ensuring that the project can be seamlessly installed as a plugin in multiple
DAWs on Windows and macOS.

##  5 Conclusion

In this paper, we presented an approach to integrate the DDSP library into a
real-time plugin and standalone application using the JUCE framework. We
succeeded in implementing a synthesizer playable based on pure user input.
While we were generally able to use the output from pre-trained models to
control the DDSP backend, further research is needed to match the sound
quality of these real-time models to that of the offline timbre transfer
examples provided by the DDSP authors.

## References

  * [1] C. Donahue, J. McAuley, and M. Puckette, “Adversarial Audio Synthesis,” arXiv:1802.04208 [cs], Feb. 2019.  arXiv: 1802.04208.
  * [2] M. Blaauw and J. Bonada, “A neural parametric singing synthesizer modeling timbre and expression from natural songs,” Applied Sciences, vol. 7, p. 1313, 2017.
  * [3] J. Engel, L. Hantrakul, C. Gu, and A. Roberts, “DDSP: Differentiable Digital Signal Processing,” International Conference on Learning Representations, 2020.
  * [4] X. Serra and J. O. Smith, “Spectral modeling synthesis. A sound analysis/synthesis system based on a deterministic plus stochastic decomposition,” Computer Music Journal, vol. 14, no. 4, pp. 12–24, 1990\.
  * [5] Native-Instruments, “Razor,” 2011.
  * [6] D. Pandey, U. Suman, and A. Ramani, “An effective requirement engineering process model for software development and requirements management,” in 2010 International Conference on Advances in Recent Technologies in Communication and Computing, pp. 287 – 291, 2010.
  * [7] A. Cheveigné and H. Kawahara, “YIN, A fundamental frequency estimator for speech and music,” The Journal of the Acoustical Society of America, vol. 111, pp. 1917–30, 2002.
  * [8] P. Brossier, Automatic annotation of musical audio for interactive applications.  PhD thesis, Queen Mary University of London, 2006.
  * [9] J. W. Kim, J. Salamon, P. Li, and J. P. Bello, “CREPE: A convolutional representation for pitch estimation,” in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 161–165, IEEE, 2018.
  * [10] N. J. Kasdin, “Discrete simulation of colored noise and stochastic processes and $1/f^{\alpha}$ power law noise generation,” Proceedings of the IEEE, vol. 83, no. 5, pp. 802–827, 1995.