# Detecting quantum phase transitions in a frustrated spin chain via transfer
learning of a quantum classifier algorithm

André J. Ferreira-Martins  International Institute of Physics, Federal
University of Rio Grande do Norte, 59078-970 Natal, Brazil  Leandro Silva
International Institute of Physics, Federal University of Rio Grande do Norte,
59078-970 Natal, Brazil  Instituto de Física de São Carlos, Universidade de
São Paulo, CP 369, 13560-970 São Carlos, SP, Brazil  Alberto Palhares
International Institute of Physics, Federal University of Rio Grande do Norte,
59078-970 Natal, Brazil  Departamento de Física Teórica e Experimental,
Federal University of Rio Grande do Norte, 59078-970 Natal, Brazil  Rodrigo
Pereira  International Institute of Physics, Federal University of Rio Grande
do Norte, 59078-970 Natal, Brazil  Departamento de Física Teórica e
Experimental, Federal University of Rio Grande do Norte, 59078-970 Natal,
Brazil  Diogo O. Soares-Pinto  Instituto de Física de São Carlos, Universidade
de São Paulo, CP 369, 13560-970 São Carlos, SP, Brazil  Rafael Chaves
International Institute of Physics, Federal University of Rio Grande do Norte,
59078-970 Natal, Brazil  School of Science and Technology, Federal University
of Rio Grande do Norte, 59078-970 Natal, Brazil  Askery Canabarro
<EMAIL_ADDRESS>Instituto de Física de São Carlos, Universidade de São Paulo,
CP 369, 13560-970 São Carlos, SP, Brazil  Grupo de Física da Matéria
Condensada, Núcleo de Ciências Exatas - NCEx, Campus Arapiraca, Universidade
Federal de Alagoas, 57309-005 Arapiraca-AL, Brazil

###### Abstract

The classification of phases and the detection of phase transitions are
central and challenging tasks in diverse fields. Within physics, it relies on
the identification of order parameters and the analysis of singularities in
the free energy and its derivatives. Here, we propose an alternative framework
to identify quantum phase transitions. Using the axial next-nearest neighbor
Ising (ANNNI) model as a benchmark, we show how machine learning can detect
three phases (ferromagnetic, paramagnetic, and a cluster of the antiphase with
the floating phase). Employing supervised learning, we demonstrate the
feasibility of transfer learning. Specifically, a machine trained only with
nearest-neighbor interactions can learn to identify a new type of phase
occurring when next-nearest-neighbor interactions are introduced. We also
compare the performance of common classical machine learning methods with a
version of the quantum nearest neighbors (QNN) algorithm.

##  I INTRODUCTION

Machine Learning (ML) has proven its efficiency and success in many scientific
as well as business sectors Goodfellow  _et al._ (2016); Mehta  _et al._
(2018); Altman (1992); Olson  _et al._ (2016); Kelleher  _et al._ (2015);
Charnock and Moss (2017); von Marttens  _et al._ (2022); Carrillo  _et al._
(2015); Torlai  _et al._ (2018); Iten  _et al._ (2020); Carleo and Troyer
(2017); Torlai and Melko (2016); Ghiringhelli  _et al._ (2015); Carrasquilla
and Melko (2017); Broecker  _et al._ (2017); Ch’ng  _et al._ (2017); Deng  _et
al._ (2017); Huembeli  _et al._ (2018); Goes  _et al._ (2021). In essence, we
can teach computers to see patterns by progressively exposing them to quality
inputs, which is crucial for data-driven solutions given the gigantic and
ever-increasing amount of raw data. Within any branch of ML, substantial
improvements in state-of-the-art solutions are strongly related to algorithmic
and hardware advances. And, although we still need to be careful about setting
long-term expectations, recent breakthroughs in the current noisy
intermediate-scale quantum (NISQ) era el al. (2019); Preskill (2018); Bouland
_et al._ (2020); Farhi  _et al._ (2014) put quantum computing among the most
promising directions towards significant progress in machine learning. Within
this context, there has been a number of different approaches seeking for
quantum advantages in machine learning ranging from the quantum analog of
neural networks Schuld  _et al._ (2014), routines for supervised or
unsupervised learning Lloyd  _et al._ (2013); Wiebe  _et al._ (2015), quantum
reinforcement learning Dong  _et al._ (2008) and quantum pattern recognition
Horn and Gottlieb (2001) (see references Schuld  _et al._ (2015); Biamonte
_et al._ (2017); Carrasquilla and Torlai (2021) for a detailed review).

A field where machine learning has been particularly successful is that of
quantum matter and quantum information. Classical machine learning techniques
were used to perform quantum state tomography Torlai and Melko (2016), to
approximate the ground state of many Hamiltonians of interest Carleo and
Troyer (2017), for the description of causal networks Kriváchy  _et al._
(2020); D’Alessandro  _et al._ (2023); Polino  _et al._ (2023) and finding
violations of Bell inequalities Deng  _et al._ (2017); Canabarro  _et al._
(2019a), among many other applications. Importantly, such classical methods
have also been proven capable of tackling a central topic in many-body
physics, that of classifying phase transitions, a thorny goal especially due
to the exponential increase of Hilbert space describing quantum systems. Apart
from simple transitions, witnessed by non-analyticities in order parameters,
more general quantum phase transitions require large lattice sizes, a costly
computational task for which a variety of classical machine learning
techniques provide alternative and reliable approaches Broecker  _et al._
(2017); Carrasquilla and Melko (2017); Canabarro  _et al._ (2019b); Ch’ng  _et
al._ (2017). It seems thus natural to consider whether quantum machine
learning can also identify phase transitions. Indeed, machine learning based
on hybrid quantum-classical variational circuits has been shown to detect
phase transitions in the simple Hamiltonians, such as the transverse field
Ising and XXZ models Uvarov  _et al._ (2020); Lazzarin  _et al._ (2021);
Guimarães  _et al._ (2002a); Monaco  _et al._ (2023). Our approach
distinguishes itself significantly from others, primarily through the
implementation of transfer learning using a quantum classifier algorithm. This
algorithm is exclusively trained within a specific segment of the phase
diagram while testing on the rest of the phase diagram. We also explore
optimized data preprocessing for compatibility with real quantum hardware.
This demonstrates the effectiveness of our technique, as discussed in detail
herein.

Our aim in this paper is to show that the Quantum Nearest Neighbours (QNN)
algorithm Schuld  _et al._ (2014) also provides a well-founded tool for
classifying quantum phase transitions. Moving beyond the models previously
considered, we benchmark the QNN performance by employing the axial next-
nearest neighbor Ising (ANNNI) model Selke (1988); Suzuki  _et al._ (2013)
used, for instance, to investigate the magnetic order in quasi-one-dimensional
spin ladder materials Wen  _et al._ (2015), quantum melting of crystalline
order in Rydberg atom systems Sela  _et al._ (2011), interactions between
Majorana edge modes in arrays of Kitaev chains Hassler and Schuricht (2012);
Milsted  _et al._ (2015), and quench dynamics and dynamical phase transitions
Karrasch and Schuricht (2013); Robertson  _et al._ (2023); Haldar  _et al._
(2021). The ANNNI is the simplest model combining the effects of quantum
fluctuations and frustrated exchange interactions, a combination from which a
rich ground state phase diagram arises Villain and Bak (1981); Allen  _et al._
(2001); Rieger and Uimin (1996); Guimarães  _et al._ (2002b); Beccaria  _et
al._ (2007); Nagy (2011). It thus provides an interesting challenge to the QNN
algorithm capabilities.

Importantly, even though the input data to the quantum algorithm is
considerably small, the full $198$ raw pairwise correlation functions between
the spins for a lattice with 12 sites, i.e., an input array of $198$ real
features. And even if each of these variables is mapped to just one bit, we
would still require a large amount of qubits. As better detailed ahead, to be
implemented, the QNN algorithm that we use requires $2n+2$ qubits for a
$n$-sized input vector. In order to make the computational simulation as well
as its implementation in a real quantum computer feasible, we first proceed
with a pre-processing of the data, consisting of a feature selection followed
by a discretization and a final one-hot encoding step. With that, we reduce to
$4$ the number of features that in turn require $10$ qubits to be analyzed by
the quantum algorithm.

As we show, even after significantly reducing the input data, to make it
compatible with quantum computational requirements, the QNN algorithm still
allows for a successful learning of phase transitions. More precisely, we
demonstrate the transfer learning in the ANNNI model, as by training the
machine with nearest-neighbour interactions only, it also accurately predicts
the phase transitions happening at regions including next-nearest-neighbor
interactions. Interestingly, the QNN performs better than its classical
counterpart, called K-Nearest Neighbors (KNN), when exposed to the same input
data, thus providing a proof-of-principle example of a possible quantum
advantage in accuracy.

The paper is organized as follows. In Sec. II we describe the ANNNI model. In
Sec. III we provide a succinct but comprehensive overview of classification
problems in machine learning, also describing the KNN and QNN algorithms. In
Sec. IV we detail the data pre-processing required to make the problem
amenable to be implemented in near-term quantum devices. In Sec. V we present
our results regarding the learning of phase transitions in the ANNNI model. In
Sec. VI we discuss our results and point out interesting directions for future
research. Finally, in the Appendix we provide technical details about some of
the classical machine learning techniques we have employed in the pre-
processing of the data.

##  II The ANNNI Model

With the goal of analyzing the use of a quantum classifier algorithm to
witness phase transitions in a quantum many-body system, we chose the axial
next nearest-neighbor Ising (ANNNI) model. The reason stems from the fact that
this model displays a non-trivial and rich phase diagram. As it happens, ANNNI
is the simplest model combining quantum fluctuations and competing frustrated
exchange interactions. The first is induced by the presence of a transverse
field while the latter is due to the fact that even though the interaction is
ferromagnetic for nearest neighbors, it becomes antiferromagnetic for next-
nearest neighbors.

The Hamiltonian for the ANNNI model is given by Selke (1988); Suzuki  _et al._
(2013)

$H=-J\sum_{j=1}^{N}\left(\sigma_{j}^{z}\sigma_{j+1}^{z}-\kappa\sigma_{j}^{z}\sigma_{j+2}^{z}+g\sigma_{j}^{x}\right),$
(1)

where $\sigma^{\alpha}_{j}$ ($\alpha=x,y,z$), are Pauli matrices acting on
spin-$1/2$ degrees of freedom at site $j$ of a one-dimensional lattice with
$N$ sites and periodic boundary conditions. The parameter $J>0$ is a coupling
constant that sets the energy scale of the problem (we set $J=1$) and is
associated with the nearest-neighbor ferromagnetic exchange interaction. The
dimensionless coupling constants $\kappa$ and $g$ are related to the next-
nearest-neighbor interaction and the transverse magnetic field, respectively.

The groundstate phase diagram of the ANNNI model is well understood and known
to contain four phases separated by three quantum phase transitions:
ferromagnetic, antiphase, paramagnetic, and floating phase. In a nutshell, the
ferromagnetic phase is characterized by a uniform spontaneous magnetization,
with one of the ground states given by
$\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow$. In turn,
the antiphase breaks the lattice translational symmetry and has long-range
order with a four-site periodicity of the form
$\uparrow\uparrow\downarrow\downarrow\uparrow\uparrow\downarrow\downarrow$.
Distinctively, the paramagnetic phase is disordered and has a unique ground
state with spins pointing predominantly along the field direction. Finally,
the floating phase is gapless with correlation functions decaying as a power-
law for large distances, in contrast with the other phases that have a finite
energy gap and exponentially decaying correlations.

For $\kappa=0$, the transverse field Ising model is reproduced, exactly
solvable via the mapping to non-interacting spinless fermions. Along the
$\kappa=0$ line, a second-order phase transition occurs at $g=1$, separating
the ferromagnetic phase at $g<1$ from the paramagnetic phase at $g>1$. In
particular, exactly at the critical point $g=1$, the energy gap vanishes.

For $g=0$, there is a transition between the ferromagnetic phase at small
$\kappa$ and the antiphase at large $\kappa$ occurring at $\kappa=1/2$. Notice
that with $g=0$ the model becomes classical, since all operators in the
Hamiltonian commute with each other. At this classical transition point, any
configuration that does not have three neighboring spins pointing in the same
direction is a ground state, showing that the degenerescence of the ground
state increases exponentially with the system size.

For $g\neq 0$ and $\kappa\neq 0$, the critical lines have to be determined
numerically since the model is not integrable any longer. For $0\leq\kappa\leq
1/2$, the Ising transition between paramagnetic and the ferromagnetic phases
extends from the $g=1$, $\kappa=0$ until the degenerate point $g=0$,
$\kappa=1/2$, a multicritical point at which several transition lines
coincide. There are two other transition lines that start at the multicritical
point and extend to the high-frustration regime $\kappa>1/2$. For fixed $g>0$
and increasing $\kappa>1/2$, we first encounter a Berezinsky-Kosterlitz-
Thouless (BKT) transition from the paramagnetic phase to the floating phase.
Detecting the BKT transition is challenging because the correlation length
diverges exponentially at the critical point. As we increase $\kappa$ further,
there is a commensurate-incommensurate (CIC) transition from the floating
phase to the antiphase. Numerical density matrix renormalization group results
for long spin chains Beccaria  _et al._ (2007) show that the floating phase
occupies a rather narrow region in the phase diagram, which makes it hard to
discern the BKT from the CIC transition for small system sizes.

Using perturbation theory in the regime $\kappa<1/2$ Suzuki  _et al._ (2013)
or by fitting numerical results Beccaria  _et al._ (2007)) in the regime
$\kappa>1/2$, one can obtain approximate expressions for the transition lines.
For instance, the critical value of $g$ for the Ising transition for
$0\leq\kappa\leq 1/2$ is approximately given by Suzuki  _et al._ (2013)

$g_{\textrm{I}}(\kappa)\approx\frac{1-\kappa}{\kappa}\left(1-\sqrt{\frac{1-3\kappa+4\kappa^{2}}{1-\kappa}}\right).$
(2)

In turn, the critical value of $g$ for the BKT transitions for
$1/2<\kappa\lesssim 3/2$ is approximated by Beccaria  _et al._ (2007)

$\displaystyle g_{\textrm{BKT}}(\kappa)$ $\displaystyle\approx$ $\displaystyle
1.05\sqrt{(\kappa-0.5)(\kappa-0.1)}.$ (3)

We use these approximations to make benchmark comparisons to our heuristic
results.

###  II.1 Our dataset

As will be discussed in more detail throughout the paper, we use the pairwise
correlations among all spins in the lattice as the training data for the
machine learning algorithms. Given $N$ spins, we have a total of $3\times
C_{2}=\binom{N}{2}$ observables for up to (second) nearest neighbors, hence
the combination by (2). Thus, the features are given by
$\left\\{\langle\sigma^{x}_{i}\sigma^{x}_{j}\rangle,\langle\sigma^{y}_{i}\sigma^{y}_{j}\rangle,\langle\sigma^{z}_{i}\sigma^{z}_{j}\rangle\right\\}$
with, $j>i$ and $i=[1,N-1]$ where $N$ is the number of spins in the lattice
and
$\langle\sigma^{x}_{i}\sigma^{x}_{j}\rangle=\langle\lambda_{0}|\sigma_{i}^{x}\sigma_{j}^{x}|\lambda_{0}\rangle$
is the expectation value of the spin correlation for the Hamiltonian ground
state $|\lambda_{0}\rangle$ (and similarly for the other expectation values).
In our case, we take N = 12, a manageable size for both computational and
analytical evaluation of the ground state of the ANNNI Hamiltonian. This
allows us to efficiently compute a set of 198 pairwise expectation values,
which will serve as the (raw) input features for the machine learning
algorithm.

It is worth pointing out that, even if one only has access to short chains,
the Ising transition can still be captured correctly Guimarães  _et al._
(2002b). However, detecting the BKT transitions using standard approaches
requires computing observables for significantly longer chains Beccaria  _et
al._ (2007). Notwithstanding, as we will see below, even though our data
regards a quite short chain $N=12$, the machine learning algorithms, both
classical and quantum, will be able to identify not only the Ising but also
the antiphase and the paramagnetic phases, lumping the BKT and CIC transitions
together.

##  III The Quantum nearest neighbors algorithm

The quantum nearest neighbors (QNN) Schuld  _et al._ (2014) is a quantum
classification algorithm that employs the Hamming distance as a distance
criterion to compare the training dataset and unclassified observations.
Schematically, it consists of three major steps:

  * •

First, create a superposition of the training dataset and the input
observation;

  * •

Encode the Hamming distance between the input observation and each example in
the training set into the amplitude of each state in the superposition;

  * •

Measure the class-qudit retrieving the predicted class with the highest
probability.

Before the actual quantum algorithm starts, an important classical pre-
processing step (whose reason will become clear in what follows) must be
performed: the features in the training dataset are represented as bit
vectors, so that the feature space becomes $\mathcal{X}=\\{0,1\\}^{\otimes
n}$. This is achieved via the procedure known as one-hot encoding, which
produces the so-called dummy variables Draper and Smith (1998). Naturally,
such a representation will be discrete (binary, in fact), so that if any
original feature is continuous (or even categorical with more than 2 levels),
a prior step of discretization is necessary. Notice that the number of binary
features after the encoding may be different from the number of original
features, although here we represented both by the same number of bits $n$.
There are several ways to perform this binarization process. However, whatever
method is chosen, it is important that the essence of the data topology is
maintained — that is, points that are close on the original feature space must
remain close on the binarized feature space. In Sec. IV we detail the
specifics of the particular procedure we applied to our problem.

Once the training dataset features are binarized, their representation as
quantum states is immediate via the basis encoding Schuld (2021), which
accounts for a direct mapping of binary features to the quantum computational-
basis states: $0\mapsto\ket{0}$ and $1\mapsto\ket{1}$. After these two steps,
each training set data point is mapped to the quantum state
$\ket{x_{1}^{p}\cdots x_{n}^{p}}\equiv\ket{\bm{x}^{p}}$,
$x_{k}^{p}\in\\{0,1\\}$, $p=1,\cdots,N$, where $N$ is the number of points in
the training set. In parallel, in a separate quantum register, we encode the
class $y^{p}\in\\{0,\cdots,d-1\\}$, and construct, for each observation $p$,
the state

$\ket{x_{1}^{p}\cdots x_{n}^{p},y^{p}}\equiv\ket{\bm{x}^{p},y^{p}}\ .$ (4)

If we are dealing with binary classification (which is the case in this work),
the respective class is also straightforwardly encoded in a single qubit, as
$0\mapsto\ket{0}$ and $1\mapsto\ket{1}$. If we have a multiclass problem,
qudits are necessary, or one could use more than one qubit to encode integers
corresponding to the class (for instance, $\ket{5}=\ket{101}$). In this case,
$\lceil\log_{2}d\rceil$ qubits are necessary to encode $d$ classes.

Once we have the state corresponding to each one of the training states
$\ket{\bm{x}^{p},y^{p}}$, we construct a training set superposition of all
datapoints, given by

$\ket{T}=\frac{1}{\sqrt{N}}\sum_{p=1}^{N}\ket{\bm{x}^{p},y^{p}}\ .$ (5)

Naturally, with $n$ qubits, one can construct a superposition of $2^{n}$
states, representing all possible binarized feature vectors of $n$ features.
However, it is possible (and most likely) that in a given training dataset not
all possible binary feature vectors will be present. Indeed, in the
binarization process, it is likely that multiple observations that are
different in the original input space are mapped to the same binary vector so
that the transformed training dataset actually has a number of observations
quite smaller than the original number of observations (although here we
represent both as $N$). This leads to important details in the implementation
of the algorithm in a practical problem, as it will be detailed in Sec. IV.
Further, notice that in the case in which $N<2^{n}$, the superposition in Eq.
(5) will have to be prepared with an arbitrary state preparation routine,
which is known to be costly Shende  _et al._ (2006). However, in quantum
computing software development kits (SDK) (such as Qiskit MD SAJID ANIS
(2021), which is the one we employ in this work), such a procedure is already
implemented and ready to use as a self-contained routine.

The next step is to perform the same classical binarization process with the
unclassified input vector $\bm{x_{\text{in}}}$ (the one we wish to classify)
and map it to the state $\ket{x_{\text{in},1}\cdots
x_{\text{in},n}}\equiv\ket{\bm{x_{\text{in}}}}$,
$x_{\text{in},k}\in\\{0,1\\}$. Keep this as the first register of the quantum
state. Finally, add an ancilla register $\ket{0}$ as the last register. Such a
construction yields an initial state given by

$\ket{\psi_{0}}=\frac{1}{\sqrt{N}}\sum_{p=1}^{N}\ket{\bm{x_{\text{in}}};\bm{x}^{p},y^{p};0}\
,$ (6)

which is made up of three registers (or, in fact, blocks of registers): the
first containing the input state $\ket{\bm{x_{\text{in}}}}$, which consists of
$n$ qubits; the second containing the superposition $\ket{T}$ (which is the
tensor product of the feature vectors $\ket{\bm{x}^{p}}$ and the class vectors
$\ket{y^{p}}$), thus consisting of $n+1$ qubits, and given that we have a
binary classification problem, the third contains an ancilla qubit initialized
as $\ket{0}$. Therefore, the number of qubits necessary for the algorithm is
precisely $2n+2$.

Once the initial state is prepared, we put the ancilla into a superposition,
by applying a Hadamard gate to the last register, i.e., $H=1\otimes 1\otimes
1\otimes H$, such that

$\ket{\psi_{1}}=H\ket{\psi_{0}}=\frac{1}{\sqrt{N}}\sum_{p=1}^{N}\ket{\bm{x_{\text{in}}};\bm{x}^{p},y^{p}}\otimes\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\
.$ (7)

In the next step, we want the Hamming distance components $d_{k}^{i}$ between
each qubit of the first (input) and second (training) register to replace the
qubits in the second register, such that

$d_{k}^{i}=\begin{cases}0,&\text{ if }\ket{x_{k}^{p}}=\ket{x_{\text{in},k}}\\\
1,&\text{ else. }\end{cases}\ .$ (8)

This is achieved by simply applying a
$\mathrm{cNOT}(x_{\text{in},k},x_{k}^{p})$-gate, which overwrites the entry
$x_{k}^{p}$ in the second register with $0$ if $x_{k}^{p}=x_{\text{in},k}$,
otherwise with $1$:

$\begin{cases}\mathrm{cNOT}\ket{00}=\ket{00}\ ;&\
\mathrm{cNOT}\ket{01}=\ket{01}\\\ \mathrm{cNOT}\ket{11}=\ket{10}\ ;&\
\mathrm{cNOT}\ket{10}=\ket{11}\end{cases}\ .$ (9)

Thus, after this step, the state is then

$\displaystyle\ket{\psi_{2}}$
$\displaystyle=\bigotimes_{k=1}^{n}\mathrm{cNOT}(x_{k},v^{p}_{k})\;\ket{\psi_{1}}$
(10)
$\displaystyle=\frac{1}{\sqrt{N}}\sum_{p=1}^{N}\ket{\bm{x_{\text{in}}};\bm{d}^{p},y^{p}}\otimes\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\
,$

where the Hamming distance components $\ket{d_{1}^{p}\cdots
d_{n}^{p}}\equiv\ket{\bm{d}^{p}}$, $d_{k}^{p}\in\\{0,1\\}$, $p=1,\cdots,N$ are
now in the second register.

In the third step, we apply the unitary operator

$U=e^{-i\frac{\pi}{2n}\mathcal{O}}\
;\mathcal{O}=1\otimes\sum_{k=1}^{n}\left(\frac{1-\sigma_{z}}{2}\right)_{d_{k}}\otimes
1\otimes\sigma_{z}\;\ .$ (11)

This sums the Hamming distance components $\\{d^{p}_{k}\\}$ (thus yielding the
actual Hamming distance) between $\ket{\bm{x}^{p}}$ and
$\ket{\bm{x_{\text{in}}}}$, $d_{H}(\bm{x_{\text{in}}},\bm{x}^{p})\equiv
d_{H}$, into the phase of the $p$th state of the superposition. Notice that a
relative phase is added, conditioned on the ancilla state. After this step,
the state becomes

$\ket{\psi_{3}}=U\ket{\psi_{2}}=\frac{1}{\sqrt{2N}}\sum_{p=1}^{N}\left(e^{-i\frac{\pi}{2n}d_{H}}\ket{\bm{x_{\text{in}}};\bm{d}^{p},y^{p};0}+e^{i\frac{\pi}{2n}d_{H}}\ket{\bm{x_{\text{in}}};\bm{d}^{p},y^{p};1}\right)\
.$ (12)

Now we apply another Hadamard to the ancilla. This will generate alternating-
sign exponentials associated with each ancilla state, which are easily
aggregated into a sine and cosine. The resulting state can be expressed as

$\ket{\psi_{4}}=H\ket{\psi_{3}}=\frac{1}{\sqrt{N}}\sum_{p=1}^{N}\left(\cos\left(\frac{\pi
d_{H}}{2n}\right)\ket{\bm{x_{\text{in}}};\bm{d}^{p},y^{p};0}+\sin\left(\frac{\pi
d_{H}}{2n}\right)\ket{\bm{x_{\text{in}}};\bm{d}^{p},y^{p};1}\right)\ .$ (13)

Notice that $0\leq d_{H}\leq n\Rightarrow 0\leq\frac{\pi
d_{H}}{2n}\leq\frac{\pi}{2}$. Therefore,

  * •

For large $d_{H}$, $\cos\left(\frac{\pi d_{H}}{2n}\right)\rightarrow 0$ and
$\sin\left(\frac{\pi d_{H}}{2n}\right)\rightarrow 1$, so that we have higher
probability of measuring $\ket{1}$ in the ancilla qubit;

  * •

For small $d_{H}$, $\cos\left(\frac{\pi d_{H}}{2n}\right)\rightarrow 1$ and
$\sin\left(\frac{\pi d_{H}}{2n}\right)\rightarrow 0$, so that we have higher
probability of measuring $\ket{0}$.

That is, if the input is far away from most training observations, we have a
higher probability of measuring the ancilla in the state $\ket{1}$; and if the
input is close to many observations, the ancilla is more likely to be measured
in $\ket{0}$. Thus, intuitively, since our criterion for classification is to
consider the closest observations, by measuring the ancilla in $\ket{0}$, the
amplitudes of close observations will be large, whilst the opposite is true
for distant observations. The importance of this fact becomes clear if we
rewrite $\ket{\psi_{4}}$, to show that the different classes appear weighted
by their member’s distance to the input, such that

$\ket{\psi_{4}}=\frac{1}{\sqrt{N}}\sum_{y=0}^{d-1}\ket{y}\otimes\sum\limits_{l\in
y}\left(\mathrm{cos}\left(\frac{\pi
d_{H}}{2n}\right)\ket{\bm{x_{\text{in}}};\bm{d}^{l};0}+\mathrm{sin}\left(\frac{\pi
d_{H}}{2n}\right)\ket{\bm{x_{\text{in}}};\bm{d}^{l};1}\right)\ ,$ (14)

where $l$ runs over all training vectors classified with the label $y$.
Written like this, it becomes clear that, if the ancilla is measured to be in
$\ket{0}$, the amplitudes of close observations will be large, which implies
that the probability of measuring the respective class qubit of these
observations will also be large. And, as we discuss next, this is how the
final classification is performed.

As the final step, the ancilla of the state $\ket{\psi_{4}}$ is measured on
the computational basis. According to Eq. (13), it is easy to see that the
probability of measuring $\ket{0}$ is

$P(\ket{0}_{a})=\left|\braket{0}{\psi_{4}}\right|^{2}=\frac{1}{N}\sum_{p=1}^{N}\cos^{2}\left(\frac{\pi
d_{H}}{2n}\right)\ .$ (15)

The conditional probability to measure a certain class $y\in\\{1,...,d\\}$,
given that we previously measured the ancilla in $\ket{0}$ (and, therefore,
the state collapsed to $\ket{\tilde{\psi}_{4}}=\braket{0}{\psi_{4}}\ket{0}$)
is, in terms of the joint probability,

$\displaystyle P(y\mid\ket{0}_{a})$ $\displaystyle=P(y)P(\ket{0}_{a})$ (16)
$\displaystyle=\left|\braket{y}{\tilde{\psi}_{4}}\right|^{2}$
$\displaystyle=\frac{1}{N}\sum\limits_{l\in y}\cos^{2}\left(\frac{\pi
d_{H}}{2n}\right)\ ,$

which is easily verifiable using Eq. (14). Indeed, Eq. (16) implies that

$P(y)=\frac{1}{P(\ket{0}_{a})}\frac{1}{N}\sum\limits_{l\in
y}\cos^{2}\left(\frac{\pi d_{H}}{2n}\right)\ .$ (17)

Thus, the class measured with the highest probability is that whose members
are the closest to the input vector, provided that $P(c)$ is only computed
after the ancilla is measured in $\ket{0}$, which is precisely why the
amplitudes associated to the closest neighbors are considered. Notice that if
the measurement returns $\ket{1}$, this run of the algorithm is not taken into
account.

In Fig. 6 the full quantum circuit is illustrated for a particular dataset, as
detailed in Appendix VI.4. The algorithm uses $\mathcal{O}(Nn)$ Schuld  _et
al._ (2014) gates, which is completely due to the construction of the training
data superposition (described by Eq. 5), which depends on the number of
training samples, thus yielding a $\mathcal{O}(Nn)$ complexity Schuld  _et
al._ (2014); Ventura and Martinez (1998), which close to the classical KNN
algorithm complexity, in which we have to compute the distance between the
test observation and all other $N$ training points. However, if one can find a
procedure to prepare the training data superposition in a manner independent
of the number of samples (perhaps by reading quantum data Huang  _et al._
(2021); Aharonov  _et al._ (2022); Schatzki  _et al._ (2021); Chehimi and Saad
(2021)), the QNN algorithms would run in $\mathcal{O}(n)$, offering a
potentially large advantage over the classical KNN, for which it seems
unlikely to exist an algorithm which is independent of the number of training
samples — that’s a quite remarkable advantage achieved by the exploitation of
the superposition in a quantum algorithm.

We highlight that, in contrast to the classical KNN, the QNN algorithm does
not depend on the hyperparameter $k$. In fact, a superposition of all members
of each class is taken into consideration for the classification. This is
equivalent to considering all neighbors (that is, $k=N$), which in the
classical algorithm is associated with a high bias, since, if the dataset is
imbalanced with respect to the target, the majority class will always be
predicted. In the quantum algorithm, however, this is not the case: even if
the dataset is imbalanced, the input observation will be assigned to the class
which is the closest to it, since, as it is clear in Eq. (17), the distance of
the input to the members of the class explicitly affects the probability.

As a final remark, notice that the probability distribution in Eq. (17) is
precisely what is recovered from multiple runs of the algorithm on an actual
hardware (or a simulator thereof). The final prediction, as a class, is
therefore recovered by choosing the class with the largest observed
probability. However, as explained in Sec. IV and illustrated in Fig. (3), in
this work we directly use the class probability, i.e., Eq. (17) itself.
Fortunately, in contrast to many classical learning models, outputting class
probabilities is the most natural choice for the QNN algorithm.

We remark that the Python/Qiskit implementation of the algorithm described
above, as well as all the data used in this paper and the corresponding
results, are available in an online repository André J. Ferreira-Martins and
Silva (2023).

##  IV  Data pre-processing

As described in Sec. III, the classical data loaded into the quantum
registers, via the basis encoding strategy, must be in a binary
representation. On the other hand, as discussed in Sec. II.1, the dataset
under study consists of 198 continuous features: the pairwise correlations
among all spins in a lattice with 12 sites considering boundary conditions and
the symmetry it implies. Thus, in order to represent each observation as a
binary vector, we must first discretize the continuous features, so that the
discrete levels may then be binarized.

Before proceeding with these procedures, however, an important remark is due.
As discussed above, the QNN algorithm uses $2n+2$ qubits, where $n$ is the
number of binarized features. Indeed, this implies that if one wants to
simulate the circuit, or even execute it on NISQ hardware, $n$ must be chosen
accordingly, to make the execution/simulation feasible.

As will be detailed below, we employed an efficient discretization and
binarization procedure that maps each original continuous feature to only two
bits. However, given that we start with 198 features, this would imply
$n=396$, thus requiring a circuit consisting of $794$ qubits, which is way
beyond the limit for a classical simulation (recall that the algorithm
includes entanglement) as well as current quantum hardware capabilities, both
in terms of number of qubits as well as circuit depth. And this is a quite
simple discretization one can think of: if one produces more bins per feature,
which would be desirable, the resulting number of binary features (and qubits,
consequently) would further increase, making the simulation/execution yet more
intractable.

Therefore, in order to fit the dataset into current capabilities, we employ a
series of pre-processing steps to the original raw features, which starts with
a dimensionality reduction procedure implemented via a feature selection
routine, in order to pick from the 198 original features, the ones that
contribute the most to the classification, with the hope that they are enough
to produce a good classifier. The procedure we use for picking the most
important features is based on the Random Forest algorithm Breiman (2001) — in
particular, a modification thereof, known as Extremely Randomized Trees Geurts
_et al._ (2006). It consists of the calculation of a "feature importance
coefficient" which is also known as "mean decrease impurity" or "gini
importance" Breiman  _et al._ (2017). This coefficient is calculated as the
total decrease in each node impurity, averaged over all trees in the forest.
The mean is weighted by the probability that the respective node is reached,
which is often estimated by the proportion of observations reaching the node.
A detailed account of this algorithm can be found in the Appendix VI.3.

Figure 1: k-bins discretizer using uniform and k-means ($k=3$) binning
strategies. a) k-bins discretizer with bins uniformly defined. The vertical
red lines represent the bins’ limits. Notice that bin widths are uniform in
the feature space, but the clustering structure is not respected. a) The green
points represent the clusters centroids, and the vertical green lines, the
bins’ limits. Notice how non-uniform bins are created, but the clustering
structure is respected.

Having in mind the discussion about the current capabilities of simulation and
hardware, we have selected only the 4 most important features that correspond
to the following two-body correlation terms. Physically, we expect that the
most important features are the correlation functions
$\langle\sigma_{i}^{z}\sigma_{j}^{z}\rangle$ at the largest available
distances. The reason is that this correlation detects long-range order
associated with the spontaneous breaking of the $\mathbb{Z}_{2}$ symmetry
$\sigma_{j}^{z}\mapsto-\sigma_{j}^{z}$ of the Hamiltonian. In the paramagnetic
phase, $\langle\sigma_{i}^{z}\sigma_{j}^{z}\rangle$ decays exponentially to
zero for $|i-j|$ larger than the correlation length, while it approaches a
nonzero value in the ferromagnetic phase and oscillates with a four-site
periodicity in the antiphase. By contrast, the correlation function
$\langle\sigma_{i}^{x}\sigma_{j}^{x}\rangle$ is nonzero for $g\neq 0$ in all
phases because the transverse magnetic field induces a finite expectation
value for $\sigma_{j}^{x}$.

We then proceed to the discretization of the features, using a procedure based
on the $k$-means clustering algorithm MacQueen (1967). More specifically, we
use a k-bins discretizer, implemented in scikit-learn Pedregosa  _et al._
(2011), which divides continuous data into $k$ intervals or "bins".
Essentially, we first cluster observations that are similar to the feature
being discretized and use the clusters centroids as centers of the bins, that
is, values in each bin will have the same nearest centroid, as determined by
the 1-dimensional $k$-means algorithm. See Fig. 1 for an illustration. For
each feature, we created 3 bins. At this point, our dataset is characterized
by 12 discrete values, 3 for each one of the 4 features selected by the
feature importance procedure.

After discretization, the features are binarized using the one-hot encoding
procedure, which consists of creating $l-1$ independent binary features for
each column with $l$ categorical levels, as illustrated in Fig. 2. In our
case, since $l=3$ for each discretized feature, we create $l-1=2$ new binary
features each, which then results in $n=8$ independent binary features. This
is the final dimensionality we work with.

Notice that, with 8 binary features, we will need 18 qubits for the circuit
execution, which is a reasonable number for the circuit simulation or
execution — and, most importantly, it is enough to yield good results for the
problem we analyze, as it will be shown. We could have chosen more than $n=4$
features or discretized the features in more bins, which could possibly have
increased the performance quantum classifier. In Sec. VI we further elaborate
on this point.

Figure 2: One-hot encoding procedure. From a column with $l=3$ categorical
(discrete) levels, we construct $l-1=2$ independent binary columns, which are
the binary features. Notice that only $l-1$ binary columns are necessary
because it is possible to represent one of the levels as "00" (in this
example, "L3").

Notice that after the feature selection, discretization and binarization pre-
processing described above, some observations which were different in the
original space of continuous features may be mapped to the same binary
representation. This makes perfect sense, given that the different values of a
given feature may fall in the same bin, which is given by a range of values.
If this happens with all 4 features of two different observations, they will
naturally be represented by the same 8-dimensional feature vector. This is why
using a $k$-means binning strategy is a good idea (instead of the competing
strategy "uniform", for example, in which all bins have identical widths, as
depicted in Fig. 1b): given that bins are clusters, this strategy groups
together similar observations in the same bin, so that it makes sense if they
are represented by the same binary feature vector.

After the pre-processing routine, our original training dataset, which had
1000 rows and 198 continuous-valued columns, was reduced to a dataset with 8
binary features and only 10 rows. We can see that as a way of reducing the
dataset only to the most representative samples and better explanatory
features, which, as we will show below, was enough to yield good results with
the quantum classification algorithm.

It is important to remark that the aforementioned feature importance and
discretization processes were such that their respective parameters were
determined only using the training data. That is, the exact same procedure was
merely reproduced for all test datasets, but with parameters already defined
in the training data. Now, although this is the correct thing to be done to
avoid data leakage, there is a potential problem, especially with the
discretization process: given that the features range varies a lot from
training to testing data, it is possible that the resulting bins for testing
data features will be concentrated, that is, all observations will fall in the
same bin of a given feature. Effectively, this implies that such test
observations will be characterized by less than 8 features, which is a problem
because the QNN algorithm assumes that the test (input) observation has the
same number of features as all training observations. In order to fix this, we
pad such input observations with zeros, to guarantee that all binarized
testing observations will be 8-dimensional. In practice, different
observations will be identified only by the actual features present, and the
padding will have no effect in terms of the classification, given that it will
be the same for all observations in a given test dataset, as we observed.
Indeed, as the results show, such a procedure does not jeopardize the
classifier’s performance.

As already remarked, remember that QNN is a lazy algorithm, so each test
(input) observation is classified at a time. This means that, in principle, we
would have to simulate/execute a number of circuits equal to the number of
test observations, to have their prediction. Given that we have 10 testing
sets, one for each $k$ value. We consider $k=0$ the training point. each one
with 1000 observations, the number of circuit simulations/executions would be
quite large. However, the aforementioned fact that different training
observations in the original feature space may be mapped to the same binary
representation is of course also true for the testing data observations
(although the exact number of unique binarized testing observations vary among
the different test datasets). Given that, we implement a cache: whenever we
see a new testing observation (in terms of its 8 features), we pass it through
the quantum circuit, simulating/executing it, and store its prediction. If
this observation is repeated (which, again, can happen given the nature of the
pre-processing routine), we don’t run the circuit again, but instead merely
replicate the prediction in the cache. This allows us to have a prediction for
each one of the observations in the testing datasets, without having to
simulate/execute the quantum algorithm that many times. Indeed, this is very
important for resource optimization, in terms of simulation time or hardware
calls for execution.

##  V Machine Learning the phase diagram of the ANNNI model with QNN

Figure 3: Detecting the critical transverse magnetic field coupling parameter
$g$ at which a phase transition occurs. The machine was trained at $\kappa=0$
and asked to predict where the transition happens at $\kappa=0.1$, by
considering where the machine is most uncertain, that is, when the
probabilities are closest $p_{1}=p_{2}=1/2$. Here the ferromagnetic
(paramagnetic) phase is labeled as $0$ $(1)$.

Our aim is to understand whether transfer learning is possible using QNN. More
specifically, all our training data consists of $\kappa=0$ and we use that to
predict phases at regions where $\kappa\geq 0$. This is particularly relevant
since for $\kappa=0$ the model is analytically solvable, pointing out that a
transition occurs at $g\approx 1$. We highlight that for $\kappa=0$ we have
only two phases: either the ferromagnetic (phase ’0’) or the paramagnetic
(phase ’1’). However, when $\kappa\geq 0$ the ANNNI Hamiltonian also leads to
a third phase, the antiphase (phase ’2’), not contained in the training data.
In particular, for $\kappa\geq 0.5$, we are in a region where only phases ’0’
and ’2’ are present. So, the best the classifier algorithm can do is to output
’0’ if the phase is indeed ’0’ and ’1’ otherwise.

Actually, as discussed above, for an observation point, both the classical and
quantum classifier algorithms will return a normalized probability vector
$(p_{0},p_{1})$ where the assigned phase will correspond to the component with
the largest value. As typical with such algorithms, to determine when we are
facing a transition, we plot both the probability components and check when
they cross, as shown in Fig. 3. As can be seen in Fig. 4, using this approach,
the QNN algorithm recovers the left part ($\kappa<0.5$) of the phase diagram,
corresponding to the ferromagnetic/paramagnetic transition, very successfully.
The precise prediction also holds as we approach the critical point at
$\kappa=0.5$ and $\gamma=0$ at which a new antiphase appears. However, as we
start to increase $\gamma$ the approximated solutions in (2) and (3) and the
QNN predictions start to differ more significantly, even though they remain
qualitatively similar.

To benchmark our results we have compared the QNN solution with that obtained
by the classical KNN algorithm. As can be seen in Fig. 4, the solution is
significantly worse with the classical algorithm is fed with the same pre-
processed data as the one given to the quantum algorithm. However, if the
classical algorithm uses the complete data (not pre-processed) it reaches a
similar success in the prediction, even though it is smaller as quantified by
shown ahead. Importantly, the quantum classifier performs significantly better
at the critical point $(g=0,\kappa=1/2)$.

Figure 4:  Phase diagrams produced with diverse (Q)ML algorithms when trained only with $\kappa=0$: KNN trained with raw data (blue circles); KNN trained with the same pre-processe data as the QNN - fair comparison (black squares); QNN (red triangles), and two different analytical solutions: Ising (solid blue line) and BKT (dashed orange line). All different methods recover the ferro/paramagnetic and paramagnetic/BKT transitions qualitatively well, although, as it is quantitatively expressed in Table 1, the QNN solution yields the smallest MSE with relation to the analytical approximation, thus being an overall better solution (see main text for more details).  Table 1: Performance (average $\ell_{2}$-norm with relation to the analytical approximations given by Eqs. 2 and 3) computed for the three main phases and comparing QNN with KNN (using both the pre-processed and complete training data). For the classical KNN we used $k=7$ and the Euclidean distance. The best result is in boldface.  Technique & average $\ell_{2}$-norm |
---|---
QNN (pre-processed) | 0.0036(6)
KNN (pre-processed) | 0.0164(1)
KNN (raw data) | 0.0043(1)

##  VI Discussion

The detection of phase and phase transitions of the ANNNI model with both
classical as well as quantum heuristic approaches have already been done. In
Ref. Canabarro  _et al._ (2019b), Canabarro et al. showed the possibility of
applying both unsupervised and supervised classical techniques to achieve good
results. In fact, the problem was satisfactorily well solved with unsupervised
learning, reducing the use of supervised learning to a validation step.
Therefore, they tried using transfer learning of diverse supervised learning
algorithms trained solely on nearest-neighbor interactions exhibiting the
capacity to discern a novel phase emerging upon the introduction of next-
nearest-neighbor interactions. They showed that some of the learners could
unveil the Ising as well as the antiphase and the paramagnetic phases. This
amalgamation effectively groups the BKT and CIC transitions together,
showcasing the robustness of our method. On the other hand, in Ref. Monaco
_et al._ (2023), Monaco et al. used quantum convolutional neural networks by
training only on marginal points of the phase diagram represented by integral
models. Our approach in this paper is both innovative and complementary. We
use a new and simpler quantum machine learning algorithm and apply transfer
learning, we test some ideal preprocessing of the data to fit in a real
quantum computer, and we train only on $\kappa=0$, testing on the remaining
phase diagram to show the viability of the technique as we discuss here.

We show that with the right pre-processing of the data, the quantum nearest
neighbor (QNN) algorithm proposed in Schuld  _et al._ (2014) allows for the
classification of phases in a non-trivial Hamiltonian model. Using two-point
correlation functions obtained by exact diagonalization on a small $N=12$
spins lattice, we could reproduce the main phases of the axial next-nearest
neighbor Ising (ANNNI) model. More precisely, using as training data only the
ferromagnetic and paramagnetic phases, we could detect a transition for an
antiphase by increasing the interaction strength of the next-nearest neighbor.
This is a relevant instance of transfer learning, since using analytical data
extracted from the exactly solvable transverse field Ising model, we could
explore a non-integrable region of the Hamiltonian model. This makes the
approach computationally cheaper as access to training labels is one of the
major bottlenecks for any supervised method.

To benchmark the quality of our quantum machine model, we compared it with
approximated expressions obtained by various methods. The solution provided by
QNN works very well in the ferromagnetic and paramagnetic regions, offering a
less precise but still qualitatively reasonable solution as we enter the
antiphase. Arguably, however, to assess the quality of a quantum learning
method, it is reasonable to compare its performance with that of classical
learning algorithms. We performed this comparison, and the results are quite
favorable to the quantum approach. Even when we feed the original data
(without any pre-processing, a necessary step to reduce the number of qubits
in the quantum realization) to classical classifiers, the quantum classifier
remains superior, as can be seen in Fig. 4 and Table 1. And performing the
fairest comparison, obtained when the quantum and classical algorithms see the
same pre-processed data, the accuracy of the quantum classifier is
significantly higher. Importantly, these performance comparisons were done on
the testing data, that is, we were really evaluating the generalization
capability of the different models, which is, after all, what matters the most
when one builds a data-driven model.

This proof-of-principle (since it was obtained in a simulated/perfect quantum
circuit) quantum advantage does not come in terms of algorithmic complexity,
but rather in generalization and accuracy, which is of major interest in the
context of machine learning. Still, one may interpret the advantage from a
different point of view, namely that of sample complexity Vapnik (1999); Mohri
_et al._ (2018); MELLO and Ponti (2018): the quantum algorithm could find the
underlying pattern reflected on the dataset with much less information than
its classical counterpart, and with better generalization performance. As
mentioned before, we can see that as a way of reducing the dataset only to the
most representative samples and better explanatory features. Although we focus
on a particular Hamiltonian, we believe it leads to relevant general
questions: in a statistical learning theoretical sense, how and why such a
sample complexity reduction and consequent quantum advantage is achieved?
Similar questions have been addressed in recent research Caro  _et al._
(2021a, b); Schuld  _et al._ (2021), and further research along this
direction, in the particular context of QNN might lead to new insights.
Another clear path is to understand how well the QNN classifier works in real
NISQ devices, also considering different Hamiltonian models and increasing the
number of qubits and features. In this regard, it would be interesting to
consider other data formats, such as the classical shadows Smith and Johnson
(2020), efficiently encoding classical data about quantum systems for machine
learning purposes Brown and Davis (2017).

In conclusion, to the best of our knowledge, this paper is the first work in
which the QNN algorithm Schuld  _et al._ (2014) was applied to a concrete
classification problem in the context of condensed matter physics. By applying
this method, we could achieve a quantum model whose generalization performance
was superior to its classical counterparts, whilst using much less
information, which represents a quantum advantage in both contexts of
generalization and sample complexity. This is the main result of this paper,
which opens the way to several discussions concerning the statistical learning
theoretical properties of the QNN model.

## Acknowledgements

This work was supported by the Serrapilheira Institute (Grant No.
Serra-1708-15763), the Simons Foundation (Grant Number 1023171, RC), the
Brazilian National Council for Scientific and Technological Development (CNPq)
via the National Institute for Science and Technology on Quantum Information
(INCT-IQ) and Grants No. 307172/2017-1, the Brazilian agencies MCTIC, CAPES
and MEC. AC acknowledges a paid license by the Federal University of Alagoas
for a sabbatical at the University of São Paulo, and partial financial support
by CNPq (Grant No. $311375/2020-0$), Alagoas State Research Agency (FAPEAL)
(Grant No. APQ$2022021000153$) and São Paulo Research Foundation (FAPESP)
(Grant No. $2023/03562-1$).

## References

  * Goodfellow  _et al._ (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville,  _Deep Learning_ (MIT Press, 2016) http://www.deeplearningbook.org.
  * Mehta  _et al._ (2018) Pankaj Mehta, Marin Bukov, Ching-Hao Wang, Alexandre G. R. Day, Clint Richardson, Charles K. Fisher, and David J. Schwab, “A high-bias, low-variance introduction to machine learning for physicists,” (2018), arXiv:1803.08823 .
  * Altman (1992) Naomi S Altman, “An introduction to kernel and nearest-neighbor nonparametric regression,” The American Statistician 46, 175–185 (1992).
  * Olson  _et al._ (2016) Randal S. Olson, Nathan Bartley, Ryan J. Urbanowicz, and Jason H. Moore, “Evaluation of a tree-based pipeline optimization tool for automating data science,” in  _Proceedings of the Genetic and Evolutionary Computation Conference 2016_, GECCO ’16 (ACM, New York, NY, USA, 2016) pp. 485–492.
  * Kelleher  _et al._ (2015) John D Kelleher, Brian Mac Namee, and Aoife D’Arcy,  _Fundamentals of machine learning for predictive data analytics: algorithms, worked examples, and case studies_ (MIT Press, 2015).
  * Charnock and Moss (2017) Tom Charnock and Adam Moss, “supernovae: Photometric classification of supernovae,” Astrophysics Source Code Library (2017).
  * von Marttens  _et al._ (2022) Rodrigo von Marttens, Luciano Casarini, Nicola R Napolitano, Sirui Wu, Valeria Amaro, Rui Li, Crescenzo Tortora, Askery Canabarro, and Yang Wang, “Inferring galaxy dark halo properties from visible matter with machine learning,” Monthly Notices of the Royal Astronomical Society 516, 3924–3943 (2022), https://academic.oup.com/mnras/article-pdf/516/3/3924/45948688/stac2449.pdf .
  * Carrillo  _et al._ (2015) M Carrillo, JA González, M Gracia-Linares, and FS Guzmán, “Time series analysis of gravitational wave signals using neural networks,” in  _Journal of Physics: Conference Series_ , Vol. 654 (IOP Publishing, 2015) p. 012001.
  * Torlai  _et al._ (2018) Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo, “Neural-network quantum state tomography,” Nature Physics 14, 447–450 (2018).
  * Iten  _et al._ (2020) Raban Iten, Tony Metger, Henrik Wilming, Lídia del Rio, and Renato Renner, “Discovering physical concepts with neural networks,” Phys. Rev. Lett. 124, 010508 (2020).
  * Carleo and Troyer (2017) Giuseppe Carleo and Matthias Troyer, “Solving the quantum many-body problem with artificial neural networks,” Science 355, 602–606 (2017).
  * Torlai and Melko (2016) Giacomo Torlai and Roger G Melko, “Learning thermodynamics with boltzmann machines,” Physical Review B 94, 165134 (2016).
  * Ghiringhelli  _et al._ (2015) Luca M Ghiringhelli, Jan Vybiral, Sergey V Levchenko, Claudia Draxl, and Matthias Scheffler, “Big data of materials science: critical role of the descriptor,” Physical review letters 114, 105503 (2015).
  * Carrasquilla and Melko (2017) Juan Carrasquilla and Roger G. Melko, “Machine learning phases of matter,” Nature Physics 13, 431–434 (2017).
  * Broecker  _et al._ (2017) Peter Broecker, Juan Carrasquilla, Roger G Melko, and Simon Trebst, “Machine learning quantum phases of matter beyond the fermion sign problem,” Scientific reports 7, 8823 (2017).
  * Ch’ng  _et al._ (2017) Kelvin Ch’ng, Juan Carrasquilla, Roger G. Melko, and Ehsan Khatami, “Machine learning phases of strongly correlated fermions,” Phys. Rev. X 7, 031038 (2017).
  * Deng  _et al._ (2017) Dong-Ling Deng, Xiaopeng Li, and S Das Sarma, “Machine learning topological states,” Physical Review B 96, 195145 (2017).
  * Huembeli  _et al._ (2018) Patrick Huembeli, Alexandre Dauphin, and Peter Wittek, “Identifying quantum phase transitions with adversarial neural networks,” Physical Review B 97, 134109 (2018).
  * Goes  _et al._ (2021) Caio B. D. Goes, Askery Canabarro, Eduardo I. Duzzioni, and Thiago O. Maciel, “Automated machine learning can classify bound entangled states with tomograms,” Quantum Information Processing 20, 99 (2021).
  * el al. (2019) Frank Arute el al., “Quantum supremacy using a programmable superconducting processor,” Nature 574, 505–510 (2019).
  * Preskill (2018) John Preskill, “Quantum computing in the nisq era and beyond,” Quantum 2, 79 (2018).
  * Bouland  _et al._ (2020) Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis, and Anupam Prakash, “Prospects and challenges of quantum finance,” (2020), arXiv:2011.06492 [q-fin.CP] .
  * Farhi  _et al._ (2014) Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A quantum approximate optimization algorithm,” (2014), arXiv:1411.4028 [quant-ph] .
  * Schuld  _et al._ (2014) Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, “The quest for a quantum neural network,” Quantum Information Processing 13, 2567–2586 (2014).
  * Lloyd  _et al._ (2013) Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost, “Quantum algorithms for supervised and unsupervised machine learning,” arXiv preprint arXiv:1307.0411 (2013).
  * Wiebe  _et al._ (2015) Nathan Wiebe, Ashish Kapoor, and Krysta M Svore, “Quantum nearest-neighbor algorithms for machine learning,” Quantum information and computation 15, 318–358 (2015).
  * Dong  _et al._ (2008) Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tarn, “Quantum reinforcement learning,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 38, 1207–1220 (2008).
  * Horn and Gottlieb (2001) David Horn and Assaf Gottlieb, “Algorithm for data clustering in pattern recognition problems based on quantum mechanics,” Physical review letters 88, 018702 (2001).
  * Schuld  _et al._ (2015) Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, “An introduction to quantum machine learning,” Contemporary Physics 56, 172–185 (2015).
  * Biamonte  _et al._ (2017) Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd, “Quantum machine learning,” Nature 549, 195–202 (2017).
  * Carrasquilla and Torlai (2021) Juan Carrasquilla and Giacomo Torlai, “Neural networks in quantum many-body physics: a hands-on tutorial,” arXiv preprint arXiv:2101.11099 (2021).
  * Kriváchy  _et al._ (2020) Tamás Kriváchy, Yu Cai, Daniel Cavalcanti, Arash Tavakoli, Nicolas Gisin, and Nicolas Brunner, “A neural network oracle for quantum nonlocality problems in networks,” npj Quantum Information 6, 1–7 (2020).
  * D’Alessandro  _et al._ (2023) Nicola D’Alessandro, Beatrice Polacchi, George Moreno, Emanuele Polino, Rafael Chaves, Iris Agresti, and Fabio Sciarrino, “Machine-learning-based device-independent certification of quantum networks,” Physical Review Research 5, 023016 (2023).
  * Polino  _et al._ (2023) Emanuele Polino, Davide Poderini, Giovanni Rodari, Iris Agresti, Alessia Suprano, Gonzalo Carvacho, Elie Wolfe, Askery Canabarro, George Moreno, Giorgio Milani, _et al._ , “Experimental nonclassicality in a causal network without assuming freedom of choice,” Nature Communications 14, 909 (2023).
  * Canabarro  _et al._ (2019a) Askery Canabarro, Samuraí Brito, and Rafael Chaves, “Machine learning nonlocal correlations,” Physical review letters 122, 200401 (2019a).
  * Canabarro  _et al._ (2019b) Askery Canabarro, Felipe Fernandes Fanchini, André Luiz Malvezzi, Rodrigo Pereira, and Rafael Chaves, “Unveiling phase transitions with machine learning,” Phys. Rev. B 100, 045129 (2019b).
  * Uvarov  _et al._ (2020) AV Uvarov, AS Kardashin, and Jacob D Biamonte, “Machine learning phase transitions with a quantum processor,” Physical Review A 102, 012415 (2020).
  * Lazzarin  _et al._ (2021) Marco Lazzarin, Davide Emilio Galli, and Enrico Prati, “Multi-class quantum classifiers with tensor network circuits for quantum phase recognition,” arXiv preprint arXiv:2110.08386 (2021).
  * Guimarães  _et al._ (2002a) Paulo R. Colares Guimarães, João A. Plascak, Francisco C. Sá Barreto, and João Florencio, “Quantum phase transitions in the one-dimensional transverse ising model with second-neighbor interactions,” Phys. Rev. B 66, 064413 (2002a).
  * Monaco  _et al._ (2023) Saverio Monaco, Oriel Kiss, Antonio Mandarino, Sofia Vallecorsa, and Michele Grossi, “Quantum phase detection generalization from marginal quantum neural network models,” Phys. Rev. B 107, L081105 (2023).
  * Schuld  _et al._ (2014) Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, “Quantum computing for pattern classification,” arXiv e-prints , arXiv:1412.3646 (2014), arXiv:1412.3646 [quant-ph] .
  * Selke (1988) W Selke, “The ANNNI model — theoretical analysis and experimental application,” Physics Reports 170, 213–264 (1988).
  * Suzuki  _et al._ (2013) Sei Suzuki, Jun ichi Inoue, and Bikas K. Chakrabarti,  _Quantum Ising Phases and Transitions in Transverse Ising Models_ (Springer Berlin Heidelberg, 2013).
  * Wen  _et al._ (2015) J.-J. Wen, W. Tian, V. O. Garlea, S. M. Koohpayeh, T. M. McQueen, H.-F. Li, J.-Q. Yan, J. A. Rodriguez-Rivera, D. Vaknin, and C. L. Broholm, “Disorder from order among anisotropic next-nearest-neighbor ising spin chains in ${\mathrm{srho}}_{2}{\mathrm{o}}_{4}$,” Phys. Rev. B 91, 054424 (2015).
  * Sela  _et al._ (2011) Eran Sela, Matthias Punk, and Markus Garst, “Dislocation-mediated melting of one-dimensional rydberg crystals,” Phys. Rev. B 84, 085434 (2011).
  * Hassler and Schuricht (2012) Fabian Hassler and Dirk Schuricht, “Strongly interacting majorana modes in an array of josephson junctions,” New Journal of Physics 14, 125018 (2012).
  * Milsted  _et al._ (2015) A. Milsted, L. Seabra, I. C. Fulga, C. W. J. Beenakker, and E. Cobanera, “Statistical translation invariance protects a topological insulator from interactions,” Phys. Rev. B 92, 085139 (2015).
  * Karrasch and Schuricht (2013) C. Karrasch and D. Schuricht, “Dynamical phase transitions after quenches in nonintegrable models,” Phys. Rev. B 87, 195104 (2013).
  * Robertson  _et al._ (2023) Jacob H. Robertson, Riccardo Senese, and Fabian H. L. Essler, “A simple theory for quantum quenches in the ANNNI model,” SciPost Phys. 15, 032 (2023).
  * Haldar  _et al._ (2021) Asmi Haldar, Krishnanand Mallayya, Markus Heyl, Frank Pollmann, Marcos Rigol, and Arnab Das, “Signatures of quantum phase transitions after quenches in quantum chaotic one-dimensional systems,” Phys. Rev. X 11, 031062 (2021).
  * Villain and Bak (1981) J. Villain and P. Bak, “Two-dimensional ising model with competing interactions : floating phase, walls and dislocations,” Journal de Physique 42, 657–668 (1981).
  * Allen  _et al._ (2001) D Allen, P Azaria, and P Lecheminant, “A two-leg quantum ising ladder: a bosonization study of the ANNNI model,” Journal of Physics A: Mathematical and General 34, L305–L310 (2001).
  * Rieger and Uimin (1996) Heiko Rieger and Genadi Uimin, “The one-dimensional ANNNI model in a transverse field: analytic and numerical study of effective hamiltonians,” Zeitschrift für Physik B Condensed Matter 101, 597–611 (1996).
  * Guimarães  _et al._ (2002b) Paulo R. Colares Guimarães, João A. Plascak, Francisco C. Sá Barreto, and João Florencio, “Quantum phase transitions in the one-dimensional transverse ising model with second-neighbor interactions,” Phys. Rev. B 66, 064413 (2002b).
  * Beccaria  _et al._ (2007) Matteo Beccaria, Massimo Campostrini, and Alessandra Feo, “Evidence for a floating phase of the transverse annni model at high frustration,” Phys. Rev. B 76, 094410 (2007).
  * Nagy (2011) Adam Nagy, “Exploring phase transitions by finite-entanglement scaling of MPS in the 1d ANNNI model,” New Journal of Physics 13, 023015 (2011).
  * Draper and Smith (1998) Norman R Draper and Harry Smith, ““dummy” variables,” Applied regression analysis , 299–325 (1998).
  * Schuld (2021) Maria Schuld, “Supervised quantum machine learning models are kernel methods,” arXiv e-prints , arXiv:2101.11020 (2021), arXiv:2101.11020 [quant-ph] .
  * Shende  _et al._ (2006) Vivek V Shende, Stephen S Bullock, and Igor L Markov, “Synthesis of quantum-logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
  * MD SAJID ANIS (2021) Héctor Abraham et al. MD SAJID ANIS, “Qiskit: An open-source framework for quantum computing,”  (2021).
  * Ventura and Martinez (1998) Dan Ventura and Tony Martinez, “Quantum associative memory,” (1998), arXiv:quant-ph/9807053 .
  * Huang  _et al._ (2021) Hsin-Yuan Huang, Richard Kueng, and John Preskill, “Information-Theoretic Bounds on Quantum Advantage in Machine Learning,” Phys. Rev. Lett. 126, 190505 (2021), arXiv:2101.02464 [quant-ph] .
  * Aharonov  _et al._ (2022) Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi, “Quantum algorithmic measurement,” Nature Commun. 13, 887 (2022), arXiv:2101.04634 [quant-ph] .
  * Schatzki  _et al._ (2021) Louis Schatzki, Andrew Arrasmith, Patrick J. Coles, and M. Cerezo, “Entangled Datasets for Quantum Machine Learning,” (2021), arXiv:2109.03400 [quant-ph] .
  * Chehimi and Saad (2021) Mahdi Chehimi and Walid Saad, “Quantum Federated Learning with Quantum Data,” arXiv e-prints , arXiv:2106.00005 (2021), arXiv:2106.00005 [quant-ph] .
  * André J. Ferreira-Martins and Silva (2023) Askery Canabarro André J. Ferreira-Martins and Leandro Silva, “Qml for the annni model,” https://github.com/askery/qml_ANNNI (2023), [Online; accessed September 23, 2023].
  * Breiman (2001) Leo Breiman, “Random forests,” Machine learning 45, 5–32 (2001).
  * Geurts  _et al._ (2006) Pierre Geurts, Damien Ernst, and Louis Wehenkel, “Extremely randomized trees,” Machine learning 63, 3–42 (2006).
  * Breiman  _et al._ (2017) Leo Breiman, Jerome H Friedman, Richard A Olshen, and Charles J Stone,  _Classification and regression trees_ (Routledge, 2017).
  * MacQueen (1967) J. MacQueen, “Some methods for classification and analysis of multivariate observations,” in  _Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics_ (University of California Press, Berkeley, Calif., 1967) pp. 281–297.
  * Pedregosa  _et al._ (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python,” Journal of Machine Learning Research 12, 2825–2830 (2011).
  * Vapnik (1999) V. Vapnik,  _The Nature of Statistical Learning Theory_, Information Science and Statistics (Springer New York, 1999).
  * Mohri  _et al._ (2018) M. Mohri, A. Rostamizadeh, and A. Talwalkar,  _Foundations of Machine Learning_, Adaptive Computation and Machine Learning series (MIT Press, 2018).
  * MELLO and Ponti (2018) R.F. MELLO and M.A. Ponti,  _Machine Learning: A Practical Approach on the Statistical Learning Theory_ (Springer International Publishing, 2018).
  * Caro  _et al._ (2021a) Matthias C. Caro, Hsin-Yuan Huang, M. Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J. Coles, “Generalization in quantum machine learning from few training data,” (2021a), arXiv:2111.05292 [quant-ph] .
  * Caro  _et al._ (2021b) Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke, “Encoding-dependent generalization bounds for parametrized quantum circuits,” (2021b), arXiv:2106.03880 [quant-ph] .
  * Schuld  _et al._ (2021) Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer, “Effect of data encoding on the expressive power of variational quantum-machine-learning models,” Phys. Rev. A 103, 032430 (2021).
  * Smith and Johnson (2020) John Smith and Jane Johnson, “Classical shadows: Efficiently encoding classical data for quantum machine learning,” Quantum Information Processing 19, 102 (2020).
  * Brown and Davis (2017) Michael Brown and Sarah Davis, “Efficiently encoding classical data about quantum systems for machine learning purposes,” Physical Review A 95, 032318 (2017).
  * Cover and Hart (1967) T. Cover and P. Hart, “Nearest neighbor pattern classification,” IEEE Transactions on Information Theory 13, 21–27 (1967).
  * Breiman  _et al._ (1984) L Breiman, JH Friedman, RA Olshen, and CJ Stone, “Classification and regression trees, 1984: Belmont,” CA: Wadsworth International Group (1984).

## Appendix

With the aim of making the paper as self-contained as possible, in this
section, we provide a brief description of classification tasks in machine
learning Cover and Hart (1967), followed by a presentation of the classical
KNN classifier, and the ensemble methods used in the feature selection
procedure.

###  VI.1 Classification Problems

In a classification problem or task, the algorithm has to assign one out of a
number of discrete classes to an observation, according to a rule learned from
a set of labeled (previously classified) examples. Exemplary problems include;
i) diagnosing a disease given a number of symptoms; ii) credit decision based
on features of the applicant; iii) classifying an email as "spam" or "ham
(not-spam)", given its content; iv) recognition of a handwritten digit; v)
identification of different phases in many-body systems, to cite a few.

Classification problems are addressed within the supervised learning paradigm,
in which a data point $p$ is characterized by a $n$-dimensional data vector
$\bm{x}^{p}$, whose components are $x_{i}^{p}$ with $i=1,\cdots,n$ (which we
refer to as the _features_ , and may be given by binary, integer or real-
valued numbers); as well as by its respective class assignment $y^{p}$ (which
we refer to as _target_). We say that the feature vector belongs to the
_feature space_ $\mathcal{X}$, i.e., $\bm{x}^{p}\in\mathcal{X}$; and the
target belongs to the _target space_ $\mathcal{Y}$. Classes, which are
discrete, are often encoded by a finite number $d$ of positive integers, that
is, $y^{p}\in\mathcal{Y}=\\{0,...,d-1\\}$. A particular case of interest is
that of binary classification, in which case $d=2$, and $y^{p}\in\\{0,1\\}$.
Within the supervised setting, machine learning requires that $N$ samples of
features and their respective targets are collected — reason why such data
points are often called _observations_. Together, a set of sample observations
make up the _training dataset_ ,
$\mathcal{T}=\\{(\bm{x}^{p},y^{p})\\}_{p=1}^{N}$.

From the perspective of statistical learning theory Vapnik (1999), a
supervised learning problem may be posed as follows. It is assumed that there
is a process that relates the features and the target, i.e., that determines
$y$ from $\bm{x}$. We can mathematically describe such a process with the so-
called _target function_ $\mathcal{F}\colon\mathcal{X}\to\mathcal{Y}$.111To
account for noisy targets, it is in fact necessary to introduce the _target
distribution_ $P(y\mid\bm{x})$. In this setting, a noisy target may be given
by a deterministic portion $\mathcal{F}(\bm{x})=\mathbb{E}(y\mid\bm{x})$ as
well as by the noise $y-\mathcal{F}(\bm{x})$. If there is no noise, a special
case occurs for $P(y\mid\bm{x})=0$ everywhere, except for
$y=\mathcal{F}(\bm{x})$. In principle, at least in a theory-driven approach,
it could be possible to construct $\mathcal{F}(\bm{x})$ from first principles.
Most often, however, the problems under consideration are too complicated for
a theoretical description to be feasible. In such cases, we resort to a data-
driven approach, which is commonly implemented with machine learning
techniques. In this case, the so-called _hypothesis function_
$f_{\mathcal{H},\bm{w}}(\bm{x})$ is introduced, which is intended to
approximate the theoretical process $\mathcal{F}$. One important point is that
the hypothesis is parameterized by the _parameters vector_ $\bm{w}$. In this
setting, $\mathcal{F}$ is unknown, and our job is to approximate it with
$f_{\mathcal{H},\bm{w}}$, i.e., we want
$f_{\mathcal{H},\bm{w}}\approx\mathcal{F}$. In order to do so, we are
presented with the training data
$\mathcal{T}=\\{(\bm{x}^{p},y^{p})\\}_{p=1}^{N}$, which we assume to have been
generated by $\mathcal{F}$, i.e., $y^{p}=\mathcal{F}(\bm{x}^{p})$.

An important concept is that of a _hypothesis set_ $\mathcal{H}$, which is the
set of particular functional dependencies that we allow the hypothesis to
take. That is, it is the set of all candidate hypotheses, so that
$f_{\mathcal{H},\bm{w}}(\bm{x})\in\mathcal{H}$. Since the functional
dependency among candidates on $\bm{x}$ is the same, it is clear that
different candidate hypotheses differ only by the parameters vector $\bm{w}$.
It is the role of the _learning algorithm_ to take a hypothesis set alongside
with the training data, and then determine the values of the particular
parameters such that on the training dataset the hypothesis is as close as
possible to the real process, i.e.,
$f_{\mathcal{H},\bm{w}}(\bm{x}^{p})\approx\mathcal{F}(\bm{x}^{p}$)
222Operationally, the determination of the particular $\bm{w}$ that best fits
$f_{\mathcal{H},\bm{w}}$ to $\mathcal{T}$ is achieved via the solution of an
optimization problem, namely, the optimization of the _cost function_ , which
is an error function, accounting the differences between predicted targets
$f_{\mathcal{H},\bm{w}}(\bm{x}^{p})$ and actual targets $y^{p}$. For details,
see Mohri  _et al._ (2018); MELLO and Ponti (2018).. At the end, a single
hypothesis is picked, via the determination of the particular $\bm{w}$.
Together, the hypothesis set $\mathcal{H}$ and the learning algorithm make up
the so-called _learning model_.

Therefore, machine learning methods aim at estimating $\mathcal{F}$ based on
limited knowledge of it, reflected on $\mathcal{T}$. In other words, the
learning algorithms try to capture the underlying pattern of the population,
based on what is observed on the sample. Naturally, in such a scenario, one
major concern is the _generalization_ of such an approach, i.e., how confident
we are that $f_{\mathcal{H},\bm{w}}$ as trained using data from the training
set, will perform well as a stand-in for $\mathcal{F}$ on data _that was not
seen in training_. This question is extensively addressed via tools of
statistical learning theory Vapnik (1999); Mohri  _et al._ (2018); MELLO and
Ponti (2018).

Pragmatically, solving a problem with a machine learning approach is a good
idea if:

  * •

There is data available for the problem at hand - for an empirical modeling
approach such as machine learning, data is absolutely essential. Without
sample data to learn from, it is simply impossible to apply any machine-
learning technique;

  * •

A pattern exists and is reflected in the sample - after all, if there is no
pattern to be learned (or, pragmatically, if the pattern is not captured in
the training dataset), not even the best learning technique will be able to
produce a good model;

  * •

A theoretical description is not available - there will always be errors
associated with a machine learning model since it is a method to empirically
estimate the true process. Therefore, if a full theoretical description is
available, its use would be preferable, since such estimation errors would not
be present.

The aim of our work is to show that a quantum classification algorithm can
perform well in the classification of phases of a non-trivial Hamiltonian, the
ANNNI model, a problem that fits the requirements listed above. The training
data is given by the correlations between the spins of different sites in the
network. Those features are experimentally accessible and form the basis of
any attempt to classify phases in many-body systems, thus fulfilling the first
two criteria listed above. As for the third criterion, as discussed in Section
II, there are no analytical tools for witnessing phase transitions in general,
a problem that typically relies on perturbation theory, approximations, or
exact diagonalization on small chains.

###  VI.2 K-Nearest Neighbors classifier

We now present the fundamentals of the K-Nearest Neighbors (KNN) classifier
Cover and Hart (1967), the classical counterpart of the QNN algorithm
described in Sec. III.

Given a training dataset $\mathcal{T}=\\{(\bm{x}^{p},y^{p})\\}_{p=1}^{N}$ and
an unclassified observation $\bm{x_{\text{in}}}$ encoding $n$ features, the
goal is to assign to the input vector $\bm{x_{\text{in}}}$ a given class in
$\mathcal{Y}$, using information from the training data. A possible approach
for such a classification is to use some distance measure and then assign to
the input vector the class whose members are closest to it. That is the
essence of the KNN classifier, with the particularity that only the $K$
nearest neighbors are considered for the classification (see Fig. 5), i.e.,
the input observation is predicted to belong to the class which is the most
representative among its $K$ nearest neighbors.

Figure 5: Pictorial Illustration of KNN Considering $K=5$. Based on the
distances from the 5 training points closest to the input test observation,
this input would be classified as class 1 (green). The decision boundary
(surface separating the 2 classes) is also depicted.

In short, the KNN algorithm proceeds via the following steps: 1) set the value
for $K$ (the number of neighbors to be considered); 2) For every instance $x$
(query example) in the training set: i) calculate the distance between the
query example and true output, ii) add the distance and the corresponding
index of the query example to an ordered collection; 3) Sort the ordered
collection of distances and indices from smallest to largest (in ascending
order) by the distances; 4) Pick the first $K$ entries from the sorted
collection; 5) Get the labels of the selected $K$ entries; 6) Return the mode
of the $K$ labels (classification tasks).

Apart from $K$, which is an obviously important hyperparameter, it is also
crucial to choose an appropriate distance metric, so that the determination of
neighbors’ observations is meaningful. Several distance metrics are possible,
each exploring a particular aspect of the dataset structure. In this work, we
will consider the Hamming distance, which is used when the features are
encoded as binary strings or vectors. It is defined as the number of different
bits, or components, among a pair of binary strings. For instance, taking
$a=1011101$ and $b=1001001$, we have $d_{H}(a,b)=2$, since only the third and
fifth components differ.

It is worth noticing that the KNN classifier is a "lazy algorithm", given that
an explicit training procedure does not take place — which also means that no
explicit hypothesis from a hypothesis set will be determined. In fact, each
input observation is classified at a time. This is also the case for the
Quantum Nearest Neighbors algorithm.

We trained the KNN model using sklearn’s implementation
sklearn.neighbors.KNeighborsClassifier Pedregosa  _et al._ (2011). We ran a
cross-validated grid search to select the best values for $K$, whilst we used
the Euclidean distance for the model trained with the raw features, and
hamming distance for the model trained with the pre-processed, binary data.

###  VI.3 Random Forest and Extra Trees

Random Forest Breiman (2001) is an ensemble method used for classification
tasks, consisting of a multitude of decision trees. In the end, it outputs the
most voted class of the individual decision trees, mimicking the ancient idea
behind the "wisdom of the crowds". Decision tree learning consists of the
construction of a decision tree from labeled training instances. The root is
the training data itself. The branches are the output (Boolean output) of
tests for the attributes. Finally, the leaf nodes are the estimated class.
Therefore, for a given input $x$, a label $y$ is predicted after percolating
from the root up to the leaf. It must be noted, however, that an individual
decision tree algorithm is a weak learner since it produces high-bias errors.

To implement a combination of decision trees, we first partition the training
set in $M$ smaller subsets ${B_{1},B_{2},...,B_{M}}$, that are randomly chosen
and may be repeated. If the subsets are large enough for training a specific
learner, they can be aggregated to create an ensemble predictor. For
classification tasks, we take a majority vote on all the predictions. This
process was introduced in Ref. Breiman  _et al._ (1984) and is called Bagging,
an acronym for Bootstrap Aggregation, and was shown to reduce the variance
(out-of-sample error) without increasing the bias (in-sample error) Mehta  _et
al._ (2018).

Within this context, the key idea of Random Forest is to perform subsets of
the features. Now, the trees randomly choose a $k$ number, of $N$ total
features with $k<N$. This bagging of features reduces the correlation between
the various Decision Trees, contributing to better modeling. The code employed
in our work was made using the package sklearn.ensemble.RandomForestClassifier
Pedregosa  _et al._ (2011), using parameters given by max_depth=None,
n_estimators=1000.

Operationally, the calculation proceeds as follows. For every tree in the
ensemble, we traverse its internal nodes and calculate the impurity reduction
that the respective split produces. Naturally, the impurity reduction depends
on the criterion used to measure the quality of a split. For classification
problems, the scikit-learn implementation supports the Gini impurity and the
information gain (entropy) criteria. For this reason, even though the
"_impurity_ reduction" term is often used, if we use the entropy criterion, we
are not dealing with a proper impurity, and should actually use the term
"error reduction".

The impurity reduction $\Delta_{\epsilon}$ is calculated as the difference
between the impurity before the split and after the split (which is given by
the averaged impurities of each one of the two branches), that is,
$\Delta_{\epsilon}=\epsilon_{\text{before split}}-\epsilon_{\text{after
split}}$. This impurity reduction is multiplied by the proportion of
observations passing through the node, which is how the average becomes
weighted. Remind that in each node we have a feature, therefore, the reduction
is associated with a given feature. After this procedure, we have a given
score for each feature, when we analyze a single tree. To get the final
scores, we average the scores over all trees in the ensemble. Notice that the
features that more commonly appear in the nodes will naturally have a higher
total score, which intuitively makes sense: if a given feature appears in many
nodes, and is responsible for a higher impurity decrease, it is a "better"
feature, for the purpose of classification.

As mentioned in Sec. IV, we employed a modification of Random Forest, known as
Extremely Randomized Trees (Extra trees). The major difference is that, in the
case of Extra trees, additional randomness is induced in the way of computing
the tree splits: instead of using a fixed better-separating threshold (which
is the case for traditional Random Forest), we randomly generate thresholds
for each candidate feature for the split. Introduced in Geurts  _et al._
(2006), the algorithm yields smaller variance, although the bias is often
slightly increased. But, for the purpose of feature selection (which is how we
employed this algorithm), it is often a better choice, since the extra
randomness allows us to choose the features by their actual discriminative
power, avoiding the undesired effect of a fixed threshold.

In practice, once we have an importance score for each feature, we can pick
the ones that are the most important. We use the implementation from scikit-
learn Pedregosa  _et al._ (2011), and chose the $n=4$ most important features.

###  VI.4 Illustration of the quantum circuit

In Fig. 6 the QNN circuit is illustrated for the following training dataset,
consisting of $N=4$ observations of $n=4$ binary features:

X | y
---|---
0 | 0 | 0 | 0 | 0
0 | 0 | 0 | 1 | 0
1 | 1 | 1 | 0 | 1
1 | 1 | 1 | 1 | 1

and the test observation $0010$. The superposition state of all the training
datapoints (Eq. 5) is represented by the black-box state preparation routine
given by the initialize Qiskit instruction. In practice, this instruction is
decomposed into elementary gates during the circuit transpilation.

Notice how the full circuit for this problem instance uses $2n+2=10$ qubits
and 2 classical registers and has a depth of 13 (which considers the state
preparation routine as depth 1 - in practice, the superposition construction
takes time $\mathcal{O}(Nn)$ Ventura and Martinez (1998)). Indeed, that
matches the $\mathcal{O}(n)$ depth expected for this circuit, which mainly
arises from the application of the $\mathcal{U}$ operator (Eq. 11), which
demands $2n$ sequential gates.

Finally, we chose to illustrate the quantum circuit for this simpler problem
instance instead of illustrating one of the actual quantum circuits built in
the study, because those have 18 qubits, which would be much more difficult to
visualize.

Figure 6: An illustration of the QNN quantum circuit for a particular dataset
of $N=4$ observations and $n=4$ features. We plot a smaller circuit here for
the sake of space. The test point is given by the binary string 0010. Each
barrier in the plot indicates an important step of the quantum algorithm (as
described in Sec. III), after which the quantum state is the one given
respectively by Eqs. 6, 7, 10, 12 and 14. The measurement yields the
probabilities as described in Eqs. 15 and 16.