the cost will be $N$. Grover realized that it was possible to perform a
similar operation but with a cost of $\sqrt{N}$ using a quantum algorithm.

To see it with a practical and very simplified example to clarify the concept,
if in a library there are 100 million books without any order, and a specific
book is required, in the worst case, it is necessary to read the title of 100
million books. This task is practically unfeasible for a single person. Using
Grover’s algorithm, it would be necessary to make an effort equivalent to
reading only 10,000 titles to find the right one, which, although tedious, is
perfectly feasible for one person. It is said that the quantum algorithm makes
an effort equivalent to reading 10,000 titles because there is no exact
equivalence between reading a title classically and having it in quantum
superposition, but the analogy of complexity can be established.

To construct his algorithm, Grover uses an oracle $f(x)$ given
$x\in\\{0,1,...,N-1\\}$. This oracle evaluates each $x$, each possible state
of the system (a title of a book in the previous example). Then, the oracle
can take two values, $f(x)=1$ if the $x$ value is the desired value, $f(x)=0$
in any other case. If this oracle is applied to a superposition of all
possible values $x$ defined in Eq. 2. The superposition is created, applying a
Hadamard gate to each qubit representing the state that initially is in the
state $\ket{\cdot}$. Being $N=2^{n}$, the oracle will only return 1 when it
matches the correct value, and the task will end.

$H^{\otimes n}\ket{\cdot}^{\otimes
n}=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\ket{x}.$ (2)

It seems that the algorithm is complete, and it will return 1 in the correct
state. Nevertheless, quantum computing is not so simple. Although it is true
that after executing the oracle once, the probability of the correct state
will go up, the difference between the probability of the correct state and
the rest of the states will be so small that when measuring the circuit, it
will not differentiate which state has the highest probability. This is a
common occurrence in quantum computing in many algorithms, and, therefore, it
is necessary to repeat a certain set of gates several times until the
probability of the correct state is sufficiently large with respect to the
others.

In the case of Grover’s algorithm, this increase in the probability of the
marked state is done by repeating two rotation operators. These two rotations
play with the phase of the states, making an inversion about the mean
probability. The first rotation marks the state in which $f(x)$ is 1 by
associating with it a phase opposite to that of the other states. The second
rotation, known as the diffusion operator, performs a rotation on the initial
state, converting the phase difference between the states into probability
amplitudes. In this way, the marked state will have a higher probability of
being measured.

The first rotation in Eq. 3, which is identified with the oracle, is
responsible for marking the state sought.

$R\ket{x}=(-1)^{f(x)}\ket{x}.$ (3)

The result of applying the operator $R$, oracle, to the superposition of
states in Eq. 2 is a 1 in all states, except in the searched state that is -1.
Then, the second rotation, the diffusion operator, has to be applied. The
rotation operator is

$U_{D}:=H^{\otimes n}(1-2\ket{0}\bra{0})H^{\otimes n}.$ (4)

This diffusion operator $U_{D}$ takes all possible states in superposition,
applying the Hadamard gate $H^{\otimes n}$ to the reflection on the average
value that was previously marked with a -1 $((1-2\ket{\cdot}\bra{0}))$. Using
a simplified example [65], given a state $\ket{\psi}$ with 4 possible
elements, each of them with a probability of $\frac{1}{4}$ and a coefficient,
amplitude of probability, of $\frac{1}{2}$.

$\ket{\psi}=[\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2}].$ (5)

If the marked element is in the second position, after applying the oracle in
Eq. 3, the resulting state is as follows:

$\ket{\psi}=[\frac{1}{2},-\frac{1}{2},\frac{1}{2},\frac{1}{2}].$ (6)

The mean of this state $\ket{\psi}$ is $\frac{1}{4}$. Applying equations 3 and
4 multiple times to $\psi$ following the Eq. 4, the resulting state is:

$\ket{\psi}=[0,1,0,0].$ (7)

The 1 is in the second position that corresponds to the searched element. It
is an explanatory example, very simplified, but it helps to understand the
mechanism used by Grover to its algorithm.

These reflection and diffusion operators went far beyond Grover’s algorithm
and have become really important in the quantum search algorithm community.
Beyond their application in non-indexed key search problems, they have been
applied to all those algorithms that needed to amplify the amplitude of a
particular state [66].

####  3.2 Quantum walks

The classical search algorithms explained in 2.1 had a common problem, the
need to search over almost all, if not all, nodes in the state space in order
to find the solution state. One of the algorithms explained, the random walks,
proposed to make a very fast but low quality exploration, so that they would
explore with a certain probability a region of the search space large enough
to find a solution of approximate quality to the optimal solution.

The main problem with random walks was that, although fast in execution, it
was very expensive for them to explore a significant part of the search space.
Moreover, this non-repetitive exploration was not guaranteed due to the
stochastic nature of the algorithm. For that reason, it was necessary for them
to execute a high number of repetitions to ensure the correct exploration of
the state space.

In the quantum case, the state space can be represented as a superposition of
states, applying each operation over the entire search space at once. This
solves the problem of the exploration limitations of random walks by switching
to their quantum counterparts, called quantum walks. In the case of quantum
walks, the difficulty does not lie in exploring all possible states, but it
becomes complicated to differentiate which state should be chosen because the
operations are applied over the entire superposition, not to individual
states.

Any type of walk is easy to imagine, thinking of a graph G with vertices
(states, S) and edges (transitions between states, T). This graph is traversed
by an agent that makes a path by randomly transiting S states. From a state s
to another state s’, it will transit with the probability defined in the edge
t. The agent can take a series of random W steps until it reaches a state that
will be considered final.

Ambainis’ initial proposal for quantum walks [36], taking advantage of the
Grover operator, demonstrated a quadratic advantage over classical random
walks. Another quantum walks model, introduced by Szegedy [67], is based on
graphs and represents the state space as a bipartite graph, as explained in
[68],

Szegedy defines the bipartite graph as two Hilbert spaces
$\mathcal{H}\otimes\mathcal{H}$, where each $\mathcal{H}$ represents the state
space $X$. These are two identical copies of the original space. Then, two
operators to transit around the graph are defined:

Update operator

$U\ket{j}\ket{\cdot}:=\ket{j}\sum_{i\in
X}\sqrt{W_{ji}}\ket{i}=\ket{j}\ket{p_{j}},$ (8)

and

$V\ket{\cdot}\ket{i}:=\sum_{j\in
X}\sqrt{W_{ij}}\ket{j}\ket{i}=\ket{p_{i}}\ket{i}.$ (9)

The matrix $W_{ij}$ can be seen as the weights of the edges T in the graph,
which represents the probability transition from $\ket{i}$ to $\ket{j}$. $U$
and $V$ are related as:

$SU=VS,$ (10)

where $S$ is the swap operation, to move from one $\mathcal{H}$ to the other.
Then, it is possible to define the subspaces $A$ and $B$.

$A:=span\\{\ket{x}\ket{\cdot}:x\in X\\},$ (11)

$B:=U^{\dagger}VSA=U^{\dagger}SUA.$ (12)

The projector applied to both subspaces:

$\Pi_{A}:=(1\otimes\ket{0}\bra{0}),$ (13)

$\Pi_{B}:=U^{\dagger}VS\Pi_{A}SV^{\dagger}U=U^{\dagger}SU\Pi_{A}U^{\dagger}SU.$
(14)

Using rotations similar to the Grover proposed, the quantum walk operator
defined by Szegedy is defined as:

$W=R_{B}R_{A}=U^{\dagger}SUR_{A}U^{\dagger}SUR_{A}.$ (15)

The quantum walk just explained is of the time-discrete quantum walk type.
This allows to execute each step of the quantum walk independently and to
adjust it to the reasoning model of the Markov agents.

As seen above, classical random walks were slow due to their random
exploration that could repeat multiple states, something that does not happen
with their quantum counterpart. Quantum walks are especially interesting in
those problems where a virtually exhaustive search of the state space has to
be performed. Just as Grover talked about an exhaustive search in a phone book
or in the library example, if a quantum walk has to be run on a problem that
needs almost all the nodes of a state space, it will find an advantage in
having the state space in superposition.

Yet, practical implementation limitations hinder the realization of
theoretical quantum walk proposals, particularly Szegedy’s idea of
representing the entire state space in a bipartite graph. Consequently,
certain operators within $W$ must be modified to achieve a more efficient
representation of the state space in the quantum walk.

Just as classical search serves as a basis for other algorithms, quantum
search based on quantum walks is used on numerous occasions, both to
accelerate classical algorithms in hybrid schemes and to build larger quantum
algorithms. In [69] is explained how to search for marked elements in a Markov
chain using the quantum walks proposed by Ambainis and Szegedy. In [70], a
quantum search based on quantum walks is used to accelerate the process of
exploiting a Reinforcement Learning algorithm.

As seen above, the difference between search & sample algorithms in quantum
computing is not as clear as it is classically. The same is true for quantum
walks. If the previous paragraph explained quantum walks applied to search,
they can also be applied to sampling processes. The best example in this line
is the work of Lemieux et al. [71] who modified the Szegedy operator by
replacing the bipartite graph by a coin and converted the $W$ operator of the
quantum walk into an operator to construct a quantum Metropolis-Hastings
algorithm, which is going to be explained in detail in the next section.

####  3.3 Quantum Metropolis-Hastings

In the work of Lemieux et al., they take the Szegedy quantum walk operator W
and replace the bipartite graph representation with a coin that is in a
superposition of 0 and 1. This coin is entagled with the state space, so that
changing the probability of the coin also changes the probability of the
states. This new quantum proposal of the M-H algorithm has three registers:

  * •

$\ket{\cdot}_{S}$ is the register containing all the qubits needed to
represent the entire state space.

  * •

$\ket{\cdot}_{M}$ is the register containing the move qubits.

  * •

$\ket{\cdot}_{C}$ is the register representing the coin, just one qubit.

Using these registers, the proposed operator is as follows:

$U_{W}=RV^{\dagger}B^{\dagger}FBV.$ (16)

The operators are:

  * •

Move preparation operator $V$: It creates the superposition in the register
$\ket{\cdot}_{M}$.

  * •

Coin operator $B$: Rotates the coin according to the criteria defined in Eq.
1, similar to the classical case. It loads the coin with a certain probability
and prepares it to the operator $F$.

  * •

Coin flip operator $F$: It flips the states $\ket{\cdot}_{S}$ according to the
probabilities in the coin, $\ket{\cdot}_{C}$.

  * •

Reflection operator $R$: It is a reflection in the registers
$\ket{\cdot}_{S}\ket{\cdot}_{C}$, derived from the Grover reflection operator.
It is responsible for increasing the probability of states marked by the coin
register $\ket{\cdot}_{C}$.

This operator $U_{W}$, in combination with the Markov models explained in
chapter 1, is used to construct the quantum version of a Metropolis-Hastings
algorithm. Similar to the graph representation, the agent that traverses the
graph G can be modeled as a Markov model in which the decision to move to one
or another of the possible states depends only on the state in which the agent
is. The probability transition of the agent from one state to the next is
codified in the rotation of the coin.

It is important to note that the operator proposed by Szegedy $W$ and the one
proposed by Lemieux et al. $U_{W}$ are not equivalent. The new operator
$U_{W}$ is a very smart implementation because it avoids the need to uncompute
the move register $\ket{\cdot}_{M}$ and the coin register $\ket{\cdot}_{C}$,
which is a very costly problem when the new move proposal is rejected.

This initial proposal of a quantum Metropolis Hastings was focused on a
specific problem, a one dimensional Ising model. This problem can be used as a
simplification of other more general optimization problems. However, as
demonstrated later, and as will be shown in the use cases, this version of
QM-H can be adapted in different ways to solve more complex optimization,
search & sample problems, such as protein folding [16], the N-Queen problem
[72], parameter estimation in gravitational waves [2], etc.

The main advantage of this QM-H algorithm is the possibility of using it in
combination with a heuristic function. This makes it possible to apply the
algorithm to almost any optimization problem. As seen above, in cases of
informed search, if one has some information about the problem domain it is
possible to guide the search to speed it up. In the case of quantum
algorithms, if the heuristic can be evaluated over all possible states, it
allows the algorithm to have much more information about the problem with
fewer operations.

The quantum M-H algorithm can be used for search problems because the agent
always looks for nodes that minimize energy, except for some random movement
with increasing energy to avoid local minima. In this way, the problem can be
encoded in such a way that the algorithm searches for the absolute minimum of
an energy function that can represent a minimum number of kilometers traveled,
minimum budget spent or minimum amount of fuel consumed.

The key to the search performance of the quantum Metropolis-Hastings is its
ability to sample the state space with high accuracy faster than the classical
algorithm. This sampling is based on knowing perfectly the probability of
acceptance of a change in the studied distribution, something that inherently
adjusts the quantum algorithm to the problem it is solving.

####  3.4 Other quantum S&S proposals

In addition to algorithms based on quantum walks, there are other quantum
computing proposals for S&S algorithms. Understanding the limitations of some
of these proposals, strengthens the capabilities of quantum walk-based
algorithms.

One of this proposal is quantum backtracking. Taking the example of an agent
moving through a maze, or the problem of loading packages into a truck, a
different type of search called backtracking is useful. The key point in
backtracking algorithms is that they perform an exhaustive search, but in an
intelligent way, avoiding exploring options that are already known not to lead
to a valid solution. This helps improve efficiency compared to brute force
approaches.

In this case, Montanaro [73] proposed to apply the techniques of quantum walks
to speed up backtracking algorithms. The main function of a backtracking
algorithm is that it represents the state space as if it were a tree. This
algorithm expands and explores branches with different states until a solution
state is found. The difference with other algorithms is the ability to
evaluate the nodes in such a way that it can know if all the successors, all
the branches, generated by that node are going to approach the solution or
not. In case it has found an unpromising branch to find the solution, it
returns, backtracking, to the root of that branch and takes a different one to
continue the search as shown in figure 14.

Figure 14:  Scheme that shows how a backtracking algorithm works. This
algorithm visits the nodes following a depth-first-search. If it detects that
the solution is not in the explored branch, it prunes the branch and
backtracks to a different branch. Extracted from [74].

The major disadvantage of quantum backtracking algorithms is intrinsic to
their advantage. These algorithms inherit the state space representation
limitations explained above for Szegedy quantum walks. They even add
additional operators that, while making the advantage greater, also add a high
complexity to bring them to a real implementation, either in simulator or
hardware, that can solve a practical problem. The limitation of quantum
backtracking remains the same as that of many quantum algorithms; it is still
difficult to prove its advantage because the very small quantum hardware
resources make its implementation impossible until several years from now.

A different paradigm from quantum walks for implementing QS&S algorithms is
quantum annealing. This proposal, which is almost at the same time an
algorithm and device, since the hardware where it is executed is only
dedicated to execute this type of algorithms, is inspired by the classical
technique of simulated annealing. These algorithms start with an easily
achievable quantum configuration and then, by gradually cooling the system,
seek to “anneal” the optimal solution. The main idea is to configure the
system in a quantum state according to the initial conditions of a problem,
and then let the system evolve until it reaches a minimum energy configuration
that corresponds to the solution of the problem [75].

To encode problems for quantum annealing, various methods can be employed. One
of the most common approaches is to formulate them as unconstrained quadratic
binary optimization (QUBO) problems. Such representations enable a binary
encoding of the variables and constraints of the problem. In this way, the
algorithm effectively solves a system of equations where it needs to maximize
or minimize certain values while adhering to specified constraints [76].

QUBO binary encoding can be quite rigid when it comes to representing complex
structures that may be necessary in an optimization problem. Therefore, it has
been relegated to a method of solving very specific problems. Nevertheless, it
remains an alternative to consider for addressing certain QS&S problems [77].
Scalability is another limitation, closely related to the lack of a formal
demonstration of its advantage over classical algorithms in large-scale
problems. Although quantum annealing tackles problems of great complexity for
classical algorithms, providing an advantage, the scalability of adiabatic
quantum hardware devices has proven to be insufficient [78]. This lack of
scalability eliminates the advantage for larger problems, leading to the
acknowledgment of quantum annealing’s importance within QS&S algorithms but
ruling it out as a research technique for algorithm construction and problem
resolution in this work.

A different perspective for QS&S started when researchers working on quantum
optimization algorithms were aware that executing a purely quantum algorithm
to solve an optimization problem faster than a classical one was tremendously
complex due to the slow evolution of hardware devices. Therefore, seeking a
middle point between complex purely quantum algorithms with significant
advantages but with questionable advantages, a new family of algorithms was
conceived. These algorithms combining classical and quantum technology are
known as quantum-inspired algorithms.

Within the quantum-inspired category, there are many types of algorithms:
quantum algorithms executed on classical hardware, classical algorithms
accelerated by small quantum hardware modules, algorithms that use quantum
methods but are implemented entirely classically, or algorithms that combine
quantum and classical modules, both hardware and software. This work
specifically focuses on hybrid algorithms.

Hybrid algorithms, the central focus of this work, are currently generating
high expectations to become the paradigm through which quantum computing
enters the industrial sector. Under the umbrella of this concept, there are
various algorithmic schemes, but the common thread is their modular nature,
which combines both classical and quantum modules.

Hybrid algorithms have different approaches, but the main ones are twofold. On
one hand, hybrid algorithms can be considered an end in themselves. They are
constructed following this paradigm because there will be operations where
quantum computing will never be faster than classical, and thus, it is always
better to combine both. In this approach, quantum processing units (QPUs) are
developed as processing modules that are added to classical supercomputers,
similar to RAM or GPU processors. On the other hand, hybrid algorithms can be
viewed as an intermediate step that must be taken because quantum devices are
not yet mature enough to support the entire quantum algorithm. As technology
develops, the classical modules of these hybrid algorithms may be phased out.

This work aligns more with the philosophy of the second approach, which is the
development of hybrid algorithms because quantum devices currently lack the
capacity to analyze the size of the problem intended for resolution. However,
the algorithms are designed with sufficient scalability so that once quantum
hardware becomes available, it will be possible to execute the entire
algorithm in a quantum manner.

Taking this intermediate step through classical-quantum hybrid computing is a
way to try to gain quantum advantages in optimization problems much earlier.
NISQ computers, specifically designed for such algorithms, are expected to be
available sooner than other paradigms of quantum computers like early fault-
tolerant computers. This implies the possibility of gaining an advantage in
certain problems in the medium term. However, large-scale quantum computers
capable of executing purely quantum algorithms are not expected until the long
term, without specifying a date.

In this first chapter on quantum search & sample, a hybrid algorithm will be
proposed that combines quantum walks technology to create a quantum
Metropolis-Hastings algorithm capable of solving optimization problems
strongly connected to industrial needs. In the following sections, various use
cases where the explained hybrid algorithm has been applied will be discussed.

###  4 Quantum Metropolis Solver (QMS)

F

ollowing the philosophy of hybrid algorithms as an intermediate step for
future fully quantum algorithms and looking for an algorithm that can be
executed in the short term in NISQ, the quantum Metropolis Solver (QMS)
algorithm is proposed. This algorithm follows the line of the Metropolis-
Hastings quantum algorithm explained in chapter 3 and modifies it to create a
software tool that can be executed following the universal computing paradigm.

As explained in the previous sections, optimization problems have always been
considered to be of great appeal for quantum algorithms. These problems are
complex for classical algorithms and, moreover, require almost exhaustive
searches. QMS seeks to solve optimization problems by making use of the
advantages of universal quantum computation of circuits. Therefore, the
designed tool is fully executable by code in both quantum simulators running
on classical hardware and purely quantum hardware following the circuit
paradigm.

####  4.1 Motivation

QMS design is strongly influenced by the types of QS&S algorithms explained in
chapter 3. It is an algorithm that combines search & sample techniques to
arrive at a solution, and is fully applicable to both search & sample
problems. To do this, QMS performs two operations iteratively, first sampling
the circuit by performing a step, similar to W in the Equation 16, and then
repeating these steps, W, a specified number of times until the probability of
measuring the correct state is sufficiently increased.

Since the core of the QMS tool is the QM-H algorithm, the quantum advantage of
this tool derives from this technique. Therefore, the main motivation to build
QMS has been to find an algorithm based on QM-H that would allow a real
implementation, keeping the same quantum advantage and that could solve a wide
range of QS&S problems, ultimately optimization problems.

Considering that one of the main motivations of this work and this thesis was
to create realistic and implementable QC algorithms, QMS has been implemented
and tested in the Python programming language and using the Qiskit quantum
computing library. In addition, the QMS code and its modifications to the use
cases have been published in public repositories on GitHub. Links can be found
in each of the releases.

By open-sourcing the code, another motivation behind this work has been
pursued, to enable any user to have an easy-to-use software tool that solves
optimization problems through quantum computing algorithms, providing a
straightforward and interpretable result. To run the code, it is only
necessary to provide a simple description of the problem, and QMS will return
the minimum/maximum energy configuration for their problem.

Finally, QMS has been designed with a completely modular philosophy, allowing
any software component to be modified or adapted to a specific use case.
Moreover, this promotes the hybrid model, as any component can be switched
from quantum to classical and vice versa. In the following sections, three use
cases for QMS are presented: quantum artificial intelligence, space
exploration, and quantum chemistry.

The idea behind these three diverse use cases is to demonstrate that QMS can
be applied to each of them and to an even broader range of optimization
problems. The only common characteristic among them is the need for their
fundamental operations to be quantum search & sample algorithms. Additionally,
there is an intention to open a new line of research, following the hypothesis
that delving deeper into these optimization algorithms is necessary through
universal computing and not dedicated hardware such as quantum annealing.

####  4.2 Methodology

QMS operates by providing a description of the problem to be solved and
specifying the precision in terms of the number of qubits with which the
states should be represented. The problem description consists of defining the
state space of the problem and the evaluation function to be applied to each
state, guiding the search towards the state of maximum or minimum energy.

Ideally, this problem description would be an input file that defines two
functions: one to generate states from an arbitrary state (inter-state
transition function) and one to calculate energies for any state (evaluation
function). However, considering the current state of quantum computing, QMS is
currently designed so that both functions are implemented directly in the
code. Depending on the use case, modifications are required to be made to the
QMS code to adapt it to the particular problem. This approach requires a
thorough understanding of the problem to be solved. It is also important to
realize that defining the problem using an input file with two functions does
not require additional research; it would simply imply that the transition and
evaluation functions would be executed in the quantum circuit, which implies a
high processing and storage capacity for a quantum computer that is not
currently available.

  * •

$\ket{\cdot}_{S}$: State register, representing the entire state space. This
register uses a binary encoding of a set of $v$ variables. Each variable has a
precision of $q$ qubits and therefore can represent $2^{q}$ states. In total,
the state space size represented by this state register is $2^{v\times q}$

  * •

$\ket{\cdot}_{M}$: Movement register, it is composed by two independent
registers, move id register $\ket{\cdot}_{move-id}$ that contains information
about which variable register is going to be modified and move value register
$\ket{\cdot}_{move-value}$ that contains if the modification of the variable
is going to be plus or minus 1.

  * •

$\ket{\cdot}_{C}$: Coin register, similar to that proposed by [71]. One qubit
to represent the coin.

  * •

$\ket{\cdot}_{A}$: Probability acceptance register, it is a register in which
the value energy associated to each state is loaded. It is used to load the
move acceptance probability on the coin.

These registers are used in a modified QM-H operator $U_{QMS}$ to fit the new
registers.

$U_{QMS}=RV^{\dagger}B^{\dagger}FBV.$ (17)

The operators that form $U_{QMS}$ are similar to those explained in chapter 3,
with differences in the implementations explained in publication 4.3.

An extra operator $E$, could be added. $E$ is the energy operator that loads
or calculate the energies associated to each state represented by
$\ket{\cdot}_{S}$. This operator can be used in two ways. The theoretical
approach is for QMS to be a fully quantum algorithm and calculate the energies
associated with each state in superposition without the need to measure the
states. This first case is the ideal, but as explained earlier, quantum
hardware is far from making this a reality. The second way to use this
operator follows the philosophy of hybrid algorithms. For this, a module is
designed in classical computing capable of calculating the energies of quantum
states. These energies are passed to the operator $E$, which reads and loads
them into the probability acceptance register $\ket{\cdot}_{A}$ using a
technique called QRAM [79, 80].

Another important aspect of QMS is its ability to be configured with different
hyperparameters to adapt it to the specific problem being executed. For
example, the number of times the operator $U_{QMS}$ is applied, the precision
to represent the probability acceptance register, or the beta parameter
($\beta$). Specifically, the $\beta$ parameter is one of the main
configuration hyperparameters of QMS, as it regulates the balance between
exploration and exploitation in the search. A low value of $\beta$ favors
exploration, while a high value favors exploitation. In practice, properly
adjusting these hyperparameters is crucial for achieving good results in
solving optimization problems.

$\beta$ is defined as $\frac{1}{T}$ being $T$ the effective (fictitious)
temperature of the system. This concept is similar to the simulated annealing
explained in subsection 3.4. The canonical use of $T$ is high temperature at
the beginning to focus on exploration and, progressively, reduce the
temperature to find the absolute minima/maxima.

QMS allows for modification of the temperature $T$ by adjusting $\beta$ in
each iteration. This enables the use of various annealing schedules, ranging
from a constant schedule with a fixed $\beta$ to an exponential reduction of
$\beta$ in each iteration, and including more gradual reductions with linear
or geometric schemes.

Another key aspect of the quantum software tool, QMS, is the comparison with
its classical counterpart, the M-H algorithm. For this purpose, a small module
has been implemented within QMS that enables the execution of the classical
algorithm on the same problem and under the same conditions. This allows
benchmarking the results of the quantum algorithm and assessing whether it
outperforms the classical one.

However, this comparison between classical and quantum is not straightforward.
The main issue is deciding which metric to compare. Comparing execution times
does not make sense because the quantum algorithm runs on a simulator on
classical hardware. Counting the number of gates does not make sense either
because quantum and classical gates are very different. Therefore, the metric
chosen for comparison is Time To Solution (TTS).

TTS is a metric explained in [71]. It is a figure of merit that assigns a
numerical value to the cost of executing a specific algorithm. In the case of
QMS, it returns a numerical value that allows the comparison of both
executions. TTS stands for time; therefore, the higher the TTS, the longer the
time to solution and the worse the performance. Thus, in the comparison, the
aim is to determine which algorithm has a lower TTS and, therefore, better
performance.

TTS is calculated following the formula:

$TTS(t):=t\frac{\log(1-\delta)}{\log(1-p(t))},$ (18)

where $t$ is the number of time steps, equivalent to $W$. $\delta$ is the
success probability, and $p(t)$ is the probability of hitting the ground state
after $t$ steps. Then the TTS is represented in a plot, shown in figure 15,
with quantum TTS on the y-axis and classical TTS on the x-axis. This plot is
divided in the diagonal by a dashed line, indicating the frontier between
classical and quantum TTS. This dashed line creates two triangles, the upper
triangle contains the points with low classical TTS and high quantum TTS,
which means classical advantage region. In the opposite, the lower triangle
contains values with low quantum TTS and high classical TTS, quantum advantage
region. Ideally, all points should be in the quantum advantage region.
Nevertheless, the quantum hardware is not ready yet for this situation. For
that reason, some points will be in the classical region and others will be in
the quantum advantage region. This makes necessary to represent the axis in
logarithmic scale and to make a scaling exponent analysis. Using a square mean
regression, it is possible to observe the tendency of the points. If the
exponent is lower to 1 means that, with more TTS, bigger sizes of problems,
all points will tend to be under the dashed line, so in the quantum advantage
region. It is important to understand this concept in order to interpret
correctly the result of the use cases.

Figure 15:  TTS comparison plot is divided by a red dashed line. This line
splits the plot in two triangles: the upper triangle contains points with low
classical TTS and high quantum TTS, which means classical advantage region. In
contrast, lower triangle contains points with low quantum TTS and high
classical TTS, which means quantum advantage region. Therefore, the desired
behavior is that all points fall into the lower triangle.

With the development and testing done on QMS, a behavior has been observed
that has been compared with other works. With small optimization problems, it
is not possible to gain quantum advantage because the execution of quantum
circuits requires a certain computational overhead. The quantum advantage is
expected to be observed with larger problem sizes.

In Figure 16, a plot with three different regions can be seen. The x-axis
represents the size of the problems, and the y-axis represents the time needed
to solve them. The three regions correspond to small, medium, and large
problems. This plot is a simplification of the results that have been observed
and compared with those of other authors. With small problems, classical
algorithms have better performance, lower execution time due to the
computational overhead of quantum circuits. This gap remains constant for a
certain problem size. When that gap starts to shrink, it is considered a
transition to medium-sized problems. In this new region of problems, the
constant computational overhead begins to have less impact on performance, and
the gap starts to close. In the last region, when equality is achieved between
the performance of quantum and classical algorithms, it is clear that the
trend for classical algorithms in complex optimization problems is to present
a cliff in performance. The time required by classical algorithms increases
exponentially. However, the expected performance of quantum algorithms grows
more steadily, entering regions of practical quantum advantage. Of course,
this figure is only an idealization of reality, but has many similarities with
what has been observed in the use cases that will be explained later.

Figure 16:  This figure represents three different sizes of problems solved by
QMS: small, medium and large. The boundaries of the three regions are
delimited by an inflection point in the ratio between quantum and classical
algorithm performance. Between the small and medium size region, the
inflection point is that the gap between quantum and classical starts to
narrow because the computational overhead is no longer so important. Between
the medium and large size region, the tipping point is that both algorithms
have similar performance and the quantum starts to be better off.

Regarding the scalability in the third region of Figure 16, which pertains to
large problems, two scenarios can be analyzed. First, if the number of states
is exceedingly high, and secondly, if the differences in the evaluation
function value between states are very low. In such cases, it becomes
necessary to apply a large number of $W$ operations.

In the first scenario, where a large number of states are involved in the
problem, thereby demanding a significant number of qubits to represent them,
the scalability of QMS is primarily determined by the number of qubits
required for the state representation. Other registers, such as those for the
coin, move value, and ancillas, either remain constant or increase
logarithmically with the number of qubits needed for state representation.
Therefore, the focus is primarily on examining how the number of qubits for
the state register grows. In QMS, this growth follows a polynomial pattern
concerning the number of variables required to represent the states,
multiplied by the number of qubits necessary to represent all possible values
of these variables.

If there are 100 variables and each variable is discretized using 20 qubits,
QMS will require $100\times 20=2000$ qubits to represent all possible states,
resulting in $2^{2000}$ possible states. If a new variable is added, the
system will require an additional $1\times 20=20$ qubits to represent the
states. Thus, the representation scales polynomially, as the number of
variables multiplied by the number of discretization qubits. Although it is
difficult to establish a comparison with the classical counterpart of QMS in
representation scalability terms, the memory to represent $2^{2000}$ possible
states will scale exponentially due to the necessity of representing them
sequentially.

In the second scenario, where the differences in evaluation values between
states are minimal, necessitating numerous repetitions of the $W$ operator, it
is crucial to examine how the number of $W$ repetitions grows to find the
solution. Due to QMS is a heuristic method which its performs depends on the
problem, it is not possible to give an exact number, just estimations based on
simulations. After the simulations of different use cases that will be
explained in the next chapters, it is known that QMS requires to execute
operator $W$ up to an exponent of 4 number of the number of qubits, $n_{q}$.
Therefore, while the number of possible states grows as $2^{n_{q}}$, the upper
limit of the number of $W$ repetitions grows as $n_{q}^{4}$. The number of
states grows much faster than the number $W$ operators. It is important for
the comparison of the number evaluations that a classical algorithm needs to
search in the whole state space.

Comparing the number of evaluations that the classical and quantum requires to
find a solution, the classical M-H algorithm requieres to explore between 60%
and 80% of the total number of states [81]. Of course, it is a rough number
that depends on multiple factors. However, it is easy to see that the
classical m-h requires exploring a very large region of space to converge and
this scales with the number of states. QMS, on the other hand, requires a
number of repetitions of W that scales much more slowly and, by definition, at
each repetition explores the entire state space in superposition.

The scalability conclusions shown here can be applied to all qms use cases
because they are all based on the same algorithm derived from quantum walks.

To obtain the results of the use cases, QMS has been designed to run on both
simulators and quantum hardware. All results from the use cases have been
obtained using Qiskit’s simulators. Additionally, in the use case of quantum
chemistry, protein folding, a reduced version of QMS was executed for this
specific use case on IBM’s quantum hardware. This demonstrated that QMS is
entirely valid for running in realistic environments.

With the ability to run on quantum hardware, coupled with QMS’s good
scalability in problem representation and algorithm execution, this tool could
be considered as part of an industrial pipeline with quantum advantage. To
reach that point, the only current limitation is the development of quantum
hardware, which, as seen in previous sections, is undergoing rapid progress.

####  4.3 Results

  * ✓

A quantum tool has been designed capable of solving real optimization problems
and using real data. It is called QMS (Quantum Metropolis Solver)

  * ✓

Implementation of software of a modified version of QM-H with the necessary
adaptation of registers and operators.

  * ✓

Implementation of hybrid architecture that can be tested in a early fault-
tolerant quantum computer.

  * ✓

Polynomial quantum advantage demonstrated in an important optimization
problem.

  * ✓

General software tool that can solve a wide range of optimization problems,
just by receiving a description of the problem as input.

  * ✓

Software tool with better scalability than a classical tool for optimization
problems.

  * ✓

Modular implementation that allows to modify any component of QMS to adapt it
to a different problem. In addition, it was developed under an open source
philosophy and published on GitHub.

See pages - of papers/publication_1.pdf

###  5 S&S applied to quantum artificial intelligence (QAI)

Q

uantum computing promises great advantages over classical algorithms in
difficult problems. One of the fields that has classically been characterized
by having the most complex problems has been artificial intelligence (AI). In
this category included all the problems in which algorithms had to process so
much data that they had to be able to make decisions autonomously. Therefore,
it is natural that quantum computing has also looked to this field to
hybridize with it and create the concept of quantum artificial intelligence
(QAI).

The concept of artificial intelligence, whether classical or quantum,
encompasses many techniques. In this work, an AI algorithm is defined as one
capable of running autonomously under changing conditions, doing some kind of
reasoning or searching. Within the family of AI algorithms, three main groups
can be distinguished: search algorithms, machine learning algorithms (ML) and
multi-agent algorithms. In previous sections, search algorithms have been
discussed in more detail, although they were not specifically dedicated to AI
problems. In this section, ML algorithms will be discussed in more detail. An
AI and ML general scheme is shown in figure 17.

ML algorithms take a set of input data and by reasoning learn from it to
generate a knowledge model of the problem to find the required solutions.
Within ML algorithms there are three other types of algorithms: supervised
learning, unsupervised learning and reinforcement learning.

Figure 17:  This figure shows the relationship between artificial
intelligence, machine learning and deep learning in the left. In the right,
there is a scheme of the different algorithms inside the machine learning
field (extracted from [82]).

The main motivation for developing the field of QAI in general and QML in
particular is to improve classical algorithms. This improvement can occur in
different areas, but especially focuses on three, reduction of training or
execution times, improvement of the accuracy of the algorithms, and reduction
of energy consumption.

Currently, AI is in a moment of high growth and implementation in industrial
technologies. However, its development limitations have already begun to
become apparent. At the software level, they are beginning to see limitations
in data processing that cannot be overcome [83]. Since these limitations
cannot be overcome with new algorithms, the solution focuses on creating
specific hardware that handles more data at higher speeds, for example, with
dedicated AI-only chips [84]. Although this approach also has limitations, the
size of the chips cannot be reduced below a certain threshold without quantum
effects appearing. In fact, this limit has already been reached and no more
transistors can be introduced on a single chip [85]. The solution is no longer
to introduce more transistors on a chip to double the capacity every two
years, as proposed by Moore’s law [86]. Now, the solution consists of stacking
chips and making computers with more interconnected chips, giving the whole a
higher capacity [87]. However, the concept of creating chips linked together
in large supercomputers following the High Performance Computing (HPC)
philosophy also has limitations and disadvantages. HPC computing centers
require increasingly complex architectures for interconnecting the processing
chips and, above all, they have very high energy consumption [88].

The first step in developing QAI algorithms, especially QML algorithms, has
been to look for a source of inspiration. Just as happened with the first
scientists who wanted to develop classical AI algorithms but did not know how
to do it and started to mimic human brain processes, the development of QML
has taken as a starting point classical algorithms that performed well and
tried to make quantum versions [89].

This strategy is valid because the objective is clear, to have more efficient
QML algorithms than the classical ones, but it is unknown how, so it was
necessary to start the research at some point. However, unlike what happened
in classical ML, which mimicking the human brain and learning proved to be
very useful, such as neural networks, evolutionary algorithms or Reinforcement
Learning, in the field of QML it seems to have led the research to a dead end.

Mimicking classical algorithms to create their quantum versions has proven to
have limitations either because there are processes that cannot be reproduced
in the quantum paradigm or because classical algorithms are so well-developed
that it is impossible to beat them. Moreover, it does not seem a good solution
to try to imitate classical algorithms because then the quantum advantage
would fall only on the advantage that the quantum HW can offer, something
that, currently, is not guaranteed that running a quantum circuit is faster
than doing it classically.

At this point, pessimism seems to prevail regarding the field of QAI and QML
in particular. Conceptual and fundamental problems have been encountered that
have made it clear that the current trend followed so far in the field is not
correct and must be redirected [90]. However, the opportunity offered by
quantum computing to accelerate algorithms in general remains a fact, and it
is clear that classical AI has limitations, so there remains an opportunity
for quantum algorithms. Once the target is clear and relevant to research, it
is necessary to open up new research lines. In this work, QS&S algorithms have
been developed that can serve as the basis for a new line of QML research that
diverges from the limited state of the art.

To explain how QS&S can be applied to the QAI field, the close relationship
between search and artificial intelligence will be explained. Then it will be
explained some QAI algorithms and the limitations that have been observed, and
finally how QMS has been applied to QAI and what are its future applications
will be explained.

####  5.1 Quantum S&S for QAI

There is a close relationship between the field of optimization and AI. Many
of the algorithms used for optimization problems are the basis for complex AI
algorithms. In fact, many of the basic AI processes can be seen as problems in
which a certain parameter needs to be optimized. This situation can be seen in
evolutionary algorithms trying to optimize a fitness function, multi-agent
algorithms trying to optimize group behavior, or ML algorithms where a
hypothesis has to be optimized to achieve a balance between generality and
expressiveness or a parameter optimization for deep learning.

A third element, quantum computing, can be introduced into this relationship.
As seen above, optimization problems have large state spaces that need to be
traversed almost exhaustively to find the solution. It has also been seen that
this is one of the tasks in which quantum computation is superior to classical
computation. Therefore, one can speak of a trichotomy or triad that relates
the three fields and that, in the center, houses a field of algorithm research
with the ability to have a high impact on certain problems.

Returning to the specific case of QML, it is known that a generic ML
algorithm, whether classical or quantum, performs reasoning, usually
inductive, on data. It takes concrete examples and tries to generalize to
obtain rules common to all examples that allow it to make predictions or
classifications. To do this, the algorithm, as it processes input examples,
generates hypotheses that explain these examples. Some hypotheses will be more
concrete, accurately covering certain cases but being wrong in many others,
and, on the contrary, other hypotheses will be more general, covering most of
the examples processed, but without accurately describing any of them. Thus,
the set of hypotheses generated is called the hypothesis space, which is
equivalent to the state space of an optimization problem. On this hypothesis
space, it is necessary to look for the one that maximizes a certain value
function that will represent a compromise between generality and abstraction
as defined in each case.

This search, which is performed during the training process, is very costly
for the algorithms. The greater the volume of examples processed and the
greater the expressiveness of the system, the greater the number of hypotheses
generated and the greater the similarity between them, the more difficult it
will be to guide the search and the longer the training time.

In variational algorithms there is the same concept of searching the
hypothesis space. The main difference is that the hypotheses are converted
into parameter settings to vary the ansatz circuit. This process is performed
by classical gradient descent algorithms, resulting in the barren plateaus
(BPs) problem and, moreover, little generalization. It is evident that the
same concept that works classically does not work quantumly, and therefore one
must look for other models of both parameter configuration search and
algorithms, going beyond the variational ones.

The QS&S algorithms are different from the gradient descent used so far. QS&S
does not perform a search following the energy landscape and, therefore,
cannot end up stuck in a plateau. The key is to leverage some domain knowledge
in the form of heuristics to guide the search toward a solution. This
heuristic must be run for each of the possible states of the problem being
solved, something impossible for classical computation, but feasible for the
quantum paradigm.

The key concept of QS&S for doing heuristic search is to include the
computation of the heuristic as an additional operator to the set of operators
in the search process. This will compute the heuristic value of the
superposition of states, that is, the value of each of the states. Thus, it
will be possible to increase the probability of the states with the highest
reward by performing an exhaustive search. This concept of QS&S is not a
concrete algorithm; it can be seen as a new philosophy, different from the
current one, to develop QML algorithms. Later, this philosophy can be
materialized in many types of algorithm, e.g., QMS.

By applying QMS to the N-Queen problem, a practical implementation following
this QS&S philosophy for QAI has been demonstrated on a problem equivalent to
the QAI problems.

####  5.2 Other QML techniques

Once the relationship between QS&S and AI and QML has been analyzed, it
possible to explain briefly other techniques. This additional techniques study
is interesting to see their problems because the QML field requires a
different approach from the current one.

The field of QML is currently dominated by variational algorithms. These types
of algorithms follow the hybrid paradigm with a quantum and a classical
module. The quantum module is a circuit with parameterized quantum gates. Gate
parameters are varied until the quantum circuit behaves in a certain way. To
vary these parameters, a classical optimization algorithm is used. This
algorithm takes the output of the circuit and evaluates it to determine the
parameter values in the next run of the quantum circuit. To vary these
parameters it follows a gradient descent based method. This system is run
iteratively a certain number of times or until convergence is reached. An
example of an architecture is in Figure 18. However, this paradigm of classic-
quantum hybrid programming has not yielded good results.

Figure 18:  This figure shows a general architecture from a variational
algorithm (extracted from [91]). The variational algorithms is composed by two
main modules. The first module is a quantum circuit and it acts as a
evaluation function. The parameters in the quantum module are modified
following the optimization of a classical module, the optimizer. This process
is repeated iteratively.

This execution scheme closely resembles that of classical neural networks.
There is an initial phase known as forward, where the network runs with
specific neurons (equivalent to quantum gates) to produce a result
(measurement of the circuit). Subsequently, a second phase of backpropagation
occurs, where the parameters of the neurons are adjusted based on the output,
following a gradient descent algorithm.

There has been much analysis of the reasons why variational algorithms do not
work. The intuition was that variational algorithms would be more expressive
than any classical algorithm and therefore learn faster and more accurately.
On the contrary, so far the ansatz implementations have not been found to have
more expressiveness than other classical algorithms [92] and it has been
observed that the barren plateaus problem limits the trainability of the
quantum circuit [93].

The barren plateaus (BPs) phenomenon occurs during the optimization process of
the quantum circuit parameters of the variational algorithm. It is expected
that each time the circuit is executed, the new parameter configuration of a
function value that evaluates it will be closer or farther away from the
solution. In this way, it is possible to know if the value of the evaluation
function has improved or worsened with respect to the last parameter setting.
In other words, the problem is expected to have a distribution in the
evaluation function that allows guiding the search towards an absolute
minimum. When looking at the BPs phenomenon, the distribution of the
evaluation function value is flat in most of the space, except for a very
small area around the solution that does have a downward gradient. This means
that the search for parameter configurations of the quantum circuit cannot be
guided, and it is necessary to carry out a practically exhaustive search,
losing all possible quantum advantage [94]. An artistic conception, and very
explicative, of the BP problem is shown in figure 19.

Reusing the most widespread metaphor for this situation, the ideal
distribution is similar to a mountainous area, where it is easy to know
whether the terrain is going up or down a mountain. In this ideal situation
there are several mountains representing local maxima and one mountain higher
than the others representing the absolute maximum. In this case, when the peak
of a mountain is reached, the local maximum, it is possible to see where there
are other higher mountains and guide the search. On the contrary, the barren
plateaus scenario is identified with a desert where everything is totally flat
and it is almost impossible to guide the search and where there is a small
well hidden in the sand where a local minimum is found.

There are multiple reasons for the existence of barren plateaus in problems,
but the main ones are: circuit expressivity, local measurements, random
initialization, and noise.

Figure 19:  This figure shows an artistic explanation of phenomena of barren
plateaus (extracted from [95]). The upper picture shows an ideal situation
without Barren Plateaus, in which at any point is possible to decide which is
the next step to be closer to highest point. The lower picture shows a
situation similar to a desert in which is impossible to decide which direction
should be taken to be closer to the maximum point.

After analyzing the BPs phenomenon in detail, some authors have come to the
conclusion that variational algorithms are a dead end for the QML field [90].
This situation is problematic because much of the QML community effort was
focused on this line.

After seeing the limitations of variational algorithms, the QML community has
tried other fields in which to make relevant contributions. Once is the
quantum backpropagation.

The classical backpropagation method allows adjusting the weights of a neural
network to reduce the difference between its prediction of a data label and
its actual label. This process is very expensive because the weights of all
neurons in a network must be adjusted. In fact, it is the process in which
most of the training time of a neural network is spent. Because of its high
cost and the possibility of parallelizing the process, something that is
already classically done, the quantum computing community has tried to create
quantum algorithms for backpropagation. However, this possibility has been
discarded due to the need to execute non-linear functions and the
impossibility of finding a quantum advantage [96].

The failed attempt to find a quantum algorithm in this field can be understood
as further evidence that the community is still looking for a justification
for research in the field of QML. It is also necessary to say that, once
again, the attempt to find a quantum advantage is using a method based on
gradient descent, similar to variational algorithms, and which has proven to
be inefficient.

Another field that is being explored in great detail is that of quantum
generative models. These algorithms are capable of generating data from noise.
Generative artificial intelligence is a machine learning paradigm that differs
from the usual discriminative models. The last ones are models used for
classification or regression, while the former ones are models that aim to
learn or discover relationships or patterns that exist between the different
points in the input set, and then use this learned information to generate new
points that mimic the characteristics of the input data set.

Quantum computing provides a perfect fit for this type of AI model for several
reasons. First, quantum computing is inherently random, so it is able to
generate samples from an ensemble stochastically without introducing any bias.
Second, it allows one to compute gradients faster than its classical
counterpart. And third, work has already been done that tests these algorithms
on current quantum computers, proving that this is a viable solution.

Quantum generative models have been proposed as one of the strongest
candidates to take advantage of quantum computing. To this end, metrics have
been created that measure the generality of these models and compare them with
classical models [97, 98]. Some examples of this quantum generative model are
quantum GANs [99, 100] and parameterized quantum circuits [101] and its
variations [102, 103]. In addition, small examples of these architectures have
been implemented in quantum hardware [104]. There are also practical
applications that make use of these quantum generative models, such as the
discovery of new drugs [105]. An example of the architecture of a hybrid
generative algorithm is shown in figure 20.

Figure 20:  Architecture of a hybrid quantum-classical generative algorithm.
It has a quantum prior module and the generator and discriminator are
classical modules. (extracted from [104]). The quantum prior samples from
noise, then, the classical generator and discriminator are trained to
transform the sample into data.

However, although they show great promise and are good candidates for quantum
advantage, many of the current generative models are still based on gradient
descent techniques, which causes them to have problems similar to those of
other variational algorithms. Therefore, in the field of QML, these algorithms
are beginning to be seen as useful in the medium to long term.

The limitations observed in the QML field are due to two main factors that are
closely related to each other, the short field run and the imitation of
classical techniques. The field of QML is barely less than 10 years old, the
first papers on quantum ML algorithms are from the mid-2010s. Just as happened
with brain mimicry as the starting point for classical ML, mimicking classical
algorithms has been the starting point for QML. Therefore, the current
algorithms are, practically, the first attempts of algorithms in this field.

However, it has been shown that this attempt to copy classical algorithms has
serious limitations because gradient descent techniques are useful in
classical algorithms but not in quantum algorithms. The future lies in
designing new algorithms that, although based on the well-known concepts of
classical ML, increasingly move away from the classical part and begin to
exploit more purely quantum techniques.

In this thesis, it is proposed that the field of QML be brought closer to QS&S
based techniques. This involves replacing gradient descent techniques with
more informed searches. In classical ML, it is not possible to do an informed
search in an algorithm like Neural Networks because it would take too much
time to adjust the weight of each neuron. However, quantum computing can do
exhaustive informed search with advantage over classical computing. The key to
this advantage is that the evaluation function can be a quantum operator
running on the superposition of states, [106] and that the search for the
marked element is quadratically faster.

To demonstrate that the QS&S concepts seen in the previous sections can help,
it is explained below how QMS has been applied to the N-Queen problem. This
problem has been used many times as a benchmark for testing search algorithms
that then have an impact on other ML techniques.

####  5.3 The N-Queen problem

The N-Queen problem consists of distributing $n$ queens over a chessboard of
dimension $n\times n$ without attacks between the queens, i.e., none of the
queens coincide in the same vertical, horizontal or diagonal line. This is a
well-known problem in the classical computing world because it is very easy to
test different algorithms to find the solution.

In the Publication 4.3 of this thesis, this problem is used to test an
algorithm that evaluates all combinations and keeps those that meet the
constraints. The solution has been proposed using a heuristic that evaluates
the quality of the solution based on the number of attacks between queens
until a state is found in which the number of attacks is 0.

The N-Queen problem has been used as a benchmark for ML algorithms because the
search necessary to find the solution is equivalent to the search that an ML
algorithm performs in the hypothesis space to find the one that maximizes a
certain function.

Thus, in order to prove that QMS works well with the N-Queen problem following
the QS&S methodology explained above, it is necessary to have one more
argument to continue this line of research.

To take the step of using QMS for QML, it is required to change the evaluation
function of the N-Queen problem to the evaluation function needed in QML. For
example, having a classifier that can discriminate the examples by 3
parameters, it is possible to create an evaluation function that determines
the quality of a hypothesis according to the value of those three parameters.
Then, it should apply that evaluation function to all possible states or
configurations of the system until the maximum reward is found.

The results of applying QMS on N-Queen show that there is an advantage over
classical algorithms. This consolidates the research line and prepares it for
future steps focused on building the generalization process around QMS.

A final consideration regarding the N-Queen problem and QMS is the execution
in quantum hardware. The results detailed in publication 4.3 were obtained in
a simulator using logical qubits fully connected between them and without
noise. However, as it was explained in previous chapters, quantum hardware
still has some limitations to be able to execute circuits like a quantum
simulator running in a classical hardware does. In a quantum hardware, the
quality of these qubits is lower, so it is necessary to increase the number of
qubits or reduce the problem. The number of qubits required for QMS is
$PQ+\lceil\log_{2}P\rceil+a+2$, being $P$ the number of parameters, $Q$ the
number of qubits for the discretization and $a$ the number of qubits for the
ancilla. Using two parameters with two qubits and three ancillas ($P=2$, $Q=2$
and $a=3$), 10 qubits are required. It is a reduced version of the problem but
it is useful to understand the requirements. Using this configuration, around
1250 quantum gates are necessary.

####  5.4 Results

  * ✓

QMS and the QS&S paradigm have been successfully applied to a problem
equivalent to any QAI and QML problem, the N-Queen problem.

  * ✓

A new approach to QML problems has been studied, the informed search in state
or hypothesis space, as opposed to the mostly used uninformed search, e.g.,
classical gradient descent optimization.

  * ✓

The alternative of using QMS offers the advantage of a search without the
phenomenon known as barren plateaus.

  * ✓

Scaling advantage results have been obtained using QMS which has a polynomial
scalability in the number of qubits to represent the states.

  * ✓

By applying QMS to the N-Queen problem and looking at its results, a tool has
been proposed that can serve as a basis for other QML algorithms.

###  6 S&S applied to Space Exploration

T

he field of space exploration encompasses any field of research that involves
learning more about any process outside our planet. Under the umbrella of the
concept of space exploration, there is a heterogeneous group of research lines
and techniques ranging from the design of new rockets to the analysis of earth
data taken from satellites in low orbit. Within space exploration, there are
more theoretical lines, such as models for predicting the movement of the
planets, or more applied lines, such as communications satellites.

A feature common to many techniques of space exploration is the complexity of
the analysis of data obtained by satellites or exploration missions. This
complexity derives partly from the volume of data to be processed and partly
from the complexity of the data. Of course, this complexity cannot be
generalized to any line of research, but it tends to be a constant in many
problems to be solved [107].

Examples of space exploration problems include analysis of Earth observation
data, optimization of satellite orbits, prediction of solar storms,
improvement of communications between satellites and ground stations, or
analysis of complex data such as gravitational waves. These are just a few
examples of space exploration use cases, but in all of them, quantum computing
has been applied in some way or another [108, 109, 110].

In fact, the world’s major space agencies are devoting great efforts to
developing quantum technologies applied to space exploration. Some examples
are NASA with its QuAIL and AMES groups, ESA with its ACT and PhiLab groups,
JAXA with the Space Exploration Innovation Hub Center or the Chinese space
agency with its Mozi and Micius satellites. But this is not limited to
government agencies; around them there are large companies that have planned
lines of research that apply quantum computing to space exploration problems
to overcome the major limitations of classical algorithms.

In this use case, QMS can be applied to space exploration problems if they can
be converted into optimization problems. In some cases, a conversion is not
even necessary, as the problems are already studied as such as optimization
problems. Specifically, this work will include as a use case the study of the
inference of gravitational wave source parameters through an adaptation of QMS
to the problem, known as qBIRD, quantum bayesian inference with
renormalization and downsampling.

####  6.1 Introduction to Gravitational Waves

A gravitational wave is a perturbation of space-time produced by an
accelerated massive body. They travel at the speed of light, contracting and
stretching anything in their path. They represent ripples in the fabric of
space-time, generated by temporal variations in the quadrupole momentum of the
source mass, and induce variations in the length of the objects they pass
through. This work is focused on gravitational waves produced by two black
holes that rotate about themselves until a merge event occurs.

Gravitational waves are really difficult to measure and were theoretically
proposed by Einstein, albeit with moments of disbelief and doubts encompassing
a long and winding road. Today, gravitational waves produced in a merge event
are measured because they are of such intensity that they can be measured
because of the deformation of the detectors; the rest of the gravitational
waves are invisible to the measuring devices currently available.

In 2015, the LIGO collaboration was able to make the first direct measurement
of gravitational waves thanks to large laser interferometers. The detection of
gravitational waves is an important new validation of the theory of general
relativity.

The LIGO scientific collaboration is the union of different universities and
research centers for the study and detection of gravitational waves. Members
of the collaboration have access to the advanced LIGO detectors located in
Hanford, Richland, and Livingston, Louisiana, both in the USA and to the VIRGO
detector located in Pisa, Italy. This collaboration was initially involved in
building the detectors with laser interferometer technology and is now
involved in upgrading the interferometers and studying all aspects of
gravitational waves. The founders of LIGO received the Nobel Prize in Physics
for their work in detecting gravitational waves in 2017.

Studying gravitational waves in detail has a great impact on the study of the
evolution of the universe and of phenomena that are still a mystery, such as
black holes. A fundamental characteristic of the gravitational waves that are
measured is that they have a validity period. This validity period is a
problem because the volume of detected events is constantly increasing due to
improvements in detector accuracy. If the usual trend of slow processing rate
and high detection rate continues, a point of collapse will be reached. In
addition, once the phenomenon disappears, it is not possible to observe it,
the only possibility is to analyze the static and past already recorded data.

Gravitational waves make possible the opening of a new window through which to
look at the universe, complementary to the observation of the electromagnetic
spectrum. This new method promises the observation of astrophysical events
that have never been seen before.

One of the possible analyses that can be done on gravitational waves is to
obtain some of the parameters of the event that generated them. It is possible
to obtain the distance they were from, the masses of the objects, their spins,
etc. This analysis is done with one of the techniques with more results as
parameter estimation, giving rise to the field of parameter estimation
gravitational waves (PEGW).

Currently, the PEGW analysis process is slow and requires a high processing
capacity and computational power. This is because it requires analyzing many
possible states and combinations of variables. PEGW can be viewed as an
optimization problem in which the value of certain parameters must be adjusted
to find a synthetic distribution that is as close as possible to the actual
distribution.

In order to better understand PEGW, it is necessary to explain the analysis
process. The interferometer that detects a gravitational wave is composed of
two large lasers. These lasers are joined at a perpendicular intersection and
when they detect a gravitational wave, they generate an interference pattern,
as shown in figure 21. This pattern contains all the information about the
event that generated the gravitational wave. Therefore, if, by adjusting the
value of certain parameters, it is possible to create a sufficiently similar
numerical wave, the value of the parameters that form or create that
interference pattern can be found. In this way, a state space is created with
a number of dimensions equivalent to the number of parameters in which it is
necessary to try all possible combinations to find which one generates a
synthetic interference pattern as similar as possible to the measured one, as
explained in Figure 22.

Figure 21:  Scheme extracted from [111]. It shows how the interferometers
built by LIGO works. Both interferometers are in a perpendicular position. If
a gravitational wave event is detected, a interference parameter is received
in the detector. Figure 22:  Scheme extracted from [112]. It shows the
gravitational waves detected by LIGO Handford (yellow) and LIGO Livingston
(blue) and the simulation of the parameter estimation process (black). The
estimation process tries to adjust the inferred wave as much as possible to
the received wave.

Following this PEGW scheme and in order to analyze in detail the gravitational
waves as a whole, both the LIGO collaboration and other universities have
implemented different gravitational wave analysis software. Among them, two
stand out, PyCBC [113] and Bilby [114]. Both allow inference, plotting, etc.
In this work, the aim is to create a hybrid algorithm that includes quantum
computation modules for PEGW and that can be included with some of the
existing tools or even be a tool in itself, in order to speed up the PEGW
process.

The classical PEGW algorithms are based on the classical Metropolis-Hastings
algorithm seen in the chapter 2. These algorithms encounter computational
constraints similar to those experienced by classical optimization algorithms.
In addition, in this case, an evaluation function, likelihood, slow to run,
and a large volume of data are added. All this makes the number of
gravitational wave events to be analyzed grow faster than their analysis
capacity, leading to different scenarios of collapse of the gravitational wave
analysis [115].

The ultimate goal of introducing quantum computing into the field of
gravitational waves is to create a pipeline that fully utilizes quantum
technologies, both in detection and in processing and analysis. However, this
goal is too general and ambitious. Therefore, it is necessary to go step by
step, and creating a quantum PEGW algorithm that gains an advantage over
classical algorithms is already a breakthrough.

To carry out the development of a PEGW algorithm with quantum computing, after
understanding the problem as an optimization, QMS has been adapted to the
problem with certain variations. This new version has been called qBIRD.

####  6.2 Methodology

Understanding the PEGW problem as an optimization problem in which a search is
required, it is necessary to define an evaluation function that determines the
quality of each state. In this case, loglikelihood is used as the evaluation
function.

The likelihood function is the conditional probability of the Bayesian theorem
$\mathcal{L}(d|\bm{\theta})=p(d|\bm{\theta})$. Being $d$ the data observed by
the interferometer, $\theta$ the set of parameters to infer that explains $d$,
$\mathcal{L}$ the likelihood function and $p$ the posteriors of the data and
parameters. For this purpose, it is common in the literature of gravitational
wave astronomy to assume a Gaussian noise in the detectors [116], so that the
Gaussian-noise likelihood function has the form:

$\mathcal{L}(d|\bm{\theta})\propto\exp\left(-\frac{1}{2}\int_{0}^{\infty}\frac{|\tilde{d}(f)-\tilde{\mu}(\bm{\theta},f)|^{2}}{\sigma^{2}(f)}df\right),$
(19)

All these functions are computed in the Fourier domain, where $f$ represents
frequencies. Here, $\tilde{d}$ denotes the data set acquired conventionally by
the detector, $\tilde{\mu}$ signifies the waveform derived from a specific
relativistic numerical model calculated using the parameter set $\theta$, and
$\sigma$ indicates the detector noise, expressed as spectral density. Notably,
although the integral spans all possible frequencies, in practice, this
interval is confined to frequencies compatible with ground-based detectors
while excluding certain frequencies like harmonics of domestic electricity.
This restriction ensures that $\sigma$ remains non-zero across these
frequencies, thereby preventing any divergence in equation 19.

Classically, the M-H algorithm is used to perform PEGW inference. The idea is
to run the M-H algorithm many times; it can be run up to 40,000 times. In each
run, the M-H algorithm will traverse the state space and stop at a point. All
of these points are then taken together to perform a statistical study of the
most probable set of values.

The concept of qBIRD is to use a quantum M-H algorithm, seeking greater
precision in each execution, and therefore to perform a smaller number of
executions. In addition, qBIRD is designed so that, in the future, with a more
developed quantum HW, the likelihood calculation will be an additional
operator in the quantum circuit, which makes the calculation of each iteration
faster.

Due to the limitations of current quantum hardware, the likelihood calculation
of each state must be classically preprocessed and introduced into the quantum
circuit via a QRAM. However, some authors have already proposed the
calculation of quantum likelihood [106]. By including the likelihood
calculation as an additional operator, it can be applied over the entire
overlay and saves both time and resources by avoiding the inclusion of the
QRAM technique, which adds a lot of depth to the circuit.

When comparing the classical PEGW algorithm with its quantum version, it is
necessary to use some figure of merit. Since qBIRD is an adaptation of QMS, it
is straightforward to use the TTS explained in subsection 4.2. Analyzing the
TTS of classical and quantum PEGW methods shows that there is an even greater
advantage over the use of other PEGW use cases. Moreover, this advantage is
expected to be even higher when larger problems can be run.

Another advantage of qBIRD over purely classical algorithms is its scalability
in qubits inherited from QMS. qBIRD uses exactly the same problem
representation as QMS and scales polynomially with the number of parameters
being analyzed.

Currently, quantum simulators running on classical hardware can simulate up to
4 parameters with a discretization of 5 or 6 qubits each. For this, the rest
of the parameters are fixed to complete the 17 that are usually inferred. As
the capabilities of quantum computers increase, this number of inferred
parameters will increase to 17 and be an inference equivalent to the state-of-
the-art.

Different tools are used to represent the results obtained in the PEGW
process. The main one to be seen in this work is the corner plot, shown in
figure 23.

A corner plot, like the shown in figure 23, is a commonly used graphical
representation in parameter estimation in the field of gravitational waves.
This type of plot effectively visualizes the joint distribution of multiple
parameters of the model being analyzed. Each axis of the plot represents a
pair of parameters under investigation. Along the margins of a corner plot,
histograms are included showing the marginal distribution of each parameter
individually. The points or contours in the plot represent samples drawn from
a Markov Chain Monte Carlo (MCMC) chain or another algorithm used to explore
the parameter space of the model. Summary statistics such as the mean or
median of the distribution of each parameter and confidence intervals are
included to highlight important features of the distribution.

Corner plots are useful tools for understanding the relationships between
multiple parameters in a model and for identifying possible correlations
between them and it is especially interesting when there are few parameters, 2
or 4, as in this case, because it allows to see the posterior probability
distributions (PDFs) of the parameters 2 to 2.

Figure 23:  Corner plot extracted from [115]. It shows a combination of the
result of estimating two parameters of a gravitational waves. It is a general
format to show the results in PEGW.

As discussed above, the aim of qBIRD is to develop a PEGW algorithm that will
speed up this process and overcome current bottlenecks. qBIRD may end up being
included in one of the currently discussed libraries, PyCBC or Bilby, or even
being a new library in its own right. To this end, in this work, there has
been a close collaboration with a scientist from the LIGO collaboration.

####  6.3 qBIRD

The simplest way to understand qBIRD is as an optimization algorithm capable
of obtaining good results on the PEGW problem. This algorithm uses sample and
search techniques to find the region of the state space in which the
likelihood value is highest. It then samples that region in order to find the
probability distributions of the posteriors. The search is guided using the
likelihood function explained in equation 19 with the objetive of maximizing
it.

The QS&S technique used by qBIRD is an adaptation of the one used in QMS, with
the objective of adjusting it to the PEGW problem. For this purpose, the
concepts of renormalization and downsampling are used.

Renormalization is a technique represented by a semigroup of transformations
that make up an iterative process of elimination (called truncation) of
degrees of freedom of a quantum system according to a certain criterion in
order to obtain an effective description of the retained degrees of freedom
[117]. The criterion can be of low energy, maximum likelihood, etc. It gives
rise to approximate computational methods of variational type. This technique
can be applied to QS&S.

QS&S techniques are primarily required for exploring large state spaces. When
dealing with quantum computing in the context of a significant state space,
the challenge lies in the probability distribution. In smaller state spaces,
the probability of finding states with lower energy functions is relatively
high compared to other states. For instance, in a search involving 8 states,
the normalized probability of lower energy states might be around 0.3,
contrasting with other states at 0.001. However, in a state space of $2^{32}$
states, the maximum probability state could still be 0.001, with the next
maximum probability state potentially as low as 0.000001. Despite the three-
order difference in magnitude, both states become indistinguishable upon
circuit measurement. Therefore, it becomes necessary to execute iteratively
the quantum circuit, eliminating the least probable states in each iteration
until a noticeable difference in probability is achieved after measurement.
This iterative process is based on renormalization.

This renormalization-inspired technique that is an adaptation of the QS&S to
PEGW problem, called qBIRD, can be seen from a different perspective. In
computer science, specially in the algorithms of digital signal processing,
there is a set of algorithms known as downsampling techniques. These
techniques are also widely applied to convolutional neural networks [118].

Downsampling refers to the comprehensive process of reducing both bandwidth
(filtering) and sample rate. When applied to a sequence of signal samples or a
continuous function, downsampling yields an approximation of the sequence that
would have been obtained by sampling the signal at a lower rate (or density,
as seen in photograph resolution reduction). In the context of qBIRD,
downsampling is employed similarly to approximate or reduce the state space to
get the likelihood distribution that requires sampling.

qBIRD receives as an input a set of parameters to infer and it returns the
posterior values of these parameters according to a likelihood function. These
parameters are initialized to a random values according to some prior
knowledge. The prior is composed by an interval and the distribution of this
interval. If the distribution is unknown, a Gaussian function is used. The
first step of the algorithm is the proposal of new values, Start in Figure 29.
Then, steps 1 to 3 are executed.

Step 0. Parameter initialization: The algorithm begins by initializing values
for each parameter drawn from a prior distribution, which is defined by the
lower and upper bounds of the prior function. These values are then stored in
the state register.

Step 1. Renormalization & Downsampling:  The first module implements the
quantum Metropolis-Hastings algorithm adapted from publication 4.3, and
incorporates a renormalization technique defining the qBIRD algorithm. During
this phase, the quantum walk is iteratively applied to narrow down the
parameter space, aiming to identify the values for each parameter that
maximize the likelihood.

a) Quantum Metropolis: Iteratively apply the walk operator $W$, defined in
Equation 17, a number of times on the initial state:

$\ket{\psi}:=W_{L}...W_{2}W_{1}\ket{\phi^{(0)}}.$ (20)

b) Sampling: Sample the state register.

c) Threshold condition: If the number of elements is the same than the number
of parameters to infer, each parameter is represented by 1 qubit, jump to Step
2, otherwise calculate the number of elements.

d) Qubit reductor: Reduce the number of qubits in the state register by 1 unit
and go to Step 1a). This condition allows eliminating one qubit for each
parameter, ending up with a minimum of one qubit per parameter.

The genesis of this second module stems from the challenge of employing the
quantum Metropolis algorithm to pinpoint the state with the highest
probability. Drawing inspiration from the renormalization techniques of
quantum lattice models [117], it is addressed the issue arising from the
vastness of the state space. In quantum systems, the normalization factor
leads to minute probability discrepancies between the most and least likely
states. Despite spanning several orders of magnitude, these disparities fail
to attain significance without an impractical number of measurements.

By progressively eliminating states with significantly lower probabilities
through the reduction of problem size and qubits, these discrepancies become
increasingly discernible. Employing this technique enables the identification
of the state with the maximum likelihood among all proposed values.

Step 2. Mean & Std Deviation calculator: The third module consists of a
classical processing that takes the results obtained in the first two modules
to generate PDFs for each parameter.

Step 3. Search interval calculator: To gradually narrow down the search area,
a new interval for each parameter is proposed.

End. After a given number of iterations of Steps $0-3$, PDFs of each of the
parameters are constructed from the values obtained in each iteration. This
algorithm is vastly detailed in [3].

The strength of qBIRD is its ability to sample a distribution with a low
number of iterations. As it is possible to observe in figure 24, using a
different number of $W$ it is possible to perform almost a perfect match with
the distribution to guess (black line). While the classical sampler would need
almost an exhaustive sampling, the quantum algorithm can do with a number of
$W$ between 3 and 5. It is just a small example, but very illustrative.

Figure 24:  Colour lines represent the state register probabilities for
different number of applications of the quantum walk operator. It is a two
source masses inference, using $Q=2$ discretization qubits, for the event
GW150914. X-axis is composed by the 16 combinations that represents the binary
encoding of a value for the first mass and another value for the second mass.
The black line represents the posterior probability function of each of these
combinations.

Once qBIRD was designed, it was implemented in a circuit. Subsequently, this
circuit was executed in a quantum simulator, which ran on a classical computer
utilizing the Qiskit library [119]. The results obtained from the simulator
are invaluable, as they validate the functionality of the algorithm. The next
step, executing qBIRD on quantum hardware, does not require any special
implementation. This implies that qBIRD’s limitations are solely dictated by
the constraints of quantum hardware, but it can scale as much as needed.

qBIRD has been tested using two benchmarks, speed and accuracy. Both metrics
are relevant for any quantum algorithm called to replace a classical one. As
explained above, the role of qBIRD is to replace the classical samplers
integrated in tools such as Bilby and PyCBC. qBIRD must be fast because
current PEGW algorithms take unacceptable times for the speed at which events
are detected. In addition, its results must be as accurate as or more accurate
than classical algorithms to be accepted by the gravitational wave community.

The core of qBIRD is the quantum Metropolis-Hastings algorithm based on
equation 17. To test the execution time of qBIRD applied to PEGW, it is
necessary to prove the performance of $W$ applied to the problem. In the work
[2] is explained how the quantum Metropolis-Hastings algorithm is able to get
a scaling quantum advantage as shown in figures 25 and 26. It is important to
notice that in both figures, the results are obtained using real LIGO data.

In both figures, TTS metric is used compare classical and quantum algorithms.
As has been shown in other results, the simulator limitations do not allow
executing problems with a size equivalent to the solved by classical
computers. However, it is possible to analyze the scaling tendency and the
quantum advantage is appreciable. In the table 1 a summary of the scaling
exponent is shown in each inference case.

This table 1 presents the same information as figures 25 and 26 in a more
concise format. The key information conveyed by the figures is the value of
the exponent, where a value lower than 1 indicates quantum advantage.
Therefore, a lower exponent signifies a better quantum advantage, with 0.5
being the maximum due to the quadratic advantage defined by Grover.
Additionally, it is observed that the exponent improves, approaching 0.5, with
an increasing number of parameters to infer. This observation is linked with
figure 16 and the problem size: with two parameters to infer, the problem is
considered small, whereas with four parameters, it falls closer to the medium-
sized category, where the gap between classical and quantum performance
diminishes.

2 PARAMETERS INFERENCE
---
Parameters inferred | Fit Exponents
Chirp mass and mass ratio | 0.95
Dimensionless spin1 and spin2 | 0.89
Comoving volume and inclination | 0.87
Comoving Volume and coalesence phase | 0.88
4 PARAMETERS INFERENCE
Parameters inferred | Fit Exponents
Coalesence time, mases and comoving volume | 0.68
Dimensionless spin1, spin2, comoving volume and inclination | 0.67
Table 1: Fitted exponents for different sets of variable parameters. Figure
25: Comparison of the minimum value of the classical and quantum TTS achieved
for the 2-parameter inference simulations. Top left the source-frame chirp
mass and the mass ratio have been inferred. Top right the comoving volume and
the inclination have been inferred. Below left the dimensionless spin-
magnitude of the larger and smaller object have been inferred. Below right the
comoving volume and the coalescence phase have been inferred. All results have
been obtained for 3-6 bits of precision with a constant value of $\beta$.
Figure 26: Comparison of the minimum value of the classical and quantum TTS
achieved for the 4-parameter inference simulations. On the left the
dimensionless spin-magnitude of the larger and smaller object, the comoving
volume and the inclination have been inferred. On the right the source-frame
chirp mass, the mass ratio, the coalescence time and the comoving volume have
been inferred. All results have been obtained for 2-3 bits of precision with a
constant value of $\beta$.

Just as important as the speed of execution is the precision and, derived from
this, the visualization of the data. This is the motivation of the second
publication that supports this work [3]. In this continuation of the first
work, qBIRD is used to get corner plots with real data similar to those used
by GWs community.

In the figures 27 and 28 it is shown the results of building corner plots
using qBIRD. Both cases are generated using injected parameters. The injection
option is very used in the GWs community to test the precision of the
algorithm. In both figures, the injection value (an orange cross) is the
middle of the inference, falling always in the dark blue region, the region
marked by qBIRD as the more likelihood or the more posterior values region.
Both corner plots are tests of the accuracy of the algorithm.

Figure 27: Posterior distributions obtained with qBIRD for the chirp mass
$\mathcal{M}_{c}$ and mass ratio $q$ of a simulated BBH gravitational wave
signal injected into Gaussian-noise using PyCBC. The injected values are
$\mathcal{M}_{c}=19.50\ {\text{M}_{\odot}}$ and $q=2.00$, shown in orange.
Figure 28: Posterior distributions obtained with qBIRD for a synthetic BBH
signal characterized with 4 unknown parameters. The simulated gravitational
wave was injected into zero-noise using Bilby, and the injected values are
$\mathcal{M}_{c}=27.43\ {\text{M}_{\odot}}$, $q=0.57$, $d_{L}=2000\text{
Mpc}$, and $\theta_{jn}=0.70$, shown in orange.

Finally, if the algorithm has demonstrated an advantage in execution speed and
good accuracy, the final test to ensure that the quantum algorithm can
outperform a classical one, once the quantum hardware limitations are solved,
is to show its scalability. It is possible to prove that the scalability of
qBIRD is polynomial in the number of parameters, $\mathcal{O}(P)$. The point
is to analyze the qubits required by the quantum walk.

The quantum walk employs a total of $PQ+\lceil\log_{2}P\rceil+a+2$ qubits:
$PQ$ represents the product of $P$, the number of inferred parameters and $Q$,
the number of discretization qubits, with $2^{Q}$ states represented for each
parameter; $\lceil\log_{2}P\rceil$ qubits to represent the register of each
parameter in binary encoding; $a$ qubits to represent the auxiliary register
for the acceptance probability. Finally, 2 qubits are needed, one for the
movement register, and another for the coin register to encode the
accept/reject probability of all states.

All terms in the scalabilty formula are dominated by the number of parameters,
and it results in a good scalability, which has a lower consumption in the
number of qubits than the qubit growth trend of quantum hardware.

The execution in quantum hardware following these numbers and using two
parameters with three qubits of discretization and three qubits of ancilla
will result in a 12 qubit execution. If qBIRD uses four $W$ operators at each
repetition, the number of gates will be close to 6.000 gates including H, X,
CX, CCX, MCX, CU and RY gates.

Figure 29:  Flowchart of qBIRD algorithm. This algorithm is divided in three
steps. Step 1 is focus on renormalization process. This renormalization
executes the quantum metropolis circuit and reduce the search. Then, steps 2
and 3 calculates the new intervals for the variables and the process starts
again.

####  6.4 Conclusions

  * ✓

QMS has been correctly adapted to a new use case in [2] and [3], the inference
of gravitational wave parameters, thus demonstrating the high versatility of
QMS as a generic tool to adapt to other optimization problems.

  * ✓

Quantum advantage results have been obtained using data from real
gravitational wave events in [2] and [3].

  * ✓

Results have been obtained with an accuracy similar to that of state-of-the-
art methods using real data from gravitational wave events in [2] and [3].

  * ✓

Generation of corner plots with accuracy similar to those generated by state-
of-the-art techniques and using data from real gravitational wave events.

  * ✓

qBIRD has good scalability in the number of qubits and is better than the
state of the art, which is essential for estimating 17 parameters.

  * ✓

Modular software tool to make any module classical or quantum or to integrate
new functionalities. In this case, the classical module that can be quantized
is the calculation of likelihoods.

  * ✓

Viable solution and new research line based on quantum software for an open
problem in LIGO collaborations.

###  7 S&S applied to Protein Folding

T

he research field of quantum chemistry includes those processes of chemistry
in which quantum phenomena occur. The cases treated by quantum chemistry must
be modeled in order to study them and predict the processes that will occur.
For example, to predict the behavior of a molecule under certain conditions,
it is necessary to create a model that explains the interactions of the
molecule with the environment.

The main limitations of the classical algorithms are to represent the
superposition and entanglement effects between particles. The only solution
for these cases is to create very simplified models that, although they do not
predict accurately, it allows to know some characteristics of the systems.
Although this is a very limited approach, it was the only possibility that
existed until the birth of quantum computing.

The advantage of quantum computing applied to quantum chemistry models is that
it can inherently represent many of the processes that occur without having to
use extra storage and processing resources. Examples include calculating the
minimum energy of a molecule, calculating the intermediate states in a
chemical reaction, predicting the best structure of a system to have certain
properties, or simulating the behavior of complex molecules in a certain
environment, for example, the protein folding problem.

Quantum chemistry is fundamental in the development of both industrial
processes and research. A large part of the research lines for the development
of new drugs, new materials, carbon footprint reduction, etc. is directly
related to quantum chemistry processes.

The fact that classical computation is very limited in this field of research
and that the basis of quantum computation is perfectly adapted to the
processes to be modeled, makes quantum chemistry the most promising candidate
for quantum advantage in the short term. This means that the first practical
application of quantum computing is expected to be in a problem that, at some
point, involves a quantum chemistry process.

This chapter has been approached as a use case of QMS and, therefore, of the
application of the QS&S philosophy to different problems. The interesting
quantum chemistry problems in this chapter are those that can be understood as
optimization problems. Within quantum chemistry, there are problems that can
be seen as a set of variables that can take different values and it is
necessary to adapt these variables to find a solution. Specifically, the
central problem that has been chosen is the protein folding problem.

####  7.1 Introduction to Protein Folding problem

The problem of protein folding is to find the three-dimensional structure of
an amino acid chain that is stable and functional in the human body. For this
to happen, it is necessary for the amino acid chain to adopt the three-
dimensional structure of minimum energy. Naturally, the human body generates
proteins folded in this minimum energy form, but introducing artificially a
protein into the body, it is necessary to calculate its structure in such a
way that it fulfills its task perfectly.

In the human body, there are many functions that are performed by a protein
that attaches to a particular tissue and captures other substances. This is
the case with insulin and glucose. Insulin is a protein capable of capturing
free glucose in the bloodstream and transporting it to a storage point for
metabolization. If the body cannot generate insulin due to a pathology known
as diabetes, hyperglycemia occurs, which can be very harmful to the human
body. To solve this problem, insulin proteins have been artificially designed,
which when injected into the blood perform the same function as if they had
been generated by the human body.

Research in the field has revelled the effects of diabetes by folding the
amino acids that make up this protein so that it could perform its function in
the human body. This structure is relatively simple because insulin is a small
protein with few amino acids, but in other cases, proteins are much more
complex, and the calculation of its structure can only be done by an
algorithm.

Classical protein folding algorithms must calculate, for each pair of amino
acids, all possible ways of binding. This extended to all the amino acids of a
protein, which can be more than 100, scales exponentially and is uncomputable
for a classical computer, at least with exhaustive methods.

Protein folding is the basis for the development of new drugs. In the human
body there are only 20 amino acids that combine to create proteins. The
functions of each of these amino acids are well known. Therefore, and
simplifying the problem, if a protein to perform a specific function is
required, it is only necessary to create it using certain amino acids. The
next complicated step is to go from a linear chain of amino acids to a three-
dimensional structure. Once the protein structure is calculated, the response
of the human body to certain stimuli can be tested, measure the degradation of
cells after exposure to certain products, and so on.

In 2021, a historic milestone in the development of algorithms applied to
protein folding occurred. The company Deep Mind released AlphaFold, a tool
that uses deep learning technology to predict the structure of proteins given
a chain of amino acids. AlphaFold proved to work very well for proteins of
large complexity and size, which earned it the recognition of the entire
community. While it has some limitations, such as training time or solution
quality for some proteins with several possible structures, it is a
breakthrough in the field.

AlphaFold makes a prediction based on convolutional neural networks equivalent
to those used for image recognition in computer vision. This type of network
does not take into account the energy of the predicted protein, therefore, the
solution offered by AlphaFold or any other DL-based algorithm can be refined
to find a structure of lower energy and, therefore, more stable. That is the
motivation of using protein folding as a use case for QMS, to create a search
algorithm that refines the solution given by a method that makes an initial
guess. In this case, QMS has been adapted to protein folding in a quantum
classical hybrid algorithm called QFold.

QFold has a hybrid architecture, apart from the internal architecture of QMS
itself, in which a classical DL algorithm is run first, which gives a first
structure of the protein that is not very stable, but serves as a starting
point for the classical algorithm to search for the three-dimensional
structure of the protein with minimum energy and maximum stability.

####  7.2 Methodology

To define the overall structure of the protein, the pairwise bonds of the
amino acids can be defined. Each amino acid bond can be defined as two torsion
angles, $\phi$ and $\psi$. The torsion angles, also called dihedral, are
angles between the atoms in the backbone structure of the protein, that
determine its folding. An example with the smallest of the dipeptides, the
glycylglycine, can be found in Figure 30. These angles are usually three per
amino acid, $\phi$, $\psi$ and $\omega$, but the latter is almost always fixed
at value $\pi$ and for that reason, not commonly taken into account.

Figure 30:  It shows the dihedral angles $\phi$ (yellow) and $\psi$ (pink) of
protein. Both angles are key to represent the bond between aminoacids. These
angles are discretized with a number of qubits to calculate the 3D structure
of the protein.

By discretizing the torsion angles between each of the amino acid pairs, the
overall structure of the protein can be described. Then, all possible angle
values of the protein are evaluated, calculating for each possible
configuration its energy. In this way, the configuration with the lowest value
in the evaluation function can be obtained following a search guided by energy
minimization.

The protein folding problem has been extensively studied both from the
perspective of classical and quantum algorithms. The latter, due to the
limitations of the algorithms and their executability, have had to resort to
very simplified models of the proteins. In fact, all models prior to QFold,
use lattice representations for proteins. This means that the angles between
amino acids can only be represented at right angles, 4 possible values. This
representation is totally unrealistic and greatly limits the results obtained.

One of the main innovations of QFold, along with the results obtained, is the
totally realistic representation of proteins. QFold represents both phi and
psi angles and does so at any value between 0 and 360, namely between $-\pi$
and $\pi$, with a user-defined discretization. This discretization is limited
by the runtime capability of the devices, but can be as large or small as
chosen, as the performance of QFold is maintained. Obviously, using a
discretization with a larger number of states, better is the performance of
the quantum algorithm versus the classical one because it increases the
complexity of the problem.

The main objective of QFold in the short term is to be able to refine the
search done by another module. In the medium to long term, QFold can be
considered as a stand-alone tool, but currently, classical algorithms have
greater capabilities. Following this objective, the QFold architecture has two
main modules, initializer and search algorithm.

The initializer is a classic deep learning module. Right now it is a module
that uses a simplified AlphaFold algorithm called MiniFold. However, this
initializer could use any other module that is proven to perform a good first
approximation of the protein structure. This first initializer module can be
understood as a fast and low quality solution, which allows one to guide the
quantum search to make it simpler. This type of mechanisms are very common
classically when the search space is too large and a fast first solution can
be obtained.

The search module is an adaptation of the QMS algorithm to the protein folding
problem. As in the previous cases, this module runs a QM-H circuit in which
the energy values of the proteins are loaded and a search is performed until
the minimum energy structure is found.

To calculate the energy of each possible protein structure, using the
evaluation function, the PSI4 software tool [120] was used. This tool receives
a set of amino acids with a given structure and returns its energy. As in
previous use cases, this energy calculation could be done by a quantum
algorithm and integrated into the algorithm itself, but the capabilities of
quantum devices do not allow it.

However, and unlike other use cases, this quantum algorithm of protein energy
calculation is really complex and expensive to implement, being the
development of these algorithms a line of research in itself. For this reason,
the following part II is devoted to study the complexity of quantum chemistry
algorithms with classical algorithms and their application in a use case.

In order to validate QFold as a valid solution, it was executed in real
quantum hardware. Due to the limitations, only a reduced size version of the
problem was tested but it is useful as a proof-of-concept. This simulation was
done using the quantum device IBMQ Casablanca with 7 qubits and quantum volume
of 32. Around 20.000 circuits were run just to ensure that the results were
valid, avoiding the noise. Besides, it was necessary to use a library, MITIQ
to mitigate the errores in the quantum hardware.

####  7.3 Results

  * ✓

Application of QMS to a high impact use case where classical computing is very
limited.

  * ✓

Polynomial quantum advantage over the classical M-H algorithm in the protein
folding problem.

  * ✓

Quantum algorithm with potential to assist or refine the solutions of the
classical algorithm.

  * ✓

The first quantum algorithm that uses a realistic model in the protein folding
problem, as opposed to quantum algorithms that represent the protein with
lattice models.

  * ✓

QFold architecture is fully modular for both the classical DL initializer and
the quantum search module, allowing the use of different initialization and
search algorithms.

  * ✓

Execution of M-H quantum algorithm with different beta schemes that allow to
study its evolution and behavior on an optimization problem.

  * ✓

Test of the QMS algorithm adapted to a use case, called QFold, on a NISQ
quantum chip to confirm the advantage results observed in the simulator.

  * ✓

Inclusion of QFold into Amazon-AWS repository as a case of study. QFold was
consired by AWS experts, as a valuable use case of quantum computing applied
to the protein folding problem. It allows any user to use it for their own
research.

See pages - of papers/publication_2.pdf

## Part II
Quantum Chemistry

###  8 TFermion

O

ne of the processes in quantum chemistry that can have the greatest impact is
to estimate the ground state energy of a quantum system (GSEE). The ground
state is the lowest possible energy state in a physical system, according to
quantum mechanics. This fundamental energy is of particular importance because
it affects the overall behavior of the system and can be crucial to
understanding its properties.

To solve the GSEE problem, there are some methods to efficiently estimate the
energy of a state. However, the problem arises because of the difficulty in
preparing the ground state (GSP) of a quantum system. The GSP problem has been
classically studied and some algorithms exist for it. However, these
algorithms do not efficiently represent the information contained in a quantum
system and, therefore, performing the evolution operations is so costly that
simplifications far removed from reality are made. These simplifications are
not able to produce reliable results, making both GSP and GSEE classically
very limited.

Quantum computing has two fundamental advantages in quantum chemical
algorithms. First, it allows a direct and realistic representation of quantum
states without approximations. Second, a QC algorithm inherently simulates
evolution. These two advantages are automatic because of the nature of quantum
algorithms but, in addition, there may be other advantages related to state
space exploration or data set processing. These advantages convert quantum
chemistry in a solid candidate for quantum advantage. These advantages
position quantum chemistry as a strong candidate for achieving quantum
advantage. Nonetheless, it is crucial to investigate the quantum gate
requirements of quantum chemistry algorithms to assess the current capability
of quantum devices to execute them. For that purpose, TFermion library is
presented.

####  8.1 Introduction to GSP and GSEE

One of the fundamental purposes of GSEE is to understand and predict the
behavior of quantum systems, such as molecules in quantum chemistry or
materials in condensed matter physics. The ability to estimate the ground
state energy is essential for practical problems, such as the simulation of
molecules for the design of new drugs or materials, where understanding the
ground state is crucial to understanding their properties and behaviors.

As seen in other sections, GSP and GSEE algorithms can combine classical and
quantum modules to create solutions that are executable in the near term on
the quantum devices at hand. However, while this can be done, it is not a
mainstream development in the scientific community. This is because the
advantage of quantum algorithms for GSEE is very large. The effort is more
focused on getting algorithms that require fewer and fewer resources than on
combining them with other classical ones. In fact, if the concept of hybrid
algorithm exists, it is simply because the objective is to find a quantum
advantage of this type of algorithms as soon as possible. An example of hybrid
quantum chemistry algorithms that will be discussed later is the Variational
Quantum Eigensolver (VQE) that served as the basis for the variational
algorithms explained in chapter 5.

In this thesis, a different approach is applied to GSEE quantum algorithms.
This approach is not intended to result in a new algorithm, neither quantum
nor hybrid. The goal of this new approach is to accelerate the development
process of quantum algorithms and to better understand their performance.

In this work, a classical computing software library has been developed that
gives information about the cost of several GSEE quantum algorithms to compare
them with each other and to understand which techniques are better. Basides,
to give information about the needs of quantum hardware to be able to execute
these algorithms. All this has resulted in the creation of a software tool for
measuring the performance of GSEE quantum algorithms called TFermion.

To explain how TFermion works and to show a practical example of its
usefulness, as a use case, it is necessary to understand some intermediate
concepts. First, the most important classical algorithms for GSP and GSEE will
be briefly explained. Then, it is necessary to explain some Hamiltonian
simulation techniques, which is the key process to represent the molecule and
various forms of representation needed. Finally, some quantum algorithms for
GSEE based on the representations explained above will be reviewed.

As discussed above, classical algorithms for GSP and GSEE make sense as long
as there are no quantum algorithms that can be run on real devices. Still,
some of these classical algorithms and their approximations have served as a
fundamental basis for other quantum algorithms. The main limitations of
classical quantum chemistry algorithms are found in the representation of
states, especially when they need to describe in great detail the behavior of
some particles with quantum effects. Of this type, three theoretical
descriptions stand out: Hartree-Fock (HF), density functional theory (DFT),
and coupled cluster (CC).

The Hartree-Fock (HF) method is an approximate form of the quantum mechanical
equations for fermions. HF method uses equations based on single-particle
orbitals that are more computationally accessible than methods based on many-
particle wave functions. It takes into account the interaction between
electrons and the influence of their electromagnetic fields.

The HF method receives as input the electronic Hamiltonian and returns the
molecular orbitals and their energies. It is an iterative method until
convergence of the orbital values. It is important to note that the Hartree-
Fock method is an approximation, it does not take into account the complete
electronic correlation. Although it is an approximation, it has been useful as
a basis for developing more sophisticated methods to describe molecular
systems with greater accuracy.

Density Functional Theory (DFT) [121, 122] is a theoretical framework in
quantum chemistry used to describe the electronic structure of atomic and
molecular systems. Unlike the HF method seen above, it does not deal directly
with electron wave functions but focuses on electron density as the
fundamental quantity.

In DFT, the electron density represents the probability of finding an electron
at a particular point in space. Upon that, DFT tries to minimize the total
energy of the system by varying the electron density. DFT is based on the
Kohn-Sham equation, which decomposes the system into non-interacting dummy
electrons, called Kohn-Sham electrons, moving in an effective potential. The
main limitation of DFT is that due to the computational complexity of
calculating the quantum effects between the electrons, approximations are
required that cause the system to lose accuracy.

DFT has proven to be a powerful and efficient tool for describing a variety of
molecular and solid systems. It is widely used in theoretical chemistry and
materials simulation, and has contributed significantly to the understanding
of electronic structures and chemical properties.

The basic idea of the Coupled Cluster procedure is to expand the wave function
as excitations of the HF state, which is an approximation to the fundamental
state of a quantum system. The method employs cluster excitation operators
that act on the reference state to create electronic excitations. These
cluster operators are decomposed in terms of single-electron excitations
(singles), double excitations (doubles) and so on. The cluster wave function
is expanded exponentially using the cluster operator. This means that higher
order terms take into account the interactions between multiple electrons.

CC is known for its high accuracy, especially in systems where electronic
correlation is crucial. However, it is also computationally intensive and its
practical use is limited to systems of moderate size due to the complexity of
the calculations. This method is also the basis for the Unitary Coupled-
Cluster ansatz used for the Variational Quantum Eigensolver.

####  8.2 Hamiltonian simulation, representation, mapping and encoding for GSP
and GSEE

In order to design quantum algorithms to simulate the evolution of the quantum
chemistry system to be evaluated, a definition of that evolution is necessary.
One such way of defining evolution is Hamiltonian simulation. This type of
simulation gives the algorithm the ability to simulate the time evolution of a
system described by a given Hamiltonian. This simulation makes it possible to
study how the quantum system evolves in time.

By describing a quantum system with its Halmiltonian and being able to use it
to describe a behavior, a more detailed study of its properties is performed.
This results in an advantage in accuracy. In addition, quantum computers allow
Hamiltonian simulation in a natural way, so this is another aspect in which a
quantum advantage is expected to be obtained in a practical problem.

The Trotter-Suzuki decomposition was the first method proposed to implement a
Hamiltonian simulation. It is based on the decomposition of the time evolution
operator into a series of more manageable operators. The main idea is to
divide the time into small steps and express the time evolution as a product
of simpler operators.

In this way, it is possible to apply the simple operators separately and then
combine the result. This algorithm tries to make a trade-off between accuracy
and performance. In such a way that higher precision implies lower
performance, higher complexity of execution. The Trotter-Suzuki algorithm can
be generalized to include higher order terms, improving the accuracy of the
approximation. However, as the order increases, the computational complexity
also increases.

Trotter’s method is the most widespread and widely used method for Hamiltonian
simulation. However, it has some points that can be improved such as the
scalability of its error. For this purpose, methods known as post-Trotter have
emerged. One of them is the Taylor series decomposition for Hamiltonian
simulation.

The terms of the Taylor series can be realized by introducing an additional
superposition and conducting controlled operations. The temporal evolution is
divided into segments, each sufficiently short to allow for an accurate
approximation of the evolution using a certain number of terms in the Taylor
series. Each segment is then performed using oblivious amplitude amplification
[66].

Another post-Trotter method is qubitization. Qubitization refers to the
expression of the time evolution operator in terms of qubits. The key idea
behind this algorithm is to find an efficient way to express the time
evolution operator in local terms of quantum operations that can be
efficiently implemented in a quantum circuit.

An example of representation, in the context of molecule simulation, is that
the Hamiltonian terms can represent interactions between atoms or between
electrons and nuclei, and the qubits represent the occupation of an orbital in
a molecular simulation. Once the quantum system has been mapped to qubit
space, other algorithms such as the Trotter-Suzuki algorithm can be applied.
The main advantage of qubitization is that it is an errorless Hamiltonian
simulation, but it is costly for a quantum computer.

In order to reduce the complexity of the implementation of the qubitization
method, the coupled cluster method was developed. In this method, the time
evolution is divided into two parts: the free part and the interaction part.

The free part describes the time evolution of the system without any
interaction, using an unperturbed Hamiltonian. The interaction part describes
how the system interacts, and its time evolution operator is constructed by
combining the free part and the interaction part. This approach facilitates
the treatment of complex systems by dividing the problem into more manageable
parts.

In order to run the GSP and GSEE quantum algorithms, it is necessary to use
the Hamiltonian describing the evolution, as seen above. In addition, it is
necessary to represent the problem, with first or second quantization, to make
a mapping between operators and qubits, by means of Jordan-Wigner or Bravyi-
Kitaev, and to make a choice of a set of basis functions to generate the wave
function, which can be gaussian functions or plane waves.

The representation of the states in a quantum circuit is one of the key
decisions when implementing an algorithm. Classically, it is already an
important decision because it largely determines whether the algorithm is
valid or not; quantumly, it becomes even more important because of the need to
optimize the number of qubits and operations. In this case, it should be
discussed how to use the logical qubits, noise-free and fully connected to
each other, to represent the possible quantum states of the system.

The first option is to use the first quantization. This representation
indicates the state of each electron, i.e., for each electron it indicates in
which orbital it is located. It is a compact representation because it only
requires a number of qubits proportional to the number of electrons and the
logarithm in base 2 of the number of orbitals. However, operating in this
quantization introduces a certain computational overhead, which slows down the
calculation.

The second option is to use the second quantization. This represents the
occupation of each orbital, i.e., in each orbital it is indicated how many
electrons there are. This representation requires a number proportional to the
number of orbitals in the system. If the number of orbitals is much larger
than the number of electrons, the second quantization is much less efficient
than the first. However, this representation does not require any additional
calculations, so it is more efficient in performing operations.

To simulate the quantum system, once the representation has been chosen, it is
necessary to map the system to the operators. In other words, designate a set
of qubit operators (matrices) which satisfy the canonical anticommutation
relations. In order to map fermions to qubits, and depending on the chosen
quantization, there are two main methods to perform the mapping, Jordan-Wigner
or Bravyi-Kitaev.

The Jordan-Wigner mapping is a theoretical method that uses second
quantization to transform spin operators into fermionic creation and
annihilation operators. This operation transforms “up” spins into fermions or
occupied states, and “down” spins into unoccupied states. The cost of Jordan-
Wigner mapping and parity mapping is $\mathcal{O}(N)$, where $N$ is the number
of qubits [123].

Alternatively, the Bravyi-Kitaev method ensures that the mapping can be done
at a complexity equivalent to the logarithm in base 2 of the number of qubits.
Balances the locality of the occupancy and parity information to improve the
efficiency of the simulation. The qubit stores the parity of the set of
occupancy numbers corresponding to that set of orbitals [124].

Once the representation and mapping methods were explained, it is necessary to
define the set of basis functions to generate the wave function. The basis set
can either be composed of atomic orbitals (yielding the linear combination of
atomic orbitals approach), which is the usual choice within the quantum
chemistry community; plane waves, which are typically used within the solid-
state community; or real-space approaches. Several types of atomic orbitals
can be used: Gaussian-type orbitals are by far the most often used, as they
allow efficient implementations of post-Hartree–Fock methods.

In molecular calculations, a common practice is to utilize a basis comprising
atomic orbitals centered at each nucleus within the molecule (linear
combination of atomic orbitals ansatz). The most physically motivated basis
sets are Slater-type orbitals (STOs), which are solutions to the Schrödinger
equation for hydrogen-like atoms. However, computing integrals with STOs poses
computational challenges, leading to the approximation of STOs as linear
combinations of Gaussian-type orbitals (GTOs). Numerous Gaussian-type orbital
basis sets have been documented in the literature [125], often organized in
hierarchies of increasing size to provide a controlled approach for obtaining
more accurate solutions, albeit at a higher computational cost.

The alternative to Gaussian basis functions is the use of plane waves, which
are better suited for periodic materials because of their periodicity.
Generally, the selection of the plane wave basis set is based on a cutoff
energy. Plane waves within the simulation cell that satisfy the energy
criterion are incorporated into the calculation. Moreover, certain integrals
and operations are more straightforward to program and execute with plane-wave
basis functions compared to their localized counterparts. The number of plane
waves is typically around 100 times larger than the Gaussian functions, as
recommended in Appendix E of [126].

Now that all the elements necessary to run a quantum algorithm based on the