# A Leap among Entanglement and Neural Networks: A Quantum Survey

Fabio Valerio Massoli<EMAIL_ADDRESS>0000-0001-6447-1301 ,  Lucia
Vadicamo  0000-0003-0171-4315<EMAIL_ADDRESS>,  Giuseppe Amato
0000-0001-7182-7038<EMAIL_ADDRESS>and  Fabrizio Falchi
0000-0001-7182-7038<EMAIL_ADDRESS>Istituto di Scienza e
Tecnologie dell’Informazione “Alessandro Faedo”, CNRVia G. Moruzzi
1PisaItaly56124

(2021)

###### Abstract.

In recent years, Quantum Computing witnessed massive improvements both in
terms of resources availability and algorithms development. The ability to
harness quantum phenomena to solve computational problems is a long-standing
dream that has drawn the scientific community’s interest since the late ’80s.
In such a context, we pose our contribution. First, we introduce basic
concepts related to quantum computations, and then we explain the core
functionalities of technologies that implement the Gate Model and Adiabatic
Quantum Computing paradigms. Finally, we gather, compare and analyze the
current state-of-the-art concerning Quantum Perceptrons and Quantum Neural
Networks implementations.

Quantum Computing, Quantum Machine Learning, Quantum Neural Network, Quantum
Deep Learning

††copyright: acmcopyright††journalyear: 2021††journalvolume: 0††journalnumber:
0††article: 0††publicationmonth: 0††ccs: Computer systems organization Quantum
computing††ccs: Computer systems organization Neural networks††ccs: Computing
methodologies Neural networks††ccs: Computing methodologies Machine
learning††ccs: Applied computing Physics††ccs: Hardware Quantum technologies

##  1\. Introduction

Artificial Intelligence (AI) has intrigued and puzzled many generations of
scientists and largely fueled novels writers’ imaginations. Perhaps, the
modern definition of AI – as the ensemble of computer systems empowered with
the ability to learn from data through statistical techniques – can be dated
back to 1959. Machine Learning (ML), a subclass of AI, is a discipline that
aims at studying algorithms that are able to learn from experience and data to
perform tasks without following explicit instructions. Often, these algorithms
are based on a computational model that belongs to differentiable programming
techniques, called Neural Networks (NNs). The success of such algorithms
resides in their ability to learn to achieve a specific goal (LeCun et al.,
1989; Hinton et al., 2006), i.e., they learn to discover hidden patterns and
relations among data to fulfill the task at hand (Hastie et al., 2009; LeCun
et al., 2015). Mathematically, NNs are made of a sequence of transformations,
called layers, composed of affine operators and elementwise nonlinearities.
Then, the goal of learning is to modify the transformations’ parameters to
fulfill a task successfully. Whenever a model accounts for more than a couple
of such layers, it is called a Deep Learning (DL) model or a Deep Neural
Network (DNN). Thanks to their enormous representation power and the
development of new technologies and training algorithms, DL models obtained
astonishing results in the last two decades, achieving superhuman performance
on certain tasks (Silver et al., 2018). However, higher performances require
more complex models and larger datasets to train them, thus constantly
increasing the hunger for resources and power (Andrae and Edler, 2015) to
learn to solve a given problem.

In this regard, quantum computers might offer new solutions that exploit
quantum phenomena such as interference, superposition, and entanglement that
are not available in classical computations. Such a characteristic is expected
to speedup the computational time and to reduce the requirements for extensive
resources, yielding the concepts of quantum advantage and quantum supremacy
(Nielsen et al., 2002; Preskill, 2012). The mentioned quantum phenomena are
described within the framework of quantum mechanics (Heisenberg, 1925;
Schrödinger, 1926; Dirac, 1981), a “young” physics theory formalized at the
beginning of the 20th century. Such a theory unveils the intrinsic statistical
characteristic of nature, a behavior that unfortunately is hidden from us, at
least in the macroscopic world.

The quest for a quantum computer started with the ideas of Benoff (Benioff,
1980) and Feynmann (Feynman, 1982; Lloyd, 1996), in the 1980s, pointing out
that quantum computers should be more efficient in solving specific problems.
Thus, for example, quantum devices might help in studying very complex, e.g.,
entangled, systems by emulating or simulating (Georgescu et al., 2014;
Paraoanu, 2014; Pérez-Salinas et al., 2021; Efthymiou et al., 2020) their
behavior into chips that are quantum by their nature (Reiher et al., 2017;
Wecker et al., 2015).

From a computer science point of view, a quantum computer represents a
computational model based on the principles and postulates of quantum
mechanics. Such techniques aim at embracing the power of quantum theory into a
device that can be conveniently “programmed” to fulfill a given task.
Moreover, the result of the computation itself might represent a quantum
object encoding different answers, each of which solves a specific problem
(Deutsch and Jozsa, 1992). It is only very recently that researchers succeeded
in realizing a quantum processor capable of performing controllable
computations based on quantum phenomena. Several industrial applications have
already been implemented successfully such as: chemistry (Kandala et al.,
2017; Cao et al., 2019), optimization problems (Moll et al., 2018), finance
(Egger et al., 2020; Lee, 2020), anomaly detection (Liu and Rebentrost, 2018),
quantum meteorology (Giovannetti et al., 2011), quantum sensing (Degen et al.,
2017), quantum illumination (Lloyd, 2008), and quantum imaging (Chen et al.,
2012) to mention some. Apart from the mentioned applications, energy
management is another topic for which quantum computers might offer advantages
compared to classical ones. Indeed, quantum processors are expected to be more
efficient in terms of energy consumption (Ajagekar and You, 2019) as compared
to supercomputers while solving a specific task. For that reason, hybrid
approaches might offer exciting solutions to lower the energy consumption for
a given computation by moving the high-energy portion of the computation on
the Quantum Processing Unit (QPU) while leaving the low-energy to the cloud
(Toosi et al., 2014). A fundamental result from quantum information theory is
the observation that, although quantum phenomena allow solving some classical
problems more efficiently than classical computations (Bernstein and Vazirani,
1997), quantum computers cannot compute any function which is not turing-
computable (Deutsch, 1985). Thus, setting a hard cut on what quantum devices
will be able to accomplish.

Concerning the context of Quantum Machine Learning (QML) (Biamonte et al.,
2017), a relevant contribution comes from the ability of quantum devices to
speedup linear algebra-related tasks. For example, the Harrow-Hassidim-Lloyd
(HHL) algorithm (Harrow et al., 2009; Zheng et al., 2017) to sample solutions
for a system of linear equations already proved an exponential speedup over
its classical counterpart. Furthermore, Shor’s algorithm (Shor, 1994, 1999)
for integer factorization, and Grover’s algorithm (Grover, 1997), for
searching unstructured databases, are other examples of procedures that
benefit from a quantum formulation. Although general QML is of great interest,
it is not the central topic of our work as it has already been covered
extensively in the literature. Therefore, we focus our attention on the QML
sub-area concerning recent Quantum Neural Networks (QNNs) approaches. Even
though their name recalls the neural network structure mentioned earlier, they
are characterized by a different architecture.

Concerning quantum computations, the most commonly adopted paradigms are the
Gate Model (GM) (Nielsen et al., 2002) and Adiabatic Quantum Computation (AQC)
(Albash and Lidar, 2018). Although they are equivalent up to a polynomial
overhead, they represent two profoundly different computation approaches. The
first one is based on the concept of “gate” that is a unitary transformation
defined by the user which is applied to one or more quantum bits, i.e. , the
basic units of quantum information (see section 3). Instead, in the AQC, one
typically encodes the desired objective function into a quantum system and
then lets it evolve naturally. However, in both paradigms, the state of the
QPU at the end of the evolution embodies the answer to the given problem.
Thus, we can highlight the main differences between the two approaches as
follows. The GM allows to control the transformation to apply on the qubits
directly and is discrete in time, while AQC does not allow to control single
qubits directly and does not discretize the time property of the system.

Unfortunately, quantum technologies are still at their dawn, having minimal
computational capacity. Furthermore, significant technological challenges
arise from the adiabatic requirements, i.e., quantum systems need to be
isolated from the environment not to experience decoherence, which causes the
lack of information stored in the quantum device. Therefore, researchers
typically rely on quantum simulators to test their ideas while waiting for the
next generation of quantum computing units. Whether quantum supremacy is real
or belongs to the fairy world is still an open question. For example, we do
not expect quantum computers to solve worst-case NP-hard problems like
combinatorial problems efficiently. Instead, we do expect that we will be able
to find a better approximation to the solution or find it faster than a
classical computer (Khot, 2016; Preskill, 2018).

Stemming from those considerations, we conceived this survey to offer both the
neophyte and the more experienced reader insights into several fundamental
topics in the quantum computation field. Moreover, noticing that the
literature lacks a detailed discussion about the latest achievements
concerning Quantum Perceptrons (QPs) and QNNs, we gather, analyze and discuss
state-of-the-art approaches related to those topics. Notably, the main
contributions of our work can be summarized as follows:

  * •

we review the current state-of-the-art regarding QPs and QNNs by discerning
among theoretical formulations, simulations, and implementations on real
quantum devices;

  * •

we report the main achievements by different research groups concerning the
topic of quantum supremacy;

  * •

we introduce the concept of qubit from a theoretical perspective and give
insights into how it is represented;

  * •

we report a gentle introduction to the Adiabatic Quantum Computing and Gate
Model computation paradigms and highlight their differences;

  * •

we introduce to the reader several basic notions about quantum mechanics and
their translations in the quantum information field;

  * •

we collect and organize the most relevant papers to this survey on a
GitHub111https://github.com/fvmassoli/survey-quantum-computation page allowing
the interested readers to easily and quickly browse through the literature.

Going through the literature, we noticed a plethora of different nomenclatures
to describe the same concepts. For that reason, we tried to rephrase all the
different approaches under a unique framework in our work. As a reference, we
report in Table 1 and Table 2 a summary of the notations and abbreviations
used throughout the rest of the manuscript. Moreover, to ease the
understanding of the paper’s content, we suggest the reader who is unfamiliar
with the topic to peruse the Appendix A before reading any further.

Table 1. Summary of notation used throughout this paper. Symbol |  Definition
---|---
$\text{Re}(z)$, $\text{Im}(z)$ |  Real and imaginary parts of the complex number $z$
${z}^{*}$ |  Complex conjugate of the complex number $z$.
${A}^{*}$ |  Complex conjugate of the matrix $A$.
${A}^{T}$ |  Transpose of the matrix $A$.
${A}^{\dagger}$ |  Complex conjugate transpose of the matrix $A$, i.e. ${A}^{\dagger}=(A^{*})^{T}$ .
${A}\otimes B$ |  Kronecker product of the matrix $A$ with the matrix $B$ .
$\hat{A}$ |  Linear operator whose matrix representation is $A$
$I$, $\hat{I}$ |  Identity matrix and Identity operator
$\hat{H}$ |  Hamiltonian
$\xi_{i}$ |  Eigenvalues of the Hamiltonian
$\dot{f}$ |  Newton’s notation for the derivative of a function $f(t)$ with respect to $t$
$\hat{\sigma}_{x}$, $\hat{\sigma}_{y}$, $\hat{\sigma}_{z}$ |  Pauli operators
$|{\psi}\rangle$ |  Vector of a Hilbert space, also called ket.
$\langle{\psi}|$ |  Vector dual to $|{\psi}\rangle$, also called bra.
$\langle{\psi}|{\phi}\rangle$ |  Inner product between $|{\psi}\rangle$ and $|{\phi}\rangle$ whose results in scalar.
$|{\psi}\rangle\langle{\phi}|$ |  Outer product between $\langle{\psi}|$ and $|{\phi}\rangle$ whose results in a matrix.
$\|\,|{\phi}\rangle\,\|=\sqrt{\langle{\phi}|{\phi}\rangle}$ |  Norm of $|{\phi}\rangle$.
$\delta_{ij}$ |  Kronecker delta that is defined to be equal to $1$ whenever $i=j$, and $0$ otherwise
$|{\psi}\rangle\otimes|{\phi}\rangle$, $|{\psi}\rangle|{\phi}\rangle$, $|{\psi,\phi}\rangle$, $|{\psi\phi}\rangle$ |  Tensor product between $|{\psi}\rangle$ and $|{\phi}\rangle$ and its abbreviated notations
$|{\psi}\rangle^{\otimes n}$ |  Tensor product between $n$ identical states $|{\psi}\rangle$, i.e. $|{\psi}\rangle^{\otimes n}=|{\psi}\rangle\otimes\dots\otimes|{\psi}\rangle$
$\langle{\psi}|\hat{A}|{\phi}\rangle$ |  Inner product between $|{\psi}\rangle$ and $\hat{A}|{\phi}\rangle$ where $\hat{A}$ is a linear operator
$\langle\hat{A}\rangle$ |  Average value of an operator w.r.t. to a given state $|{\psi}\rangle:\langle{\psi}|\hat{A}|{\psi}\rangle$
$\\{|{0}\rangle,|{1}\rangle\\}$ or $\\{|{\uparrow}\rangle,|{\downarrow}\rangle\\}$ |  Computational basis
$|{+}\rangle$, $|{-}\rangle$ |  Hadamard basis states, defined by $|{+}\rangle=\frac{1}{\sqrt{2}}(|{0}\rangle+|{1}\rangle)$, and $|{-}\rangle=\frac{1}{\sqrt{2}}(|{0}\rangle-|{1}\rangle)$
$\rho$ |  Density matrix describing a given system’s state: $\rho=\sum_{i}\lambda_{i}|{\psi_{i}}\rangle\langle{\psi_{i}}|$
Table 2. Summary of abbreviations and acronyms used throughout this paper. Acronym |  Definition |  First occurrence
---|---|---
AI |  Artificial Intelligence |  section 1
ANN |  Artificial Neural Network |  section 6
AQC |  Adiabatic Quantum Computation |  section 1
AT |  Adiabatic Theorem |  subsection 4.2
DL |  Deep Learning |  section 1
DNN |  Deep Neural Network |  section 1
DCNN |  Deep Convolutional Neural Network |  subsection 6.3
NISQ |  Noisy Intermediate-Scale Quantum |  section 5
GM |  Gate Model |  section 1
ML |  Machine Learning |  section 1
NN |  Neural Network |  section 1
QAE |  Quantum AutoEncoders |  subsection 6.3
QAOA |  Quantum Approximate Optimization Algorithm |  subsection 6.1
QCNN |  Quantum Convolutional Neural Network |  subsection 6.3
QGNN |  Quantum Graph Neural Networks |  subsection 6.3
QML |  Quantum Machine Learning |  section 1
QNN |  Quantum Neural Network |  section 1
QP |  Quantum Perceptron |  section 1
QPU |  Quantum Processing Unit |  section 1
QVNN |  Quanvolutional Neural Networks |  subsection 6.3
RUS |  Repeat-Until-Success |  subsection 6.2
qSLP |  Single Layer Perceptron |  subsection 6.3
UAT |  Universal Approximation Theorem |  subsection 6.3
VQA |  Variational Quantum Algorithm |  subsection 6.1

Concerning the remaining part of the paper, it is organized as follows. First,
in section 2, we report about other surveys on the topic at hand, while in
section 3 we introduce the fundamental concept of the qubit and how it is
represented. Then, in section 4 and section 5 we give the reader a brief
overview about the currently most widespread quantum computational models and
tackle the concept of quantum speedup since it represents the cornerstone of
many scientific debates, respectively. Subsequently, in section 6, we move to
the core topic of this survey, i.e., QNNs approaches. Finally, the conclusions
are drawn in section 7.

##  2\. Other surveys

In the literature, many review papers have been devoted to the realm of
quantum computation and information. Several surveys addressed quantum ML and
its applications. However, very little has been said about QNNs, and reviews
that include this topic often cover it marginally or lack a detailed
discussion on the most recent achievements. For such a reason, we devoted our
work mainly to review Variational Learning approaches which encompass Quantum
Approximate Optimization Algorithms, Variational Quantum Eigensolver, Quantum
Perceptrons, and Quantum Neural Networks. As the surveys that are already
available in the literature cover extensively the basics of quantum computing
and quantum machine learning, in the following, we briefly review some of them
that may help the interested reader to approach these topics.

Gyongyosi and Imre (Gyongyosi and Imre, 2019) reviewed the technological
status of quantum computation and information systems by discussing several
papers that can be useful for researchers interested in delving deep into
specific aspects of quantum computations. Savchuk and Fesenko (Savchuk and
Fesenko, 2019) reported a brief analysis of some of the fundamental principles
beneath quantum computing. McGeoch (McGeoch, 2020) presented a comparison
between concepts and expected results based on a purely theoretical
calculation about complexity theory and what is currently achievable and
achieved on the modern physical realization of quantum processors based on
quantum annealing. They also gave interesting insights about basic notions
concerning the quantum annealing process, which is at the heart of the D-Wave
quantum platforms, and what kind of problems can be solved on it. Preskill
(Preskill, 2012, 2018) debated the concept of “quantum supremacy” and future
potential of quantum computing.

In the last two decades, there has been a strong interest and commitment in
the scientific community to develop quantum algorithms to solve ML problems,
giving life to the field of QML. Apparently, there is not a universally
accepted definition of QML yet. However, Aïmeur et al. (Aïmeur et al., 2006)
and Adcock et al. (Adcock et al., 2015) provided useful categorizations based
on the employed learning paradigms. For example, in (Adcock et al., 2015), the
term QML is used to refer to two learning categories: 1) approaches where the
learning process is performed mainly using classical computation and just some
sub-routines relying on quantum computation (input data can come from both
classical or quantum system); 2) leaning approaches designed to be run only
using quantum computations and for which there are no subroutines that can be
performed equally well on a classical computer (also in this case input data
can be both classical or quantum). This categorization excludes from the QML
class all the learning approaches performed on a classical machine but that
use data that come from quantum devices.

A viable approach to QML stems from the quantum algorithms that speedup linear
algebra-related tasks (see, e.g., (Wittek, 2014; Aaronson, 2015; Biamonte et
al., 2017; Schuld et al., 2015a; Havlíček et al., 2019)). In this context,
several quantum extension of classical algorithms have already been proposed,
for example, for clustering (Kerenidis et al., 2018; Lloyd et al., 2013;
Otterbach et al., 2017), Support Vector Machines (Rebentrost et al., 2014),
semidefinite programs (SDPs) (Brandão et al., 2019), gradient descent for
linear systems (Kerenidis and Prakash, 2020), PCA (Lloyd et al., 2014), RBMs
(Amin et al., 2018), variational generation for adversarial learning (Romero
and Aspuru-Guzik, 2021), just to cite some. Biamonte et al. (Biamonte et al.,
2017), and Schuld et al. (Schuld et al., 2015a) gave a lovely overview of the
achievements and challenges of quantum-enhanced machine learning algorithms,
considering aspects of both gate and adiabatic computational models. Basic
algorithms for quantum machine learning, such as Grover’s algorithm (Grover,
1997), quantum state "similarity" estimation, and the HLL algorithm (Harrow et
al., 2009), are nicely reviewed in (Zhang and Ni, 2020). The authors also
illustrate how these algorithms (based on the quantum gate model) have been
used in literature to speedup standard ML algorithms, like Support vector
machine, $k$-means clustering, Principle Component Analysis, and Linear
discriminant analysis. Some quantum operators and subroutines for ML are also
reviewed in (Ablayev et al., 2020a, b), with a particular focus on quantum
solutions (using the gate model) for binary classification and k-Nearest
Neighbour problems. Ciliberto et al. (Ciliberto et al., 2018) covered quantum
machine learning approaches with emphasis on theoretical aspects, such as
computational complexity analysis, discussion on limitations of quantum ML,
and challenging aspects like learning under noise. Theoretical aspects of ML
using quantum computers are also discussed in (Arunachalam and de Wolf, 2017).
Many other survey papers overview quantum algorithms for ML and their
applications, see for example (Manju and Nigam, 2014; Aïmeur et al., 2013;
Bharti et al., 2020; Dunjko and Briegel, 2018; Dunjko and Wittek, 2020; Schuld
and Killoran, 2019; Ramezani et al., 2020) and references therein.

Benedetti et al. (Benedetti et al., 2019) reviewed parametrized quantum
circuits, which are arguably the quantum analogous of NN models. The
Variational Quantum Algorithms, which employ parameterized quantum circuits,
are also discussed in (Cerezo et al., 2020). Kamruzzaman et al. (Kamruzzaman
et al., 2019) reviewed the status of (theoretical) Quantum Neural Networks and
their limitations. Allcock and Zhang (Allcock and Zhang, 2019) focused on
quantum generalizations and applications of some popular neural-network
concepts, like Boltzmann machine, generative adversarial networks, and
autoencoders.

##  3\. Qubit

The qubit, shorten for “quantum bit”, represents the fundamental unit of
information for quantum devices. It is the quantum correspondent of the bit
but, apart from the last part of its name, the qubit does not share much with
its classical cousin. Similar to the bit, which assumes two values only (0 or
1), the qubit can be “observed” (i.e. , measured) in two possible states,
typically indicated as $|{0}\rangle$ and $|{1}\rangle$. However, differently
from the bit, a qubit can also be in a so-called superposition of states
before the measurement. Intuitively, that means that the qubit can be in
either the state $|{0}\rangle$ or $|{1}\rangle$ with a certain probability.
Notwithstanding, when measured, the qubit state “collapses” into one of them.
The qubit is a rather abstract concept since such an object does not exist in
the real world. Instead, we relate it with artificial atoms, i.e., physical
systems able to emulate the behavior of an atom. Specifically, we are
typically interested in emulating the behavior of two-state systems that
satisfy a certain number of hard constraints such as small dissipation and
isolation from the environment.

In the following, first, we define the qubit at a theoretical level and
explain how it is represented, and then we report briefly a few examples of
how such an object is physically realized.

###  3.1. Theoretical Framework

From a mathematical point of view, a qubit state $|{\psi}\rangle$ is a unit
vector in $\mathbb{C}^{2}$. The symbol $|{\cdot}\rangle$ we just used is
inherited from Dirac (Dirac, 1939) formalism employed in the quantum mechanics
(please see subsection A.1 for an extensive introduction to such formalism).
In a nutshell, the object $|{\psi}\rangle$, called ket, represents a vector in
a Hilbert space. Similarly, $\langle{\psi}|$, called bra, is defined as the
adjoint (or dual) of such a ket. The letter “$\psi$” inside a ket or a bra is
just a label. Note that often binary labels are used, especially to indicate
the vectors of a space basis. For example, the basis
$\left\\{\begin{bmatrix}1\\\ 0\end{bmatrix},\begin{bmatrix}0\\\
1\end{bmatrix}\right\\}$ of $\mathbb{C}^{2}$, referred to as the computational
basis, is typically indicated as $\\{|{0}\rangle,|{1}\rangle\\}$, or sometimes
also as $\\{|{\uparrow}\rangle,|{\downarrow}\rangle\\}$. Using this formalism,
a qubit state can be represented by

(1) $|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$

where $\alpha$ and $\beta$, called amplitudes, are complex numbers such that
$|\alpha|^{2}+|\beta|^{2}=1$. Therefore, a qubit state is a coherent
superposition of the computational basis states $|{0}\rangle$ and
$|{1}\rangle$. However, this does not mean that a qubit has a value between
$|{0}\rangle$ and $|{1}\rangle$ but rather that it is not possible to say that
the qubit is definitively in the state $|{0}\rangle$, or definitively in the
state $|{1}\rangle$. In fact, when we measure a qubit we observe either
$|{0}\rangle$ with probability $|\alpha|^{2}$, or $|{1}\rangle$ with
probability $|\beta|^{2}$. After the measurement, the qubit state collapses to
whatever value ($|{0}\rangle$ or $|{1}\rangle$) was observed, irreversibly
losing memory of the former $\alpha$ and $\beta$ amplitudes. Please note that
different kinds of measurements exist for quantum computation, and the one we
referred to above is called measurement concerning the computational basis,
which is among the most widely used. Other measurements are discussed in the
appendix (subsubsection A.2.3).

We now turn our attention from the theoretical definition to a more physical
one. Any physical system whose state space can be described by
$\mathbb{C}^{2}$ can serve as a qubit’s physical realization. These systems
are referred to as quantum two-level systems, as their state can be described
by a vector in a 2-dimensional Hilbert space. The state of an isolated quantum
mechanical system composed by $n$ two-level system, called quantum
$n$-register, is described by a vector in a $2^{n}$-dimensional Hilbert space
($\mathcal{H}^{2^{n}}$). This means that a state of a $n$-register can
represent the superposition of $2^{n}$ basis states, which is the cornerstone
of the quantum parallelism exploited by the quantum computational models.
Formally, an n-register state can be described by the linear combination of
the basis vector $\\{|{0}\rangle,\dots|{2^{n}-1}\rangle\\}$:

(2)
$|{\psi}\rangle=\sum_{i=0}^{2^{n}-1}\alpha_{i}|{i}\rangle,\qquad\text{with}\quad\sum_{i=0}^{2^{n}-1}|\alpha_{i}|^{2}=1.$

If we measure the state $|{\psi}\rangle$ with respect to the computational
basis we get one of the basis state labels $i$ with probability
$p(i)=|\alpha_{i}|^{2}$ and the corresponding post-measurement state is
$|{i}\rangle$.

Usually a binary labeling is used to denote the $2^{n}$ basis states. For
example the state of a two-qubit system can be expressed as

(3)
$|{\psi}\rangle=\alpha_{00}|{00}\rangle+\alpha_{01}|{01}\rangle+\alpha_{10}|{10}\rangle+\alpha_{11}|{11}\rangle\qquad\text{with}\quad\sum_{i,j}|\alpha_{ij}|^{2}=1.$

The composition of two or more quantum system is represented by the tensor
product. For example if two systems A and B have the states
$|{\psi_{A}}\rangle=\alpha|{0}\rangle+\beta|{1}\rangle$ and
$|{\psi_{B}}\rangle=\gamma|{0}\rangle+\delta|{1}\rangle$, respectively, then
the system C composed by A and B has the state

(4)
$|{\psi_{C}}\rangle=|{\psi_{A}}\rangle\otimes|{\psi_{B}}\rangle=\alpha\gamma|{00}\rangle+\alpha\delta|{01}\rangle+\beta\gamma|{10}\rangle+\beta\delta|{11}\rangle$

Finally, note that a state $|{\psi}\rangle\in\mathcal{H}^{2^{n}}$ of a
$n$-register is called entangled if it that cannot be decomposed as the tensor
product of $n$ single qubit states.

####  3.1.1. The Bloch Sphere

Since a qubit $|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$ has more
states available than simply two levels, often it is useful to visualize it as
a point of a unit sphere in a Euclidean space. In fact, as shown in the
following, quantum states can be put in correspondence with the points of the
so-called Bloch sphere (Figure 1), which is a unit sphere in a three-
dimensional Euclidean space with the north and south pole corresponding to the
computational basis states $|{0}\rangle$ and $|{1}\rangle$, respectively.

Figure 1.  Bloch sphere representation of a qubit: a quantum state
$|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$, where
$\alpha=|\alpha|e^{i\varphi_{\alpha}}$ and
$\beta=|\beta|e^{i\varphi_{\beta}}$, is represented as the point of the Bloch
sphere with spherical coordinates given by the angles $\theta$ and $\varphi$,
where $\theta=\arccos{(|\alpha|^{2}-|\beta|^{2})}\in[0,\pi]$ and
$\varphi=\varphi_{\beta}-\varphi_{\alpha}\in[0,2\pi)$. Vice versa, a point of
the unit sphere with spherical coordinates $x=\sin\theta\cos\varphi$,
$y=\sin\theta\sin\varphi$, and $z=\cos\theta$ corresponds to the quantum state
$|{\psi}\rangle\equiv\cos\frac{\theta}{2}\,|{0}\rangle+e^{i\varphi}\sin\frac{\theta}{2}\,|{1}\rangle$.

An immediate geometrical interpretation of a state as a vector of a unit
sphere can be obtained by the map
$[\alpha,\beta]\in\mathbb{C}^{2}\to[\text{Re}(\alpha),\text{Im}(\alpha),\text{Re}(\beta),\text{Im}(\beta)]\in\mathbb{R}^{4}$,
but this interpretation is not useful for visualization purposes as it relies
on a four-dimensional Euclidean space. However, since we are interested only
in unitary 2-dimensional complex vectors, we can exploit the condition
$|\alpha|^{2}+|\beta|^{2}=1$ to reduce the parameters needed to describe the
quantum state, obtaining a three-dimensional representation that can be easily
visualized. Specifically, we could use the following transformation

(5) $\begin{cases}x=2\,\text{Re}(\alpha^{*}\beta)\\\
y=2\,\text{Im}(\alpha^{*}\beta)\\\ z=|\alpha|^{2}-|\beta|^{2}\\\ \end{cases}$

It can be easily proved that for $|\alpha|^{2}+|\beta|^{2}=1$ then
$x^{2}+y^{2}+z^{2}=1$. Thus, the above transformation maps a state
$|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$ onto a point of a
unitary sphere in $\mathbb{R}^{3}$, which is referred to as the Bloch sphere
(Figure 1). Note that any point of a unitary sphere in $\mathbb{R}^{3}$ can be
described using the spherical coordinate system

$\begin{cases}x=\sin\theta\cos\varphi\\\ y=\sin\theta\sin\varphi\\\
z=\cos\theta\end{cases}\qquad\theta\in[0,\pi],\quad\varphi\in[0,2\pi)$

which further reduces the number of parameters needed to describe the quantum
state. In fact, given the quantum state
$|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$, where
$\alpha=|\alpha|e^{i\varphi_{\alpha}}$, $\beta=|\beta|e^{i\varphi_{\beta}}$,
and $|\alpha|^{2}+|\beta|^{2}=1$, the spherical coordinates $(\theta,\varphi)$
can be computed by solving the system

(6)
$\begin{cases}\sin\theta\cos\varphi=2\,\text{Re}\left(\alpha^{*}\beta\right)\\\
\sin\theta\sin\varphi=2\,\text{Im}\left(\alpha^{*}\beta\right)\\\
\cos\theta=|\alpha|^{2}-|\beta|^{2}\end{cases}$

Since $|\alpha|^{2}-|\beta|^{2}=2|\alpha|^{2}-1=1-2|\beta|^{2}$, from the last
condition in Equation 6 we obtain that

(7)
$\displaystyle|\alpha|=\sqrt{\frac{1}{2}+\frac{1}{2}\cos\theta}=\cos\frac{\theta}{2},\qquad|\beta|=\sqrt{\frac{1}{2}-\frac{1}{2}\cos\theta}=\sin\frac{\theta}{2}$

Moreover, by combining Equation 7 and the first two conditions in Equation 6
we obtain $\varphi=\varphi_{\beta}-\varphi_{\alpha}$ because

(8)
$2\alpha^{*}\beta=2|\alpha||\beta|e^{i(\varphi_{\beta}-\varphi_{\alpha})}=2\cos\frac{\theta}{2}\sin\frac{\theta}{2}e^{i(\varphi_{\beta}-\varphi_{\alpha})}=\sin\theta
e^{i(\varphi_{\beta}-\varphi_{\alpha})}.$

Therefore, the spherical coordinates associated to the quantum state
$|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$ are

(9)
$\displaystyle\theta=\arccos{(|\alpha|^{2}-|\beta|^{2})},\qquad\varphi=\varphi_{\beta}-\varphi_{\alpha}$

Vice versa, any point of the Bloch sphere with spherical coordinates
$(\theta,\varphi)$ can be mapped to the quantum state
$\cos\frac{\theta}{2}\,|{0}\rangle+e^{i\varphi}\sin\frac{\theta}{2}\,|{1}\rangle$.
At first thought, since $\cos\frac{\theta}{2}$ is a real number, it might seem
that such a mapping from the Bloch sphere to the quantum state space is not
surjective because the amplitudes $\alpha$ and $\beta$ of a generic quantum
state $|{\psi}\rangle=\alpha\,|{0}\rangle+\beta\,|{1}\rangle$ are both complex
numbers. However, it should be noted that since the magnitudes $|\alpha|$ and
$|\beta|$ are positive real number constrained to lie on the unitary circle
then they can be specified by a single angle, i.e. there exist a
$\gamma\in[0,\frac{\pi}{2}]$ such that $|\alpha|=\cos{\gamma}$ and
$|\beta|=\sin{\gamma}$, or equivalently, $|\alpha|=\cos\frac{\theta}{2}$ and
$|\beta|=\sin\frac{\theta}{2}$ for $\theta=2\gamma\in[0,\pi]$. Thus, we have
$\alpha=e^{i\varphi_{\alpha}}\cos\frac{\theta}{2}$ and
$\beta=e^{i\varphi_{\beta}}\sin\frac{\theta}{2}$ for some
$\varphi_{\alpha},\varphi_{\beta}\in[0,2\pi)$. It follows that any state
$|{\psi}\rangle$ can be rewritten as

(10)
$\displaystyle|{\psi}\rangle=e^{i\varphi_{\alpha}}\left(\cos\frac{\theta}{2}\,|{0}\rangle+e^{i(\varphi_{\beta}-\varphi_{\alpha})}\sin\frac{\theta}{2}\,|{1}\rangle\right)\qquad\text{with}\quad\varphi_{\alpha},\varphi_{\beta}\in[0,2\pi),\,\theta\in[0,\pi]$

where $e^{i\varphi_{\alpha}}$ is called global phase factor and
$e^{i(\varphi_{\beta}-\varphi_{\alpha})}$ is the relative phase factor. As the
global phase has no observable effect (i.e. , quantum states $|{\psi}\rangle$
and $e^{-i\varphi_{\alpha}}|{\psi}\rangle$ are indistinguishable when
performing a measurement222The quantum states $|{\psi}\rangle$ and
$e^{i\gamma}|{\psi}\rangle$ are indistinguishable when performing a
measurement because they have the same probabilities of observing the
computational basis states, i.e. $|e^{i\gamma}\alpha|^{2}=|\alpha|^{2}$ and
$|e^{i\gamma}\beta|^{2}=|\beta|^{2}$ for any $\gamma\in[0,2\pi)$.) it can be
ignored. In other words, any quantum state $|{\psi}\rangle$ can be expressed
as

(11)
$|{\psi}\rangle\equiv\cos\frac{\theta}{2}\,|{0}\rangle+e^{i\varphi}\sin\frac{\theta}{2}\,|{1}\rangle$

where $\theta\in[0,\pi]$ and $\varphi\in[0,2\pi)$ are equal, respectively, to
the polar and azimuthal angles of the Bloch Sphere representation.

Note that antipodal points in the Bloch sphere correspond to orthogonal
states. In fact, two states
$|{\psi_{1}}\rangle=\cos\frac{\theta_{1}}{2}\,|{0}\rangle+e^{i\varphi_{1}}\sin\frac{\theta_{1}}{2}\,|{1}\rangle$
and
$|{\psi_{2}}\rangle=\cos\frac{\theta_{2}}{2}\,|{0}\rangle+e^{i\varphi_{2}}\sin\frac{\theta_{2}}{2}\,|{1}\rangle$,
with $\theta_{1},\theta_{2}\in[0,\pi]$ and
$\varphi_{1},\varphi_{2}\in[0,2\pi)$, are orthogonal if and only if
$\langle{\psi_{1}}|{\psi_{2}}\rangle=0$. It can easily proved that the
orthogonality condition holds if and only if either
$(\theta_{1},\theta_{2})=(0,\pi)$, $(\theta_{1},\theta_{2})=(\pi,0)$, or
$\theta_{1}+\theta_{2}=\varphi_{2}-\varphi_{1}=\pi$, which exactly identifies
antipodal points in the sphere.

It is worth mentioning that the normalized sum of the computational basis
vectors is called diagonal state, which is indicated by
$|{+}\rangle=\dfrac{1}{\sqrt{2}}|{0}\rangle+\dfrac{1}{\sqrt{2}}|{1}\rangle$.
It corresponds to the intersection of the positive x-axis and the Bloch
sphere. The state
$|{-}\rangle=\dfrac{1}{\sqrt{2}}|{0}\rangle-\dfrac{1}{\sqrt{2}}|{1}\rangle$
corresponds to the intersection point of the negative x-axis and the sphere.
The intersection points of the y-axis and the sphere are the states
$\dfrac{1}{\sqrt{2}}|{0}\rangle\pm\mathrm{i}\dfrac{1}{\sqrt{2}}|{1}\rangle$.
The basis formed by $\\{|{+}\rangle,|{-}\rangle\\}$ is referred to as Hadamard
basis.

Figure 2. Q-sphere for a 4-qubit system. The represented state is the uniform
superposition of all possible states of the 4-qubit system.

The Bloch sphere can be generalized to $n$-qubit systems and, in such a case,
it is named Q-sphere. Concerning multi-qubit systems, the states
$|{0}\rangle^{\otimes n}$ and $|{1}\rangle^{\otimes n}$ sit at the north and
south pole, respectively, analogously to the single-qubit case. All the other
states are placed along parallels with an increasing number of 1’s from top to
bottom. For example, in Figure 2, we report the Q-sphere for a 4-qubit system
in the uniform superposition of all the possible states. Specifically, the
size of the colored circles represents the probability amplitude for each
state, which is the same for all of them, while the color represents the
phase. Finally, we notice that the states $|{0000}\rangle$ and
$|{1111}\rangle$ sit at the north and south pole while all the other states
are distributed along parallels grouped by the same number of 1’s (increasing
from top to bottom), as mentioned above.

###  3.2. Physical Realization

Since the qubit represents the fundamental information carrier for a quantum
computer, its physical design and realization represented a milestone
concerning the outspread of such technologies. Albeit the topic is
fascinating, a comprehensive discussion about all the available technologies
and implementations of physical qubits is out of scope for this survey.
Nonetheless, we refer the curious reader to several specialized reviews that
are available in the literature: (Wendin, 2017; Gu et al., 2017; Gambetta et
al., 2017; Krantz et al., 2019; Kjaergaard et al., 2020). Instead, in what
follows, we just mention the most two currently successful technologies for
implementing qubits on real devices, namely, transmon (Peterer et al., 2015)
and flux (Harris et al., 2010a) qubits, both based on superconducting
technologies (Nakamura et al., 1999).

Among the various designs, currently, the flux and transmon qubits are the
most successful ones in terms of availability to end-users to develop custom
applications. The main difference between the two approaches stems from the
theoretical interpretation of the two-state system adopted to represent a
qubit. Indeed, in the first case, we talk about the spin interpretation while,
in the second case, we find the oscillator interpretation of a quantum bit.
Concerning transmon qubits, they are currently implemented in the QPUs of IBM
(Smith and Thornton, 2018; Barr et al., 2021) and Google (Arute et al., 2019),
while flux qubits are employed in the D-Wave’s (McGeoch, 2020) quantum
processors. At this point, it is interesting to compare the two types of QPUs.
Indeed, while the transmon-based chips made available to users by IBM (Vu,
2016) account for up to 65 transmon qubits, the D-Wave’s QPUs comprise up to
5000 qubits already. However, although the numbers would say that the flux-
based technology is currently winning the “quantum” race, it is not that
obvious. Especially since the computational capabilities of the two
technologies are quite different, and it is not fair to solely compare them
based on the number of qubits.

Concerning the different computations these QPUs can perform, we refer the
reader to the following section, in which we give more details about the
subject.

##  4\. Computational Models

In this section, we report a brief overview of the two main paradigms of
quantum computation: the Gate Model (GM), or Universal Quantum Computing, and
the Adiabatic Quantum Computation (AQC). A comprehensive analysis of the
mentioned approaches is out of scope for our work. However, in what follows,
we try to empower the reader with a basic grasp of those two types of
computations.

###  4.1. Gate Model

Perhaps the first proposal of a quantum model of computation dates back to
1985 from the physical interpretation of the Church-Turing hypothesis
(Deutsch, 1985).

At the heart of the GM, there is the concept of circuit model, i.e., a
sequence of building blocks that realize elementary operations. Such building
blocks are called gates. Thus, a gate encodes a well-controlled operation
acting on a single qubit or, in general, on a subset of qubits (Nielsen et
al., 2002; Preskill, 2018) in a given system. When acting on more than one
qubit, these gates can give raise to the quantum phenomenon of entanglement
among qubits which establishes a strong correlation among them.

As a direct consequence of the postulates of quantum mechanics (subsection
A.2), quantum gates are represented by unitary operators $\hat{U}$, i.e.,
$\hat{U}^{\dagger}\hat{U}=\hat{I}$ (Barenco et al., 1995; Nielsen et al.,
2002). Such a property automatically translates into saying that all the
quantum gates must be reversible, unlike classical logic gates. However, there
is an exception to such a rule. Indeed, measurements are the only
transformations on qubits that are allowed not to be reversible.

As mentioned, gates are unitary operators. As such, they can be represented in
different ways. Although it might be easier to formalize them as matrices,
typically the Dirac notation (subsection A.1), or the outer product among
state vector, is leveraged:

(12) $U=\begin{bmatrix}u_{00}&\cdots&u_{0({2^{n}-1})}\\\
\vdots&\ddots&\vdots\\\
u_{({2^{n}-1})0}&\cdots&u_{({2^{n}-1})({2^{n}-1})}\end{bmatrix}=\sum_{i=0}^{2^{n}-1}\sum_{j=0}^{2^{n}-1}u_{ij}|{i}\rangle\langle{j}|$

where $\\{|{i}\rangle\\}_{i=0,\dots,2^{n}-1}$ is the currently used basis.
Hence, in the simplest case of a single-qubit gate, it is represented by a
$2\times 2$ unitary matrix whose coordinates are completely specified by its
action on the basis states. More formally, single-qubit gates describe
transformations that belong to the Lie group of $2\times 2$ unitary matrices
with determinant 1, called special unitary group of degree 2 ($SU(2)$)
(Barenco et al., 1995).

A particularly useful set of one-qubit gates are the Pauli gates (defined in
subsection 4.1) that, together with the Identity operator, span the vector
space formed by all one-qubit unitary operators. In other words, any one-qubit
gate can be expressed as a linear combination of the Pauli gates. It is worth
mentioning that the Pauli gates $\hat{\sigma}_{x}$, $\hat{\sigma}_{y}$, and
$\hat{\sigma}_{z}$ corresponds to rotations around the $x$-, $y$\- and
$z$-axes of the Bloch sphere, respectively. As an example, the
$\hat{\sigma}_{x}$ matrix represents an operation called the “bit flip”, or
NOT gate, which maps the $|{0}\rangle$ to $|{1}\rangle$ and vice versa, in the
computational basis:

(13) $\hat{\sigma}_{x}|{0}\rangle=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}|{0}\rangle=\left(|{0}\rangle\langle{1}|+|{1}\rangle\langle{0}|\right)|{0}\rangle=|{0}\rangle\langle{1}|0\rangle+|{1}\rangle\langle{0}|0\rangle=|{1}\rangle$

Interestingly, we can notice that the operation in Equation 13 resembles the
NOT gate in classical computations.

Apart from the single-qubit gates, there are unitaries that involve two or
more qubits. Perhaps, the most famous ones are the Controlled-NOT (CNOT) and
Toffoli gates. We report in subsection 4.1 and subsection 4.1 the explanation
and formulation of the mentioned single- and multi-qubit gates.

Table 3. Basic one-qubit gates: Notations typically used in literature, the
corresponding matrices with respect to the basis
$\\{|{0}\rangle,|{1}\rangle\\}$, the action on a quantum state, and the
corresponding action on the spherical coordinates in the Bloch sphere
representation.
$\footnotesize\begin{tabular}[]{p{0.05\columnwidth}cp{0.06\columnwidth}p{0.1\columnwidth}p{0.21\columnwidth}p{0.37\columnwidth}}\hline\cr\hline\cr{Name}&{{Symbols}}&{{Circuit}}&{Matrix}&{Action
on $|{\psi}\rangle=\alpha|{0}\rangle+\beta|{1}\rangle$}&{Action on coordinates
$(\theta,\varphi)$ of the Bloch sphere representation}\\\ \hline\cr
Identity&{$I$}&{\Qcircuit@C=1em @R=.7em {& \gate{\,I\,} &\qw}}
&$\begin{bmatrix}\,\,1&0\,\,\\\
\,\,0&1\,\,\end{bmatrix}$&$I|{\psi}\rangle=|{\psi}\rangle$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}$I(\theta,\varphi)=(\theta,\varphi)$\end{tabular}}\hbox{}\hfill}}\\\
\hline\cr\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}Pauli-X\\\
({bit flip},\\\ {NOT})\end{tabular}}\hbox{}\hfill}}&$X$,
$\hat{\sigma}_{x}$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}{\Qcircuit@C=1em
@R=.7em {& \gate{X} &\qw}} \\\ or\\\ {\Qcircuit@C=1em @R=.7em {& \targ&\qw}}
\end{tabular}}\hbox{}\hfill}}&$\begin{bmatrix}\,\,0&1\,\,\\\
\,\,1&0\,\,\end{bmatrix}$&$X|{\psi}\rangle=\beta|{0}\rangle+\alpha|{1}\rangle$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}$X(\theta,\varphi)=(\pi-\theta,2\pi-\varphi)$\\\
{rotation around the $x$-axis by $\pi$
radians}\end{tabular}}\hbox{}\hfill}}\\\ \hline\cr Pauli-Y&$Y$,
$\hat{\sigma}_{y}$&{\Qcircuit@C=1em @R=.7em {& \gate{Y} &\qw}}
&$\begin{bmatrix}0&-\mathrm{i}\\\
\mathrm{i}&0\end{bmatrix}$&$Y|{\psi}\rangle=-\mathrm{i}\beta|{0}\rangle+\mathrm{i}\alpha|{1}\rangle$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}$Y(\theta,\varphi)=(\pi-\theta,\pi-\varphi\,(\text{mod
}(2\pi))$\\\ {rotation around the $y$-axis by $\pi$
radians}\end{tabular}}\hbox{}\hfill}}\\\
\hline\cr\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}Pauli-Z\\\
({phase flip})\end{tabular}}\hbox{}\hfill}}&$Z$,
$\hat{\sigma}_{z}$&{\Qcircuit@C=1em @R=.7em {& \gate{Z} &\qw}}
&$\begin{bmatrix}1&0\\\
0&-1\end{bmatrix}$&$Z|{\psi}\rangle=\alpha|{0}\rangle-\beta|{1}\rangle$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}$Z(\theta,\varphi)=(\theta,\varphi+\pi\,(\text{mod
}(2\pi))$\\\ {rotation around the $z$-axis by $\pi$
radians}\end{tabular}}\hbox{}\hfill}}\\\ \hline\cr
Phase&{$S$}&{\Qcircuit@C=1em @R=.7em {& \gate{S} &\qw}}
&$\begin{bmatrix}1&0\\\
0&\mathrm{i}\end{bmatrix}$&$S|{\psi}\rangle=\alpha|{0}\rangle+\mathrm{i}\beta|{1}\rangle$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}$S(\theta,\varphi)=(\theta,\varphi+\pi/2\,(\text{mod
}(2\pi))$\\\ {rotation around the $z$-axis by $\pi/2$
radians}\end{tabular}}\par\hbox{}\hfill}}\\\
\hline\cr$\pi/8$&{$T$}&{\Qcircuit@C=1em @R=.7em {& \gate{T} &\qw}}
&$\begin{bmatrix}1&0\\\
0&e^{\mathrm{i}\pi/4}\end{bmatrix}$&$T|{\psi}\rangle=\alpha|{0}\rangle+e^{\mathrm{i}\pi/4}\beta|{1}\rangle$&\noindent\hbox{}\hfill{{\hbox{\begin{tabular}[c]{@{}c@{}}$T(\theta,\varphi)=(\theta,\varphi+\pi/4\,(\text{mod
}(2\pi))$\\\ {rotation around the $z$-axis by $\pi/4$
radians}\end{tabular}}\hbox{}\hfill}}\\\ \hline\cr
Hadamard&{$H$}&{\Qcircuit@C=1em @R=.7em {& \gate{H} &\qw}}
&$\dfrac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\
1&-1\end{bmatrix}$&$H|{\psi}\rangle=\dfrac{\alpha+\beta}{\sqrt{2}}|{0}\rangle+\dfrac{\alpha-\beta}{\sqrt{2}}|{1}\rangle$&$H(\theta,\varphi)=\begin{cases}(\varphi,\frac{3}{2}\pi)\quad\text{if}\,\,\theta=\frac{\pi}{2},\,0\leq\varphi\leq\pi\\\
(2\pi-\varphi,\frac{\pi}{2})\quad\text{if}\,\,\theta=\frac{\pi}{2},\,\pi<\varphi<2\pi\\\
\left(\cos^{-1}(\sin\theta\cos\varphi),\cos^{-1}\left(\frac{\cos\theta}{\sin(\cos^{-1}(\sin\theta\cos\varphi))}\right)\right)\\\
\qquad\qquad\qquad\qquad\qquad\qquad\quad\text{otherwise}\end{cases}$
\par\par{rotation around the y-axis by $\pi/2$ radians} {followed by a
rotation about the $x$-axis by} { $\pi$ radians}\\\ \hline\cr\hline\cr $$
\par\end{table} \par\begin{table}[tbp] \@@toccaption{{\lx@tag[
]{{4}}{Frequently used multi-qubit gates.}}}\@@caption{{\lx@tag[. ]{{Table
4}}{Frequently used multi-qubit gates.}}}
$$\centering\footnotesize\begin{tabular}[]{p{0.12\columnwidth}p{0.06\columnwidth}p{0.13\columnwidth}p{0.25\columnwidth}
p{0.30\columnwidth}}\hline\cr\hline\cr{Name}&{Symbol}&{Circuit}&{Matrix
representation}&{Action}\\\ \hline\cr Controlled-
NOT&{$CNOT$}&$\quad\qquad{\Qcircuit<EMAIL_ADDRESS>\lstick{|{\gamma}\rangle}&\targ&\qw}}$&$\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&0&1\\\ 0&0&1&0\\\
\end{bmatrix}$&$CNOT\left(|{\psi}\rangle\otimes|{\gamma}\rangle\right)=|{\psi}\rangle\otimes|{\psi\,\text{{XOR}}\,\gamma}\rangle$\\\
\hline\cr
SWAP&&$\quad\qquad{\Qcircuit<EMAIL_ADDRESS>\lstick{|{\gamma}\rangle}&\qw&\link{-1}{-1}&\rstick{|{\psi}\rangle}
\qw}}$&$\begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
\end{bmatrix}$&Itswapstwoqubits\\\ \hline\cr
Toffoli&$CCNOT$&$\quad\qquad{\Qcircuit<EMAIL_ADDRESS>\lstick{|{\delta}\rangle}&\ctrl{1}&\qw\\\
\lstick{|{\gamma}\rangle}&\targ&\qw\\\ } $&$\begin{bmatrix}1 &0 &0 &0 &0 &0 &0
&0 \\\ 0 &1 &0 &0 &0 &0 &0 &0 \\\ 0 &0 &1 &0 &0 &0 &0 &0 \\\ 0 &0 &0 &1 &0 &0
&0 &0 \\\ 0 &0 &0 &0 &1 &0 &0 &0 \\\ 0 &0 &0 &0 &0 &1 &0 &0 \\\ 0 &0 &0 &0 &0
&0 &0 &1 \\\ 0 &0 &0 &0 &0 &0 &1 &0 \\\ \end{bmatrix}$&$
\begin{matrix}CCNOT\left(|{\psi}\rangle \otimes|{\gamma}\rangle
\otimes|{\delta}\rangle\right) \\\ \qquad\qquad= |{\psi}\rangle
\otimes|{\gamma}\rangle \otimes|{ (\psi\, \text{{AND}}\, \gamma) \,
\text{{XOR}}\, \delta}\rangle \end{matrix}
$\par\par\end{tabular}\end{tabular}{\\\ }{\hline}{\hline}$$\end{table} \par It
is worth noting that many multi-qubit gates are designed to perform
``controlled'' operations, that is an operation is executed on a qubit, named
the {target} qubit, if another qubit (called {control} qubit) is in a specific
state. For example, the CNOT gate applies the NOT gate operation to the target
qubit only when the control one is in the state $|{1}\rangle$. It is
formalized as:
\begin{equation}CNOT(|{\psi}\rangle\otimes|{\gamma}\rangle)=|{\psi}\rangle\otimes|{\psi\
\texttt{XOR}\ \gamma}\rangle\end{equation} where $|{\psi}\rangle$ and
$|{\gamma}\rangle$ are the control and target qubit, respectively. \par An
interesting result coming from the GM paradigm is that not all gates are
``fundamental'' for computations. Indeed, as it happens in the classical case,
there is a set of quantum gates, named {universal}, that can be used to
approximate to arbitrary accuracy any quantum circuit\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{nielsen2002quantum}{\@@citephrase{,
}}{})}. The Hadamard (H), Controlled-NOT (CNOT), phase (S), and $\pi/8$ (T)
gates constitute a universal quantum computation set of gates. Although the
S-gate can be constructed from the T-gate, it is typically assumed as a
component of the universal set due to its large usage in fault-tolerant
circuit construction. \par As we mentioned above, a circuit is made of a
sequence of gates acting on a given set of qubits. To characterize a circuit,
two metrics are typically reported, namely, the {width} and the {depth}. The
first one refers to the number of qubits involved in the calculations, while
the second one represents the longest path in the circuit resembling the
largest number of operations applied to a given qubit from the beginning to
the end of the computations. In\leavevmode\nobreak\
\autoref{fig:gate_circuit}, we report an example of a circuit in which we
applied single- and two-qubit gates. Specifically, the circuit represents one
of the most famous algorithms in the scientific community called the Deutsch's
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid}{\@@citephrase{,
}}{})}, which determines if a given Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ is balanced or constant. \par\begin{figure}[tbh]
\centering\includegraphics[width=260.17464pt]{images/djozsa_gm.pdf}
\@@toccaption{{\lx@tag[ ]{{3}}{Quantum circuit implementing Deutsch's
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid,nielsen2002quantum}{\@@citephrase{,
}}{})}.}}}\@@caption{{\lx@tag[. ]{{Figure 3}}{Quantum circuit implementing
Deutsch's algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid,nielsen2002quantum}{\@@citephrase{,
}}{})}.}}} \@add@centering\end{figure} \par As we can see
from\leavevmode\nobreak\ \autoref{fig:gate_circuit}, a quantum circuit is
depicted as a set of qubits, represented by lines, to which the gates
(squares) are applied, and where the order from left to right represents the
flow of time. However, it is worth noting that there is not an actual ``flow''
of the qubits in a quantum device. Indeed, the state of qubits at each given
time represents the state of the QPU, while gates are the transformations
applied to them to change the device's status.
\par\par\par\@@numbered@section{subsection}{toc}{Adiabatic Quantum
Computation} \par In the previous section, we introduced the GM in which a
qubits' state is evolved by applying a series of gates on it. In such a
design, the time evolution is discretized since the different operations are
performed at subsequent time instants. Quite differently, the Adiabatic
approach to quantum computation\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2000quantum}{\@@citephrase{,
}}{})} leverages a time-continuous evolution of the qubits' state according to
the Schr{\"{o}}dinger equation\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schrodinger1926quantisierung}{\@@citephrase{,
}}{})}. Moreover, it does not require nor allow to apply transformations, such
as gates, directly on qubits. Rather, everything is encoded into a quantum
operator, called {Hamiltonian} ($\hat{H}$), that describes the forces to apply
to a given system of qubits to move it into the desired state over time.
However, it is possible to show that these two approaches are polynomially
equivalent\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2000quantum,aharonov2008adiabatic}{\@@citephrase{,
}}{})} by using the technique introduced in\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{lloyd1996universal}{\@@citephrase{,
}}{})}. Such a goal is reached by discretizing the evolution time interval and
applying the Trotter formula\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2000quantum}{\@@citephrase{,
}}{})} to each time segment. In what follows, we give for granted that the
reader knows what a Hamiltonian is or at least its definition in classical
mechanics. For our purposes, all that we need to consider is that $\hat{H}$
can be interpreted as the energy operator, in the sense that its eigenvectors
are the energy eigenstates, and its eigenvalues are the energies of the
corresponding eigenvectors. Hence, as it will become obvious from the
following discussion, in the AQC, any problem is recast as an energy
minimization one. The key ingredient of the AQC is that $\hat{H}$ is not
constant, rather it varies with time: $\hat{H}\rightarrow\hat{H}(t)$. The AQC
derives its name from the Adiabatic Theorem (AT)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{messiah1962quantum}{\@@citephrase{,
}}{})} which asserts how to follow the evolution of a system when $\hat{H}(t)$
slowly varies over time. Generally speaking, it guarantees that a quantum
system will stay near its instantaneous ground state ({i.e.\ }, its lowest-
energy state) if the Hamiltonian that governs its evolution varies enough
slowly\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{born1928beweis,farhi2001quantum,aharonov2004adiabatic}{\@@citephrase{,
}}{})}. More in detail, the system's dynamical evolution is governed by a
time-dependent Hamiltonian that interpolates between an initial and a final
Hamiltonians within a given time interval. For the formal definition and proof
of the AT, we refer the reader to\leavevmode\nobreak\
\autoref{appendix_adiabatic_theorem} in the appendix. Moreover, we refer the
reader to the comprehensive and fascinating review by\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{albash2018adiabatic}{\@@citephrase{,
}}{})} for a deep dive into the AQC. \par\par We now briefly report about what
is meant by a slowly enough varying Hamiltonian. As previously mentioned, AQC
exploits the continuous time-evolution of a qubits' system within a time
interval $[0,T]$, where $T$ represents the end of the adiabatic evolution.
Commonly, the varying Hamiltonian is expressed as a one-parameter function,
given by $\hat{H}(s)$ where $s=t/T\in[0,1]$. Note that the eigenvalues of
$\hat{H}(s)$, indicated as $\xi_{i}(s)$, represent different energy levels of
the system ordered with increasing values of $i\geq 0$ (e.g. the ground state
energy is $\xi_{0}(s)$). To ease the understanding of the concepts we indicate
the eigenstate for $\hat{H}(s)$ related to the energy eigenvalue $\xi_{i}(s)$
to as $|{\phi{{}_{i}}(s)}\rangle$, where we stressed the time dependence
through the parameter $s$. Therefore the instantaneous eigenstates for
$\hat{H}(s)$ are the states satisfying
$\hat{H}(s)|{\phi_{i}(s)}\rangle=\xi_{i}(s)|{\phi_{i}(s)}\rangle$ For example,
the ground state of $\hat{H}(s)$, that is $|{\phi_{0}(s)}\rangle$, is
characterized by
$\hat{H}(s)|{\phi_{0}(s)}\rangle=\xi_{0}(s)|{\phi_{0}(s)}\rangle$. Given such
definitions and restricting our interest to the ground state of $\hat{H}(s)$,
the adiabatic theorem ensures us that if it is guaranteed that the difference
among the ground and the first excited state energies, $\Delta=\underset{0\leq
s\leq 1}{\mathrm{min}}\big{(}\xi_{1}(s)-\xi_{0}(s)\big{)}$, remains large
enough throughout the entire adiabatic evolution, then the system is likely to
lie in the ground state of the instantaneous Hamiltonian. Specifically, such a
requirement directly affect the length of the adiabatic evolution $T$ since
$T\propto\Delta^{-2}$. \par\par As said at the beginning of the section,
$\hat{H}(s)$ is interpolated between an initial ($\hat{H}_{I}$) and a final
($\hat{H}_{P}$), also called the problem, Hamiltonians. Specifically, the
``problem'' operator encodes the solution to a given problem in such a way
that its ground state configuration, $|{\phi_{0}(s=1)}\rangle$, expresses the
solution to the optimization problem at hand. Concerning the AQC, the strategy
is first to prepare the qubits in the ground state of $\hat{H}_{I}$, and then
the operator is evolved towards $\hat{H}_{P}$ by following the so-called
adiabatic path $\hat{H}(s)=(1-s)\cdot\hat{H}_{I}+s\cdot\hat{H}_{P}$. From a
mathematical perspective, $\hat{H}_{I}$ and $\hat{H}_{P}$ can be defined in
terms of the Pauli-matrices. Concerning a system made by $n$-qubits, the
initial Hamiltonian can be defined as:
$\hat{H}_{I}=\sum_{i=0}^{n-1}\frac{1}{2}(1-\hat{\sigma}_{x}^{i})$ where
$\hat{\sigma}_{x}$ is the Pauli-$x$ operator. The ground state of
$\hat{H}_{I}$ is characterized by all qubits aligned with the $x$-axis, i.e.,
the state $|{+}\rangle^{\otimes
n}=\frac{1}{2^{n/2}}\sum_{z_{1}}\sum_{z_{2}}\cdots\sum_{z_{n}}|{z_{i}}\rangle^{\otimes
n}$, where $|{z_{i}}\rangle\in\\{|{0}\rangle,|{1}\rangle\\}$, which resembles
the uniform superposition of computational basis states. To obtain such a
state, one couples a magnetic field, called the transverse or disordering
field, in the $x$-direction to each quantum bit. The choice of such a shape
for $\hat{H}_{I}$ relates to specific symmetries that the operator must
satisfy to allow for the sought computations. For example, such a choice is
mandatory to avoid the so-called ``level crossing''\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2000quantum}{\@@citephrase{,
}}{})}. Moreover, $\hat{H}_{P}$ is typically expressed in terms of the
$\hat{\sigma}_{z}$ operator so that the final configuration of the qubit
system is represented by eigenvectors of $\hat{\sigma}_{z}$, i.e., each qubit
can be found either in the $|{0}\rangle$ or $|{1}\rangle$ state. Such a
configuration is nothing more than a classical sequence of bits. Thus, by
starting from an initial quantum superposition, the adiabatic process evolves
the state into a classical configuration which can then be read to return the
solution to the problem at hand. One of the first ``proof of concenpt'' to
show the effectiveness of such a computation model was first realized
in\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2001quantum}{\@@citephrase{,
}}{})} for solving instances of the satisfiability problem. Apart from such a
first example, many optimization problems can be recast as an energy
minimization problem, such as the Grover search algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grover1997quantum}{\@@citephrase{,
}}{})} for which the adiabatic approach offers a quadratic
speedup\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2000quantum,farhi9612026analog}{\@@citephrase{,
}}{})} over the classical formulation. We report in\leavevmode\nobreak\
\autoref{fig:adiabatic_circuit} a schematic representation of an adiabatic
path representing the Deutsch's algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid}{\@@citephrase{,
}}{})}. The reader might compare such an image with\leavevmode\nobreak\
\autoref{fig:gate_circuit} to notice the difference between the two designs.
\par\begin{figure}[tbph]
\centering\includegraphics[width=260.17464pt]{images/djozsa_aqc.pdf}
\@@toccaption{{\lx@tag[ ]{{4}}{Schematic adiabatic evolution for the Deutsch's
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid}{\@@citephrase{,
}}{})}.}}}\@@caption{{\lx@tag[. ]{{Figure 4}}{Schematic adiabatic evolution
for the Deutsch's algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid}{\@@citephrase{,
}}{})}.}}} \@add@centering\end{figure}
\par\@@numbered@section{section}{toc}{The Quest for Quantum Supremacy} \par
The first claim about an attainable advantage with a hypothetic quantum
computer upon a classical one is attributed to Feynmann\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{feynman1982simulating}{\@@citephrase{,
}}{})}. However, at that time, such an idea concerned quantum simulations of
physical systems rather than universal computations. Indeed, considering the
simulation of a dynamical system characterized by $N=2^{d}$ degree of
freedoms, one can immediately see that a classical simulation living in a
$2^{d}$-dimensional Hilbert space requires resources that grow exponentially
with the problem size, while only polynomially if using a quantum
device\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{lloyd1996universal}{\@@citephrase{,
}}{})}. \par However, soon after, researchers started to think about gaining
an advantage over generic classical computations by leveraging quantum
effects. Thus, the concepts of ``quantum advantage'' (or ``quantum speedup'')
and ``quantum supremacy''\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{preskill2012quantum,harrow2017quantum}{\@@citephrase{,
}}{})} appeared in the literature. Although both terms refer to the same
principle, loosely speaking, one can distinguish among them as follows. The
first one typically refers to the ability of a quantum computer to perform a
given computation faster than a classical one. Instead, the last one assesses
that a quantum computer can find solutions to the problem at hand that no
classical computer will be ever able to solve (or at least won't be able in a
reasonable amount of time). Thus, even though both terms express the same
principle, sometimes they are used with slightly different meanings. \par One
of the most important phenomena for quantum computations is the entanglement,
which allows propagating the action on a qubit to others and compressing the
resource requirements to describe a given state. Highly entangled states
cannot be simulated efficiently by classical systems, representing one of the
fundamental proofs to assess the real advantage of quantum devices over
classical ones. Interestingly, assuming that it is true that there are
computational tasks beyond any classical computer's capability that can be
solved with a universal quantum computer, then in that case, it could be
possible to refute the ``extended Church-Turing thesis''. As we mentioned
previously, concerning an algorithmic point of view, the size of the Hilbert
space grows exponentially for a classical algorithm while only polynomially in
the quantum case. Moreover, quantum phenomena such as entanglement,
superposition, and tunnelling, help to navigate such a vast space and should
allow for a quantum speedup\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{lloyd1996universal,abrams1999quantum,harrow2009quantum}{\@@citephrase{,
}}{})}. Concerning the GM, Deutsch\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1985quantum}{\@@citephrase{,
}}{})} was among the first ones to show that a quantum circuit can be built of
reversible quantum logic gates to compute any classical function $f$ defined
on $n$ bits. In 1992, the first example of quantum advantage in computation
was formalized in\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deutsch1992rapid}{\@@citephrase{,
}}{})} in which the authors showed that, for a given class of problems, a
quantum device required exponentially less time to solve them compared to any
deterministic classical approach. \par When talking about quantum advantage or
speedup, there are two algorithms that are typically cited: Grover's search
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grover1996fast,grover1997quantum}{\@@citephrase{,
}}{})} and Shor's factoring one\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{shor1994algorithms,shor1999polynomial}{\@@citephrase{,
}}{})}. However, there is a fundamental difference in the way they reach the
advantage. Indeed, while for the first one, the ``modest'' quadratic speedup
over the classical formulation is mathematically demonstrated, concerning the
second one, this is not the case. Specifically, all that can be said about the
Shor's algorithm is that it reaches an exponential speedup over the most
efficient classical analogous available today. However, nothing forbids that a
new classical formulation might reduce or even eliminate such a gap. \par
Generally speaking, there are several definitions of quantum speedup.
``Provable quantum speedup'' stems from the existence of a mathematical proof
that there is not any classical algorithm that can perform better than the
quantum one\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grover1997quantum,bennett1997strengths}{\@@citephrase{,
}}{})}. A different concept is expressed by the ``strong quantum
speedup''\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{papageorgiou2013measures}{\@@citephrase{,
}}{})} which considers the performance of the best classical algorithm. Shor's
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{shor1994algorithms,shor1999polynomial}{\@@citephrase{,
}}{})} is an instance of such a definition. Indeed, although classical
algorithms require super-polynomial cost in the number of digits, the proof of
an exponential lower bound for classical factorization has not been found yet.
Thus, one typically adopts the concept of quantum speedup by referring to the
case in which the comparison is raised among the best known classical
algorithm, which, however, might not the best possible one, and its quantum
counterpart. \par Another class of problems that is probed to prove and
harness a quantum advantage is the sampling problems'
class\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{harrow2017quantum}{\@@citephrase{,
}}{})}, such as: constant-depth circuits\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{terhal2002adaptive}{\@@citephrase{,
}}{})}, boson sampling\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{aaronson2011computational}{\@@citephrase{,
}}{})}, and random quantum circuits containing commuting and non-commuting
gates\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{shepherd2009temporally,bremner2011classical,boixo2018characterizing}{\@@citephrase{,
}}{})}. Such examples are somehow in between the factoring
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{shor1994algorithms}{\@@citephrase{,
}}{})} and analog quantum simulators\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{cirac2012goals,georgescu2014quantum,cheuk2016observation}{\@@citephrase{,
}}{})}. \par In\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{ronnow2014defining}{\@@citephrase{,
}}{})}, the authors performed experiments on a ``D-Wave Two'' quantum
annealer. As a benchmark, they tasked the QPU with finding the ground state of
a 2D planar graph of an Ising spin glass model, which is known to be an NP-
hard problem\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{barahona1982computational}{\@@citephrase{,
}}{})}. The authors compared the results from simulated
annealing\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kirkpatrick1983optimization}{\@@citephrase{,
}}{})}, simulated quantum annealing\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{santoro2002theory,martovnak2002quantum}{\@@citephrase{,
}}{})}, and the actual quantum device from D-Wave\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{harris2010experimental,johnson2010scalable,berkley2010scalable,johnson2011quantum}{\@@citephrase{,
}}{})}. From their experiments, they did not observe any evidence for a
genuine quantum speedup. Recently, the Google company claimed to have reached
the quantum supremacy\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{arute2019quantum}{\@@citephrase{,
}}{})}. In their work, the authors proposed an ad-hoc experiment involving a
QPU containing 53 qubits and a circuit of depth equals to 20, and claimed that
a classical computer would have required thousands of years to simulate the
obtained results. However, several research groups immediately replied to such
a claim by showing how it was possible to simulate such a quantum computer in
just slightly more than two days\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{pednault2019leveraging}{\@@citephrase{,
}}{})} or even less\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{zhou2020limits}{\@@citephrase{,
}}{})}. Such deeply different results witnesses the difficulty that
researchers typically face when trying to estimate the real power of Noisy
Intermediate-Scale Quantum (NISQ) devices. Thus, imposing to scientists to be
more careful when announcing breakthroughs in this field being quantum
phenomena very hard to harness and sometimes to fully understand in all their
manifestations. \par We conclude this brief overview over the concept of
quantum supremacy and the various attempts to harness it by observing that,
despite the tremendous efforts that scientists are devoting to embrace the
quantum phenomena, such a goal is still far from being reached. Moreover, it
is clear that any claim about quantum supremacy must undertake a detailed
analysis based on the most recent achievements in classical simulation
algorithms\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bremner2017achieving,rahimi2016sufficient,kalai2014gaussian}{\@@citephrase{,
}}{})}. \par\@@numbered@section{section}{toc}{Quantum Learning} \par The
research on Quantum Neural Networks is a quest started more than twenty years
ago\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{altaisky2001quantum,faber2002quantum,schuld2014quest,schuld2015simulating}{\@@citephrase{,
}}{})} and it is still an open issue. Studies from Behrman et
al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{behrman1996quantum}{\@@citephrase{,
}}{})} and Toth et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{toth1996quantum}{\@@citephrase{,
}}{})} are examples of seminal works that introduced the concept of QNNs.
Behrman et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{behrman1996quantum}{\@@citephrase{,
}}{})} described a mathematical model based on quantum dot molecules and
showed by simulations that such a model was able to realize any classical
logic gate. Instead, Toth et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{toth1996quantum}{\@@citephrase{,
}}{})} proposed a more biologically inspired architecture, where quantum dots
were coupled to form a cellular structure in which near-neighbor connectivity
allowed the information to flow. The realization of a quantum analogous of an
Artificial Neural Network (ANN), as an algorithm able to combine the features
from both the classical and quantum worlds, is a long-standing
dream\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schuld2014quest}{\@@citephrase{,
}}{})} for the scientific community. In the classical realm, a feedforward ANN
is a universal approximator of continuous functions\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hornik1989multilayer}{\@@citephrase{,
}}{})}, thus a QNN should at least satisfy such a requirement. \par In what
follows, we focus especially on the GM paradigm since, currently, it is the
most widely adopted approach in such a context. However, we also report some
interesting formulations based on the AQC. First, we introduce the concept of
ANN and how it can benefit from a quantum formulation. Then, we describe two
techniques to train QNNs. Subsequently, we report several designs for QPs and
QNNs. \par Classically, an ANN is composed by a sequence of layers each of
which applies a specific mathematical transformation on its input and produces
an output that is taken as input by the subsequent layer in the network. To
enhance the representation power of these algorithms, typically the various
layers are interleaved by non-linear functions. Indeed, if only linear
operations are considered, one could reduce the entire network to a single
affine mapping. ANNs owe their name to the structure which is loosely inspired
by the brain structure. Moreover, still based on biological similarities, the
basic building block of ANNs is the artificial neuron, called
\emph{perceptron}, a computational model originally proposed by
Rosenblatt\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{rosenblatt1957perceptron}{\@@citephrase{,
}}{})}. These algorithms typically deal with large amounts of data aiming at
finding patterns to describe them by surfing the parameters' space. Thus, they
are perfect candidates to leverage the advantage of quantum phenomena that
allows to navigate more efficiently high dimensional spaces. From the
classical perspective, a perceptron is a computational model characterized by
a non-linear response to its input and is parametrized as:
\begin{equation}s_{i}=f\big{(}\mathbf{w}_{i}^{T}\mathbf{x}-b_{i}\big{)}=f\bigg{(}\sum_{j}w_{ij}x_{j}-b_{i}\bigg{)}\end{equation}
where $\mathbf{x}$ is the input, and $f$ is the non-linear activation
function, and $\mathbf{w}$ and $\mathbf{b}$ are the weight matrix and the bias
vector, respectively. Depending from the value of $s_{i}$, the perceptron is
said to be either active or at rest. Such an interpretation of a two-state
system, naturally brought to the researcher mind that perhaps a similarity
with a qubit-based system can be explored. \par Concerning the quantum realm,
in 1994, Lewenstein\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{lewenstein1994quantum}{\@@citephrase{,
}}{})} was among the first ones to propose a quantum-mechanical perceptron as
an ideal basic element that processes input quantum states into output states
through unitary transformations. Since then, several studies have been
conducted aiming at both formulating QNNs as made up of basic cells such as
QPs or as completely new computing architectures. Indeed, the design of QNNs
can be much different from that of classical ANNs meaning that the first ones
do not require to be made of several layers of QPs. For example, they can be
realized as variational circuits (see\leavevmode\nobreak\ \autoref{sec:qnn})
without relying on a direct implementation of a basic cell resembling the
quantum analog of a perceptron. \par A QNN by its own nature accepts quantum
states as input, hence classical data must be translated into quantum states,
a process called ``state preparation''. Researchers proposed several encoding
strategies to such an aim and the quantum amplitudes
encoding\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schuld2018supervised}{\@@citephrase{,
}}{})} is one of them. Amplitudes encoding associates quantum amplitudes with
real vectors with the only caveat that they must be normalized. Formally,
given a normalized vector $x\in\mathbb{R}^{d}$, where $d=2^{n}$ for an
$n$-qubit system, we have the following mapping:
\begin{equation}\mathbf{x}=\begin{bmatrix}\,\,x_{0}\,\,\\\ \,\,x_{1}\,\,\\\
\,\,\vdots\,\,\\\ \,\,x_{2^{n}-1}\,\,\end{bmatrix}\ \ \ \ \rightarrow\ \ \ \
|{x}\rangle=\dfrac{1}{\|\mathbf{x}\|}\sum_{i=0}^{2^{n}-1}x_{i}|{i}\rangle\end{equation}
where $|{i}\rangle$ represents the $i$-th computational base state. For
example, if $\mathbf{x}=[1,-1]$ then
$|{x}\rangle=(|{0}\rangle-|{1}\rangle)/\sqrt{2}$, upon normalization. Hence,
the main advantage of this encoding is that it only requires $\mathrm{log}Md$
qubits to encode a dataset of size $M$ and dimensionality
$d$\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schuld2018supervised}{\@@citephrase{,
}}{})}. \par\par\par\par\par\@@numbered@section{subsection}{toc}{Variational
Algorithms} \par Currently, the leading approach to the optimization of
quantum circuits\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{benedetti2019parameterized}{\@@citephrase{,
}}{})} exploits Variational Quantum Algorithms (VQA)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{peruzzo2014variational,mcclean2016theory,guerreschi2017practical,cerezo2020variational}{\@@citephrase{,
}}{})}, hybrid quantum-classical algorithms that leverage both quantum as well
as classical components. They owe their name to the fact that they are
inspired by the well known result from physics called the {Variational
Principle}, which provides an upper bound of the ground state's energy of a
quantum system. Generally speaking, the Variational Principle gives a recipe
to construct a {trial state} ({i.e.\ }, a quantum state parameterized by
learnable parameters) for optimization purposes. We refer the interested
reader to\leavevmode\nobreak\ \autoref{app:variational_principle} where we
report the formal definition and proof of the variational principle. \par From
a computer science point of view, one can formulate a VQA as follows. A hybrid
quantum-classical architecture comprising a set of quantum operations, termed
the {ansatz}, that are applied to the initial qubits state and produce a final
state, called {trial state}. The ansatz is characterized by a set of gates
controlled by some parameters $\\{\boldsymbol{\theta}_{i}\\}$ whose value is
modified with the help of a classical procedure, e.g., gradient descent.
Therefore, the design of such algorithms typically relies on three main
components. The first one is the ansatz, which sometimes includes the
embedding of classical data into a quantum state. Subsequently, one must
specify an objective function, whose value is used to drive the optimization
procedure, and finally a classical optimization procedure used to modify the
ansatz's parameters, $\\{\boldsymbol{\theta}_{i}\\}$, that defines the
transformations applied on qubits. Hence, it is clear that variational quantum
circuits represent the practical embodiment of the idea to train quantum
computers as we train neural networks. We report in\leavevmode\nobreak\
\autoref{fig:vqa} a schematic view of a VQA. \par\begin{figure}[tbph]
\centering\includegraphics[width=433.62pt]{images/variational_circuit.pdf}
\@@toccaption{{\lx@tag[ ]{{5}}{Schematic view of a
VQA.}}}\@@caption{{\lx@tag[. ]{{Figure 5}}{Schematic view of a VQA.}}}
\@add@centering\end{figure} \par The first application of such a method is the
Variational Quantum Eigensolver\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{peruzzo2014variational,kandala2017hardware,wang2019accelerated}{\@@citephrase{,
}}{})}. \par The Quantum Approximate Optimization Algorithm
(QAOA)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2014quantum}{\@@citephrase{,
}}{})} is a famous quantum algorithms that defines an ansatz to generate
approximate solutions to a given problems. It was initally proposed to solve
combinatorial optimization problem, and then it was generalized as a standard
ansatz\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hadfield2019quantum,cerezo2020variational}{\@@citephrase{,
}}{})}. QAOA finds the trial state by repeatedly applying unitary evolutions
according to a two-terms Hamiltonian\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2014quantum}{\@@citephrase{,
}}{})}, namely, $\hat{H}_{C}$ and $\hat{H}_{B}$. The first one, encodes the
classical cost function to be optimized and it is typically diagonal in the
computational basis, while the second one is the mixing Hamiltonian which
coherently moves the system through different configurations in the Hilbert
space seeking for the ground state of $\hat{H}_{C}$. Typically, $\hat{H}_{B}$
is a global transverse field, i.e.,
$\hat{H}_{B}=-\sum_{i}\hat{\sigma}_{x}^{i}$. Thus, given the problem
Hamiltonian $\hat{H}_{C}$, one can use QAOA to find its ground state by
applying the evolution operator $\hat{U}$:
\begin{equation}|{\psi(\boldsymbol{\beta},\boldsymbol{\gamma})}\rangle=\hat{U}(\boldsymbol{\beta},\boldsymbol{\gamma})|{\psi_{0}}\rangle=\prod_{i=0}^{p}e^{-i\beta_{i}\hat{H}_{B}}e^{-i\gamma_{i}\hat{H}_{C}}|{\psi_{0}}\rangle=e^{-i\beta_{p}\hat{H}_{B}}e^{-i\gamma_{p}\hat{H}_{C}}\cdots
e^{-i\beta_{1}\hat{H}_{B}}e^{-i\gamma_{1}\hat{H}_{C}}H^{\otimes
n}|{0}\rangle\end{equation} where the set of angles
$\\{\boldsymbol{\beta},\boldsymbol{\gamma}\\}$ are the parameters to be
optimized. Starting from a generic initial state, e.g., the uniform
superposition of the basis states $|{\psi_{0}}\rangle$, one can evolve it by
using\leavevmode\nobreak\ \autoref{eq:qaoa_ansatz} and obtain
$|{\psi(\boldsymbol{\beta},\boldsymbol{\gamma})}\rangle$. The parameters are
then adjusted such as to minimize the objective function expressed as:
\begin{equation}f(\boldsymbol{\beta},\boldsymbol{\gamma})=\langle{\psi(\boldsymbol{\beta},\boldsymbol{\gamma})}|\hat{H}_{C}|{\psi(\boldsymbol{\beta},\boldsymbol{\gamma})}\rangle=\langle{\psi_{0}}|\hat{U}^{\dagger}(\boldsymbol{\beta},\boldsymbol{\gamma})\hat{H}_{C}\hat{U}(\boldsymbol{\beta},\boldsymbol{\gamma})|{\psi_{0}}\rangle\end{equation}
\par A fundamental ingredient for QAOA is the parameter $p$
in\leavevmode\nobreak\ \autoref{eq:qaoa_ansatz} since it regulates the
precision of the approximate solution. Growing $p$ means reducing the
``distance'' from the optimal solution, however, for large $p$ decoherence
starts to play a significant role in the computation since the ansatz will
contain more gates. We refer the reader to the original
paper\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{farhi2014quantum}{\@@citephrase{,
}}{})} for a full discussion about the impact of the $p$ parameter and for
QAOA in general. \par In the next two sections, we move to the topics of QPs
and QNNs. Differently from what happens in classical learning approaches,
quantum ansatz are typically specialized to build perceptrons or to represent
an entire network. From such an observation, we first delve deep into the QPs
and then to full QNNs proposals.
\par\par\par\@@numbered@section{subsection}{toc}{Quantum Perceptron} \par The
implementation of the Quantum Perceptron is still an open quest. We know that
classically there is one reference implementation of such objects
(\autoref{eq:cls_perceptron}). However, due to due intrinsic differences among
the quantum hardware platforms currently available, different formulations
report advantages and disadvantages depending on the context in which they are
used. Thus, allowing for distinct implementations equally valid in the
respective fields of application. To ease the reader's understanding of the
current state-of-the-art concerning QPs, we report a summary
in\leavevmode\nobreak\ \autoref{tab:q_perceptron_summary}. It should be noted
that some approaches have been implemented on real QPUs (e.g., IBM Q 5) while
other methods have so far only been tested using numerical simulations. \par
\begin{table}[tbph] \par\centering\@@toccaption{{\lx@tag[ ]{{5}}{Summary
comparison among various quantum perceptron proposals. The symbol ``nr''
stands for ``not reported'' meaning that the authors did not explicit reported
that specific information. In the column ``Simulation'' we reported whether
the method was implemented on an actual QPU or tested using numerical
simulations only (reporting in brackets the library used when the information
was available).}}}\@@caption{{\lx@tag[. ]{{Table 5}}{Summary comparison among
various quantum perceptron proposals. The symbol ``nr'' stands for ``not
reported'' meaning that the authors did not explicit reported that specific
information. In the column ``Simulation'' we reported whether the method was
implemented on an actual QPU or tested using numerical simulations only
(reporting in brackets the library used when the information was
available).}}} \small\begin{threeparttable} \begin{tabular}[]{
>{\raggedright\arraybackslash}p{0.2\columnwidth}
>{\centering\arraybackslash}p{0.51\columnwidth}
>{\centering\arraybackslash}p{0.14\columnwidth}
>{\centering\arraybackslash}p{0.04\columnwidth} }\hline\cr\hline\cr
Work\@add@raggedright&Formulation\@add@centering&Implementation\@add@centering&Code\@add@centering\\\
\hline\cr\lx@intercol\hfil{Using the Gate Model}\hfil\lx@intercol\\\ \hline\cr
Cao et al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{cao2017quantum}{\@@citephrase{,
}}{})}\@add@raggedright&Circuit based on RUS (using a tangent-based non-linear
function). The input data are encoded into an N-qubit
state\@add@centering&{Simulation}\@add@centering&\char 55\@add@centering\\\ Hu
et al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hu2018towards}{\@@citephrase{,
}}{})}\@add@raggedright&Circuit based on RUS (using a sigmoid-based non-linear
function). The input data are encoded into an N-qubit
state.\@add@centering&IBM Q 5\@add@centering&\char 55\@add@centering\\\ Du et
al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{du2018implementable}{\@@citephrase{,
}}{})}\@add@raggedright&Variational quantum circuit based on a parametrized
Grover oracle learned with a classical optimization
approach.\@add@centering&{Simulation (pyQuil)}\@add@centering&\char
55\@add@centering\\\ Wiebe et al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{wiebe2018quantum}{\@@citephrase{,
}}{})}\@add@raggedright&Quantum search problem, based on the version space
interpretation of the perceptron, based on the Grover's
algorithm.\@add@centering&nr\@add@centering&\char 55\@add@centering\\\ Liu et
al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{liu2019unitary}{\@@citephrase{,
}}{})}\@add@raggedright&Given a supervised dataset, construct the weights'
matrix as the tensor product of input and target and then apply SVD to
it.\@add@centering&nr\@add@centering&\char 55\@add@centering\\\ Wiersema et
al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{wiersema2019implementing}{\@@citephrase{,
}}{})}\@add@raggedright&Qubit represented as a density matrix that describes
the classifier as a Boltzmann-like finite-temperature
distribution.\@add@centering&{Simulation (Tensorflow)}\@add@centering&\char
51$\,{}^{*}$\@add@centering\\\ Tacchino et al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{tacchino2019artificial}{\@@citephrase{,
}}{})}\@add@raggedright&Quantum variational circuit in which the
$m$-dimensional input datum is encoded into the $m$ coefficients of an N-qubit
state.\@add@centering&{IBM Q 5 ``Tenerife''}\@add@centering&\char
51$\,{}^{\circ}$\@add@centering\\\ \hline\cr\lx@intercol\hfil {Using the
Adiabatic Model}\hfil\lx@intercol\\\ \hline\cr Soloviev et al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{soloviev2018adiabatic}{\@@citephrase{,
}}{})}\@add@raggedright&Perceptrons and synapses are implemented as JJ-based
superconducting circuits.\@add@centering&nr\@add@centering&\char
55\@add@centering\\\ Torrontegui et al.
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{torrontegui2019unitary}{\@@citephrase{,
}}{})}\@add@raggedright&Two-level system (qubit) with a non-linear excitation
response to the input field.\@add@centering&{Simulation
(Tensorflow)}\@add@centering&\char 51$\,{}^{\bullet}$\@add@centering\\\
\hline\cr\hline\cr\end{tabular}
\begin{itemize}\footnotesize\par\itemize@item@[] {Code:} \char 55$\,$ the code
is not publicly available, \char 51$\,$ the code is available either on GitHub
($*$), upon request to the authors of the original work ($\circ$), or in the
supplementary material of the original work ($\bullet$). \par\end{itemize}
\end{threeparttable} \@add@centering\end{table} \par\par\par\par\par\par \par
Due to the linear, unitary, and non-dissipative nature of the quantum
transformations, one of the hardest challenges to design a QP resides in the
design and implementation of non-linear activation functions for quantum
computations. In 2017, Cao et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{cao2017quantum}{\@@citephrase{,
}}{})} proposed an approach based on the Repeat-Until-Success
(RUS)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{paetznick2014repeat,bocharov2015efficient}{\@@citephrase{,
}}{})} technique to synthesize quantum gates. As we mentioned previously, the
classical perceptron realizes the mapping
$g:\mathbb{R}^{n}\rightarrow\mathbb{R}$. Given an input vector
$\mathbf{x}=[x_{0},x_{1},\dots,x_{n-1}]^{T}$ it evaluates the non-linear
transformation $g(\mathbf{x})=f(\mathbf{w}^{T}\mathbf{x}+b)$ that, once
thresholded, defines the activation status of the perceptron. In such a
context, $f$ represents the non-linear operation whose output lies in $[l,u]$
where typically $l=-1$ or $0$ and $u=1$. Such an operation can be mapped to
the quantum realm by defining the perceptron as a qubit whose state is defined
as:
$\hat{R}_{y}(a\frac{\pi}{2}+\frac{\pi}{2})|{0}\rangle=\mathrm{cos}(a\frac{\pi}{4}+\frac{\pi}{4})|{0}\rangle+\mathrm{sin}(a\frac{\pi}{4}+\frac{\pi}{4})|{1}\rangle$,
where $a\in[-1,1]$ and $\hat{R}_{y}$ represents a rotation around the $y$-axis
as described by $\hat{\sigma}_{y}$. Note that as far as the extreme values of
$a$ are concerned, they recover a classical behavior being the system in the
state $|{0}\rangle$ or $|{1}\rangle$. Instead, in all other cases it behaves
quantum-mechanically. Input data are encoded into a state vector acting as the
control register over the ancilla qubits and the non-linearity is realized by
exploiting the RUS\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{paetznick2014repeat}{\@@citephrase{,
}}{})} design. Specifically, the authors implemented a sigmoid-like, tangent-
based, non-linear function: arctan(tan${}^{2}(x)$). Stemming from the same
approach, Hu et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hu2018towards}{\@@citephrase{,
}}{})} implemented a different RUS circuit to represent a sigmoid-based
activation function, $f(x)=\mathrm{arcsin}(\sqrt{\mathrm{sigmoid}(x)})$, thus
avoiding the drawbacks of using a periodic functions, such as the tangent.
Moreover, being based on the sigmoid, it accepted any real number as input
rather than in [0, $2\pi$] only. \par Wiebe et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{wiebe2018quantum}{\@@citephrase{,
}}{})} assumed a very interesting and completely different perspective.
Indeed, the authors reported that the only way to unveil a quantum advantage
is to formalize approaches that do not try to emulate classical algorithms in
the quantum world. Instead, a new point of view is needed. Thus, they based
their approach on the \emph{Version Space} interpretation of the perceptron
and the Grover's search algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grover1996fast,grover1997quantum}{\@@citephrase{,
}}{})}. Specifically, they exploited a general method referred to as amplitude
amplification\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{brassard2002quantum}{\@@citephrase{,
}}{})} for which Grover's algorithm represents a particular case. Using the
\emph{Version Space}, the authors posit the problem of training a perceptron
as a search problem ({i.e.\ }, search for the optimal parameters rather than
``learn'' them), hence fully exploiting the quantum advantage offered by the
amplitude amplification technique. \par Wiersema et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{wiersema2019implementing}{\@@citephrase{,
}}{})} exploited the formalism of density matrices to cast the perceptron
learning problem in terms of a quantum cross-entropy:
\begin{equation}\mathcal{L}_{q}=-\sum_{\mathbf{x}}q(\mathbf{x})\mathrm{Tr}\\{\eta_{\mathbf{x}}\ln\rho_{\mathbf{x}}\\}\end{equation}
where $q(\mathbf{x})$ is the empirical distribution of observing the datum
$\mathbf{x}$, $\eta_{\mathbf{x}}\equiv|{\Psi}\rangle\langle{\Psi}|$, with
$|{\Psi}\rangle=\sqrt{q(y|\mathbf{x})}|{0}\rangle+\sqrt{q(-y|\mathbf{x})}|{1}\rangle$,
is the density matrix associated with the distribution $q(y|\mathbf{x})$ of
observing the label $y\in\\{1,-1\\}$ given $\mathbf{x}$, while
$\rho_{\mathbf{x}}\equiv\rho(\mathbf{x},\mathbf{w};\mathbf{y})$ is the density
matrix associated to the model distribution $p(y|\mathbf{x};\mathbf{w})$. Note
that such a formulation resembles the classical cross-entropy objective:
$\mathcal{L}_{cl}=-\sum_{\mathbf{x}}q(\mathbf{x})\sum_{y}q(y|\mathbf{x})\ln
p(y|\mathbf{x};\mathbf{w})$. The matrix $\rho_{\mathbf{x}}$, which embodies
the perceptron's description, represents a finite-temperature description of a
qubit formulated as:
\begin{equation}\rho_{\mathbf{x}}=\exp{(-\beta\sum_{k}h^{k}\hat{\sigma}_{k})}/Z,\end{equation}
where the term $h^{k}\in\mathbb{R}$ is evaluated as
$\mathbf{w}^{k}\mathbf{x}$, and $\hat{\sigma}_{k}$ are the Pauli matrices.
Thus, there is a direct dependence from the classical input data of the
perceptron state. When the dataset $\\{\mathbf{x}\\}$ is linearly separable,
the convergence point is similar to the classical case. Instead, in the
presence of label noise, there is a contribution also from Pauli operators
other than $\hat{\sigma}_{z}$ that allows the perceptron to perform better
than its classical counterpart. \par Torrontegui et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{torrontegui2019unitary}{\@@citephrase{,
}}{})} based their approach on the similarity between the classical perceptron
and a single qubit interpreted as a two-levels system. Indeed, they
implemented the perceptron as a qubit, with sigmoid non-linear activation,
that undergoes a unitary transformation given by
\par\begin{equation}\hat{U}_{j}(\hat{x}_{j};f)=\exp{\left(i\
\arcsin\left(f(\hat{x}_{j})^{1/2}\right)\hat{\sigma}_{y}^{j}\right)}\ \ \ \
\mathrm{with}\ \ \ \
\hat{x}_{j}=\sum_{k<j}w_{jk}\hat{\sigma}_{z}^{k}-\theta_{j}\end{equation} \par
where $\hat{x}_{j}$ is the input field, $\hat{\sigma}_{y}$ and
$\hat{\sigma}_{z}$ are the Pauli matrices, and $f(\cdot)$ encodes the non-
linear activation function. The authors formalized the implementation of such
a model using an adiabatic process. Specifically, they proposed implementing
the evolution of the system as a single adiabatic path for an Ising model of
interacting spins. With such a definition, the authors proved that such a
perceptron acts as a universal approximator. Moreover, they report how it is
possible to treat such objects as the basic building block for large neural
networks. \par In Liu et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{liu2019unitary}{\@@citephrase{,
}}{})}, the authors proposed a quantum algorithm based on unitary weights,
suitable to implement a one-iteration learning approach. The weights' operator
is constructed as the tensor product
$\hat{w}=\sum_{j}|{y_{j}}\rangle\otimes\langle{x_{j}}|$, where
$\langle{x_{j}}|$ represents the conjugate transpose matrix of a training
input and $|{y_{j}}\rangle$ is the desired output. The Singular Value
Decomposition procedure is then applied to $\hat{w}$ to decompose it as the
product of unitary matrices. In their work, the authors showed how to
approximate several quantum gates with such an algorithm. A similar approach
is also exploited by Khan et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{khan2020derivative}{\@@citephrase{,
}}{})}. \par Du et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{du2018implementable}{\@@citephrase{,
}}{})} proposed a variational QP implementing a parametrized oracle for a
Grover-like search algorithm. The parametrized quantum circuit is used to
learn features from the input dataset, and a classical optimization algorithm
guides the parameters update. \par Differently from the previously introduced
approaches, Soloviev et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{soloviev2018adiabatic}{\@@citephrase{,
}}{})} reported a discussion about how to exploit superconducting circuits
equipped with Josephson junctions\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{josephson1962possible,josephson1974discovery}{\@@citephrase{,
}}{})} to physically realize perceptrons and synapses to build up a neural
network. Specifically, the authors exploited the operational principles of
adiabatic superconducting cells to implement multilayer perceptrons. In such a
design, the current-phase relation is used to implement the non-linear
response, while the input to the system is supplied as magnetic fluxes to
which the circuits, operating at a few kelvins, couple. \par Finally, in 2019,
Tacchino et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{tacchino2019artificial}{\@@citephrase{,
}}{})} proposed a binary perceptron model that can be implemented on
NISQ\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{preskill2018quantum}{\@@citephrase{,
}}{})} devices. To reduce the resource demand of the algorithm, the authors
formalized a new procedure to generate multipartite entangled states based on
the so-called hypergraph states\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{rossi2013quantum,ghio2017multipartite}{\@@citephrase{,
}}{})}. Given the preparation state as $|{0}\rangle^{\otimes N}$, the authors
evolved the state employing two unitaries, $\hat{U}_{i}$ and $\hat{U}_{w}$,
that encoded the input patterns, $\mathbf{i}$, and the weight vector,
$\mathbf{w}$. The computation performed by the perceptron was vein by the
inner product among the quantum states encoding the weights and the input,
i.e., $\langle{\psi_{w}}|{\psi_{i}}\rangle$. Finally, the non-linearity was
implemented as a measurement whose output represented the probability for the
system of being activated by the given input pattern. The authors successfully
proved that for any given weight vector, $\mathbf{w}$, the perceptron was able
to single out from the 16 possible input patterns only $\mathbf{i}=\mathbf{w}$
(with output probability of 1, i.e., the perfect activation of the neuron),
while all other inputs gave outputs smaller than 0.25.
\par\par\par\@@numbered@section{subsection}{toc}{Quantum Neural Networks} \par
Before delving deep into the most recent achievements in the field of QNNs, we
briefly mention a few seminal works that, although were published several
years ago, played a relevant role for the advancement of the discipline at
hand. One of the first proposals concerning a hybrid algorithm for QNNs, can
be dated back to 2000 with the work of Narayanan and
Menneer\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{narayanan2000quantum}{\@@citephrase{,
}}{})}. Using simulations, the authors compared the performance of a classical
artificial network in which from one experiment to the next, different
components were substituted with their quantum analogous. Interestingly, the
authors found that a fully quantum network did not report any tangible
advantage compared to a ``partially'' quantum one. Ventura and
Martinez\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{ventura2000quantum}{\@@citephrase{,
}}{})} proposed a quantum version of associative memories to harness the
exponential increase in storage capacity, originated from superposition
effects that quantum mechanics allows, concerning classical algorithms. To
their aim, the authors exploited a generalization of the Grover's
algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grover1996fast,grover1997quantum}{\@@citephrase{,
}}{})} able to fulfill the search and completion tasks. \par QVA is the most
commonly adopted choice to design quantum neural networks. In such a context,
the qubits' states are manipulated by unitaries characterized by a set of
parameters that are classically learned at training time. Finally, the value
of a given observable is accessed through a measurement that outputs a
discrete quantity. Although in what follows we focus on those algorithms, it
is worth mentioning that another class of quantum algorithms exploits
continuous variables, namely Continous-Variable (CV)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{killoran2019continuous}{\@@citephrase{,
}}{})} models. These models do not use qubits to store quantum information.
Instead, they exploit continuous degrees of freedom such as the amplitude of
the electromagnetic field, thus making them suited for photonic hardware. \par
Differently from the variational approach, a quantum generalization of the
classical feedforward neural networks was proposed by Wan et
al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{wan2017quantum}{\@@citephrase{,
}}{})}. The quantum neural network accounted for a reformulation of the
perceptron model by making each transformation reversible and unitary.
Although different from VQA, such networks have been shown, by employing
numerical simulation, to be trainable using gradient descent for a given
objective function. In such a case, the goal was to minimize the difference
between the quantum circuit's output and the expected one. A viable way to
physically realize such an architecture was by employing quantum photonics. As
an example, to prove the effectiveness of their approach, the authors proposed
a quantum autoencoder to compress two quantum states with high accuracy. \par
In Grant et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grant2018hierarchical}{\@@citephrase{,
}}{})}, the authors exploited the tensor networks' hierarchical structure to
represent quantum circuits. Specifically, they employed tree tensor
networks\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{shi2006classical}{\@@citephrase{,
}}{})} and the multi-scale entanglement renormalization ansatz
(MERA)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{vidal2008class}{\@@citephrase{,
}}{})} to implement a quantum classifier subsequently tested against the Iris,
MNIST, and a synthetic quantum datasets. The classifiers were implemented on
the ibmqx4 quantum computer and trained using the mean squared error loss
evaluated between the circuit's output and the expected one. Specifically,
concerning the first quantity, it represented the outcome of a measurement on
the target qubit:
$\langle\hat{M}_{\theta}(|{\psi}\rangle)\rangle=\langle{\psi}|\hat{U}_{\theta}^{\dagger}\hat{M}\hat{U}_{\theta}|{\psi}\rangle$.
To minimize the objective function, the authors employed the
Adam\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kingma2014adam}{\@@citephrase{,
}}{})} optimizer. As an example of hierarchical structure, the tree tensor
networks-inspired circuit begins by applying a set of two-qubit unitaries
among the nearest qubits. After each operation, one qubit is discarded, thus
halving the total number of qubits to the next layer. After a sequence of such
unitaries, the state of the final remaining qubit is measured. \par Classical
AutoEncoders are tasked with data reduction, i.e., given an $(n+k)$-bit
representation, the encoder generates a compressed $n$-bit datum with the same
discrimination power of the original input. Romero et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{romero2017quantum}{\@@citephrase{,
}}{})} proposed a Quantum AutoEncoder (QAE) as a solution to the compression
problem concerning quantum states represented by $(n+k)$-qubits. Specifically,
they were meant to facilitate quantum data compression especially concerning
quantum simulations. Such models should recognize patterns due to quantum
phenomena, such as superposition and entanglement, not accessible to classical
algorithms. In their paper, the authors tested their architecture to compress
ground states of the Hubbard model and molecular Hamiltonians. The task of a
QAE was then to get rid of a certain number of qubits, say $k$, while
maintaining the same amount of quantum information in the remaining ones.
Thus, the QAE must entangle qubits, and to such an aim, the authors exploited
unitary gates to build the variational circuit. As a cost function, QAE
leverages the expected fidelity\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{nielsen2002quantum}{\@@citephrase{,
}}{})}, $F(|{\psi_{i}}\rangle,\rho_{i}^{out})$, which quantifies the deviation
from the initial state $|{\psi_{i}}\rangle$ to the output one
$\rho_{i}^{out}$. The authors used a hybrid approach to train the model in
which the quantum device took care of the state preparation and the
measurement while the optimization procedure was carried out through classical
techniques. To train the circuit, the authors exploited two different
optimizers, namely, L-BFGS-B and Basin-Hopping. After training, the authors
proved that QAE could compress the ground state of the two-sites Hubbard model
from 4 qubits down to 1 with an error of below $10^{-4}$. It is relevant to
notice that such a compression allows moving from a space of size $2^{4}$ to
one of size 2. \par Inspired by the success of deep convolutional neural
networks (DCNN) on the task of pattern recognition\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{lecun1995convolutional,krizhevsky2012imagenet}{\@@citephrase{,
}}{})}, in Cong et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{cong2019quantum}{\@@citephrase{,
}}{})} a variational ansatz is proposed named Quantum Convolutional Neural
Networks (QCNN). As typically happens for variational circuits,
hyperparameters such as the number of gates are fixed, while the parameters
characterizing them are learned by classical optimization. The similarity
between DCNN and QCNN stems from the interpretation given to each ``layer'' of
the last one. However, it is fundamental not to confuse the concept of layer
between the classical and quantum architectures. Indeed, concerning the last
one, a layer is represented by a unitary operator applied to the data
register. With such a difference in mind, one can think of the structure of a
QCNN as a sequence of layers as follows. The first layer applies a single
quasilocal unitary, $\hat{U}_{\theta}$, in a translationally invariant manner
followed by a measurement on a subset of the input qubits, which resembles the
pooling operation. The outcome of such an operation determines the unitary
operation, $V_{\gamma}$, applied to the nearby qubits. These two operations
are applied a few times until the system is small enough. A final unitary,
$F_{\beta}$, is then applied to emulate the action of a fully connected layer.
Finally, the outcome of the QCNN is obtained by measuring a specific set of
output qubits. Such a model was applied successfully to solve the problem of
Quantum Phase Recognition (QPR), which aims at recognizing whether a given
input quantum state $\rho_{i}$ belongs to a particular quantum phase of
matter. Given a QCNN, the training set comprised training vectors
$\\{(|{\psi_{i}}\rangle,y_{i})|i=0,1,...N\\}$, where the binary labels $y_{i}$
identified a given input state vector. As objective, the authors exploited the
mean squared error between the label $y_{i}$ and the output from the QCNN.
Thus, the learning process consisted of initializing all the unitaries and
then optimizing them until convergence, for example, via gradient descent.
\par Graph Neural Networks\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{sperduti1997supervised}{\@@citephrase{,
}}{})} were introduced to exploit the geometrical structure in the input data
and accounted for the application of neural networks to acyclic graphs. Based
on a similar principle, a general ansatz was proposed by Verdon et
al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{verdon2019quantum}{\@@citephrase{,
}}{})}, named Quantum Graph Neural Networks (QGNN), consisting of a sequence
of $Q$ different Hamiltonian evolutions repeated $P$ times:
\begin{equation}\hat{U}({\boldsymbol{\eta};\boldsymbol{\theta}})=\prod_{p}^{P}\Big{[}\prod_{q}^{Q}e^{-i\eta_{pq}\hat{H}_{q}(\boldsymbol{\theta})}\Big{]}\end{equation}
where the $\boldsymbol{\eta}$ and $\boldsymbol{\theta}$ are the sets of
variational parameters, and the $\hat{H}_{q}(\boldsymbol{\theta})$ are the
Hamiltonians encoding the problem to be solved. The authors proposed different
variants for the general QGNN ansatz concerning the following tasks: learning
Hamiltonian dynamics of quantum systems, learning how to create multipartite
entanglement in a quantum network, unsupervised learning for spectral
clustering, and supervised learning for graph isomorphism classification.
Concerning the first task, they specialized the ansatz naming it Quantum Graph
Recurrent Neural Network (QGRNN) that tied the temporal parameters between
iterations, thus resembling the classical sequence networks in which the
parameters are shared among the various time step of the representation
evolution. To train such a model, the authors used the
Adam\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kingma2014adam}{\@@citephrase{,
}}{})} optimizer to minimize the average fidelity:
\begin{equation}1-\frac{1}{B}\sum_{j=1}^{B}|\langle{\psi_{T_{j}}}|\hat{U}^{j}(\Delta,\theta)|{\psi_{0}}\rangle|^{2}\end{equation}
where the
$|{\psi_{T}}\rangle=\hat{U}(T)|{\psi_{0}}\rangle=e^{-iT\hat{H}(\boldsymbol{\theta})}|{\psi_{0}}\rangle$
is the state evolved from $|{\psi_{0}}\rangle$, for a time $T$, after $P\sim
T/\Delta$ iterations with $\Delta$ being a hyperparameter determining the
Trotter step size, and the average is evaluated over a batch of size $B$.
\par\hfill\par
\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par\par
\hfill\hbox{}\par A slightly different approach is investigated in Henderson
et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{henderson2020quanvolutional}{\@@citephrase{,
}}{})}, where the authors proposed to empower a classical DCNN with a layer
containing filters implemented as quantum circuits. Such architecture was
named Quanvolutional Neural Networks (QVNN). Such a proposal stemmed from the
observation that, on the one side, machine learning algorithms benefit from
random non-linear features in terms of accuracy and training time, while on
the other, quantum circuits can model complex functional relationships. Each
quanvolutional layer was characterized by a certain number of filters designed
as a sequence of single- or single-controlled qubit gates. Specifically, each
circuit was built by considering each qubit as a node in a graph and assigning
what the authors named a ``connection probability'' between each qubit. A key
difference of such a formulation of QVNN compared to others is the lack of a
variational tuning of the circuits' parameters. QVNNs were tested against the
MNIST dataset using the QxBranch Quantum Computer Simulation System and,
unfortunately, the authors did not find any advantage over the classical
counterpart. Indeed, the performance of the QVNN was indistinguishable from
that of a random model. \par The Universal Approximation Theorem
(UAT)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{hornik1989multilayer}{\@@citephrase{,
}}{})} represents a milestone in the context of machine learning. Practically
speaking, it ensures that, a neural network comprising a single hidden layer
with enough units can approximate any continuous function. Somehow similar
results were reported by Perez et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{perez2020data}{\@@citephrase{,
}}{})}, in which the authors showed that it is possible to use a single-qubit
quantum circuit to implement a universal quantum classifier. Interestingly,
the authors presented an equivalence between UAT and the data re-uploading
strategy. Data re-uploading consists of uploading several times the inputs
while quantum computations proceed. In such a framework, data are uploaded by
single-qubit rotations followed by another set of unitaries representing the
evolution of the quantum state. These two operations can be compressed into
one by defining quantum layers with tunable parameters as:
$\hat{L}(i)=\hat{U}(\boldsymbol{\theta}_{i}+\mathbf{w}_{i}^{T}\mathbf{x})$,
where $\mathbf{x}$ represents the input data, $\mathbf{w}_{i}$ are weights
that plays a similar role as in artificial neural networks, while
$\boldsymbol{\theta}_{i}$ are a set of variational parameters. Although, at
first sight, it seems that there is no non-linearity in such a construction,
the authors reported that they come directly from the structure of the used
gates. The final state generated by the circuit is then function of all these
parameters: $|{\psi(\boldsymbol{\theta},\mathbf{w},\mathbf{x})}\rangle$. To
train their classifier, the authors employed the L-BFGS-B optimization
algorithm and used the average fidelity among the output state and the
expected one, $|{\psi}\rangle_{s}$. \par Schuld et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schuld2020circuit}{\@@citephrase{,
}}{})} proposed a low-depth variational circuit acting as a binary classifier.
Differently from previously mentioned approaches, here the models were applied
to classical data encoded into quantum states using the amplitude
encoding\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schuld2018supervised}{\@@citephrase{,
}}{})} technique. The circuit ansatz accounted for a set of single- and
single-controlled qubit gates divided into the so-called ``cyclic codes''.
Once the initial state is evolved, the first qubit is measured, and the
probability of finding it in the state $|{1}\rangle$ is used to infer the
input label. Specifically, such a probability is given by:
\begin{equation}p(q_{0}=1,x;\theta)=\sum_{k=2^{n-1}+1}^{2^{n}}|(\hat{U}_{\theta}|{\phi(x)}\rangle)_{k}|^{2}\end{equation}
where $\hat{U}_{\theta}$ is the parametrized unitary matrix describing the
model circuit, and $(\hat{U}_{\theta}|{\phi(x)}\rangle)_{k}$ is the $k$-th
entry of the result after the application of the operator $\hat{U}_{\theta}$
to $|{\phi(x)}\rangle$. The sum over the second half of the resulting vector
corresponds to the single-qubit measurement resulting in state 1.
Postprocessing adds the bias $b$ and thresholds to compute a binary
prediction: $\pi(x;\theta,b)=p(q_{0}=1,x;\theta)+b$. To estimate such a
probability, the circuit must be run several times. The overall operation is
equivalent to evaluate the expectation value of the $\hat{\sigma}_{z}$
operator acting on the first qubit of the evolved state:
$\mathbb{E}(\hat{\sigma}_{z})=\langle{\phi(x)}|\hat{U}_{\theta}^{\dagger}(\hat{\sigma}_{z}\otimes\mathbb{I}\otimes...\otimes\mathbb{I})\hat{U}_{\theta}|{\phi(x)}\rangle$.
To validate their ansatz, the authors' employed numerical simulation on
several UCI datasets, namely CANCER, SONAR, WINE, and SEMEION, and on the
MNIST dataset. While the first two are binary classification problems, the
last three are multiclass problems. In such last cases, the authors employed
the ``one-vs-all'' approach, thus allowing them to use their binary classifier
in these cases too. The author's approach is particularly relevant since it
was among the first ones to apply a quantum ansatz to solve machine learning
problems using variational circuits. \par Building on top
of\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{schuld2020circuit}{\@@citephrase{,
}}{})}, Macaluso et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{macaluso2020variational}{\@@citephrase{,
}}{})} are among the first ones to propose a learning framework for a quantum
Single Layer Perceptron (qSLP) that is implemented on an actual quantum
device, representing the quantum analogous of a single layer perceptron
containing two neurons. Thus, resembling the first attempt at a quantum neural
network. Specifically, the circuit computes linear operations in
superposition, each characterized by a different set of parameters. The
approach is based on three quantum registers, namely, control, data, and
temporary. At the end of the computation, the second one stores the results of
the two linear operations in superposition. The final response of the qSLP can
be obtained as the expected value of $\hat{\sigma}_{z}$ acting on the data
register. Notably, in such a work, a non-linear activation function is not
implemented in the quantum circuit. Instead, it is part of post-processing
operations. Finally, to train the qSLP, the authors used the Sum of Squared
Errors (SSE) loss, and the Nesterov\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{ruder2016overview}{\@@citephrase{,
}}{})} accelerated gradient method. \par Instead, Beer et
al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{beer2020training}{\@@citephrase{,
}}{})} formulated the QP as a unitary operator acting on $n$ input and $m$
output qubits. The idea was to stack such a kind of unitaries to form
``layers'' which emulate the behavior of a classical deep model. Thus,
concatenating more layers, one could obtain a design similar to a classical
networks. The overall QNN can be then described as follows:
$\mathcal{\hat{U}}=\prod_{l}^{L}\hat{U}^{l}$, where
$\hat{U}^{l}=\prod_{i}\hat{U}^{l}_{i}$ represents the set of unitaries of
layer $l$, i.e., the QPs of that specific layer. The QNN is applied to the
input state, $\rho^{\mathrm{in}}$, with the goal of producing a desired output
state, $\rho^{\mathrm{out}}$. To asses the performance of their approach, the
authors used numerical simulations with a QNN concerning input and output
spaces of 2 and 3 qubits. To train their model, they employed a gradient
descent technique, while as a loss function they employed the average fidelity
among the input and the output states. \par Jaderberg et
al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{jaderberg2021quantum}{\@@citephrase{,
}}{})} proposed a VQA to solve a classification task by employing a self-
supervised training approach\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{de1994learning}{\@@citephrase{,
}}{})}. They formulated the ansatz to be part of a hybrid encoder network
tested against the classification task on the first two classes, airplane and
automobile, of the CIFAR10 dataset. To train the model, the authors exploited
the contrastive learning procedure\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{oord2018representation,he2020momentum}{\@@citephrase{,
}}{})} applied to the representations generated by their models. As the
objective function, they used the normalized temperature-scaled cross entropy
loss\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{sohn2016improved}{\@@citephrase{,
}}{})}. As mentioned, the QNN was part of a hybrid network which first part
was classical. Specifically, the overall architecture began with a
ResNet-18\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{he2016deep}{\@@citephrase{, }}{})}
that compressed the features representation down to an eight-dimensional
vector such that to encoded it into the an entangled state comprising $W=8$
qubits. The input quantum state was given by:
$|{\psi}\rangle=\hat{R}_{x}(v^{i})^{\otimes_{i}^{W}}$, where $\hat{R}_{x}$ is
a rotation on the Bloch sphere as generated by the $\hat{\sigma}_{x}$ operator
and $v$ is the eight-dimensional features vector. Finally, to get the output
from the QNN, the authors measured the qubits state in the computational
basis. The authors tested their approach concerning quantum state vector
simulation and on real quantum devices. In both cases, they observed that the
hybrid architecture reported performance similar or higher than the full
classical implementation, thus giving an interesting hint about the capability
of such hybrid models applied to computer vision-related tasks. \par Transfer
learning is a very known and widely used technique in deep learning that
exploits pre-trained neural models on a different task. Interestingly, such an
approach can be ``hybridized'' by combining classical and quantum algorithms.
Indeed, Mari et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{mari2020transfer}{\@@citephrase{,
}}{})} considered three different scenarios for transfer learning, namely,
classical-to-quantum, quantum-to-classical, and quantum-to-quantum. In what
follows, we focus on the classical-to-quantum configuration. In such a case, a
ResNet-18\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{he2016deep}{\@@citephrase{, }}{})}
network trained on the ImageNet dataset\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{deng2009imagenet}{\@@citephrase{,
}}{})}, was used as a features extractor for the quantum circuit. The
variational ansatz was interpreted as made by three components:
$Q=\mathcal{M}\circ\mathcal{Q}\circ\mathcal{E}$. The first component,
$\mathcal{E}$, represents the quantum embedding of the classical features
vector into the Hilbert space depending on $\mathbf{x}$; the second one,
$\mathcal{Q}$, is a variational circuit of a given depth composing single and
two-qubit gates, while the $\mathcal{M}$ term represents the measurement on
the circuit's output. The authors trained such a circuit to classify images of
bees and ants utilizing the Adam\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kingma2014adam}{\@@citephrase{,
}}{})} optimizer and the cross-entropy loss. The authors assessed the
performance of their models through numerical simulations by using the
PennyLane framework and then implemented the quantum circuit on the ibmqx4 and
the Aspen-4-4Q-A quantum processors from IBM and Rigetti, respectively. The
authors' results demonstrated that there was already the possibility to
investigate efficient algorithms to process high-resolution images in the NISQ
era\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{preskill2018quantum}{\@@citephrase{,
}}{})} concerning the classical-to-quantum transfer learning scheme. Quantum
State Discrimination (QSD)\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{barnett2009quantum}{\@@citephrase{,
}}{})} requires the design of measurements to optimally identify the $\rho$
that represents the unknown state of a quantum device which is believed to
belong to a non-orthogonal set of states $\\{\rho_{i}\\}$. Such a capability
has a broad range of applications. For example, quantum state discrimination
by itself plays a crucial role in quantum information processing protocols and
is used in quantum cryptography\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{bennett1992quantum}{\@@citephrase{,
}}{})}, quantum cloning\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{duan1998probabilistic}{\@@citephrase{,
}}{})}, quantum state separation, and entanglement
concentration\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{barnett2009quantum}{\@@citephrase{,
}}{})}. Typically, distinguishing among non-orthogonal states is a challenging
task, and specialized measurements are required. An exciting approach for
solving such a problem was proposed by Chen et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{chen2021universal}{\@@citephrase{,
}}{})} that formalized a framework to learn to simulate the unknown structure
of the generalized quantum measurement, or Positive-Operator-Value-
Measure\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{nielsen2002quantum}{\@@citephrase{,
}}{})} (POVM). The circuit designed by the authors contained only a single-
qubit and CNOT gates, and the proper non-linearities were introduce by
measuring qubits states. Specifically, they assessed the performance of their
circuits by employing numerical simulation on classical machines and by using
the Adam\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kingma2014adam}{\@@citephrase{,
}}{})} optimizer to learn the circuit's parameters. However, differently from
the previously cited variational approaches, in the current case, the authors
aimed at maximizing their circuit's generalization performance given a
specific range of the parameters rather than looking through all the available
space. \par Finally, it is worth mentioning a few approaches based on an
optimization procedure which is different from the variational approaches we
have seen so far. For example, Silva et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{silva2010superposition,da2012classical}{\@@citephrase{,
}}{})} proposed a learning algorithm in which all the input patterns were
presented concurrently in superposition to the neural networks. Their model
was based on a quantum version of the RAM-based neural
networks\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{aleksander1966self}{\@@citephrase{,
}}{})}, termed quantum-RAM (q-RAM) node\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{de2009quantum}{\@@citephrase{,
}}{})}, a weightless network in which the learning procedure consisted upon
simply writing the proper output value in the corresponding look-up table
entries of the q-RAM node. The model was designed as a quantum circuit based
on the gate model paradigm. Moreover, the authors commented on the possibility
to stack mode nodes to form a deeper network. A fundamental step in the
training procedure accounted for the Grover's algorithm\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{grover1996fast,grover1997quantum}{\@@citephrase{,
}}{})} applied to the input until the desired output was returned. Another
interesting approach comes from Kerenidis et al.\leavevmode\nobreak\
\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{kerenidis2019quantum}{\@@citephrase{,
}}{})} that proposed to vectorize the convolution operations in a DCNN to
exploit linear-algebra subroutines to carry out the calculation exploiting
quantum phenomena. To their aim, the authors proposed algorithms both for the
forward and backward passes while training a QNN. Typically, data and
convolutional kernels are stored into QRAMs' registers that are called when
needed. To conclude the section and ease a comparison among the various
approaches we described so far, we give in\leavevmode\nobreak\
\autoref{tab:q_nn_summary} a summary of relevant properties of these quantum
neural networks. \par\par\par\@@numbered@section{subsubsection}{toc}{Final
Remarks} As we have seen, VQAs currently represent the most adopted approach
to QNNs. Perhaps, their capability to allow implementing learning circuits on
NISQ devices, and the similarities between the ansatz and the architecture of