11institutetext: LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden,
Netherlands

# Hyperparameter Importance of Quantum Neural Networks Across Small Datasets

Charles Moussa  0000-0002-5387-564X Jan N. van Rijn  0000-0003-2898-2168
Thomas Bäck  0000-0001-6768-1478 Vedran Dunjko  0000-0002-2632-7955

###### Abstract

As restricted quantum computers are slowly becoming a reality, the search for
meaningful first applications intensifies. In this domain, one of the more
investigated approaches is the use of a special type of quantum circuit - a
so-called quantum neural network – to serve as a basis for a machine learning
model. Roughly speaking, as the name suggests, a quantum neural network can
play a similar role to a neural network. However, specifically for
applications in machine learning contexts, very little is known about suitable
circuit architectures, or model hyperparameters one should use to achieve good
learning performance. In this work, we apply the functional ANOVA framework to
quantum neural networks to analyze which of the hyperparameters were most
influential for their predictive performance. We analyze one of the most
typically used quantum neural network architectures. We then apply this to $7$
open-source datasets from the OpenML-CC18 classification benchmark whose
number of features is small enough to fit on quantum hardware with less than
$20$ qubits. Three main levels of importance were detected from the ranking of
hyperparameters obtained with functional ANOVA. Our experiment both confirmed
expected patterns and revealed new insights. For instance, setting well the
learning rate is deemed the most critical hyperparameter in terms of marginal
contribution on all datasets, whereas the particular choice of entangling
gates used is considered the least important except on one dataset. This work
introduces new methodologies to study quantum machine learning models and
provides new insights toward quantum model selection.

###### Keywords:

Hyperparameter importance Quantum Neural Networks Quantum Machine Learning.

##  1 Introduction

Quantum computers have the capacity to efficiently solve computational
problems believed to be intractable for classical computers, such as factoring
[42] or simulating quantum systems [12]. However, with the Noisy Intermediate-
Scale Quantum era [33], quantum algorithms are confronted with many
limitations (e.g., the number of qubits, decoherence, etc). Consequently,
hybrid quantum-classical algorithms were designed to work around some of these
constraints while targeting practical applications such as chemistry [27],
combinatorial optimization [10], and machine learning [2]. Quantum models can
exhibit clear potential in special datasets where we have theoretically
provable separations with classical models [22, 18, 35, 46]. More theoretical
works also study these models from a generalization perspective [8]. Quantum
circuits with adjustable parameters, also called quantum neural networks, have
been used to tackle regression [25], classification [14], generative
adversarial learning [50], and reinforcement learning tasks [18, 44].

However, the value of quantum machine learning on real-world datasets is still
to be investigated in any larger-scale systematic fashion [13, 32]. Currently,
common practices from machine learning, such as large-scale benchmarking,
hyperparameter importance, and analysis have been challenging tools to use in
the quantum community [39]. Given that there exist many ways to design quantum
circuits for machine learning tasks, this gives rise to a hyperparameter
optimization problem. However, there is currently limited intuition as to
which hyperparameters are important to optimize and which are not. Such
insights can lead to much more efficient hyperparameter optimization [5, 11,
26].

In order to fill this gap, we employ functional ANOVA [16, 45], a tool for
assessing hyperparameter importance. This follows the methodology of [34, 41],
who employed this across datasets, allowing for more general results. For
this, we selected a subset of several low-dimensional datasets from the
OpenML-CC18 benchmark [4], that are matching the current scale of simulations
of quantum hardware. We defined a configuration space consisting of ten
hyperparameters from an aggregation of quantum computing literature and
software. We extend this methodology by an important additional verification
step, where we verify the performance of the internal surrogate models.
Finally, we perform an extensive experiment to verify whether our conclusions
hold in practice. While our main findings are in line with previous intuition
on a few hyperparameters and the verification experiments, we also discovered
new insights. For instance, setting well the learning rate is deemed the most
critical hyperparameter in terms of marginal contribution on all datasets,
whereas the particular choice of entangling gates used is considered the least
important except on one dataset.

##  2 Background

In this section, we introduce the necessary background on functional ANOVA,
quantum computing, and quantum circuits with adjustable parameters for
supervised learning.

###  2.1 Functional ANOVA

When applying a new machine learning algorithm, it is unknown which
hyperparameters to modify in order to get high performances on a task. Several
techniques for hyperparameter importance exist, such as functional ANOVA [36].
The latter framework can detect the importance of both individual
hyperparameters and interaction effects between different subsets of
hyperparameters. We first introduce the relevant notations following, based
upon the work by [16].

Let $A$ be an machine learning algorithm that has $n$ hyperparameters with
domains $\Theta_{\\_}1,\ldots,\Theta_{\\_}n$ and _configuration space_
$\bm{\Theta}=\Theta_{\\_}1\times\ldots\times\Theta_{\\_}n$. An instantiation
of $A$ is a vector $\bm{\theta}=\\{\theta_{\\_}1,\ldots,\theta_{\\_}n\\}$ with
$\theta_{\\_}i\in\Theta_{\\_}i$ (this is also called a _configuration_ of
$A$). A partial instantiation of $A$ is a vector
$\bm{\theta}_{\\_}U=\\{\theta_{\\_}{i_{\\_}1},\ldots,\theta_{\\_}{i_{\\_}k}\\}$
with a subset $U=\\{i_{\\_}1,\ldots,i_{\\_}k\\}\subseteq
N=[n]=\\{1,\dots,n\\}$ of the hyperparameters fixed, and the values for other
hyperparameters unspecified. Note that $\bm{\theta}_{\\_}N=\bm{\theta}$.

Functional ANOVA is based on the concept of a marginal of a hyperparameter,
i.e., how a given value for a hyperparameter performs, averaged over all
possible combinations of the other hyperparameters’ values. The _marginal
performance_ $\hat{a}_{\\_}U(\bm{\theta}_{\\_}U)$ is described as the average
performance of all complete instantiations $\bm{\theta}$ that have the same
values for hyperparameters that are in $\bm{\theta}_{\\_}U$. As an
illustration, Fig. 1 shows marginals for two hyperparameters of a quantum
neural network and their union. As the number of terms to consider for the
marginal can be very large, the authors of [16] used tree-based surrogate
regression models to calculate efficiently the average performance. Such a
model yields predictions $\hat{y}$ for the performance $p$ of arbitrary
hyperparameter settings.

Functional ANOVA determines how much each hyperparameter (and each combination
of hyperparameters) contributes to the variance of $\hat{y}$ across the
algorithm’s hyperparameter space $\bm{\Theta}$, denoted $\mathds{V}$.
Intuitively, if the marginal has high variance, the hyperparameter is highly
important to the performance measure. Such framework has been used for
studying the importance of hyperparameters of common machine learning models
such as support vector machines, random forests, Adaboost, and Residual neural
networks [34, 41]. We refer to [16] for a complete description and introduce
the quantum supervised models considered in this study along with the basics
of quantum computing.

(a)  (b)  (c)

Figure 1:  Examples of marginals for a quantum neural network with validation
accuracy as performance on the banknote-authentication dataset. The
hyperparameters correspond to the learning rate used during training (a), and
the number of layers, also known as depth (b), and their combination (c). The
hyperparameter values for learning rate are on a log scale. When considered
individually, we see for instance that depth and learning rate should not be
set too high for better performances. However, when grouped together, the
learning rate seems most influential.

###  2.2 Supervised learning with Parameterized Quantum Circuits

####  2.2.1 Basics of quantum computing

In quantum computing, computations are carried out by the manipulation of
qubits, similarly to classical computing with bits. A system of $n$ qubits is
represented by a $2^{n}$-dimensional complex vector in the Hilbert space
$\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$. This vector describes the state of
the system $\ket{\psi}\in\mathcal{H}$ of unit norm
$\innerproduct{\psi}{\psi}=1$. The bra-ket notation is used to describe
vectors $\ket{\psi}$, their conjugate transpose $\bra{\psi}$ and inner-
products $\innerproduct{\psi}{\psi^{\prime}}$ in $\mathcal{H}$. Single-qubit
computational basis states are given by $\ket{0}=(1,0)^{T},\ket{1}=(0,1)^{T}$,
and their tensor products describe general computational basis states, e.g.,
$\ket{10}=\ket{1}\otimes\ket{0}=(0,0,1,0)$.

The quantum state is modified with unitary operations or gates $U$ acting on
$\mathcal{H}$. This computation can be represented by a quantum circuit (see
Fig. 2). When a gate $U$ acts non-trivially only on a subset $S\subseteq[n]$
of qubits, we denote such operation $U\otimes\mathbbm{1}_{\\_}{[n]\backslash
S}$. In this work, we use, the Hadamard gate $H$, the single-qubit Pauli gates
$Z,Y$ and their associated rotations $R_{\\_}X,R_{\\_}Y,R_{\\_}Z$:

$\begin{gathered}H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix},Z=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix},R_{\\_}Z(w)=\exp(-i\frac{w}{2}Z),\\\
Y=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix},R_{\\_}Y(w)=\exp(-i\frac{w}{2}Y),X=\begin{pmatrix}0&1\\\
1&0\end{pmatrix},R_{\\_}X(w)=\exp(-i\frac{w}{2}X),\end{gathered}$ (1)

The rotation angles are denoted $w\in\mathbb{R}$ and the 2-qubit
controlled-$Z$ gate $\leavevmode\hbox to2.5pt{\vbox
to8.96pt{\pgfpicture\makeatletter\hbox{\hskip 1.24998pt\lower-4.47914pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}}{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{-3.22916pt}\pgfsys@lineto{0.0pt}{3.22916pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{0.0pt}{-3.22916pt}\pgfsys@moveto{1.04999pt}{-3.22916pt}\pgfsys@curveto{1.04999pt}{-2.64926pt}{0.5799pt}{-2.17917pt}{0.0pt}{-2.17917pt}\pgfsys@curveto{-0.5799pt}{-2.17917pt}{-1.04999pt}{-2.64926pt}{-1.04999pt}{-3.22916pt}\pgfsys@curveto{-1.04999pt}{-3.80905pt}{-0.5799pt}{-4.27914pt}{0.0pt}{-4.27914pt}\pgfsys@curveto{0.5799pt}{-4.27914pt}{1.04999pt}{-3.80905pt}{1.04999pt}{-3.22916pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-3.22916pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}{}\pgfsys@moveto{0.0pt}{3.22916pt}\pgfsys@moveto{1.04999pt}{3.22916pt}\pgfsys@curveto{1.04999pt}{3.80905pt}{0.5799pt}{4.27914pt}{0.0pt}{4.27914pt}\pgfsys@curveto{-0.5799pt}{4.27914pt}{-1.04999pt}{3.80905pt}{-1.04999pt}{3.22916pt}\pgfsys@curveto{-1.04999pt}{2.64926pt}{-0.5799pt}{2.17917pt}{0.0pt}{2.17917pt}\pgfsys@curveto{0.5799pt}{2.17917pt}{1.04999pt}{2.64926pt}{1.04999pt}{3.22916pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{3.22916pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}=\text{diag}(1,1,1,-1)$
as well as the $\sqrt{\text{iSWAP}}$ given by the matrix

$\frac{1}{\sqrt{2}}\begin{pmatrix}\sqrt{2}&0&0&0\\\ 0&1&i&0\\\ 0&i&1&0\\\
0&0&0&\sqrt{2}\end{pmatrix}.$ (2)

Measurements are carried out at the end of a quantum circuit to obtain
bitstrings. Such measurement operation is described by a Hermitian operator
$O$ called an observable. Its spectral decomposition
$O=\sum_{\\_}m\lambda_{\\_}mP_{\\_}m$ in terms of eigenvalues $\lambda_{\\_}m$
and orthogonal projections $P_{\\_}m$ defines the outcomes of this
measurement, according to the Born rule: a measured state $\ket{\psi}$ gives
the outcome $\lambda_{\\_}m$ and gets projected onto the state
$P_{\\_}m\ket{\psi}/\\!\ \sqrt{p(m})$ with probability
$p(m)=\bra{\psi}P_{\\_}m\ket{\psi}=\expectationvalue{P_{\\_}m}_{\\_}\psi$. The
expectation value of the observable $O$ with respect to $\ket{\psi}$ is
$\mathbb{E}_{\\_}\psi[O]=\sum_{\\_}mp(m)\lambda_{\\_}m=\expectationvalue{O}_{\\_}{\psi}$.
We refer to [30] for more basic concepts of quantum computing, and follow with
parameterized quantum circuits.

####  2.2.2 Parameterized Quantum Circuits

A parameterized quantum circuit (also called _ansatz_) can be represented by a
quantum circuit with adjustable real-valued parameters $\bm{\theta}$. The
latter is then defined by a unitary $U(\bm{\theta})$ that acts on a fixed
$n$-qubit state (e.g., $\ket{0^{\otimes n}}$). The ansatz may be constructed
using the formulation of the problem at hand (typically the case in chemistry
[27] or optimization [10]), or with a problem-independent generic
construction. The latter are often designated as _hardware-efficient_.

For a machine learning task, this unitary encodes an input data instance
$x\in\mathbb{R}^{d}$ and is parameterized by a trainable vector $\bm{\theta}$.
Many designs exist but hardware-efficient parameterized quantum circuits [19]
with an alternating-layered architecture are often considered in quantum
machine learning when no information on the structure of the data is provided.
This architecture is depicted in an example presented in Fig. 2 and
essentially consists of an alternation of encoding unitaries
$U_{\\_}\text{enc}$ and variational unitaries $U_{\\_}\text{var}$. In the
example, $U_{\\_}\text{enc}$ is composed of single-qubit rotations $R_{\\_}X$,
and $U_{\\_}\text{var}$ of single-qubit rotations $R_{\\_}z,R_{\\_}y$ and
entangling Ctrl-$Z$ gates, represented as  in Fig. 2, forming the entangling
part of the circuit. Such entangling part denoted $U_{\\_}\text{ent}$, can be
defined by connectivity between qubits.

These parameterized quantum circuits are similar to neural networks where the
circuit architecture is fixed and the gate parameters are adjusted by a
classical optimizer such as gradient descent. They have also been named
quantum neural networks. The parameterized layer can be repeated multiple
times, which increases its _expressive power_ like neural networks [43]. The
data encoding strategy (such as reusing the encoding layer multiple times in
the circuit - a strategy called _data reuploading_) also influences the latter
[31, 40].

Finally, the user can define the observable(s) and the post-processing method
to convert the circuit outputs into a prediction in the case of supervised
learning. Commonly, observables based on the single-qubit $Z$ operator are
used. When applied on $m\leq n$ qubits, the observable is represented by a
$2^{m}-1$ square diagonal matrix with $\\{-1,1\\}$ values, and is denoted
$\mathcal{O}=Z\otimes Z\otimes\cdots\otimes Z$.

Having introduced parameterized quantum circuits, we present the
hyperparameters of the models, the configuration space, and the experimental
setup for our functional ANOVA-based hyperparameter importance study.

$\textstyle{\ket{0}}$$\textstyle{R_{\\_}X(x_{\\_}1)}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{R_{\\_}Y(\theta^{1}_{\\_}1)}$$\textstyle{R_{\\_}Z(\theta^{1}_{\\_}2)}$$\textstyle{\ket{0}}$$\textstyle{R_{\\_}X(x_{\\_}2)}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{R_{\\_}Y(\theta^{2}_{\\_}1)}$$\textstyle{R_{\\_}Z(\theta^{2}_{\\_}2)}$$\textstyle{\ket{0}}$$\textstyle{R_{\\_}X(x_{\\_}3)}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{R_{\\_}Y(\theta^{3}_{\\_}1)}$$\textstyle{R_{\\_}Z(\theta^{3}_{\\_}2)}$$\textstyle{\ket{0}}$$\textstyle{R_{\\_}X(x_{\\_}4)}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{R_{\\_}Y(\theta^{4}_{\\_}1)}$$\textstyle{R_{\\_}Z(\theta^{4}_{\\_}2)}$
Figure 2: Parameterized quantum circuit architecture example with $4$ qubits
and ring connectivity (qubit $1$ is connected to $2$, $2$ to $3$, $3$ to $4$,
and $4$ to $1$ makes a ring). The first layer of $R_{\\_}X$ is the encoding
layer $U_{\\_}\text{enc}$, taking a data instance $x\in\mathbb{R}^{4}$ as
input. It is followed by the entangling part with Ctrl-$Z$ gates. Finally a
variational layer $U_{\\_}\text{var}$ is applied. Eventually, we do
measurements to be converted into predictions for a supervised task. The
dashed part can be repeated many times to increase the expressive power of the
model.

##  3 Methods

In this section, we describe the network type and its hyperparameters and
define the methodology that we follow.

###  3.1 Hyperparameters and configuration space

Many designs have been proposed for parameterized quantum circuits depending
on the problem at hand or motivated research questions and contributions. Such
propositions can be aggregated and translated into a set of hyperparameters
and configuration space for the importance study. As such, we first did an
extensive literature review on parameterized quantum circuits for machine
learning [2, 14, 15, 17, 18, 21, 23, 24, 25, 32, 38, 44, 47, 48, 49, 50] as
well as quantum machine learning software [1, 3, 7]. This resulted in a list
of $10$ hyperparameters, presented in Table 1. We choose them so we balance
between having well-known hyperparameters that are expected to be important,
and less considered ones in the literature. For instance, many works use Adam
[20] as the underlying optimizer, and the learning rate should generally be
well chosen. On the contrary, the entangling gate used in the parameterized
quantum circuit is generally a fixed choice.

From the literature, we expect data encoding strategy/circuit to be important.
We choose two main forms for $U_{\\_}\text{enc}$. The first one is the
hardware-efficient $\bigotimes_{\\_}{i=1}^{n}R_{\\_}X(x_{\\_}i)$. The second
takes the following form from [3, 17, 14]:

$U_{\\_}\text{enc}(\bm{x})=U_{\\_}z(\bm{x})H^{\otimes n}$ (3)
$U_{\\_}z(\bm{x})=\exp(-\mathrm{i}\pi\left[\sum_{\\_}{i=1}^{n}x_{\\_}iZ_{\\_}i+\sum_{\\_}{\begin{subarray}{c}j=1,\\\
j>i\end{subarray}}^{n}x_{\\_}ix_{\\_}jZ_{\\_}iZ_{\\_}j\right]).$ (4)

Using data-reuploading [31] results in a more expressive model [40], and this
was also demonstrated numerically [18, 31, 44]. Finally, pre-processing of the
input is also sometimes used in encoding strategies that directly feed input
features into Pauli rotations. It also influences the expressive power of the
model [40]. In this work, we choose a usual activation function $tanh$
commonly used in neural networks. We do so as its range is $[-1,1]$, which is
the same as the data features during training after the normalization step.

The list of hyperparameters we take into account is non-exhaustive. It can be
extended at will, at the cost of more software engineering and budget for
running experiments.

Table 1: List of hyperparameters considered for hyperparameter importance for quantum neural network, as we named them in our Tensorflow-Quantum code. Hyperparameter | Values |  Description
---|---|---
Adam learning rate |  $[10^{-4},0.5]$ (log) |  The learning rate with which the quantum neural network starts training. The range was taken from the automated machine learning library Auto-sklearn [11]. We uniformly sample taking the logarithmic scale.
batchsize |  $16$, $32$, $64$ |  Number of samples in one batch of Adam used during training
depth |  $\\{1,2,$ $\cdots,10\\}$ |  Number of variational layers defining the circuit
is dataencoding hardware efficient |  True, False |  Whether we use the hardware-efficient circuit $\bigotimes_{\\_}{i=1}^{n}R_{\\_}X(x_{\\_}i)$ or an IQP circuit defined in Eq.3 to encode the input data.
use reuploading |  True, False |  Whether the data encoding layer is used before each variational layer or not.
have less rotations |  True, False |  If True, only use layers of $R_{\\_}Y,R_{\\_}Z$ gates as the variational layer. If False, add a layer of $R_{\\_}X$ gates.
entangler operation |  cz, sqiswap |  Which entangling gate to use in $U_{\\_}\text{ent}$
map type |  ring, full, pairs |  The connectivity used for $U_{\\_}\text{ent}$. The ring connectivity use an entangling gate between consecutive indices $(i,i+1),i\in\\{1,\dots,n\\}$ of qubits. The full one uses a gate between each pair of indices $(i,j),i<j$. Pairs connects even consecutive indices first, then odd consecutive ones.
input activation function |  linear, tanh |  Whether to input $tanh(x_{\\_}i)$ as rotations or just $x_{\\_}i$.
output circuit |  2Z, mZ |  The observable(s) used as output(s) of the circuit. If 2Z, we use all possible pairs of qubit indices defining $Z\otimes Z$. If mZ, the tensor product acts on all qubits. Note we do not use single-qubit $Z$ observables although they are quite often used in the literature. Indeed, they are provably not using the entire circuit when it is shallow. Hence we decided to use $Z\otimes Z$ instead. Also, a single neuron layer with a sigmoid activation function is used as a final decision layer similar to [38].

###  3.2 Assessing Hyperparameter Importance

Once the list of hyperparameters and configuration space are decided, we
perform the hyperparameter importance analysis with the functional ANOVA
framework. Assessing the importance of the hyperparameters boils down to four
steps. Firstly, the models are applied to various datasets by sampling various
configurations in a hyperparameter optimization process. The performances or
metrics of the models are recorded along. The sampled configurations and
performances serve as data for functional ANOVA. As functional ANOVA uses
internally tree-based surrogate models, namely random forests [6], we decided
to add an extra step with reference to [34]. As the second step, we verify the
performance of the internal surrogate models. We cross-evaluate them using
regression metrics commonly used in surrogate benchmarks [9]. Surrogates
performing badly at this step are then discarded from the importance analysis,
as they can deteriorate the quality of the study. Thirdly, the marginal
contribution of each hyperparameter over all datasets can be then obtained and
used to infer a ranking of their importance. Finally, a verification step
similar to [34] is carried out to confirm the inferred ranking previously
obtained. We explain such a procedure in the following section.

###  3.3 Verifying Hyperparameter Importance

Figure 3:  Performances of $1\,000$ quantim machine learning models defined by
different configurations of hyperparameters over each dataset. The metric of
interest in the study is the $10$-fold cross-validation accuracy. We take the
best-achieved metric per model trained over $100$ epochs.

When applying the functional ANOVA framework, an extra verification step is
added to confirm the output from a more intuitive notion of hyperparameter
importance [34]. It is based on the assumption that hyperparameters that
perform badly when fixed to a certain value (while other hyperparameters are
optimized), will be important to optimize. The authors of [34] proposed to
carry out a costly random search procedure fixing one hyperparameter at a
time. In order to avoud a bias to the chosen value to which this
hyperparameter is fixed, several values are chosen, and the optimization
procedure is carried out multiple times. Formally, for each hyperparameter
$\theta_{\\_}j$ we measure $y^{*}_{\\_}{j,f}$ as the result of a random search
for maximizing the metric, fixing $\theta_{\\_}j$ to a given value $f\in
F_{\\_}j,F_{\\_}j\subseteq\Theta_{\\_}j$. For categorical $\theta_{\\_}j$ with
domain $\Theta_{\\_}j$, $F_{\\_}j=\Theta_{\\_}j$ is used. For numeric
$\theta_{\\_}j$, the authors of [34] use a set of $10$ values spread uniformly
over $\theta_{\\_}j$’s range. We then compute
$y^{*}_{\\_}j=\frac{1}{|F_{\\_}j|}\sum_{\\_}{f\in F_{\\_}j}y^{*}_{\\_}{j,f}$,
representing the score when not optimizing hyperparameter $\theta_{\\_}j$,
averaged over fixing $\theta_{\\_}j$ to various values it can take.
Hyperparameters with lower value for $y^{*}_{\\_}j$ are assumed to be more
important, since the performance should deteriorate more when set sub-
optimally.

In our study, we extend this framework to be used on the scale of quantum
machine learning models. As quantum simulations can be very expensive, we
carry out the verification experiment by using the predictions of the
surrogate instead of fitting new quantum models during the verification
experiment. The surrogates yield predictions $\hat{y}$ for the performance of
arbitrary hyperparameter settings sampled during a random search. Hence, they
serve to compute $y^{*}_{\\_}{j,f}$. This is also why we assessed the quality
of the built-in surrogates as the second step. Poorly-performing surrogates
can deteriorate the quality of the random search procedure.

##  4 Dataset and inclusion criteria

To apply our quantum models and study the importance of the previously
introduced hyperparameters, we consider classical datasets. Similarly to [34],
we use datasets from the OpenML-CC18 benchmark suite [4]. In our study, we
consider only the case where the number of qubits available is equal to the
number of features, a common setting in the quantum community. As simulating
quantum circuits is a costly task, we limit this study to the case where the
number of features is less than $20$ after preprocessing111A $10$-fold cross-
validation run in our experiment takes on average $262$ minutes for $100$
epochs with Tensorflow Quantum [7].. Our first step was to identify which
datasets fit this criterion. We include all datasets from the OpenML-CC18 that
have 20 or fewer features after categorical hyperparameters have been one-hot-
encoded, and constant features are removed. Afterward, the input variables are
also scaled to unit variance as a normalization step. The scaling constants
are calculated on the training data and applied to the test data.

The final list of datasets is given in Table 2. In total, $7$ datasets fitted
the criterion considered in this study. For all of them, we picked the OpenML
Task ID giving the $10$-fold cross-validation task. A quantum model is then
applied using the latter procedure, with the aforementioned preprocessing
steps.

Table 2: List of datasets used in this study. The number of features is obtained after a usual preprocessing used in machine learning methods, such as one-hot-encoding.  Dataset |  OpenML Task ID |  Number of features |  Number of instances
---|---|---|---
breast-w | 15 | $9$ | $699$
diabetes | 37 | $8$ | $768$
phoneme | 9952 | $5$ | $5\,404$
ilpd | 9971 | $11$ | $583$
banknote-authentication | 10093 | $4$ | $1\,372$
blood-transfusion-service-center | 10 101 | $4$ | $748$
wilt | 146820 | $5$ | $4\,839$

##  5 Results

In this section, we present the results obtained using the hyperparameters and
the methodology defined in Section 3 with the datasets described in Section 4.
First, we show the distribution of performances obtained during a random
search where configurations are independently sampled for each dataset. Then
we carry out the surrogate verification. Finally, we present the functional
ANOVA results in terms of hyperparameter importance with marginal
contributions and the random search verification per hyperparameter.

###  5.1 Performance distributions per dataset

For each dataset, we sampled independently $1\,000$ hyperparameter
configurations and run the quantum models for $100$ epochs as budget. As a
performance measure, we recorded the best validation accuracy obtained over
$100$ epochs. Fig. 3 shows the distribution of the $10$-fold cross-validation
accuracy obtained per dataset. We observe the impact of hyperparameter
optimization by the difference between the least performing and the best model
configuration. For instance, on the wilt dataset, the best model gets an
accuracy close to $1$, and the least below $0.25$. We can also see that some
datasets present a smaller spread of performances. ilpd and blood-transfusion-
service-center are in this case. It seems that hyperparameter optimization
does not have a real effect, because most hyperparameter configurations give
the same result. As such, the surrogates could not differentiate between
various configurations. In general, hyperparameter optimization is important
for getting high performances per dataset and detecting datasets where the
importance study can be applied.

###  5.2 Surrogate verification

Functional ANOVA relies on an internal surrogate model to determine the
marginal contribution per hyperparameter. If this surrogate model is not
accurate, this can have a severe limitation on the conclusions drawn from
functional ANOVA. In this experiment, we verify whether the hyperparameters
can explain the performances of the models. Table 3 shows the performance of
the internal surrogate models. We notice low regression scores for the two
datasets (less than $0.75$ R2 scores). Hence we remove them from the analysis.

Table 3: Performances of the surrogate models built within functional ANOVA over a $10$-fold cross-validation procedure. We present the average coefficient of determination (R2), root mean squared error (RMSE), and Spearman’s rank correlation coefficient (CC). These are common regression metrics for benchmarking surrogate models on hyperparameters [9]. The surrogates over ilpd and blood-transfusion-service-center obtain low scores (less than $.75$ R2), hence we remove them from the study. Dataset | R2 score |  RMSE |  CC
---|---|---|---
breast-w | 0.8663 | 0.0436 | 0.9299
diabetes | 0.7839 | 0.0155 | 0.8456
phoneme | 0.8649 | 0.0285 | 0.9282
ilpd | 0.1939 | 0.0040 | 0.4530
banknote-authentication | 0.8579 | 0.0507 | 0.9399
blood-transfusion-service-center | 0.6104 | 0.0056 | 0.8088
wilt | 0.7912 | 0.0515 | 0.8015

###  5.3 Marginal contributions

For functional ANOVA, we used $128$ trees for the surrogate model. Fig. 4(a,b)
shows the marginal contribution of each hyperparameter over the remaining $5$
datasets. We distinguish $3$ main levels of importance. According to these
results, the learning rate, depth, and the data encoding circuit and
reuploading strategy are critical. These results are in line with our
expectations. The entangler gate, connectivity, and whether we use $R_{\\_}X$
gates in the variational layer are the least important according to functional
ANOVA. Hence, our results reveal new insights into these hyperparameters that
are not considered in general.

(a)  (b)

Figure 4:  The marginal contributions per dataset are presented as a) the
variance contribution and b) the difference between the minimal and maximal
value of the marginal of each hyperparameter. The hyperparameters are sorted
from the least to most important using the median. We distinguish from the
plot $3$ main levels of importance.

###  5.4 Random search verification

In line with the work of [34], we perform an additional verification
experiment that verifies whether the outcomes of functional ANOVA are in line
with our expectations. However, the verification procedure involves an
expensive, post-hoc analysis: a random search procedure fixing one
hyperparameter at a time. As our quantum simulations are costly, we used the
surrogate models fitted on the current dataset considered over the $1\,000$
configurations obtained initially to predict the performances one would obtain
when presented with a new configuration.

Fig. 5 shows the average rank of each run of random search, labeled with the
hyperparameter whose value was fixed to a default value. A high rank implies
poor performance compared to the other configurations, meaning that tuning
this hyperparameter would have been important. We witness again the $3$ levels
of importance, with almost the same order obtained. However, the
input_activation_function is deemed more important while batchsize is less.

Figure 5:  Verification experiment of the importance of the hyperparameters. A
random search procedure up to $500$ iterations excluding one parameter at a
time is used. A lower curve means the hyperparameter is deemed less important.

More simulations with more datasets may be required to validate the
importance. However, we retrieve empirically the importance of well-known
hyperparameters while considering less important ones. Hence functional ANOVA
becomes an interesting tool for quantum machine learning in practice.

##  6 Conclusion

In this work, we study the importance of hyperparameters related to quantum
neural networks for classification using the functional ANOVA framework. Our
experiments are carried out over OpenML datasets that match the current scale
of quantum hardware simulations (i.e., datasets that have at most $20$
features after pre-processing operators have been applied, hence using $20$
qubits). We selected and presented the hyperparameters from an aggregation of
quantum computing literature and software. Firstly, hyperparameter
optimization highlighted datasets where we observed high differences between
configurations. This underlines the importance of hyperparameter optimization
for these datasets. There were also datasets that showed little difference.
These led us to extend the methodology by adding an additional verification
step of the internal surrogate performances. From our results, we
distinguished $3$ main levels of importance. On the one hand, Adam’s learning
rate, depth, and the data encoding strategy are deemed very important, as we
expected. On the other hand, the less considered hyperparameters such as the
particular choice of the entangling gate and using $3$ rotation types in the
variational layer are in the least important group. Hence, our experiment both
confirmed expected patterns and revealed new insights for quantum model
selection.

For future work, we plan to further investigate methods from the field of
automated machine learning to be applied to quantum neural networks [5, 26,
11]. Indeed, our experiments have shown the importance of hyperparameter
optimization, and this should become standard practice and part of the
protocols applied within the community. We further envision functional ANOVA
to be employed in future works related to quantum machine learning and
understanding how to apply quantum models in practice. For instance, it would
be interesting to consider quantum data, for which quantum machine learning
models may have an advantage. Plus, extending hyperparameter importance to
techniques for scaling to a large number of features with the number of
qubits, such as dimensionality reduction or divide-and-conquer techniques, can
be left for future work. Finally, this type of study can also be extended to
different noisy hardware and towards algorithm/model selection and design. If
we have access to a cluster of different quantum computers, then choosing
which hardware works best for machine learning tasks becomes possible. One
could also extend our work with meta-learning [5], where a model configuration
is selected based on meta-features created from dataset features. Such types
of studies already exist for parameterized quantum circuits applied to
combinatorial optimization [28, 29, 37].

Acknowledgements CM and VD acknowledge support from TotalEnergies. This work
was supported by the Dutch Research Council (NWO/OCW), as part of the Quantum
Software Consortium programme (project number 024.003.037). This research is
also supported by the project NEASQC funded from the European Union’s Horizon
2020 research and innovation programme (grant agreement No 951821).

## References

  * [1] ANIS, M.S., et al.: Qiskit: An open-source framework for quantum computing (2021). https://doi.org/10.5281/zenodo.2573505
  * [2] Benedetti, M., Lloyd, E., Sack, S., Fiorentini, M.: Parameterized quantum circuits as machine learning models. Quantum Science and Technology 4(4), 043001 (2019)
  * [3] Bergholm, V., Izaac, J.A., Schuld, M., Gogolin, C., Killoran, N.: Pennylane: Automatic differentiation of hybrid quantum-classical computations. CoRR abs/1811.04968 (2018)
  * [4] Bischl, B., Casalicchio, G., Feurer, M., Gijsbers, P., Hutter, F., Lang, M., Mantovani, R.G., van Rijn, J.N., Vanschoren, J.: Openml benchmarking suites. In: Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks (2021)
  * [5] Brazdil, P., van Rijn, J.N., Soares, C., Vanschoren, J.: Metalearning: Applications to Automated Machine Learning and Data Mining. Springer, 2nd edn. (2022)
  * [6] Breiman, L.: Random forests. Machine Learning 45(1), 5–32 (2001)
  * [7] Broughton, M., et al.: Tensorflow quantum: A software framework for quantum machine learning. arXiv:2003.02989 (2020)
  * [8] Caro, M.C., Gil-Fuster, E., Meyer, J.J., Eisert, J., Sweke, R.: Encoding-dependent generalization bounds for parametrized quantum circuits. Quantum 5, 582 (2021)
  * [9] Eggensperger, K., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Efficient benchmarking of hyperparameter optimizers via surrogates. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. pp. 1114–1120. AAAI Press (2015)
  * [10] Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv:1411.4028 (2014)
  * [11] Feurer, M., Eggensperger, K., Falkner, S., Lindauer, M., Hutter, F.: Auto-sklearn 2.0: Hands-free automl via meta-learning. arXiv:2007.04074v2 [cs.LG] (2021)
  * [12] Georgescu, I.M., Ashhab, S., Nori, F.: Quantum simulation. Review of Modern Physics 86, 153–185 (2014)
  * [13] Haug, T., Self, C.N., Kim, M.S.: Large-scale quantum machine learning. CoRR abs/2108.01039 (2021)
  * [14] Havlíček, V., Córcoles, A.D., Temme, K., Harrow, A.W., Kandala, A., Chow, J.M., Gambetta, J.M.: Supervised learning with quantum-enhanced feature spaces. Nature 567(7747), 209–212 (2019)
  * [15] Heimann, D., Hohenfeld, H., Wiebe, F., Kirchner, F.: Quantum deep reinforcement learning for robot navigation tasks. CoRR abs/2202.12180 (2022)
  * [16] Hutter, F., Hoos, H., Leyton-Brown, K.: An efficient approach for assessing hyperparameter importance. In: Proceedings of the 31th International Conference on Machine Learning, ICML 2014. JMLR Workshop and Conference Proceedings, vol. 32, pp. 1130–1144 (2014)
  * [17] Jerbi, S., Fiderer, L.J., Nautrup, H.P., Kübler, J.M., Briegel, H.J., Dunjko, V.: Quantum machine learning beyond kernel methods. CoRR abs/2110.13162 (2021)
  * [18] Jerbi, S., Gyurik, C., Marshall, S., Briegel, H.J., Dunjko, V.: Parametrized quantum policies for reinforcement learning. In: Advances in Neural Information Processing Systems 34. pp. 28362–28375 (2021)
  * [19] Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J.M., Gambetta, J.M.: Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature 549(7671), 242–246 (2017)
  * [20] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization (2015)
  * [21] Liu, J.G., Wang, L.: Differentiable learning of quantum circuit born machines. Physical Review A 98, 062324 (2018)
  * [22] Liu, Y., Arunachalam, S., Temme, K.: A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics 17(9), 1013–1017 (2021)
  * [23] Marshall, S.C., Gyurik, C., Dunjko, V.: High dimensional quantum machine learning with small quantum computers. CoRR abs/2203.13739 (2022)
  * [24] Mensa, S., Sahin, E., Tacchino, F., Barkoutsos, P.K., Tavernelli, I.: Quantum machine learning framework for virtual screening in drug discovery: a prospective quantum advantage. CoRR abs/2204.04017 (2022)
  * [25] Mitarai, K., Negoro, M., Kitagawa, M., Fujii, K.: Quantum circuit learning. Physical Review A 98, 032309 (2018)
  * [26] Mohr, F., van Rijn, J.N.: Learning curves for decision making in supervised machine learning - A survey. CoRR abs/2201.12150 (2022)
  * [27] Moll, N., et al: Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology 3(3), 030503 (2018)
  * [28] Moussa, C., Calandra, H., Dunjko, V.: To quantum or not to quantum: towards algorithm selection in near-term quantum optimization. Quantum Science and Technology 5(4), 044009 (2020)
  * [29] Moussa, C., Wang, H., Bäck, T., Dunjko, V.: Unsupervised strategies for identifying optimal parameters in quantum approximate optimization algorithm. EPJ Quantum Technology 9(1) (2022)
  * [30] Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press (2011)
  * [31] Pérez-Salinas, A., Cervera-Lierta, A., Gil-Fuster, E., Latorre, J.I.: Data re-uploading for a universal quantum classifier. Quantum 4, 226 (2020)
  * [32] Peters, E., Caldeira, J., Ho, A., Leichenauer, S., Mohseni, M., Neven, H., Spentzouris, P., Strain, D., Perdue, G.N.: Machine learning of high dimensional data on a noisy quantum processor. npj Quantum Information 7(1), 161 (2021)
  * [33] Preskill, J.: Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018)
  * [34] van Rijn, J.N., Hutter, F.: Hyperparameter importance across datasets. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018. pp. 2367–2376. ACM (2018)
  * [35] Sajjan, M., Li, J., Selvarajan, R., Sureshbabu, S.H., Kale, S.S., Gupta, R., Kais, S.: Quantum computing enhanced machine learning for physico-chemical applications. CoRR arXiv:2111.00851 (2021)
  * [36] Saltelli, A., Sobol, I.: Sensitivity analysis for nonlinear mathematical models: Numerical experience. Matematicheskoe Modelirovanie 7 (1995)
  * [37] Sauvage, F., Sim, S., Kunitsa, A.A., Simon, W.A., Mauri, M., Perdomo-Ortiz, A.: Flip: A flexible initializer for arbitrarily-sized parametrized quantum circuits. CoRR abs/2103.08572 (2021)
  * [38] Schetakis, N., Aghamalyan, D., Boguslavsky, M., Griffin, P.: Binary classifiers for noisy datasets: a comparative study of existing quantum machine learning frameworks and some new approaches. CoRR abs/2111.03372 (2021)
  * [39] Schuld, M., Killoran, N.: Is quantum advantage the right goal for quantum machine learning? Corr abs/2203.01340 (2022)
  * [40] Schuld, M., Sweke, R., Meyer, J.J.: Effect of data encoding on the expressive power of variational quantum-machine-learning models. Physical Review A 103, 032430 (2021)
  * [41] Sharma, A., van Rijn, J.N., Hutter, F., Müller, A.: Hyperparameter importance for image classification by residual neural networks. In: Discovery Science - 22nd International Conference. Lecture Notes in Computer Science, vol. 11828, pp. 112–126. Springer (2019)
  * [42] Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. Siam Review 41, 303–332 (1999)
  * [43] Sim, S., Johnson, P.D., Aspuru-Guzik, A.: Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms. Advanced Quantum Technologies 2(12), 1900070 (2019)
  * [44] Skolik, A., Jerbi, S., Dunjko, V.: Quantum agents in the gym: a variational quantum algorithm for deep q-learning. CoRR abs/2103.15084 (2021)
  * [45] Sobol, I.M.: Sensitivity estimates for nonlinear mathematical models. Mathematical Modelling and Computational Experiments 1(4), 407–414 (1993)
  * [46] Sweke, R., Seifert, J., Hangleiter, D., Eisert, J.: On the quantum versus classical learnability of discrete distributions. Quantum 5, 417 (2021)
  * [47] Wang, H., Gu, J., Ding, Y., Li, Z., Chong, F.T., Pan, D.Z., Han, S.: Quantumnat: Quantum noise-aware training with noise injection, quantization and normalization. CoRR abs/2110.11331 (2021)
  * [48] Wang, H., Li, Z., Gu, J., Ding, Y., Pan, D.Z., Han, S.: Qoc: Quantum on-chip training with parameter shift and gradient pruning. CoRR abs/2202.13239 (2022)
  * [49] Wossnig, L.: Quantum machine learning for classical data. CoRR abs/2105.03684 (2021)
  * [50] Zoufal, C., Lucchi, A., Woerner, S.: Quantum generative adversarial networks for learning and loading random distributions. npj Quantum Information 5(1), 103 (2019)


* [14] I. P. Cornfeld, S. V. Fomin and Ya. G. Sinaĭ,  _Ergodic Theory_ ,  vol. 245 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, New York, 1982.
  * [15] R. Diestel,  _Graph Theory_ ,  5th edition, vol. 173 of Graduate Texts in Mathematics, Springer, Berlin, 2017.
  * [16] D. Dikranjan, C. Milan and A. Tonolo,  A characterization of the maximally almost periodic abelian groups,  _J. Pure Appl. Algebra_ , 197 (2005), 23–41.
  * [17] T. Downarowicz, D. Huczek and G. Zhang,  Tilings of amenable groups,  _J. Reine Angew. Math._ , 747 (2019), 277–298.
  * [18] H. A. Dye,  On the ergodic mixing theorem,  _Trans. Amer. Math. Soc._ , 118 (1965), 123–130.
  * [19] B. Fayad and A. Kanigowski,  Rigidity times for a weakly mixing dynamical system which are not rigidity times for any irrational rotation,  _Ergodic Theory Dynam. Systems_ , 35 (2015), 2529–2534.
  * [20] B. Fayad and J.-P. Thouvenot,  On the convergence to 0 of $m_{n}\xi\mod{1}$,  _Acta Arith._ , 165 (2014), 327–332.
  * [21] A. H. Forrest,  _Recurrence in Dynamical Systems: A Combinatorial Approach_ ,  Ph.D thesis, The Ohio State University, 1990.
  * [22] L. Fuchs,  _Infinite Abelian Groups. Vol. I_ ,  vol. 36 of Pure and Applies Mathematics, Academic Press, New York-London, 1970.
  * [23] J. T. Griesmer,  Recurrence, rigidity, and popular differences,  _Ergodic Theory Dynam. Systems_ , 39 (2019), 1299–1316.
  * [24] P. R. Halmos,  In general a measure preserving transformation is mixing,  _Ann. of Math. (2)_ , 45 (1944), 786–792.
  * [25] E. Hewitt and K. A. Ross,  _Abstract Harmonic Analysis. Vol. I_ ,  2nd edition, vol. 115 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin-New York, 1979.
  * [26] E. Hewitt and K. A. Ross,  _Abstract Harmonic Analysis. Vol. II_ ,  vol. 152 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin-New York, 1970.
  * [27] S. Janson,  _Gaussian Hilbert Spaces_ ,  vol. 129 of Cambridge Tracts in Mathematics,Cambridge University Press, Cambridge, 1997.
  * [28] A. Katok and J.-P. Thouvenot,  Spectral properties and combinatorial constructions in ergodic theory,  _Handbook of Dynamical Systems._ , 1B (2006), 649–743.
  * [29] A. S. Kechris,  _Global Aspects of Ergodic Group Actions_ ,  vol. 160 of Mathematical Surveys and Monographs, American Mathematical Society, Providence, RI, 2010.
  * [30] B. O. Koopman and J. von Neumann,  Dynamical systems of continuous spectra,  _Proc. Nat. Acad. Sci. U.S.A._ , 18 (1932), 255–263.
  * [31] C. McDiarmid.  On the method of bounded differences,  _Surveys in Combinatorics, 1989 (Norwich, 1989),Cambridge Univ. Press, Cambridge_ , 141 (1989), 148–188.
  * [32] M. G. Nadkarni,  _Basic Ergodic Theory_ ,  3rd edition, vol. 6 of Texts and Readings in Mathematics, Hindustan Book Agency, New Delhi, 2013.
  * [33] D. S. Ornstein and B. Weiss,  Ergodic theory of amenable group actions. I. The Rohlin lemma,  _Bull. Amer. Math. Soc. (N.S.)_ , 2 (1980), 161–164.
  * [34] I. V. Protasov and E. G. Zelenyuk,  Topologies on abelian groups,  _Izv. Akad. Nauk SSSR Ser. Mat._ , 54 (1990), 1090–1107.
  * [35] W. Rudin,  _Fourier Analysis on Groups_ ,  Wiley Classics Library, John Wiley & Sons, Inc., New York, 1990.
  * [36] I. Z. Ruzsa,  Arithmetical topology,  _Number Theory, Vol. I (Budapest, 1987),Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam_ , 51 (1990), 473–504.
  * [37] K. Schmidt,  Asymptotic properties of unitary representations and mixing,  _Proc. London Math. Soc._ , 48 (1984), 445–460.
  * [38] K. Schmidt and P. Walters,  Mildly mixing actions of locally compact groups,  _Proc. London Math. Soc._ , 45 (1982), 506–518.
  * [39] W. M. Schmidt,  On continued fractions and Diophantine approximation in power series fields,  _Acta Arith._ , 95 (2000), 139–166.
  * [40] P. Walters,  _An Introduction to Ergodic Theory_ ,  vol. 79 of Graduate Texts in Mathematics, Springer-Verlag, New York-Berlin, 1982.
  * [41] B. Weiss,  Monotileable amenable groups,  _Amer. Math. Soc. Transl. Ser. 2_ , 202 (2001), 257–262.


# Phase-coded Radar Waveform Design with Quantum Annealing

Timothé Presles  Thales Defense Mission Systems, 2 av. Gay Lussac, 78851
Elancourt, France  Cyrille Enderli  Thales Defense Mission Systems, 2 av. Gay
Lussac, 78851 Elancourt, France  Gilles Burel  Univ. Brest, Lab-STICC, CNRS,
UMR 6285, 6 av. Le Gorgeu, 29200 Brest, France  El Houssaïn Baghious  Univ.
Brest, Lab-STICC, CNRS, UMR 6285, 6 av. Le Gorgeu, 29200 Brest, France

###### Abstract

The Integrated Side Lobe Ratio (ISLR) problem we consider here consists in
finding optimal sequences of phase shifts in order to minimize the mean
squared cross-correlation side lobes of a transmitted radar signal and a
mismatched replica. Currently, ISLR does not seem to be easier than the
general polynomial unconstrained binary problem, which is NP-hard. In our
work, we aim to take advantage of the exponential scalability of quantum
computing to find new optima, by solving the ISLR problem on a quantum
annealer. This quantum device is designed to solve quadratic optimization
problems with binary variables (QUBO). After proposing suitable formulation
for different instances of the ISLR, we discuss the performances and the
scalability of our approach on the D-Wave quantum computer. More broadly, our
work enlightens the limits and potential of the adiabatic quantum computation
for the solving of large instances of combinatorial optimization problems.

##  1 Introduction

Waveform optimization is an important issue in the design of radar systems. It
consists in finding the ”best” transmitted signal (to some criterion related
to the addressed operational tasks). Under certain system constraints like
e.g. peak power limitation, dissipation time, etc. The signal processing
methods on receive yield undesirable side-lobes creating false alarms or
masking multiple close targets. It is therefore important to mitigate these
side-lobes while keeping the main-lobe energy corresponding to the actual
localization of the target.

In the literature, previous works enlightens different ways to improve the
quality of target or scene imaging with post-processing methods such as
Spatially Variant Apodization [1], FFT Weighting [2] or transmitted signal
replica weighting (for mismatched filtering) [3]. In this latter case, the
joint design of the transmitted signal and the replica is a more general
problem of waveform optimization.
In this paper, we address the Integrated Side-Lobe Ratio (ISLR) problem, which
consists in maximizing the ratio between the energy of the main-lobe and the
side-lobes. We will consider phase-coded waveforms for high range resolution
applications: The problem is thus to find optimal phase codes within a finite
set of quantized feasible values. In order to assess optimality, we compute
the correlation function and calculate the ISLR as a performance indicator.
Finding optimal sequences is NP-hard [4], as the number of possible sequences
exponentially increases with the length i.e. the number of possible phase
shifts, and the number of phase states. In the literature, different methods
are employed as branch-and-bound [4], search algorithms [5, 6] or more general
optimization methods [7]. All these approaches demonstrate the hardness of
finding optimal sequences for large instances in a reasonable amount of time.

Quantum computing is an emerging technology which exploits the laws of quantum
mechanics in order to perform logical operations. Instead of classical bits,
quantum computers operate on qubits, which are in a superposition of two
states. Among various applications, solving optimisation problems with quantum
devices promises an exponential speedup over current non-quantum approaches
[8], especially for large instances of NP-Hard problems. There are currently
two main approaches in the design of quantum computers: Circuit-oriented
quantum computers and quantum annealers. Circuit oriented quantum computers
have a sequential approach of quantum computation, using gates to perform
operations on single or multiple qubits. Quantum annealers have a simultaneous
approach of quantum computation, making all the qubits involved in the
computation converge from an initial state to a final state. Although having,
today, more qubits than their circuit oriented analogs, quantum annealers are
limited to optimisation problems in the form of Quadratic Unconstrained Binary
Optimisation (QUBO) problem.

QUBOs are optimisation problems with binary valued variables and a quadratic
cost function which is not subject to constraints. In the so called Ising
Model, the binary variables can take on values in $\\{-1,1\\}$. In the
literature, previous work proposes numerous QUBO formulations for a wide
variety of problems as clustering [9], machine learning model training [10],
graph problems [11, 12]… The goal of this paper is to pursue this work by
proposing a QUBO formulation for a radar waveform optimization problems, and
compare the performance and first results of our approach with brute-force
optimization on small sized instances of the ISLR problem. Hence, we aim to
use the exponential scalability of quantum computing to find new optimums for
large instances of the Integrated Side-Lobe Ratio (ISLR) problem. In the
following sections, we propose a QUBO formulation for the ISLR problem in its
most common formulation [13] i.e. with 2 possible phase states. Then, we
extend this formulation to a discrete number of phase states. In the end of
the paper, we propose a comparison of our first results with those obtained
with classical approaches, and we discuss the scalability of our algorithm
regarding the future improvements of quantum technologies.

##  2 The ISLR problem

###  2.1 The binary matched filter case

In this part, we introduce the ISLR cost function as defined in [13]. For this
instance, we consider that the reception filter is encoded with the same phase
shifts as the emitted signal. This instance is called the matched case. We
also consider only two possible values for the phases, $0$ and $\pi$,
respectively associated in the following to $-1$ and $1$. Hence, the solutions
take the form of a sequence of $N$ phase shift such as
$S=\\{s_{1},\dots,s_{N}\\}$ with $s_{i}\in\\{-1,1\\}$. The correlation for
delay $k$ is:

$C_{k}(S)=\sum_{i=1}^{N-k}s_{i}s_{i+k}\ ,$ (1)

Here, due to the symmetry of the product, we only consider strictly positive
values of $k$. From (1) we define the ISLR cost function as follows:

$E(S)=\sum_{k=1}^{N-1}C_{k}^{2}(S)\ .$ (2)

The above equation is a degree 4 polynomial i.e. not a QUBO form. The binary
matched filter case has been partially addressed in [14]. In section 3.1, we
improve the formulation by adding ancillary variables for a complete treatment
of this case, resulting in a QUBO equivalent of (2).

###  2.2 The binary mismatched filter case

In the previous section, we have defined the cost function of the binary
matched case of the ISLR problem. If we now consider that the reception filter
can be different, in term of length and phases shift values, from the emitted
signal, we consider the mismatched case. For this formulation, we pose
$S=\\{s_{1},\dots,s_{N}\\}$ and
$S^{\prime}=\\{s^{\prime}_{1},\dots,s^{\prime}_{M}\\}$ resp. the phases of the
emitted signal and the reception filter. In that case, $S^{\prime}$ can be
subdivided as $S^{\prime}=\\{S^{\prime}_{A},S^{\prime}_{M},S^{\prime}_{B}\\}$,
with $S^{\prime}_{A}$ the prefix of length $L_{A}$, $S^{\prime}_{M}$ of length
$N$ and $S^{\prime}_{B}$ the suffix of length $L_{B}$. Hence, we have
$k\in\\{-N+1,\dots,M-1\\}$ and we consider the main lobe for a delay
$k=L_{A}$. The cost function to minimize becomes:

$E_{M}(S,S^{\prime})=\sum_{\begin{subarray}{c}k=-N+1\\\ k\neq
L_{A}\end{subarray}}^{M-1}C_{k}^{{}^{\prime}2}(S,S^{\prime})\ \ with\ \
C^{\prime}_{k}(S,S^{\prime})=\sum_{i=\max(1,1-k)}^{\min(N,M-k)}s_{i}s^{\prime}_{i+k}\
.$ (3)

###  2.3 The poly-phase matched filter case

Previous work underlines the limitation for the binary matched case in terms
of ISLR minimal value. Barker codes [15] are defined as the best possible
sequences for some sequences of length $N\leq 13$, with maximal values of
side-lobes equal to 1. Current state of art states that there exists no other
Barker codes, at least for even sequence length [16]. In order to find new
optima, we can consider another instance where we no longer consider $2$
possible phase states, but a discrete number $Q$. In that case, phase states
are the $Q^{th}$ roots of unity $e^{\frac{i2\pi q}{Q}}$ with
$q\in\\{0,\dots,Q-1\\}$, and $R$ is defined as $R=\\{r_{1},\dots,r_{N}\\}$,
each $r_{n}$ being one of the $Q$ roots of unity, $n\in\\{1,\dots,N\\}$. In
the following, we will write $\bar{z}$ the conjugate of the complex number $z$
and $\mid.\mid$ the norm operator. From (1) and (2), we deduce the following
cost function in the poly-phase matched case.

$E_{Q}(R)=\sum_{k=1}^{N-1}\mid\tilde{C}_{k}(R)\mid^{2}\ \ with\ \
\tilde{C}_{k}(R)=\sum_{i=1}^{N-k}r_{i}\overline{r_{i+k}}\ .$ (4)

##  3 Problem implementation

In this section, we propose an extension on our previous work presented in
[14]. We first recall some notations and results in section 3.1. Then, in
section 3.2, we improve the QUBO formulation in the binary matched case.
Finally, we extend this work in section 3.3 to the poly-phase case.
Experimental results on quantum hardware are reported in section 4.

###  3.1 Previous work

The latter proposes a QUBO formulation for the ISLR problem in the binary
case. Due to the non-quadratic form of (3), we had to reformulate the problem
in the form of a QUBO, increasing the number of variables.

In [14], we pose the problem as follows : Given $x\in\\{-1;1\\}^{N}$ and
$y\in\\{-1;1\\}^{M}$ the sequence of spins respectively associated to the
emitted sequence and the reception filter. In the following, we pose $x^{T}$
the transpose of the vector $x$. Then, from (3), we pose:

$H_{C}(x,y)=\sum_{k\neq L_{A}}(x^{T}Q^{k}y)^{2}\ ,$ (5)

With $Q^{k}$ the delay matrix for a delay $k\in\\{-N+1,\dots,M-1\\}$ such as
$Q_{i,j}^{k}=1$ if $j=i+k$ and $0$ else. As mentioned in section 2.1, the ISLR
cost function is not a quadratic form. Hence, we have to pose:

$z=\widetilde{xy^{T}}\ \ and\ \ D=\sum_{k\neq
L_{A}}\widetilde{Q^{k}}\widetilde{Q^{k}}^{T}\ .$ (6)

Here, $\widetilde{.}$ represents the reshaping of a $(NM)$ matrix $A$ into a
$(NM,1)$ vector $a$ where $\widetilde{A_{(i,j)}}=a_{\psi(i,j)}$ with
$\psi(i,j)=jN+i$. Straightforward calculation show that:

$H_{C}(z)=z^{T}Dz\ .$ (7)

Due to this reformulation, most of $z$ solutions do not correspond to actual
$x,y$ solutions. Moreover, $z$ sequences minimizing $H_{C}(z)$ do not
correspond to actual solutions $x,y$ of $H_{C}(x,y)$. In order to get actual
solutions, we reshape back the vector $z$ of length $NM$ into a $(N,M)$ matrix
such as $Z_{i,j}=z_{\psi(i,j)}$. If and only if $rank(Z)=1$, we can write
$Z=xy^{T}$ and get $x$ and $y$ respectively from the first column and row of
$Z$. In [14], we define the following necessary and sufficient set of
conditions for $rank(Z)=1$. Note that this set of constraints imposes that
$x=y$, which corresponds to the binary matched case formulation of the ISLR
problem:

  1. 1.

$\forall\ i\in\\{0,\dots,N-1\\},\ Z_{i,i}=1$ ,

  2. 2.

$\forall\ (i,j)\in\\{0,\dots,N-1\\}^{2},\ Z_{i,j}=Z_{j,i}$ ,

  3. 3.

$\forall\ (i,j,k)\in\\{0,\dots,N-1\\}^{3}$, with $i<j<k,\
Z_{i,j}Z_{i,k}=Z_{j,k}$ .

In order to guarantee that it is never profitable to not respect the
constraint on the rank, we have to define a set of linear and quadratic cost
functions i.e. QUBOs which are minimal if and only if $rank(Z)=1$. The QUBO
formulations for the first two constraints are:

$h_{1}(z)=N-\sum_{i=0}^{N-1}z_{\psi(i,i)}\ ,$ (8)
$H_{2}(z)=\frac{(N-1)N}{2}-\sum_{\begin{subarray}{c}i,j=0\\\
i<j\end{subarray}}^{N-1}z_{\psi(i,j)}z_{\psi(j,i)}\ .$ (9)

For the sake of clarity in the following section, we add constants to these
formulations in order to set their minimal values to zero. However, during the
optimization, these constants can be removed without impacting the quality of
the result.

###  3.2 Improvements on QUBO formulation for the binary matched case

In [14], we concluded that the third constraint, due to its non-quadratic
formulation, could not be straightforward implemented as a QUBO. In [17], it
is demonstrated that there exists no quadratic equivalent of the third
constraint without addition of ancillary variables. Hence, we propose a QUBO
formulation for the third constraint which requires a set of
$N_{\alpha}=\binom{N}{3}$ ancillary variables
$z^{\alpha}\in\\{-1,1\\}^{N_{\alpha}}$, inspired by the work presented in
[17]. For the sake of simplicity, we consider that $z^{\alpha}_{(i,j,k)}$ is
the ancillary variable associated to the triplet $(i,j,k)$ where $0\leq
i<j<k\leq N$.

$H_{3}(z,z^{\alpha})=4\binom{N}{3}+H_{3Q}(z,z^{\alpha})+h_{3L}(z,z^{\alpha})\
,$ (10) $\displaystyle
H_{3Q}(z,z^{\alpha})=\sum_{\begin{subarray}{c}i,j,k=0\\\
i<j<k\end{subarray}}^{N-1}$
$\displaystyle(z_{\psi(i,j)}z_{\psi(i,k)}-z_{\psi(i,j)}z_{\psi(j,k)}-z_{\psi(i,k)}z_{\psi(j,k)}\dots$
$\displaystyle\dots-2z_{\psi(i,j)}z^{\alpha}_{(i,j,k)}\
,-2z_{\psi(i,k)}z^{\alpha}_{(i,j,k)}+2z_{\psi(j,k)}z^{\alpha}_{(i,j,k)})\ .$
(11)

$h_{3L}(z,z^{\alpha})=\sum_{\begin{subarray}{c}i,j,k=0\\\
i<j<k\end{subarray}}^{N-1}\left(z_{\psi(i,j)}+z_{\psi(i,k)}-z_{\psi(j,k)}-2z^{\alpha}_{(i,j,k)}\right)\
.$ (12)

From (7), (8), (9) and (10), we deduce the QUBO formulation for solving the
ISLR problem in the binary matched case :

$H(z,z^{\alpha})=H_{C}(z)+\lambda_{1}h_{1}(z)+\lambda_{2}H_{2}(z)+\lambda_{3}H_{3}(z,z^{\alpha})\
.$ (13)

With $\lambda_{1}$, $\lambda_{2}$ and $\lambda_{3}$ positive real factors
related to Lagrange multipliers. In order to prevent that a non-viable
solution minimizes (13), we have to define minimal values for the Lagrange
multipliers. First, straightforward calculations from (2) show that
$\smash{\displaystyle\max_{S}}\ E(S)=\frac{N(N-1)(2N-1)}{6}$. In the
following, we set $\Delta_{N}=\smash{\displaystyle\max_{S}}\ E(S)$ as the
difference between the lowest and the highest possible value of $H(z)$. As the
non-respect of constraints could lead to $H_{C}(z)=0$, there is no strictly
positive lower bound for the ISLR criteria in this case. However, in the
literature, lower bounds for (2) can be found in the binary matched case [18].
For $\lambda_{1}$, lets consider the worst case scenario where the optimal
solution of $H(z)$ implies that a single diagonal value of $Z$ is equal to
$-1$. In that situation, $h_{1}(z)=2$, and we have to set
$\lambda_{1}>\frac{\Delta_{N}}{2}$ in order to guarantee that it is never
profitable to break the constraint to get a better solution.
For $\lambda_{2}$, we consider a similar scenario where for a single couple of
$(i,j)$, $Z_{i,j}\neq Z_{j,i}$. In this situation, $H_{2}(z)=2$ and we have to
set $\lambda_{2}>\frac{\Delta_{N}}{2}$. For $\lambda_{3}$, we also consider a
scenario where the constraint is respected except for a single triplet
$(i,j,k)$. Hence, $H_{3}(z)\geq 2$ and we have to set
$\lambda_{3}>\frac{\Delta_{N}}{2}$.
In practice, these Lagrange multiplies can be set at lower positive values. We
consider here that a single non-respect of constraint will reduce the value of
$H_{C}(z)$ from the worst to the best possible solution, which is not the case
for most instances with different values of $N$.

###  3.3 QUBO formulation for the polyphase matched case

In this section, we propose a QUBO formulation of (4) in the polyphase matched
case. In this formulation, we consider a phase code of length $N$. Recall that
each phase state can take $Q$ possible values defined as the $Q^{th}$ roots of
unity $e^{\frac{i2\pi q}{Q}}$. In order to implement these complex and
discrete phase state, we pose $b=\\{0,1\\}^{NQ}$. $b$ is composed of $N$ blocs
of length $Q$ such as each bloc $b_{i}$ has exactly one non-null value at
index $q\in\\{0,\dots,Q-1\\}$. We also pose the $(N,NQ)$ phase matrix:

$\Phi=\begin{pmatrix}[e^{0},\dots,e^{\frac{i2\pi(Q-1)}{Q}}]&\dots&0\\\
\vdots&\ddots&\vdots\\\
0&\dots&[e^{0},\dots,e^{\frac{i2\pi(Q-1)}{Q}}]\end{pmatrix}\ .$ (14)

Straightforward calculations show that $x=\Phi b$, with $x\in\\{e^{\frac{i2\pi
q}{Q}},q=0,\dots,Q-1\\}^{N}$ encoding the complex phase values. With the same
approach as in section 3.1, we pose :

$\begin{split}&A^{k}=\Phi^{*}Q^{k}\Phi\ ,\\\ &D^{\prime}=\sum_{k\neq
0}\widetilde{A^{k}}\widetilde{A^{k^{T}}}^{T}\ ,\\\
&z^{\prime}=\widetilde{bb^{T}}\ .\end{split}$ (15)

In (15), $\Phi^{*}$ is the conjugate transpose $\overline{\Phi^{T}}$ of
$\Phi$. Straightforward calculations show that:

$H^{\prime}_{C}(z)=z^{\prime T}D^{\prime}z^{\prime}\ .$ (16)

As a consequence of the reformulation, most of $z^{\prime}$ solutions do not
correspond to actual $b$ solutions. As in 3.1, in order to get actual
solutions, $z^{\prime}$ of length $(NQ)^{2}$ has to be reshaped into a
$(NQ,NQ)$ matrix $Z^{\prime}$. $Z^{\prime}$ is composed of $N^{2}$ blocs
$Z^{(n,m)},n,m\in\\{0,\dots,N-1\\}^{2}$ of shape $(Q,Q)$ having a single non-
null element each such as:

$Z^{\prime}=\begin{pmatrix}Z^{\prime(0,0)}&\dots&Z^{\prime(0,N-1)}\\\
\vdots&\ddots&\vdots\\\
Z^{\prime(N-1,0)}&\dots&Z^{\prime(N-1,N-1)}\end{pmatrix}\ .$ (17)

In the following, we will note $Z^{\prime(n,m)}_{i,j}$ the term at the
$i^{th}$ row and $j^{th}$ column of the bloc $Z^{\prime(n,m)}$. We pose
$\phi(n,m)=nNQ+mQ$ and $\mu(n,m,i,j)=\phi(n,m)+\psi(i,j)$ such as
$z^{\prime}_{\mu(n,m,i,j)}=Z^{\prime(n,m)}_{i,j}$ with
$n,m\in\\{0,\dots,N-1\\}^{2}$ and $i,j\in\\{0,\dots,Q-1\\}^{2}$. In order to
guarantee that it is never favorable, in term of value of the cost function,
to not respect the one-hot encoding, we pose the following constraint cost
function :

$H^{\prime}_{OH}(z^{\prime})=\sum_{n=0}^{N-1}\sum_{m=0}^{N-1}\left(\sum_{i=0}^{Q-1}\sum_{j=0}^{Q-1}z^{\prime}_{\mu(n,m,i,j)}-1\right)^{2}\
.$ (18)

As in section 3.1, we can write $Z^{\prime}=bb^{T}$ and get the values of $x$
if and only if $rank(Z^{\prime})=1$. Then, by admitting that the one-hot
encoding is respected, we define the following set of necessary and sufficient
conditions $\forall n,m\in\\{0,\dots,N-1\\}^{2}$ and $\forall
i,j\in\\{0,\dots,Q-1\\}^{2}$:

  1. 1.

$Z^{\prime(n,m)}_{i,j}=Z^{\prime(m,n)}_{j,i}$ ,

  2. 2.

If $Z^{\prime(n,n)}_{i,i}=1$, then
$\sum_{m=0}^{N-1}\sum_{j=0}^{Q-1}Z^{\prime(m,n)}_{j,i}=N$ and
$\sum_{m=0}^{N-1}\sum_{j=0}^{Q-1}Z^{\prime(n,m)}_{i,j}=N$ ,

  3. 3.

If $Z^{\prime(n,n)}_{i,i}=0$, then
$\sum_{m=0}^{N-1}\sum_{j=0}^{Q-1}Z^{\prime(m,n)}_{j,i}=0$ and
$\sum_{m=0}^{N-1}\sum_{j=0}^{Q-1}Z^{\prime(n,m)}_{i,j}=0$ .

Figure 1: Example of solution matrix $Z$ for $N=4$ and $Q=3$. The value of
each phase state $n$ is retrieved by looking at the index $q$ of each non-null
value in the first row of blocs. Here, the corresponding sequence is
$x=[e^{\frac{i2\pi}{3}},e^{\frac{i2\pi}{3}},e^{0},e^{\frac{i2\pi}{3}}]$

With $Z^{\prime}$ taking values in $\\{0,1\\}$, the second and third
conditions imply that for given $p,q$, if $Z^{\prime(p,q)}_{i,j}=1$, then
$\forall n,m\in\\{0,\dots,N-1\\}^{2}$, $Z^{\prime(n,m)}_{i,j}=1$. This results
in a $Z^{\prime}$ matrix full of zeros except for $N$ rows (resp. columns)
having exactly $N$ non-null values which implies that $rank(Z^{\prime})=1$.
For the first condition, we pose the following cost function inspired by (9) :

$H^{\prime}_{S}(z^{\prime})=\sum_{n=0}^{N-1}\sum_{n<m}^{N-1}\sum_{i=0}^{Q-1}\sum_{i<j}^{Q-1}z^{\prime}_{\mu(n,m,i,j)}+z^{\prime}_{\mu(m,n,j,i)}-2z^{\prime}_{\mu(n,m,i,j)}z^{\prime}_{\mu(m,n,j,i)}\
.$ (19)

Straightforward calculation from the second condition leads to a $3^{rd}$
degree polynomial, which is not a QUBO form. However, as one-hot encoding is
imposed, we know that each row (resp. column) of each block
$Z^{\prime(n,m)}_{i,j}$ contains at most $1$ non-null value. This implies that
if the non-null value is at a given row (resp. column) of the block, it cannot
be at another row (resp. column) of the block. If we impose that all rows
(resp. columns) of each horizontally (resp. vertically) adjacent blocks have
to be equal, then for a given $n,m\in\\{0,\dots,N-2\\}^{2}$ and $i$ (resp.
$j$) $\in\\{0,\dots,Q-1\\}$:

$\begin{split}&\sum_{j=0}^{Q-1}Z^{\prime(n,m)}_{i,j}=\sum_{j=0}^{Q-1}Z^{\prime(n,m+1)}_{i,j}\
,\\\ \text{resp.}\ \
&\sum_{i=0}^{Q-1}Z^{\prime(n,m)}_{i,j}=\sum_{i=0}^{Q-1}Z^{\prime(n+1,m)}_{i,j}\
.\end{split}$ (20)

Note that the above equalities both guarantee the second and third conditions,
as the value of the sums, equal to $0$ or $1$, imply that the sum of values of
each rows of $Z^{\prime}$ is equal to $0$ or $N$. Hence, from (20),
straightforward calculation allow us to define the constraint cost function
for both the second and the third conditions :

$H_{CH}(z^{\prime})=\sum_{n=0}^{N-1}\sum_{i=0}^{Q-1}\sum_{m=0}^{N-2}\left(\sum_{j=0}^{Q-1}z^{\prime}_{\mu(n,m,i,j)}-\sum_{j=0}^{Q-1}z^{\prime}_{\mu(n,m+1,i,j)}\right)^{2}\
,$ (21)
$H_{CV}(z^{\prime})=\sum_{m=0}^{N-1}\sum_{j=0}^{Q-1}\sum_{n=0}^{N-2}\left(\sum_{i=0}^{Q-1}z^{\prime}_{\mu(n,m,i,j)}-\sum_{i=0}^{Q-1}z^{\prime}_{\mu(n+1,m,i,j)}\right)^{2}\
.$ (22)

From (16), (18), (19), (22) and (21), we deduce the following cost function
for solving the ISLR problem in the $Q$-phase states matched case :

$H^{\prime}(z^{\prime})=H_{C}(z^{\prime})+\lambda_{OH}H^{\prime}_{OH}(z^{\prime})+\lambda_{S}H^{\prime}_{S}(z^{\prime})+\lambda_{CH}H_{CH}(z^{\prime})+\lambda_{CV}H_{CV}(z^{\prime})\
.$ (23)

With $\lambda_{OH}$, $\lambda_{S}$, $\lambda_{CH}$ and $\lambda_{CV}$ positive
real factors called Lagrange multipliers. As in (13), we have to define
minimal values for these multipliers by considering the worst case scenario
favoring the non respect of their associated constraints. Then, we can pose
$\Delta_{N,Q}$ as in section 3.2, which corresponds to the difference between
the best and the worst possible value, and define the Lagrange multipliers
following this value. For $\lambda_{OH}$, a single non-respect of the
corresponding constraint implies that $H_{OH}(z^{\prime})=1$ which leads to
setting $\lambda_{OH}>\Delta_{N,Q}$. Same goes for $\lambda_{S}$ and
$\lambda_{CH}$ as respectively $H^{\prime}_{S}(z^{\prime})=1$ and
$H^{\prime}_{CH}(z^{\prime})=1$ in case of a single non respect, which leads
to $\lambda_{S}>\Delta_{N,Q}$ and $\lambda_{CH}>\Delta_{N,Q}$. Due to the
similar form of $H^{\prime}_{CV}(z^{\prime})$ and
$H^{\prime}_{CH}(z^{\prime})$, we can set $\lambda_{CV}=\lambda_{CH}$. As for
the binary case, in practice, these Lagrange multipliers can be set at lower
values, as near-optimal values of $H^{\prime}_{C}(z^{\prime})$ can be obtained
with respect of all the constraints.

##  4 Results

###  4.1 Experimental context

In this section, we propose and discuss the results obtained on the D-Wave
adiabatic quantum computer [19]. D-Wave is a Canadian company which proposes
access to their quantum devices through a cloud based service called D-Wave
Leap. The device we use in the following is the D-Wave Advantage quantum
computer, having 5760 available qubits and 15 couplers per qubits. The number
of couplers quantifies the number of interconnections available between qubits
i.e. variables. In the QUBO formulations presented above, a product between
two variables implies there is a coupler between their two corresponding
qubits. As this number of products can exceed 15, the embedding function
provided by D-Wave libraries binds qubits with each other, creating logical
qubits from multiple physical qubits. In the computation, logical qubits act
as a single variable. Consequently, due to this embedding constraint, the
actual limitation of problem size that can be implemented on the quantum
machine is below the theoretical limitation ($(NQ)^{2}<5760$ for example for
the Q-states formulation). Recent publications from D-Wave present their
hardware having 7800+ qubits available and more interconnections. However, in
the following, we will consider current limitations of D-Wave hardware at 5760
qubits and 15 interconnections available.
In order to compare our results, we also used a simulated annealing library
provided by D-Wave called dwave-neal. First, we used this tool in order to
implement larger instances of the problem which cannot be implemented in the
quantum hardware. Then, due to the inherent noise of quantum computation,
multiple executions i.e. samples were required in order to guarantee the
quality of solutions obtained and correctly estimate the average computation
time for a given instance of the problem. Fig. 2 presents the correlation
between the number of variables and the probability of obtention of a global
minima for small instances. Green dotted lines represent the average number of
iterations required to obtain an optimal solutions for a given number of
variables. Nevertheless, note that actual solutions (respecting all
constraints without minimizing the ISLR criteria) are more often obtained.
Unfortunately, as we write these lines, dwave-neal does not provide a quantum
noise simulator. Consequently, our estimations of the time required to obtain
a solution for any instance will be based on an extrapolation of computation
time for small instances.

Figure 2: Number of variables required to implement the binary and poly-phase
formulations for small instances of the ISLR problem.

In the following, we define the computation time for a single sample as a sum
of the delay time, the annealing time and the readout time. Delay time is
fixed at $21\mu s$, and consist in preparing the system in an equiprobability
of obtention of any sequence. Then, the annealing time represents the
convergence time from the initial state to the final state. The latter is
parameterized by the QUBO, and its minimal energy configurations correspond to
solutions minimizing the QUBO i.e. solutions respecting all constraints and
minimizing the ISLR criteria. Previous work shown that the optimal annealing
time logarithmically scales with the number of variables [20]. For this
problem, search heuristics have shown that optimal solutions were most
probably obtained for annealing time values between $50\mu s$ and $250\mu s$
with a number of variables scaling from $10$ to $144$. The readout time also
logarithmically scales with the number of variables, from $80\mu s$ to $115\mu
s$ for variables scaling from $10$ to $144$.

###  4.2 Results in the binary matched case

As a reminder, this section will consider submitting the binary formulation
defined by (13) and the $Q$-phase states formulation defined by (23) with
$Q=2$ to the D-Wave quantum computer. For this instance of the ISLR problem,
current limitations in terms of sequence length i.e. the value of $N$ are
presented in various papers [21, 22, 23]. Our first results are presented in
Fig. 3 for both binary and poly-phase state formulations. On this graph,
computation time is obtained by multiplying the average number of samples
required to obtain an optimal solution by the computation time of a single
sample. For the simulated annealing plot, the average number of samples is
obtained on a classical simulator, but the computation time is based on the
quantum annealing obtention time. The goal of this plot is to represent the
obtention time on a quantum computer with similar error rates than simulated
annealing. Finally, state-of-art plot corresponds to results presented in [24]
with different classical approaches.

Figure 3: Comparison of computation time for different instances of the ISLR
problem and classical approaches in the binary matched case

For these results and for both formulations, we have set all the Lagrange
multipliers at $\lambda=10$. As discussed in section 3.2, these multipliers
can be set as lower values than the theory (based on worst case scenario) in
order to increase the probability of obtention of optimal solutions. Indeed,
as the quantum annealer uses tunneling effect in order to converge to a global
minima, decreasing the energy of the potential barriers between configurations
increases the probability of the system to cross the barrier and reach a new
minima [19]. Search heuristics shown that on the D-Wave hardware we used for
our first results, high values of Lagrange multipliers reduces the number of
optimal solutions. This is due to the relative low difference in energy
between sub-optimal actual solutions (minimizing constraint cost functions
without minimizing (7)) and optimal solutions.

###  4.3 Results in the poly-phase states case

In this section, we present the improvements in the value of the cost function
for a discrete number of phase state. In the previous section, we presented a
straightforward correlation between the computation time and the number of
variables. Hence, obtention time for the $Q$-phase state instances can be
deduced from the obtention time in the binary case presented in sections 4.1
and 4.2, as the number of logical variables required is $(NQ)^{2}$, with $N$
the length of the sequence and $Q$ the number of phase states. However, for
small $N$ and $Q$ values, simulations and brute-force computation provided new
minimum for the ISLR criteria, presented in Fig. 3. These results underline
the advantage of increasing the number of phase states, especially for high
values of N.

Figure 4: Value of the ISLR criteria for Q $\geq$ 2 phase states

In the literature, [18] statistically demonstrated that for high values of $N$
and when $N=Q$, poly-phase Barker codes can be found. Poly-phase Barker codes
have a maximal peak-to-side-lobe (PSL) value of 1, which implies that the ISLR
criteria is at most equal to $N$. These results can also be compared to
periodic poly-phases codes like Golomb sequences [18] for example.

###  4.4 Comparisons between the approaches and limits of the model

In section 3, we presented two approaches to solve the ISLR problem in binary
and poly-phase cases. Due to the quadratic reformulation, especially in the
binary case, size of the search space has been increased. Consequently, we
restricted our results to the matched case, where the reception filter has the
same phase code as the emitted signal, in order to limit the size of the
search space and present our first results. Moreover, the mismatched case (3)
requires an additional condition to maximize the value of the main-lobe, which
also has to be implemented as a penalty cost function in the form of a QUBO.
In our present work, we have not found any way in the literature yet to
implement it, or at least without greatly increasing the size of the search
space. Nevertheless, note that removing the symmetry cost function in (23)
extends the formulation to the mismatched case, without any guarantee of
optimality for the main-lobe value.
Disregarding the error of the quantum hardware, highlighted in Fig. 3, larger
instances may be implemented by duplicating some variables with a lot of
connections. Even if D-Wave embedding functions already binds logical
variables to multiple physical qubits, these generic functions may not provide
an optimal embedding. Hence, including the optimal embedding in the QUBO
formulation could increase the number of implementable instances, at the cost
of additional ancillary variables.
In term of scalability in the binary matched case, for $N>21$, the number of
variables required to encode the binary case formulation $N^{2}+\binom{N}{3}$
is greater that the number of variables required for the $Q$-phase state
formulation $4N^{2}$. Moreover, optimal sequences of length $N<21$ have
already been found. Hence, in term of number of variables, the $Q$-phase state
formulation with $Q=2$ would be more profitable than the binary case
formulation in order to find new optimums for the ISLR problem.

##  5 Conclusion

In conclusion, our work proposes a new method to find optimal waveforms in the
binary and poly-phase matched case, which is compatible with the promising
quantum annealing technology. We also present our first results on the D-Wave
quantum computer and discuss the scalability of our algorithm regarding the
machine hardware constraints. We conclude that current limitations are
hardware based, and that improvements of the machine would close the gap
between our results and state-of-the-art optimal phase sequences. In the poly-
phase state, our first results underlines the advantage of generalizing the
formulation to a discrete number of phases, by proposing new minimums for the
ISLR criteria.
To complete this paper, future work will consist in studying the optimal
parameters of the model, especially for the annealing time and the way the
problem is embedded. It could be also interesting to test our method on other
quantum annealers, as the Pasqal machine [25], which uses spatially arranged
cold atoms to perform quantum annealing. Moreover, we could find QUBO
formulations to optimize other signal processing criteria as Doppler tolerance
[26] or the PSL criteria [27].

## References

  * [1] C. F. Castillo-Rubio, S. Llorente-Romano, and M. Burgos-Garcia, “Spatially variant apodization for squinted synthetic aperture radar images,” _IEEE Transactions on Image Processing_ , vol. 16, no. 8, pp. 2023–2027, 2007\.
  * [2] F. Arlery, R. Kassab, U. Tan, and F. Lehmann, “Efficient optimization of the ambiguity functions of multi-static radar waveforms,” in _2016 17th International Radar Symposium (IRS)_ , 2016, pp. 1–6.
  * [3] F. Xin, B. Wang, S. Li, X. Song, and C.-H. Wang, “Adaptive radar waveform design based on weighted mi and the difference of two mutual information metrics,” _Complexity_ , vol. 2021, pp. 1–12, 01 2021.
  * [4] T. Packebusch and S. Mertens, “Low autocorrelation binary sequences,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 49, 12 2015.
  * [5] J. Gallardo, C. Cotta, and A. Fernández-Leiva, “Finding low autocorrelation binary sequences with memetic algorithms,” _Applied Soft Computing_ , vol. 9, pp. 1252–1262, 09 2009.
  * [6] B. Militzer, M. Zamparelli, and D. Beule, “Evolutionary search for low autocorrelated binary sequences,” _IEEE Transactions on Evolutionary Computation_ , vol. 2, no. 1, pp. 34–39, 1998.
  * [7] U. Tan, O. Rabaste, C. Adnet, F. Arlery, and J.-P. Ovarlez, “Optimization Methods for Solving the Low Autocorrelation Sidelobes Problem,” pp. 1–5, May 2016. [Online]. Available: https://hal.science/hal-01360260
  * [8] B. Tasseff, T. Albash, Z. Morrell, M. Vuffray, A. Y. Lokhov, S. Misra, and C. Coffrin, “On the emerging potential of quantum annealing hardware for combinatorial optimization,” 2022.
  * [9] C. Bauckhage, N. Piatkowski, R. Sifa, D. Hecker, and S. Wrobel, “A qubo formulation of the k-medoids problem,” 09 2019.
  * [10] P. Date, D. Arthur, and L. Pusey-Nazzaro, “QUBO formulations for training machine learning models,” _Scientific Reports_ , vol. 11, no. 1, may 2021\. [Online]. Available: https://doi.org/10.1038%2Fs41598-021-89461-4
  * [11] C. Calude, M. Dinneen, and R. Hua, “Qubo formulations for the graph isomorphism problem and related problems,” _Theoretical Computer Science_ , vol. 701, 06 2017.
  * [12] A. Lucas, “Ising formulations of many NP problems,” _Frontiers in Physics_ , vol. 2, 2014. [Online]. Available: https://doi.org/10.3389%2Ffphy.2014.00005
  * [13] T. Packebusch and S. Mertens, “Low autocorrelation binary sequences,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 49, no. 16, p. 165001, mar 2016. [Online]. Available: https://doi.org/10.1088%2F1751-8113%2F49%2F16%2F165001
  * [14] T. Presles, C. Enderli, R. Bricout, F. Aligne, and F. Barba-Resco, “Phase-coded radar waveform AI-based augmented engineering and optimal design by Quantum Annealing,” Aug. 2021, working paper or preprint. [Online]. Available: https://hal.science/hal-03318130
  * [15] M. Trevorrow and D. Farmer, “The use of barker codes in doppler sonar measurements,” _Journal of Atmospheric and Oceanic Technology - J ATMOS OCEAN TECHNOL_ , vol. 9, pp. 699–704, 10 1992.
  * [16] J. Willms, “A note on barker sequences of even length,” 2021.
  * [17] A. Mandal, A. Roy, S. Upadhyay, and H. Ushijima-Mwesigwa, “Compressed quadratization of higher order binary optimization problems,” 2020.
  * [18] “Matched filter,” pp. 20–33, 2004. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/0471663085.ch2
  * [19] M. Johnson, M. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. Berkley, J. Johansson, P. Bunyk, E. Chapple, C. Enderud, J. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, and G. Rose, “Quantum annealing with manufactured spins,” _Nature_ , vol. 473, pp. 194–8, 05 2011.
  * [20] O. Galindo and V. Kreinovich, “What is the optimal annealing schedule in quantum annealing,” pp. 963–967, 2020.
  * [21] E. Rodríguez-Heck, “Linear and quadratic reformulations of nonlinear optimization problems in binary variables,” _4OR_ , vol. 17, 11 2018.
  * [22] J. Gallardo, C. Cotta, and A. Fernández-Leiva, “Finding low autocorrelation binary sequences with memetic algorithms,” _Applied Soft Computing_ , vol. 9, pp. 1252–1262, 09 2009.
  * [23] D. Padilha, “Solving np-hard problems on an adiabatic quantum computer,” Ph.D. dissertation, 10 2014.
  * [24] M. V. H Houdrouge, “Low auto-correlation binary sequences,” 8 2019.
  * [25] “Pasqal quantum computer.” [Online]. Available: https://www.pasqal.com/
  * [26] R. Amar, M. Alaee-Kerahroodi, P. Babu, and B. S. M. R., “Designing interference-immune doppler-tolerant waveforms for radar systems,” _IEEE Transactions on Aerospace and Electronic Systems_ , pp. 1–20, 2022\.
  * [27] M. F. Keskin, R. F. Tigrek, C. Aydogdu, F. Lampel, H. Wymeersch, A. Alvarado, and F. M. Willems, “Peak sidelobe level based waveform optimization for ofdm joint radar-communications,” pp. 1–4, 2021.