# On constant-time quantum annealing and guaranteed approximations for graph
optimization problems

Arthur Braida  Atos quantum lab and Laboratoire d’Informatique Fondamentale
d’Orléans, France<EMAIL_ADDRESS>https://orcid.org/0000-0002-1825-0097  Simon Martiel  Atos quantum lab,
France<EMAIL_ADDRESS>Ioan Todinca  Laboratoire d’Informatique
Fondamentale d’Orléans, France<EMAIL_ADDRESS>
###### Abstract

Quantum Annealing (QA) is a computational framework where a quantum system’s
continuous evolution is used to find the global minimum of an objective
function over an unstructured search space. It can be seen as a general
metaheuristic for optimization problems, including NP-hard ones if we allow an
exponentially large running time. While QA is widely studied from a heuristic
point of view, little is known about theoretical guarantees on the quality of
the solutions obtained in polynomial time.

In this paper we use a technique borrowed from theoretical physics, the Lieb-
Robinson (LR) bound, and develop new tools proving that short, constant time
quantum annealing guarantees constant factor approximations ratios for some
optimization problems when restricted to bounded degree graphs. Informally, on
bounded degree graphs the LR bound allows us to retrieve a (relaxed) locality
argument, through which the approximation ratio can be deduced by studying
subgraphs of bounded radius.

We illustrate our tools on problems MaxCut and Maximum Independent Set for
cubic graphs, providing explicit approximation ratios and the runtimes needed
to obtain them. Our results are of similar flavor to the well-known ones
obtained in the different but related QAOA (quantum optimization algorithms)
framework.

Eventually, we discuss theoretical and experimental arguments for further
improvements.

##  1 Introduction

Quantum Annealing (QA)[3, 14, 9] is a computational framework where a quantum
system’s continuous evolution is used to find the global minimum of an
objective function over an unstructured search space. This metaheuristic
proceeds by preparing a simple, problem independent, quantum state and
evolving it along a problem-dependent trajectory, reaching a final state that
overlaps non trivially with the optimal solution. A well known theoretical
result, called the adiabatic theorem, ensures that this overlap will be large
if we respect some simple condition on the initial quantum state and if the
system’s evolution is slow enough (adiabaticity condition). This time-
continuous approach for quantum computing can be shown to be equivalent to the
more traditional, circuit based quantum computing model [9, 1], in the sense
that quantum circuits can simulate QA using a number of gates that only
depends polynomially on the precision of the simulation. Conversely, quantum
states produced by quantum circuits can be prepared via a polynomial time QA
(i.e. a QA trajectory that has polynomially small spectral gap). In [1], the
authors provide a complete review of this equivalence and generalize some
known results of digital quantum computing to the continuous setting, such as
quadratic speed-up for search in an unstructured data-set, thus generalizing
Grover’s algorithm [10]. The QA framework has been (mostly numerically)
investigated [6, 5] as a tool to solve combinatorial optimization problems
including $k$-clique and Exact Cover. Moreover, many classical NP-hard
optimization problems can be expressed with reasonable efforts in the QA
framework [15], making it a very general heuristic. On the negative side, the
adiabaticity condition asks for a "slow enough" evolution in order to obtain
the optimal solution. In general, QA needs exponential time for NP-hard
problems [2]. While there is not much hope for finding exact solutions
efficiently, one can still try and study QA as a probabilistic approximation
algorithm and quantify the achievable approximation ratio for various
combinatorial problems when run in reasonable time.

We believe that quantum annealing is a promising, general framework for
designing approximation algorithms, but to the best of our knowledge there are
no general results on guaranteed approximation bounds in the literature. The
main obstacle seems to be the current lack of mathematical tools for analyzing
the solutions obtained in limited time. The purpose of this work is to make a
step forward toward such tools, and show that QA produces reasonable solutions
for specific graph optimization problems, on specific graph classes.

In a closed system, the evolution of a quantum state $|\psi(t)\rangle$ is
guided by Schrödinger’s equation:

$\displaystyle i\frac{\partial}{\partial
t}|\psi(t)\rangle=H(t)|\psi(t)\rangle\quad\text{ for }t\in[0,T]$ (1)

where $T$ is the runtime of the evolution, or in our case, of the algorithm
(taking the constant $\hbar$ as unity) and $H(t)$ is the instantaneous
Hamiltonian of the system. QA can be used for computation (see., e.g., [1] and
Section 2.1 for more details) by clever choices of $H$. Typically, we choose a
problem-independent initial Hamiltonian $H_{0}=H(0)$, and a target Hamiltonian
$H_{1}=H(T)$ whose ground state (i.e., the eigenvector of minimum eigenvalue)
corresponds to an optimum solution of our given problem. The time-dependent
Hamiltonian $H(t)$ will then follow a specific trajectory according to a
chosen schedule.

The adiabatic theorem ensures that, under some technical assumptions, if time
$T$ is large enough (exponentially large), the system evolves towards the
ground state of $H_{1}$, hence towards an optimal solution. No general result
is known for polynomial time or even shorter, constant time. In this work we
focus on short, constant-time evolution, and we are interested in getting an
approximate solution for graph optimization problems. Indeed, we would like to
understand what guarantee on the results quantum computers can expect to reach
while they are stable only for a very short time.

#### Related work.

In the past years, a constant depth digital variant of QA, called Quantum
Approximate Optimization Algorithm (QAOA) has been intensively studied as a
promising heuristic for combinatorial optimization. In consists in a
discretization of a QA trajectory followed by a parametrization of the time
steps of this discretization. Some approximation bounds have been derived in
this model for particular classes of instances of MaxCut [8] (among other
similar problems). More recently [7], it has been shown that for some
problems, QAOA requires at least $O(\log{n})$ depth in order to have a shot at
beating Goesman-Williamson ratio for MaxCut problem. This result has been
transposed [16] to QA using a technique borrowed from theoretical physics
called the Lieb-Robinson bound that provides a tool to bound correlation
strength in continuous time dynamics. This same tool was also used to improve
simulation schemes for geometrically constrainted continuous dynamics [12,
19].

#### Our contribution.

The main technical contribution in this work is the use of LR-like bounds to
retrieve a relaxed locality argument in QA.

We see QA as a probabilistic algorithm and analyze the expected cost of its
output. For the graph optimization problems considered here, the output cost
can be decomposed as the sum of costs of vertices and edges. Hence the
challenge will be to evaluate the expected values of these terms, called
energies, for vertices and edges. Informally speaking, when considering a
Hamiltonian whose interaction terms are restricted to the input graph, by
making the quantum system evolve according to this Hamiltonian and observing
the energy of an edge or a vertex, the result will be comparable to the same
observation made on a quantum system evolving according to the Hamiltonian
restricted to a ball of bounded radius around the observed location. LR-type
bounds give us a tool to effectively bound the difference between these two
quantities.

With this relaxed notion of locality, we are able to reuse the same
combinatorial arguments as developed in the QAOA framework [8]. This general
method is firstly applied to MaxCut, which is a standard benchmark for QAOA.
In order to illustrate the generality of our method, we also apply it to the
Maximum Independent Set (MIS) problem. We show that we reach approximation
ratios better than random guess in these two cases, for regular (cubic)
graphs. We guarantee ratios of 0.5933 for MaxCut and of 0.3171 for MIS, to be
compared with the ratios obtained by naive algorithms, of 0.5 and 0.25
respectively. We perform further numerical studies suggesting that constant
time QA can achieve an approximation ratio of $0.6963$ for MaxCut on 3-regular
graphs, which is significantly better than the one we actually prove.

#### Organization of the paper.

The paper organization is as follows. In Section 2 we give the necessary
notations and detail the setting in which we use QA. We then develop the
notion of local algorithm and explain why focusing on regular (in particular
cubic) graphs is convenient when dealing with such algorithms. We then show
the main tool to recover locality in quantum annealing, namely a Lieb-Robinson
bound. In Section 3, we apply the method described to MaxCut and MIS to output
an approximation ratio at a fixed time, on cubic graphs. Section 4 brings
arguments suggesting that the actual approximation ratio of short-time QA for
MaxCut in cubic graphs is significantly better than the one that is proved in
the previous section. In practice, we are only able to compute the ratios for
small cubic graphs (up to 30 nodes) and get the ratio up to $T=5$. Eventually,
we talk about the non-tightness of the LR bound used here and where we can
earn to improve the ratio.

##  2 Locality in short-time QA

###  2.1 Preliminaries

#### Optimization problems on graphs.

We consider optimization problems whose input is a graph $G=(V,E)$ and the
output is a set of vertices, or a two-partition of the vertex set, maximizing
some global cost function. We are interested in combinatorial graph problems
where the global cost is a sum of cost functions localized on nodes and edges
of the input graph.

Formally, we are given as input graph $G=(V,E)$ on $n$ vertices, and our cost
function $C$ associates to any $n$-bit vector $x$ (bit $x_{i}$ corresponding
to the boolean value of node $i$) a value $C(x)=\sum_{i\in
V(G)}v(x_{i})+\sum_{\langle i,j\rangle\in E(G)}u(x_{i},x_{j})$, for some
functions $v:\\{0,1\\}\rightarrow\mathbb{N}$ and
$u:\\{0,1\\}\times\\{0,1\\}\rightarrow\mathbb{N}$.

The optimization problem consists in finding a bitstring $x$ maximizing value
$C_{G}(x)$. Bitstring $x$ can represent a subset of vertices (e.g., in the
case of Maximum Independent Set) or a two-partition of the vertex set (e.g.,
in the case of MaxCut).

#### Quantum annealing and combinatorial optimization.

For notations and basic notions in quantum computing, we refer to the
classical book of Nielsen and Chuang [17].

A quantum annealing algorithm for optimizing a cost function $C$ on $n$-vertex
graphs is defined by three ingredients.

  1. 1.

A problem-independent initial Hamiltonian $H_{0}$ (i.e., hermitian operator in
$Herm(\mathbb{C}^{2^{n}})$) to start our annealing. A standard choice for this
is $H_{0}=-\sum_{i}X_{i}$ where $X_{i}$ is the bit-flip operator acting on
qubit $i$. The ground state (i.e. the eigenvector of minimum eigenvalue) of
this Hamiltonian is the product state
$|\psi_{0}\rangle=\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)^{\otimes
n}$, the uniform superposition of all possible bit-strings of length $n$. This
state is particularly easy to prepare (it is not entangled) and will be the
starting point of our computation.

  2. 2.

A target Hamiltonian $H_{1}$ encoding the cost function $C$, in the sense that
for all $x\in\\{0,1\\}^{n}$, $H_{1}|x\rangle=-C(x)|x\rangle$. This completely
defines $H_{1}$ and thus is diagonal in the computational basis. This
construction is achieved by encoding each clause of $C$ separately:
$H_{1}=-\sum_{i\in V(G)}N^{(i)}-\sum_{\langle i,j\rangle\in E(G)}M^{(i,j)}$.
Thus, the structure of $C$ is preserved by the final Hamiltonian $H_{1}$ and,
local clauses become local terms (also called observables). Here, $N^{(i)}$
encodes the local cost function $v(x_{i})$ of node $i$ acting on qubit $i$ and
$M^{(i,j)}$ the local cost function $u(x_{i},x_{j})$ of edge $\langle
i,j\rangle$ acting on qubits $i$ and $j$. They can be defined as follow:

$\displaystyle N^{(i)}=(v(0)|0\rangle\langle 0|+v(1)|1\rangle\langle
1|)\otimes\mathbb{I}_{V-\\{i\\}}$ $\displaystyle
M^{(i,j)}=(u(0,0)|00\rangle\langle 00|+u(0,1)|01\rangle\langle
01|+u(1,0)|10\rangle\langle 10|+u(1,1)|11\rangle\langle
11|)\otimes\mathbb{I}_{V-\\{i,j\\}}$

  3. 3.

A running time $T$ and a trajectory $H(t)$ for $t\in[0,T]$ from $H_{0}=H(0)$
to $H_{1}=H(T)$. The instant Hamiltonian $H(t)$ will be defined here by the
linear interpolation $H(t)=(1-\frac{t}{T})H_{0}+\frac{t}{T}H_{1}$, but one can
imagine any smooth trajectory such that $H(0)=H_{0}$ and $H(T)=H_{1}$.

Driving our quantum system according to the Hamiltonian $H$ over a graph $G$
between times $s<t$ induces a unitary evolution $U^{G}_{s,t}$. Using this
notation, the state of the quantum system after a time $t$ is given by
$|\psi^{G}(t)\rangle=U^{G}_{0,t}|\psi_{0}\rangle$. This evolution operator is
defined by $U^{G}_{0,0}=I$ and respects the Schrodinger equation where the
total Hamiltonian $H$ depends on the graph $G$:

$\displaystyle i\frac{\partial}{\partial
t}U^{G}_{0,t}=H(t)U^{G}_{0,t}\quad\text{ for }t\in[0,T]$ (2)

In general, when running a QA to solve a combinatorial problem, the final
state is a superposition of all bit-strings inducing a probability
distribution over all possible solutions. By the adiabatic theorem, increasing
the running time $T$ effectively concentrates this distribution around the
optimal solution. In our case, we want to derive an approximation ratio,
therefore we need to compute the expected value of the cost function over the
final distribution. In quantum computing [17], this expected value is defined
as $E_{f}(T)=-\langle\psi^{G}(T)|H_{1}|\psi^{G}(T)\rangle$. By linearity, this
expected value can be written as:

$\displaystyle
E_{f}(T)=\sum_{i}\langle\psi^{G}(T)|N^{(i)}|\psi^{G}(T)\rangle+\sum_{\langle
i,j\rangle}\langle\psi^{G}(T)|M^{(i,j)}|\psi^{G}(T)\rangle$ (3)

Thus, we are ultimately interested in producing lower bounds for this quantity
in the non-adiabatic regime where $T$ is small.

###  2.2 Locality and restriction to regular graph

We denote by $|\psi^{G}\rangle$ the state produced by the QA algorithm on the
input graph $G$. This state depends on the whole input, in particular this
entails that each term in Eq. 3 might depend on the structure of the whole
graph $G$.

Let us assume for a moment that our algorithm is "local" in the sense that,
for each node and edge, it does not create correlations farther than a
neighborhood at distance $p$. As a consequence, the expectation value of a
local observable $N^{(i)}$/$M^{(i,j)}$ only depends on the structure of the
neighborhood at distance $p$ around this vertex/edge. Here, by neighborhood at
distance $p$ around subgraph $X$, we mean the subgraph $\Omega$ of $G$
containing $X$ and all vertices and edges situated on a path of $G$ of length
at most $p$, with an end-point in $X$. (Note that our notion of locality is
very similar to the classical notion of local algorithm on graphs used in
distributed computing, where "the output of a node in a local algorithm is a
function of the input available within a constant-radius neighbourhood of the
node" [18].) In that particular setting, Eq. 3 can be written as:

$\displaystyle
E_{f}=\sum_{i}\langle\psi^{\Omega(i)}|N^{(i)}|\psi^{\Omega(i)}\rangle+\sum_{\langle
i,j\rangle}\langle\psi^{\Omega(i,j)}|M^{(i,j)}|\psi^{\Omega(i,j)}\rangle$ (4)

where $|\psi^{\Omega(i)}\rangle$ (resp. $|\psi^{\Omega(i,j)}\rangle$) is the
quantum state obtained by running the algorithm on the neighborhood at
distance $p$ around vertex $i$ (resp. edge $\langle i,j\rangle$).

This locality condition for QA is of course too optimistic at this stage. We
shall see in the next subsection that, thanks to Lieb-Robinson type
inequalities, we can bound the difference between the actual values of
energies on nodes and edges on the whole graph, and those obtained by only
considering bounded radius balls around a node or an edge, hence obtaining a
result very similar to Equation 4.

Regular graphs have the particularity of having very few distinct small
subgraphs. For instance, the neighborhood at distance $1$ of a vertex is
always a star graph. As for edges, their neighborhoods at distance $1$ also
form a limited number of configurations, and the number of triangles in such
neighborhoods will play a major role. For example, on 3-regular graphs, Fig. 1
shows the star subgraph $\Omega_{0}$ at distance one from node $i$ and the
three different subgraphs $\Omega_{1},\Omega_{2}$ and $\Omega_{3}$, at
distance one from an edge $\langle i,j\rangle$.

$\begin{array}[]{cccc}\leavevmode\hbox to69.11pt{\vbox
to69.11pt{\pgfpicture\makeatletter\hbox{\hskip
34.55559pt\lower-34.55559pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.93701pt}{0.0pt}\pgfsys@curveto{4.93701pt}{2.72667pt}{2.72667pt}{4.93701pt}{0.0pt}{4.93701pt}\pgfsys@curveto{-2.72667pt}{4.93701pt}{-4.93701pt}{2.72667pt}{-4.93701pt}{0.0pt}\pgfsys@curveto{-4.93701pt}{-2.72667pt}{-2.72667pt}{-4.93701pt}{0.0pt}{-4.93701pt}\pgfsys@curveto{2.72667pt}{-4.93701pt}{4.93701pt}{-2.72667pt}{4.93701pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.38889pt}{-3.3393pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{i}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.90283pt}{-28.45276pt}\pgfsys@curveto{5.90283pt}{-25.19267pt}{3.26009pt}{-22.54993pt}{0.0pt}{-22.54993pt}\pgfsys@curveto{-3.26009pt}{-22.54993pt}{-5.90283pt}{-25.19267pt}{-5.90283pt}{-28.45276pt}\pgfsys@curveto{-5.90283pt}{-31.71284pt}{-3.26009pt}{-34.35559pt}{0.0pt}{-34.35559pt}\pgfsys@curveto{3.26009pt}{-34.35559pt}{5.90283pt}{-31.71284pt}{5.90283pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-32.20276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.35559pt}{28.45276pt}\pgfsys@curveto{34.35559pt}{31.71284pt}{31.71284pt}{34.35559pt}{28.45276pt}{34.35559pt}\pgfsys@curveto{25.19267pt}{34.35559pt}{22.54993pt}{31.71284pt}{22.54993pt}{28.45276pt}\pgfsys@curveto{22.54993pt}{25.19267pt}{25.19267pt}{22.54993pt}{28.45276pt}{22.54993pt}\pgfsys@curveto{31.71284pt}{22.54993pt}{34.35559pt}{25.19267pt}{34.35559pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{24.70276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.54993pt}{28.45276pt}\pgfsys@curveto{-22.54993pt}{31.71284pt}{-25.19267pt}{34.35559pt}{-28.45276pt}{34.35559pt}\pgfsys@curveto{-31.71284pt}{34.35559pt}{-34.35559pt}{31.71284pt}{-34.35559pt}{28.45276pt}\pgfsys@curveto{-34.35559pt}{25.19267pt}{-31.71284pt}{22.54993pt}{-28.45276pt}{22.54993pt}\pgfsys@curveto{-25.19267pt}{22.54993pt}{-22.54993pt}{25.19267pt}{-22.54993pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{24.70276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{-5.13701pt}\pgfsys@lineto{0.0pt}{-22.34993pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{3.63242pt}{3.63242pt}\pgfsys@lineto{24.1374pt}{24.1374pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-3.63242pt}{3.63242pt}\pgfsys@lineto{-24.1374pt}{24.1374pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to68.1pt{\vbox to69.11pt{\pgfpicture\makeatletter\hbox{\hskip
33.58977pt\lower-34.55559pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-23.51575pt}{0.0pt}\pgfsys@curveto{-23.51575pt}{2.72667pt}{-25.72609pt}{4.93701pt}{-28.45276pt}{4.93701pt}\pgfsys@curveto{-31.17943pt}{4.93701pt}{-33.38977pt}{2.72667pt}{-33.38977pt}{0.0pt}\pgfsys@curveto{-33.38977pt}{-2.72667pt}{-31.17943pt}{-4.93701pt}{-28.45276pt}{-4.93701pt}\pgfsys@curveto{-25.72609pt}{-4.93701pt}{-23.51575pt}{-2.72667pt}{-23.51575pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-29.84164pt}{-3.3393pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{i}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.90283pt}{28.45276pt}\pgfsys@curveto{5.90283pt}{31.71284pt}{3.26009pt}{34.35559pt}{0.0pt}{34.35559pt}\pgfsys@curveto{-3.26009pt}{34.35559pt}{-5.90283pt}{31.71284pt}{-5.90283pt}{28.45276pt}\pgfsys@curveto{-5.90283pt}{25.19267pt}{-3.26009pt}{22.54993pt}{0.0pt}{22.54993pt}\pgfsys@curveto{3.26009pt}{22.54993pt}{5.90283pt}{25.19267pt}{5.90283pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{24.70276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.3136pt}{0.0pt}\pgfsys@curveto{34.3136pt}{3.2369pt}{31.68965pt}{5.86084pt}{28.45276pt}{5.86084pt}\pgfsys@curveto{25.21587pt}{5.86084pt}{22.59192pt}{3.2369pt}{22.59192pt}{0.0pt}\pgfsys@curveto{22.59192pt}{-3.2369pt}{25.21587pt}{-5.86084pt}{28.45276pt}{-5.86084pt}\pgfsys@curveto{31.68965pt}{-5.86084pt}{34.3136pt}{-3.2369pt}{34.3136pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{26.92497pt}{-2.36708pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{j}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.90283pt}{-28.45276pt}\pgfsys@curveto{5.90283pt}{-25.19267pt}{3.26009pt}{-22.54993pt}{0.0pt}{-22.54993pt}\pgfsys@curveto{-3.26009pt}{-22.54993pt}{-5.90283pt}{-25.19267pt}{-5.90283pt}{-28.45276pt}\pgfsys@curveto{-5.90283pt}{-31.71284pt}{-3.26009pt}{-34.35559pt}{0.0pt}{-34.35559pt}\pgfsys@curveto{3.26009pt}{-34.35559pt}{5.90283pt}{-31.71284pt}{5.90283pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-32.20276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-24.82034pt}{3.63242pt}\pgfsys@lineto{-4.31535pt}{24.1374pt}\pgfsys@moveto{4.31535pt}{24.1374pt}\pgfsys@lineto{24.1671pt}{4.28566pt}\pgfsys@moveto{24.1671pt}{-4.28566pt}\pgfsys@lineto{4.31535pt}{-24.1374pt}\pgfsys@moveto{-4.31535pt}{-24.1374pt}\pgfsys@lineto{-24.82034pt}{-3.63242pt}\pgfsys@moveto{-23.31575pt}{0.0pt}\pgfsys@lineto{22.39192pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to69.11pt{\vbox to69.11pt{\pgfpicture\makeatletter\hbox{\hskip
34.55559pt\lower-34.55559pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-23.51575pt}{0.0pt}\pgfsys@curveto{-23.51575pt}{2.72667pt}{-25.72609pt}{4.93701pt}{-28.45276pt}{4.93701pt}\pgfsys@curveto{-31.17943pt}{4.93701pt}{-33.38977pt}{2.72667pt}{-33.38977pt}{0.0pt}\pgfsys@curveto{-33.38977pt}{-2.72667pt}{-31.17943pt}{-4.93701pt}{-28.45276pt}{-4.93701pt}\pgfsys@curveto{-25.72609pt}{-4.93701pt}{-23.51575pt}{-2.72667pt}{-23.51575pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-29.84164pt}{-3.3393pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{i}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.90283pt}{28.45276pt}\pgfsys@curveto{5.90283pt}{31.71284pt}{3.26009pt}{34.35559pt}{0.0pt}{34.35559pt}\pgfsys@curveto{-3.26009pt}{34.35559pt}{-5.90283pt}{31.71284pt}{-5.90283pt}{28.45276pt}\pgfsys@curveto{-5.90283pt}{25.19267pt}{-3.26009pt}{22.54993pt}{0.0pt}{22.54993pt}\pgfsys@curveto{3.26009pt}{22.54993pt}{5.90283pt}{25.19267pt}{5.90283pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{24.70276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.3136pt}{0.0pt}\pgfsys@curveto{34.3136pt}{3.2369pt}{31.68965pt}{5.86084pt}{28.45276pt}{5.86084pt}\pgfsys@curveto{25.21587pt}{5.86084pt}{22.59192pt}{3.2369pt}{22.59192pt}{0.0pt}\pgfsys@curveto{22.59192pt}{-3.2369pt}{25.21587pt}{-5.86084pt}{28.45276pt}{-5.86084pt}\pgfsys@curveto{31.68965pt}{-5.86084pt}{34.3136pt}{-3.2369pt}{34.3136pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{26.92497pt}{-2.36708pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{j}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.35559pt}{-28.45276pt}\pgfsys@curveto{34.35559pt}{-25.19267pt}{31.71284pt}{-22.54993pt}{28.45276pt}{-22.54993pt}\pgfsys@curveto{25.19267pt}{-22.54993pt}{22.54993pt}{-25.19267pt}{22.54993pt}{-28.45276pt}\pgfsys@curveto{22.54993pt}{-31.71284pt}{25.19267pt}{-34.35559pt}{28.45276pt}{-34.35559pt}\pgfsys@curveto{31.71284pt}{-34.35559pt}{34.35559pt}{-31.71284pt}{34.35559pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-32.20276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.54993pt}{-28.45276pt}\pgfsys@curveto{-22.54993pt}{-25.19267pt}{-25.19267pt}{-22.54993pt}{-28.45276pt}{-22.54993pt}\pgfsys@curveto{-31.71284pt}{-22.54993pt}{-34.35559pt}{-25.19267pt}{-34.35559pt}{-28.45276pt}\pgfsys@curveto{-34.35559pt}{-31.71284pt}{-31.71284pt}{-34.35559pt}{-28.45276pt}{-34.35559pt}\pgfsys@curveto{-25.19267pt}{-34.35559pt}{-22.54993pt}{-31.71284pt}{-22.54993pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-32.20276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{22.39192pt}{0.0pt}\pgfsys@lineto{-23.31575pt}{0.0pt}\pgfsys@moveto{-24.82034pt}{3.63242pt}\pgfsys@lineto{-4.31535pt}{24.1374pt}\pgfsys@moveto{4.31535pt}{24.1374pt}\pgfsys@lineto{24.1671pt}{4.28566pt}\pgfsys@moveto{28.45276pt}{-6.06084pt}\pgfsys@lineto{28.45276pt}{-22.34993pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-28.45276pt}{-5.13701pt}\pgfsys@lineto{-28.45276pt}{-22.34993pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to69.11pt{\vbox to69.11pt{\pgfpicture\makeatletter\hbox{\hskip
34.55559pt\lower-34.55559pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-23.51575pt}{0.0pt}\pgfsys@curveto{-23.51575pt}{2.72667pt}{-25.72609pt}{4.93701pt}{-28.45276pt}{4.93701pt}\pgfsys@curveto{-31.17943pt}{4.93701pt}{-33.38977pt}{2.72667pt}{-33.38977pt}{0.0pt}\pgfsys@curveto{-33.38977pt}{-2.72667pt}{-31.17943pt}{-4.93701pt}{-28.45276pt}{-4.93701pt}\pgfsys@curveto{-25.72609pt}{-4.93701pt}{-23.51575pt}{-2.72667pt}{-23.51575pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-29.84164pt}{-3.3393pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{i}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.54993pt}{28.45276pt}\pgfsys@curveto{-22.54993pt}{31.71284pt}{-25.19267pt}{34.35559pt}{-28.45276pt}{34.35559pt}\pgfsys@curveto{-31.71284pt}{34.35559pt}{-34.35559pt}{31.71284pt}{-34.35559pt}{28.45276pt}\pgfsys@curveto{-34.35559pt}{25.19267pt}{-31.71284pt}{22.54993pt}{-28.45276pt}{22.54993pt}\pgfsys@curveto{-25.19267pt}{22.54993pt}{-22.54993pt}{25.19267pt}{-22.54993pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{24.70276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.3136pt}{0.0pt}\pgfsys@curveto{34.3136pt}{3.2369pt}{31.68965pt}{5.86084pt}{28.45276pt}{5.86084pt}\pgfsys@curveto{25.21587pt}{5.86084pt}{22.59192pt}{3.2369pt}{22.59192pt}{0.0pt}\pgfsys@curveto{22.59192pt}{-3.2369pt}{25.21587pt}{-5.86084pt}{28.45276pt}{-5.86084pt}\pgfsys@curveto{31.68965pt}{-5.86084pt}{34.3136pt}{-3.2369pt}{34.3136pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{26.92497pt}{-2.36708pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{j}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.35559pt}{-28.45276pt}\pgfsys@curveto{34.35559pt}{-25.19267pt}{31.71284pt}{-22.54993pt}{28.45276pt}{-22.54993pt}\pgfsys@curveto{25.19267pt}{-22.54993pt}{22.54993pt}{-25.19267pt}{22.54993pt}{-28.45276pt}\pgfsys@curveto{22.54993pt}{-31.71284pt}{25.19267pt}{-34.35559pt}{28.45276pt}{-34.35559pt}\pgfsys@curveto{31.71284pt}{-34.35559pt}{34.35559pt}{-31.71284pt}{34.35559pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-32.20276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.54993pt}{-28.45276pt}\pgfsys@curveto{-22.54993pt}{-25.19267pt}{-25.19267pt}{-22.54993pt}{-28.45276pt}{-22.54993pt}\pgfsys@curveto{-31.71284pt}{-22.54993pt}{-34.35559pt}{-25.19267pt}{-34.35559pt}{-28.45276pt}\pgfsys@curveto{-34.35559pt}{-31.71284pt}{-31.71284pt}{-34.35559pt}{-28.45276pt}{-34.35559pt}\pgfsys@curveto{-25.19267pt}{-34.35559pt}{-22.54993pt}{-31.71284pt}{-22.54993pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-32.20276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{34.35559pt}{28.45276pt}\pgfsys@curveto{34.35559pt}{31.71284pt}{31.71284pt}{34.35559pt}{28.45276pt}{34.35559pt}\pgfsys@curveto{25.19267pt}{34.35559pt}{22.54993pt}{31.71284pt}{22.54993pt}{28.45276pt}\pgfsys@curveto{22.54993pt}{25.19267pt}{25.19267pt}{22.54993pt}{28.45276pt}{22.54993pt}\pgfsys@curveto{31.71284pt}{22.54993pt}{34.35559pt}{25.19267pt}{34.35559pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{24.70276pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{*}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{22.39192pt}{0.0pt}\pgfsys@lineto{-23.31575pt}{0.0pt}\pgfsys@moveto{-28.45276pt}{5.13701pt}\pgfsys@lineto{-28.45276pt}{22.34993pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{28.45276pt}{22.34993pt}\pgfsys@lineto{28.45276pt}{6.06084pt}\pgfsys@moveto{28.45276pt}{-6.06084pt}\pgfsys@lineto{28.45276pt}{-22.34993pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-28.45276pt}{-5.13701pt}\pgfsys@lineto{-28.45276pt}{-22.34993pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\\\
\Omega_{0}&\Omega_{1}&\Omega_{2}&\Omega_{3}\end{array}$

Figure 1: Subgraphs of 3-regulars for 1-qubit and 2-qubits neighborhood at
distance 1.

Coming back to Eq. 4, all the terms in the first sum will be identical since
all vertices have the same distance $1$ neighborhood $\Omega_{0}$. The terms
of the second sum can be regrouped into $3$ terms, corresponding to edges
having $\Omega_{1}$, $\Omega_{2}$, and $\Omega_{3}$ for distance $1$
neighborhood. Thus, the expression of $E_{f}$ becomes:

$\displaystyle E_{f}=nE_{0}+g_{1}E_{1}+g_{2}E_{2}+g_{3}E_{3}$ (5)

where $g_{k}$ is the number of edges having $\Omega_{k}$ for distance $1$
neighborhood, and
$E_{0}=\langle\psi^{\Omega_{0}}|N^{(i)}|\psi^{\Omega_{0}}\rangle$ because
$\forall i,\Omega(i)=\Omega_{0}$,
$E_{k}=\langle\psi^{\Omega_{k}}|M^{(i,j)}|\psi^{\Omega_{k}}\rangle$ because
$\forall\langle i,j\rangle,\Omega(i,j)$ is one of the $\Omega_{k}$. The
indices $i$ and $i,j$ of the observables refer to the labels on the subgraphs
in Fig. 1. We assume that, for configuration $\Omega_{1}$, the two nodes
marked with a $*$ are non-adjacent (if this happens then the four vertices
form a connected component of the input graph, which is not critical for our
analysis). Lets note $n_{k}$ the number of configurations $\Omega_{k}$. Hence
there are $n_{1}=g_{1}$ edges in configuration 1 and $4n_{1}+3n_{2}=g_{2}$ in
configuration 2 because there are four sides of $\Omega_{1}$ and three edges
of the triangle in $\Omega_{2}$, each of them being in a configuration of type
$\Omega_{2}$. The number of edges in configuration $\Omega_{3}$ corresponds to
the remaining ones, i.e., $3n/2-5n_{1}-3n_{2}=g_{3}$. Therefore, the final
energy can be written as

$\displaystyle
E_{f}=nE_{0}+n_{1}E_{1}+(4n_{1}+3n_{2})E_{2}+(3n/2-5n_{1}-3n_{2})E_{3}$ (6)

where $E_{k}=\langle\psi^{\Omega_{k}}|O_{X}|\psi^{\Omega_{k}}\rangle$ and
$O_{X}$ refers to the appropriate observable $O$ on $X$.

This construction is the one used to analyze the performances of the QAOA for
MaxCut on $3$-regular graphs in [8]. The authors used Eq. 6 together with an
upper bound on the maximum cut in $3$-regular graphs in order to derive a
worst case lower bound of $0.6924$ on the ratio achieved by a depth $1$ QAOA.
In our setting of QA, we cannot directly use such construction since the
locality condition that allows us to write the final expected cost as in Eq. 4
does not hold. To allow the same combinatorial arguments, we thus need to
recover some form of locality in the QA framework.

###  2.3 Lieb-Robinson like bound

The main tool we use in this work to regain some relaxed notion of locality in
QA is a Lieb-Robinson like bound. Many different versions exist but they all
convey the idea of a bounded speed of information in a quantum system. This
bounded speed of information entails that, after evolving our system for a
short amount of time, a local observation cannot depend too strongly on
features lying far from the observed subsystem. In other words, considering an
observable $O_{X}$ localized on subsystem $X$, the quantity
$\langle\psi^{G}|O_{X}|\psi^{G}\rangle$ will be close to
$\langle\psi^{\Omega}|O_{X}|\psi^{\Omega}\rangle$ for $\Omega$ a neighborhood
of $X$. More formally, we want to bound the following quantity:

$\displaystyle|\langle\psi^{G}|O_{X}|\psi^{G}\rangle-\langle\psi^{\Omega}|O_{X}|\psi^{\Omega}\rangle|$
$\displaystyle=|\langle\psi_{0}|(U_{0,t}^{G})^{\dagger}O_{X}U_{0,t}^{G}|\psi_{0}\rangle-\langle\psi_{0}|(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega}|\psi_{0}\rangle|$
$\displaystyle=|\langle\psi_{0}|\left[(U_{0,t}^{G})^{\dagger}O_{X}U_{0,t}^{G}-(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega}\right]|\psi_{0}\rangle|$

Since state-dependent LR bounds does not seem to exist to the best of our
knowledge, we first start by neglecting the initial state $|\psi_{0}\rangle$
of unit norm, and write:

$\displaystyle|\langle\psi^{G}|O_{X}|\psi^{G}\rangle-\langle\psi^{\Omega}|O_{X}|\psi^{\Omega}\rangle|\leq\left\lVert(U_{0,t}^{G})^{\dagger}O_{X}U_{0,t}^{G}-(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega}\right\rVert$

where $\left\lVert.\right\rVert$ denotes the operator norm. The two terms in
the norm represent the time evolution of the observable $O_{X}$ over the whole
graph $G$ and over the subgraph $\Omega$. Despite explicit expression of Lieb-
Robinson bounds exist like in [13], they are too loose for our applications on
approximation ratios. A numerically tractable expression (not necessarily in a
closed form) is enough. Although the expression used here is not a LR bound in
the strict sense of the concept, it bounds the same quantity, and for
simplicity we refer to it as an LR bound. We will use the following result,
adapted from [19] (see proof in Appendix 6, inspired from Appendix A of [19]).

######  Proposition 1 ([19])

Let $\Omega$ be a subgraph of $G$, $H_{\Omega}$ be the terms of the total
Hamiltonian $H_{G}$ supported on the subgraph, and $O_{X}$ an observable
supported on $X$ included in $\Omega$. The total Hamiltonian $H_{G}$ is a
linear interpolation between $H_{0}$ and $H_{1}$ where only $H_{1}$ has
interactions terms. For an evolution during $T$ and $t\in[0,T]$, we have that:

$\displaystyle\left\lVert(U_{0,t}^{G})^{\dagger}O_{X}U_{0,t}^{G}-(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega}\right\rVert\leq\int_{0}^{t}ds\frac{s}{T}\left\lVert[(U^{\Omega}_{s,t})^{\dagger}O_{X}U^{\Omega}_{s,t},H_{1,\partial\Omega}]\right\rVert:=LR^{\Omega}_{O_{X}}(t)$
(7)

where $H_{1,\partial\Omega}$ is the final Hamiltonian reduced to the border of
$\Omega$. In practice, only the interaction terms $M^{(i,j)}$ are left.
Notation $[.,.]$ corresponds to the commutator operation, i.e. for any
operators $A$ and $B$, $[A,B]=AB-BA$.

On the left-hand side of the inequality, we have the norm of the difference
between the time evolution of $O_{X}$ over a graph $G$ with the time evolution
of the same observable over a subsystem $\Omega$. This value corresponds to
the largest noticeable difference in energy one could possibly measure between
the evolution on the full graph or restricted to $\Omega$. Interestingly, the
right-hand side of this inequality (i.e. the LR type bound) does not depend on
the whole graph $G$. Potentially, only $H_{1,\partial\Omega}$ could depend on
the graph but when working with regular graphs, there are only a few possible
choices for this term which depend on $\Omega$. This bound only depends on the
local shape $\Omega$ of the system around $X$. Thus, looking at the value of a
local observable of an edge or a node on the whole graph or only locally on a
subgraph is the same up to a small error given by this bound. This LR bound
will quickly diverge when letting the evolution run for a large amount of
time. In particular, this entails that this result can only be used to analyze
the performances of very short time-continuous evolutions. Moreover, the time
dependence of the bound is such that considering a larger subsystem $\Omega$
will yield a smaller bound for a fixed $T$. In other words, if one needs to
study some evolution during a longer time (e.g. to get closer to the exact
solution), one might need to increase the size of $\Omega$. Fig. 2 illustrates
the time evolution of an observable $O_{X}$ on a path graph. The light cone of
the information spreading is colored in blue. In this work, we choose to work
with balls of radius $p=1$ around each vertex and edge, hence the subgraphs of
Fig. 1, so we expect to have a very short running time $T$.

Figure 2: Lieb-Robinson bound illustration on a path graph. The amount of LR
bound is in practice quasi null at the beginning and diverges exponentially.

Now, with this result, we can lower bound the value of
$\langle\psi^{G}|O_{X}|\psi^{G}\rangle$ that appears in the expression of the
final energy $E_{f}$. So we have a lower bound that is graph-independent on
the expected value of the quantum state output by QA. Choosing a tight upper
bound on the optimal value will give a global lower bound of the approximation
ratio. Indeed, we have that
$\langle\psi^{G}|O_{X}|\psi^{G}\rangle\geq\langle\psi^{\Omega}|O_{X}|\psi^{\Omega}\rangle-
LR^{\Omega}_{O_{X}}$, so with
$E_{k}^{*}=\langle\psi^{\Omega_{k}}|O_{X}|\psi^{\Omega_{k}}\rangle-
LR^{\Omega_{k}}_{O_{X}}$, the approximation ratio can be computed via:

$\displaystyle\rho(T)=\frac{E_{f}}{C_{\hbox{opt}}}\geq\frac{nE_{0}^{*}+n_{1}E_{1}^{*}+(4n_{1}+3n_{2})E_{2}^{*}+(3n/2-5n_{1}-3n_{2})E_{3}^{*}}{C_{\hbox{opt}}}$
(8)

In this section, we have shown that restricting the combinatorial problem to
regular graphs helps to study locally the problem because the number of small
subgraphs is finite. Then, thanks to the Lieb-Robinson bound, we can lower
bound the expected value of a local observable on the whole graph which is
needed to compute the final expected value of QA’s quantum state. In practice,
we shall use Proposition 1 to calculate the LR type bound numerically. In the
next section, we will apply this construction to two combinatorial problems on
graphs: MaxCut and Maximum Independent Set (MIS).

##  3 Application to MaxCut and MIS

In this section, we apply the method suggested to derive approximation ratios
for MaxCut and MIS on 3-regular graphs using QA metaheuristic. In both cases,
we need first to explicit the cost function, then to encode it in the
Hamiltonian $H_{1}$. We then proceed by numerically evaluating the energies
$E_{k}^{*}(T)$ on the four subgraphs $\Omega_{k}$ described in Fig. 1, and by
optimizing the ratio with respect to the annealing time $T$.

For $k\in\\{0,1,2,3\\}$, we compute the value of $E_{k}^{*}(T)$ for
$T\in[0,5]$. To do this, we need the value of $E_{k}(T)$ and the Lieb-Robinson
like bound $LR_{O_{X}}^{\Omega_{k}}(T)$ for appropriate $O_{X}$. $E_{k}(T)$
can be computed directly from the quantum state
$|\psi^{\Omega_{k}}(T)\rangle$. This state is computed by numerically solving
the Schrödinger equation (1) with a relative tolerance of $10^{-9}$ on
$\Omega_{k}$. These computations were performed on an Atos QLM (Quantum
Learning Machine) using boost. To compute the LR bound, we have to compute the
unitary evolution operator $U_{s,T}^{\Omega_{k}}$ for all $s\in[0,T]$ and
compute the integral on the right hand side of Eq. 7. We chose a time step of
$10^{-3}$ to compute the integral. We compute the unitary operator for each
time step by solving the Schrödinger equation for evolution operator (Eq. 2).
These computations were carried using the Differential Equations Julia
library.

Let us detail the interaction terms $H_{1,\partial\Omega}$. This is a sum over
all interactions $M^{(i,j)}$ for edges $\langle i,j\rangle$ which are not in
$\Omega$ but have at least one endpoint in $\Omega$. Therefore, the larger the
sum is, the larger the LR bound will be. Considering interactions between two
nodes of $\Omega$ reduces the bound because we work with bounded degree
graphs. So the worst case considers only interactions between $\Omega$ and
$\bar{\Omega}$, i.e. interactions that leave the subgraph. To include the
$\Omega_{k}$’s in cubic graphs, there are 6 similar terms with $\Omega_{0}$, 2
same terms when considering $\Omega_{1}$, 5 terms including 4 identical ones
with $\Omega_{2}$ and 8 similar terms with $\Omega_{3}$.

###  3.1 MaxCut

The cost function $C$ we want to maximize counts the size of a cut, i.e. the
number of edges cut by a solution $x=x_{1}x_{2}...x_{n}$, where
$x_{i}\in\\{0,1\\}$ (nodes $i$ such that $x_{i}=0$ are considered as on the
left-hand side of the cut, while nodes $j$ with $x_{j}=1$ are on the right-
hand side). So we have $C(x)=\sum_{\langle i,j\rangle}x_{i}\oplus x_{j}$, a
sum of xor operations between the extremities of each edge. By a change of
basis from $x_{i}\in\\{0,1\\}$ to $z_{i}\in\\{1,-1\\}$, the cost function
becomes $C(z)=\sum_{\langle i,j\rangle}\frac{1}{2}(1-z_{i}z_{j})$. In quantum
computing, there is a natural operator that does this basis change called
$\sigma_{z}$. Therefore, the natural expression for the final Hamiltonian that
QA will minimize is $H_{1}=-\sum_{\langle
i,j\rangle}\frac{1}{2}(1-\sigma_{z}^{(i)}\sigma_{z}^{(j)})$. Thus, for MaxCut,
we have $N^{(i)}=0$ and
$M^{(i,j)}=\frac{1}{2}(1-\sigma_{z}^{(i)}\sigma_{z}^{(j)})$. For the optimal
cut, we use the same reasoning in [8]: the size of the maximum cut is at most
$3n/2$ and each configuration of type $\Omega_{1}$ and $\Omega_{2}$ (see
Figure 1) has at least one edge that is not cut (they each contain a triangle
that is disjoint from all other triangles). Hence, we have that
$C_{\hbox{opt}}\leq 3n/2-n_{1}-n_{2}$. By normalizing with $n_{1}\leftarrow
n_{1}/n$ and $n_{2}\leftarrow n_{2}/n$, we end up with a global approximation
ratio $\rho_{mc}$ for problem MaxCut that verifies:

$\displaystyle\rho_{mc}\geq\min_{\begin{array}[]{c}n_{1},n_{2}\text{ s.t.}\\\
4n_{1}+3n_{2}\leq
1\end{array}}\max_{T}\frac{n_{1}E_{1}^{*}(T)+(4n_{1}+3n_{2})E_{2}^{*}(T)+(3/2-5n_{1}-3n_{2})E_{3}^{*}(T)}{3/2-n_{1}-n_{2}}$
(11)

By numerically evaluating the $E_{k}^{*}(T)$ and optimizing over
$T,n_{1},n_{2}$, we find that the approximation ratio reaches 0.5933 at
$T_{mc}=1.62$ and $n_{1}=n_{2}=0$. The numerical values for $E_{k}^{*}$ are
presented in Table 1, we can see that $\rho_{mc}\geq E_{3}^{*}$. This means
that QA struggles the most with triangle-free graphs, as it also happens with
QAOA [8]. A refined numerical analysis is presented in Appendix 7 where we
point out more intuitions about QA on MaxCut.

k | 1 | 2 | 3
---|---|---|---
$E_{k}$ | 0.5951 | 0.6152 | 0.6350
$LR_{O_{X}}^{\Omega_{k}}$ | 0.0203 | 0.0310 | 0.0417
$E_{k}^{*}$ | 0.5748 | 0.5842 | 0.5933
Table 1: Numerical values to get $E_{k}^{*}(T_{mc})$

###  3.2 Maximum Independent Set

For MIS problem, we use the same cost function as in [7]. For a vector
$x=x_{1}x_{2}...x_{n}$, with $x_{i}\in\\{0,1\\}$, the cost function tries to
maximize the Hamming weight and minimize the number of edges in the subset
$x$, i.e., the subset of nodes $i$ such that $x_{i}=1$. We write
$C(x)=\sum_{i}x_{i}-\sum_{\langle i,j\rangle}x_{i}x_{j}$. Even though this
function only weakly encodes the independent set constraint, one can easily
transform any bit-string $x$ of cost $C(x)$ into a stable of size at least
$C(x)$. This can be done considering each edge that violates the stable
condition (i.e. each edge $\langle i,j\rangle$ such that $x_{i}=x_{j}=1$),
picking at random one of its extremities, and removing it from the solution.
This effectively removes a vertex from $x$ while "fixing" at least an edge,
thus creating a new solution with an increased cost. Eventually, the maximum
of $C(x)$ corresponds to a maximum independent set.

In order to implement $C$ into a Hamiltonian we proceed to the same change of
basis as for MaxCut: $\\{0,1\\}$ is transformed into $\\{1,-1\\}$ and $C$ can
be written as $C(z)=\sum_{i}\frac{1-z_{i}}{2}-\sum_{\langle
i,j\rangle}\frac{1-z_{i}}{2}\frac{1-z_{j}}{2}$. Thus, the final Hamiltonian
for MIS that QA will minimize is:
$H_{1}=-\sum_{i}\frac{1}{2}(1-\sigma_{z}^{(i)})+\sum_{\langle
i,j\rangle}\frac{1}{4}(1-\sigma_{z}^{(i)})(1-\sigma_{z}^{(j)})$. Unlike
MaxCut, we see here that we have a component on the nodes and a component on
the edges; $N^{(i)}=\frac{1}{2}(1-\sigma_{z}^{(i)})$ and
$M^{(i,j)}=-\frac{1}{4}(1-\sigma_{z}^{(i)})(1-\sigma_{z}^{(j)})$. In order to
upper bound the size of an IS in regular graph, we use the following claim.

###### Claim 1

For a $d$-regular graph, the size of the MIS is upper bounded by $n/2$ and
this value is reached by bipartite graphs.

The proof is straightforward once we see that the total number of edges in a
$d$-regular graph is $\frac{dn}{2}$, and any independent set $I$ has $d|I|$
edges incident to it.

To compute the approximation ratio of MIS on 3-regular graphs, we will use
this upper bound on $C_{\hbox{opt}}$. By the same normalization with
$n_{1}\leftarrow n_{1}/n$ and $n_{2}\leftarrow n_{2}/n$, we end up with the
following bound on the approximation ratio:

$\displaystyle\rho_{mis}\geq\min_{\begin{array}[]{c}n_{1},n_{2}\text{ s.t.}\\\
4n_{1}+3n_{2}\leq
1\end{array}}\max_{T}\left(2(E_{0}^{*}+n_{1}E_{1}^{*}+(4n_{1}+3n_{2})E_{2}^{*}+(\frac{3}{2}-5n_{1}-3n_{2})E_{3}^{*})\right)$
(14)

By numerically evaluating the $E_{k}^{*}(T)$ and optimizing over
$T,n_{1},n_{2}$, we find that the approximation ratio reaches 0.3171 at
$T_{mis}=1.32$ for $n_{1}=n_{2}=0$. The numerical values for $E_{k}^{*}$ are
presented in Table 2, and we have that $\rho_{mis}\geq
2E_{0}^{*}(T_{mis})+3E_{3}^{*}(T_{mis})$.

k | 0 | 1 | 2 | 3
---|---|---|---|---
$E_{k}$ | 0.4653 | -0.1939 | -0.1920 | -0.1901
$LR_{O_{X}}^{\Omega_{k}}$ | 0.0072 | 0.0034 | 0.0065 | 0.0096
$E_{k}^{*}$ | 0.4581 | -0.1972 | -0.1985 | -0.1997
Table 2: Numerical values to get $E_{k}^{*}(T_{mis})$

Our purpose is to illustrate the generality of the approach based on Lieb-
Robinson bounds, which can be used for estimating the energy both on vertices
and on edges. We reach with a constant-time local algorithm a ratio that is
better than random guess. Here, the random guess is among all bitstrings
$x\in\\{0,1\\}^{n}$ so the expectation of $C(x)$ (thus the expected size of
MIS) is of $n/8$, which gives an approximation ratio of 0.25.

##  4 Toward a better bound for MaxCut?

In the previous section, we have shown how to apply a general method using an
LR bound with QA to compute an approximation ratio with a constant time, local
algorithm (at distance 1), for cubic graphs.

We believe that the algorithm behaves significantly better than the
approximation bounds that we were able to prove. In Subsection 4.1, we give a
theoretical algorithm to find a tighter bound on the approximation ratio and
argue that the actual approximation ratio for MaxCut in cubic graphs with a
distance 1 analysis might be of $0.6963$, while we only guarantee $0.59$.
Then, in Subsection 4.2, we discuss the (non) tightness of our LR type bound
used in the analysis, explaining this gap, and suggesting some directions for
improvements.

###  4.1 Hints for better approximation ratios

To derive a better bound with a distance 1 analysis, i.e. still using Eq. (6),
ideally we should use energies $E_{k}^{\mathcal{G}}$, corresponding to the
minimum energy of the edge $X$ in $\Omega_{k}$ among all possible cubic graphs
containing $\Omega_{k}$:

$E_{k}^{\mathcal{G}}(T)=\min_{G\text{ s.t. }X\in\Omega_{k}\subseteq
G}\langle\psi^{G}(T)|O_{X}|\psi^{G}(T)\rangle.$

Instead we used values $E_{k}^{*}$ that are lower bounds for
$E_{k}^{\mathcal{G}}$, obtained through our LR-type bound of Proposition 1. In
order to improve the approximation ratio, we need to access to a more accurate
estimation of values $E_{k}^{\mathcal{G}}$. Values $E_{k}^{\mathcal{G}}$ are
obviously intractable in practice because there are infinitely many cubic
graphs $G$ that can complete $\Omega_{k}$.

However, we can make a different use of LR bounds to reduce the search space
to the finite space of all balls $\mathcal{B}$ that can be completed in a
3-regular graph with finite radius $r$ (from the edge $X$). Here we employ
[12, Lemma 5] stating that there are some constants $v_{LR}>0$ (called the
Lieb-Robinson velocity) and $\mu>0$ such that for any $r\geq v_{LR}t$, there
exists a ball $B_{r}$ centered on $X$ with radius $r$ such that:

$\left\lVert(U_{0,T}^{G})^{\dagger}O_{X}U_{0,T}^{G}-(U_{0,T}^{B_{r}})^{\dagger}O_{X}U_{0,T}^{B_{r}}\right\rVert\leq\mathcal{O}(e^{-\mu
r})$ (15)

Thus, by only considering balls of radius $r$, we get can get an estimate of
the true value of $E^{*}_{k}(T)$ up to $\mathcal{O}(e^{-\mu r})$.

For any constant time $T$, in bounded degree graphs, this statement allows us
to fix an arbitrarily small error $\varepsilon>0$ which fixes a radius
$r(\varepsilon,T)$. From there, we can approximate the energy of a vertex or
an edge at time $T$ of a QA process by only studying a neighborhood at
constant distance around the vertex or the edge. The corollary is an
application of Theorem 1 in [16], it can also be deduced from Lemma 5 of [12].

###### Corollary 1

Let $G$ be a bounded degree graph, $O_{X}$ an observable supported on X and
let $B_{r}$ denote the neighborhood of $X$ at distance at most $r$. For any
$\varepsilon>0$ and short runtime $T$, there exists $r(\varepsilon,T)$ such
that :

$\displaystyle|E_{G}(T)-E_{B_{r(\varepsilon,T)}}(T)|\leq\varepsilon$ (16)

where $E_{\Lambda}(T)=\langle\psi^{\Lambda}(T)|O_{X}|\psi^{\Lambda}(T)\rangle$

Let us come back to our distance $1$ analysis of MaxCut on cubic graphs. This
corollary entails that one can pick a precision $\varepsilon$ and a time $T$
and obtain a distance $r(\varepsilon,T)$ such that for all balls of distance
$r(\varepsilon,T)$ around an edge, any completions of this ball into a full
cubic graph will not change the expected value of the energy of this edge by
more than $\varepsilon$. This gives us an effective (but not realistic) way to
find a graph-independent lower bound on $E_{k}^{\mathcal{G}}(T)$ up to an
additive error of $\varepsilon$:

  1. 1.

consider each type of distance $1$ neighborhood $\Omega_{k}$, for
$k\in\\{1,2,3\\}$,

  2. 2.

for each completion of $\Omega_{k}$ into a distance $r(\varepsilon,T)$ ball
$B_{r}$, compute $\langle\psi^{B}|O_{X}|\psi^{B}\rangle$,

  3. 3.

pick the lowest value $E_{k}^{\mathcal{B}}(T)=\min_{B\text{ s.t.
}X\in\Omega_{k}\subseteq B}\langle\psi^{B}|O_{X}|\psi^{B}\rangle,$ and output
$E_{k}^{\mathcal{B}}-\varepsilon$ as lower bound for $E_{k}^{\mathcal{G}}(T)$.

These estimations $E_{k}^{\mathcal{B}}-\varepsilon$ are tighter than the ones
in Section 3, basically thanks to the use of larger balls. Once equipped with
these values for each $k\in\\{1,2,3\\}$, we can use Eq. 11 to compute a
tighter lower bound than the one derived in Section 3 for the approximation
ratio $\rho_{mc}$. This algorithm is well defined but not practical because
there are exponentially many balls to enumerate w.r.t. the quantity
$r(\varepsilon,T)$, which might be quite large even for reasonably small
values of $T$ and of $\varepsilon$.

That being said, we still tried to numerically investigate the values we could
reach for $E_{k}^{\mathcal{B}}$ in the case of MaxCut. We wish to obtain the
minimum energies $E_{k}^{\mathcal{B}}$ for each of the three types of edges,
$k\in\\{1,2,3\\}$. Intuitively, these minimum energies are reached by edges
that are necessarily uncut by the optimal cut. Indeed, these edges see their
energies converge to 0 after the initial rise due to locality (experienced by
all edges). Thus, our strategy was to construct (small) balls $B_{k}$ for each
configuration $\Omega_{k}$ such that the energy of the observed edge quickly
goes to 0 after its expected initial rise. In order to accelerate the
convergence speed to 0, we enforced this condition via the adjunction of the
smallest possible odd cycles. Indeed, as we can see in Appendix 8, small
cycles converge faster to their target. The proposed balls $B_{k}$ for each
configuration $\Omega_{k}$ are shown in Fig. 3. We computed the energy of the
edge $\langle 1,2\rangle$ in each of these balls for $T\in[0,5]$ and used Eq.
11, giving us a ratio of 0.6963 at $T^{*}=3.15$. As mentioned above, this is
just a numerical estimate and by no mean a formal derivation. However, unless
some very non-monotonous behavior arises when growing the radius of these
balls, this is most likely an accurate estimate.

$\begin{array}[]{cccc}\leavevmode\hbox to68.28pt{\vbox
to68.28pt{\pgfpicture\makeatletter\hbox{\hskip
34.13933pt\lower-34.13933pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-1.62662pt}{0.0pt}\pgfsys@curveto{-1.62662pt}{3.03018pt}{-4.08301pt}{5.48657pt}{-7.11319pt}{5.48657pt}\pgfsys@curveto{-10.14337pt}{5.48657pt}{-12.59976pt}{3.03018pt}{-12.59976pt}{0.0pt}\pgfsys@curveto{-12.59976pt}{-3.03018pt}{-10.14337pt}{-5.48657pt}{-7.11319pt}{-5.48657pt}\pgfsys@curveto{-4.08301pt}{-5.48657pt}{-1.62662pt}{-3.03018pt}{-1.62662pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-7.11319pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-9.61319pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{28.45276pt}\pgfsys@curveto{5.48657pt}{31.48294pt}{3.03018pt}{33.93933pt}{0.0pt}{33.93933pt}\pgfsys@curveto{-3.03018pt}{33.93933pt}{-5.48657pt}{31.48294pt}{-5.48657pt}{28.45276pt}\pgfsys@curveto{-5.48657pt}{25.42258pt}{-3.03018pt}{22.96619pt}{0.0pt}{22.96619pt}\pgfsys@curveto{3.03018pt}{22.96619pt}{5.48657pt}{25.42258pt}{5.48657pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{25.23055pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{33.93933pt}{0.0pt}\pgfsys@curveto{33.93933pt}{3.03018pt}{31.48294pt}{5.48657pt}{28.45276pt}{5.48657pt}\pgfsys@curveto{25.42258pt}{5.48657pt}{22.96619pt}{3.03018pt}{22.96619pt}{0.0pt}\pgfsys@curveto{22.96619pt}{-3.03018pt}{25.42258pt}{-5.48657pt}{28.45276pt}{-5.48657pt}\pgfsys@curveto{31.48294pt}{-5.48657pt}{33.93933pt}{-3.03018pt}{33.93933pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-28.45276pt}\pgfsys@curveto{5.48657pt}{-25.42258pt}{3.03018pt}{-22.96619pt}{0.0pt}{-22.96619pt}\pgfsys@curveto{-3.03018pt}{-22.96619pt}{-5.48657pt}{-25.42258pt}{-5.48657pt}{-28.45276pt}\pgfsys@curveto{-5.48657pt}{-31.48294pt}{-3.03018pt}{-33.93933pt}{0.0pt}{-33.93933pt}\pgfsys@curveto{3.03018pt}{-33.93933pt}{5.48657pt}{-31.48294pt}{5.48657pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-31.67497pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.96619pt}{0.0pt}\pgfsys@curveto{-22.96619pt}{3.03018pt}{-25.42258pt}{5.48657pt}{-28.45276pt}{5.48657pt}\pgfsys@curveto{-31.48294pt}{5.48657pt}{-33.93933pt}{3.03018pt}{-33.93933pt}{0.0pt}\pgfsys@curveto{-33.93933pt}{-3.03018pt}{-31.48294pt}{-5.48657pt}{-28.45276pt}{-5.48657pt}\pgfsys@curveto{-25.42258pt}{-5.48657pt}{-22.96619pt}{-3.03018pt}{-22.96619pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-5.73407pt}{5.51675pt}\pgfsys@lineto{-1.37921pt}{22.936pt}\pgfsys@moveto{4.02101pt}{24.43175pt}\pgfsys@lineto{24.43175pt}{4.02101pt}\pgfsys@moveto{24.43175pt}{-4.02101pt}\pgfsys@lineto{4.02101pt}{-24.43175pt}\pgfsys@moveto{-1.37912pt}{-22.936pt}\pgfsys@lineto{-5.73398pt}{-5.51675pt}\pgfsys@moveto{-1.42662pt}{0.0pt}\pgfsys@lineto{22.76619pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-4.02101pt}{24.43175pt}\pgfsys@lineto{-24.43175pt}{4.02101pt}\pgfsys@moveto{-24.43175pt}{-4.02101pt}\pgfsys@lineto{-4.02101pt}{-24.43175pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to68.28pt{\vbox to82.51pt{\pgfpicture\makeatletter\hbox{\hskip
34.13933pt\lower-48.3657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.96619pt}{0.0pt}\pgfsys@curveto{-22.96619pt}{3.03018pt}{-25.42258pt}{5.48657pt}{-28.45276pt}{5.48657pt}\pgfsys@curveto{-31.48294pt}{5.48657pt}{-33.93933pt}{3.03018pt}{-33.93933pt}{0.0pt}\pgfsys@curveto{-33.93933pt}{-3.03018pt}{-31.48294pt}{-5.48657pt}{-28.45276pt}{-5.48657pt}\pgfsys@curveto{-25.42258pt}{-5.48657pt}{-22.96619pt}{-3.03018pt}{-22.96619pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{28.45276pt}\pgfsys@curveto{5.48657pt}{31.48294pt}{3.03018pt}{33.93933pt}{0.0pt}{33.93933pt}\pgfsys@curveto{-3.03018pt}{33.93933pt}{-5.48657pt}{31.48294pt}{-5.48657pt}{28.45276pt}\pgfsys@curveto{-5.48657pt}{25.42258pt}{-3.03018pt}{22.96619pt}{0.0pt}{22.96619pt}\pgfsys@curveto{3.03018pt}{22.96619pt}{5.48657pt}{25.42258pt}{5.48657pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{25.23055pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{33.93933pt}{0.0pt}\pgfsys@curveto{33.93933pt}{3.03018pt}{31.48294pt}{5.48657pt}{28.45276pt}{5.48657pt}\pgfsys@curveto{25.42258pt}{5.48657pt}{22.96619pt}{3.03018pt}{22.96619pt}{0.0pt}\pgfsys@curveto{22.96619pt}{-3.03018pt}{25.42258pt}{-5.48657pt}{28.45276pt}{-5.48657pt}\pgfsys@curveto{31.48294pt}{-5.48657pt}{33.93933pt}{-3.03018pt}{33.93933pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{33.93933pt}{-28.45276pt}\pgfsys@curveto{33.93933pt}{-25.42258pt}{31.48294pt}{-22.96619pt}{28.45276pt}{-22.96619pt}\pgfsys@curveto{25.42258pt}{-22.96619pt}{22.96619pt}{-25.42258pt}{22.96619pt}{-28.45276pt}\pgfsys@curveto{22.96619pt}{-31.48294pt}{25.42258pt}{-33.93933pt}{28.45276pt}{-33.93933pt}\pgfsys@curveto{31.48294pt}{-33.93933pt}{33.93933pt}{-31.48294pt}{33.93933pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-31.67497pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.96619pt}{-28.45276pt}\pgfsys@curveto{-22.96619pt}{-25.42258pt}{-25.42258pt}{-22.96619pt}{-28.45276pt}{-22.96619pt}\pgfsys@curveto{-31.48294pt}{-22.96619pt}{-33.93933pt}{-25.42258pt}{-33.93933pt}{-28.45276pt}\pgfsys@curveto{-33.93933pt}{-31.48294pt}{-31.48294pt}{-33.93933pt}{-28.45276pt}{-33.93933pt}\pgfsys@curveto{-25.42258pt}{-33.93933pt}{-22.96619pt}{-31.48294pt}{-22.96619pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-31.67497pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-14.22638pt}\pgfsys@curveto{5.48657pt}{-11.1962pt}{3.03018pt}{-8.7398pt}{0.0pt}{-8.7398pt}\pgfsys@curveto{-3.03018pt}{-8.7398pt}{-5.48657pt}{-11.1962pt}{-5.48657pt}{-14.22638pt}\pgfsys@curveto{-5.48657pt}{-17.25656pt}{-3.03018pt}{-19.71295pt}{0.0pt}{-19.71295pt}\pgfsys@curveto{3.03018pt}{-19.71295pt}{5.48657pt}{-17.25656pt}{5.48657pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-17.4486pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-42.67914pt}\pgfsys@curveto{5.48657pt}{-39.64896pt}{3.03018pt}{-37.19257pt}{0.0pt}{-37.19257pt}\pgfsys@curveto{-3.03018pt}{-37.19257pt}{-5.48657pt}{-39.64896pt}{-5.48657pt}{-42.67914pt}\pgfsys@curveto{-5.48657pt}{-45.70932pt}{-3.03018pt}{-48.16571pt}{0.0pt}{-48.16571pt}\pgfsys@curveto{3.03018pt}{-48.16571pt}{5.48657pt}{-45.70932pt}{5.48657pt}{-42.67914pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-45.90135pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{22.76619pt}{0.0pt}\pgfsys@lineto{-22.76619pt}{0.0pt}\pgfsys@moveto{-24.43175pt}{4.02101pt}\pgfsys@lineto{-4.02101pt}{24.43175pt}\pgfsys@moveto{4.02101pt}{24.43175pt}\pgfsys@lineto{24.43175pt}{4.02101pt}\pgfsys@moveto{28.45276pt}{-5.68657pt}\pgfsys@lineto{28.45276pt}{-22.76619pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-28.45276pt}{-5.68657pt}\pgfsys@lineto{-28.45276pt}{-22.76619pt}\pgfsys@moveto{-23.36656pt}{-25.90962pt}\pgfsys@lineto{-5.0862pt}{-16.76942pt}\pgfsys@moveto{0.0pt}{-8.53981pt}\pgfsys@lineto{0.0pt}{22.76619pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{5.0862pt}{-16.76952pt}\pgfsys@lineto{23.36656pt}{-25.90971pt}\pgfsys@moveto{23.36656pt}{-30.9959pt}\pgfsys@lineto{5.0862pt}{-40.1361pt}\pgfsys@moveto{-5.0862pt}{-40.136pt}\pgfsys@lineto{-23.36656pt}{-30.9958pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to68.28pt{\vbox to96.73pt{\pgfpicture\makeatletter\hbox{\hskip
34.13933pt\lower-48.3657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.96619pt}{0.0pt}\pgfsys@curveto{-22.96619pt}{3.03018pt}{-25.42258pt}{5.48657pt}{-28.45276pt}{5.48657pt}\pgfsys@curveto{-31.48294pt}{5.48657pt}{-33.93933pt}{3.03018pt}{-33.93933pt}{0.0pt}\pgfsys@curveto{-33.93933pt}{-3.03018pt}{-31.48294pt}{-5.48657pt}{-28.45276pt}{-5.48657pt}\pgfsys@curveto{-25.42258pt}{-5.48657pt}{-22.96619pt}{-3.03018pt}{-22.96619pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.96619pt}{28.45276pt}\pgfsys@curveto{-22.96619pt}{31.48294pt}{-25.42258pt}{33.93933pt}{-28.45276pt}{33.93933pt}\pgfsys@curveto{-31.48294pt}{33.93933pt}{-33.93933pt}{31.48294pt}{-33.93933pt}{28.45276pt}\pgfsys@curveto{-33.93933pt}{25.42258pt}{-31.48294pt}{22.96619pt}{-28.45276pt}{22.96619pt}\pgfsys@curveto{-25.42258pt}{22.96619pt}{-22.96619pt}{25.42258pt}{-22.96619pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{25.23055pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{33.93933pt}{0.0pt}\pgfsys@curveto{33.93933pt}{3.03018pt}{31.48294pt}{5.48657pt}{28.45276pt}{5.48657pt}\pgfsys@curveto{25.42258pt}{5.48657pt}{22.96619pt}{3.03018pt}{22.96619pt}{0.0pt}\pgfsys@curveto{22.96619pt}{-3.03018pt}{25.42258pt}{-5.48657pt}{28.45276pt}{-5.48657pt}\pgfsys@curveto{31.48294pt}{-5.48657pt}{33.93933pt}{-3.03018pt}{33.93933pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{33.93933pt}{-28.45276pt}\pgfsys@curveto{33.93933pt}{-25.42258pt}{31.48294pt}{-22.96619pt}{28.45276pt}{-22.96619pt}\pgfsys@curveto{25.42258pt}{-22.96619pt}{22.96619pt}{-25.42258pt}{22.96619pt}{-28.45276pt}\pgfsys@curveto{22.96619pt}{-31.48294pt}{25.42258pt}{-33.93933pt}{28.45276pt}{-33.93933pt}\pgfsys@curveto{31.48294pt}{-33.93933pt}{33.93933pt}{-31.48294pt}{33.93933pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{-31.67497pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{5}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-22.96619pt}{-28.45276pt}\pgfsys@curveto{-22.96619pt}{-25.42258pt}{-25.42258pt}{-22.96619pt}{-28.45276pt}{-22.96619pt}\pgfsys@curveto{-31.48294pt}{-22.96619pt}{-33.93933pt}{-25.42258pt}{-33.93933pt}{-28.45276pt}\pgfsys@curveto{-33.93933pt}{-31.48294pt}{-31.48294pt}{-33.93933pt}{-28.45276pt}{-33.93933pt}\pgfsys@curveto{-25.42258pt}{-33.93933pt}{-22.96619pt}{-31.48294pt}{-22.96619pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-28.45276pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-30.95276pt}{-31.67497pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{33.93933pt}{28.45276pt}\pgfsys@curveto{33.93933pt}{31.48294pt}{31.48294pt}{33.93933pt}{28.45276pt}{33.93933pt}\pgfsys@curveto{25.42258pt}{33.93933pt}{22.96619pt}{31.48294pt}{22.96619pt}{28.45276pt}\pgfsys@curveto{22.96619pt}{25.42258pt}{25.42258pt}{22.96619pt}{28.45276pt}{22.96619pt}\pgfsys@curveto{31.48294pt}{22.96619pt}{33.93933pt}{25.42258pt}{33.93933pt}{28.45276pt}\pgfsys@closepath\pgfsys@moveto{28.45276pt}{28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{25.95276pt}{25.23055pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{42.67914pt}\pgfsys@curveto{5.48657pt}{45.70932pt}{3.03018pt}{48.16571pt}{0.0pt}{48.16571pt}\pgfsys@curveto{-3.03018pt}{48.16571pt}{-5.48657pt}{45.70932pt}{-5.48657pt}{42.67914pt}\pgfsys@curveto{-5.48657pt}{39.64896pt}{-3.03018pt}{37.19257pt}{0.0pt}{37.19257pt}\pgfsys@curveto{3.03018pt}{37.19257pt}{5.48657pt}{39.64896pt}{5.48657pt}{42.67914pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{39.45692pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{7}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{-42.67914pt}\pgfsys@curveto{5.48657pt}{-39.64896pt}{3.03018pt}{-37.19257pt}{0.0pt}{-37.19257pt}\pgfsys@curveto{-3.03018pt}{-37.19257pt}{-5.48657pt}{-39.64896pt}{-5.48657pt}{-42.67914pt}\pgfsys@curveto{-5.48657pt}{-45.70932pt}{-3.03018pt}{-48.16571pt}{0.0pt}{-48.16571pt}\pgfsys@curveto{3.03018pt}{-48.16571pt}{5.48657pt}{-45.70932pt}{5.48657pt}{-42.67914pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-42.67914pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-45.90135pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{8}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.64113pt}{-7.11319pt}\pgfsys@curveto{2.64113pt}{-4.08301pt}{0.18474pt}{-1.62662pt}{-2.84544pt}{-1.62662pt}\pgfsys@curveto{-5.87563pt}{-1.62662pt}{-8.33202pt}{-4.08301pt}{-8.33202pt}{-7.11319pt}\pgfsys@curveto{-8.33202pt}{-10.14337pt}{-5.87563pt}{-12.59976pt}{-2.84544pt}{-12.59976pt}\pgfsys@curveto{0.18474pt}{-12.59976pt}{2.64113pt}{-10.14337pt}{2.64113pt}{-7.11319pt}\pgfsys@closepath\pgfsys@moveto{-2.84544pt}{-7.11319pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.34544pt}{-10.3354pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{9}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \par{{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{22.76619pt}{0.0pt}\pgfsys@lineto{-22.76619pt}{0.0pt}\pgfsys@moveto{-28.45276pt}{5.68657pt}\pgfsys@lineto{-28.45276pt}{22.76619pt}\pgfsys@moveto{-23.36656pt}{30.9959pt}\pgfsys@lineto{-5.0862pt}{40.1361pt}\pgfsys@moveto{5.0862pt}{40.136pt}\pgfsys@lineto{23.36656pt}{30.9958pt}\pgfsys@moveto{26.34087pt}{23.17288pt}\pgfsys@lineto{2.1119pt}{-37.39926pt}\pgfsys@moveto{-5.0862pt}{-40.136pt}\pgfsys@lineto{-23.36656pt}{-30.9958pt}\pgfsys@moveto{-26.34087pt}{-23.17288pt}\pgfsys@lineto{-2.1119pt}{37.39926pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{28.45276pt}{22.76619pt}\pgfsys@lineto{28.45276pt}{5.68657pt}\pgfsys@moveto{28.45276pt}{-5.68657pt}\pgfsys@lineto{28.45276pt}{-22.76619pt}\pgfsys@moveto{23.75433pt}{-25.2493pt}\pgfsys@lineto{1.85298pt}{-10.31656pt}\pgfsys@moveto{-6.16812pt}{-2.49832pt}\pgfsys@lineto{-25.13008pt}{23.83789pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-28.45276pt}{-5.68657pt}\pgfsys@lineto{-28.45276pt}{-22.76619pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{5.0862pt}{-40.136pt}\pgfsys@lineto{23.36656pt}{-30.9958pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>B_{1}&B_{2}&B_{3}&\text{Simulations}\end{array}$

Figure 3: Balls $B_{k}$ of 3-regular graphs around the edge $\langle
1,2\rangle$ in corresponding configuration $\Omega_{k}$. On the right,
evolution of the edge $\langle 1,2\rangle$’s energy against $T$, E(B1) in
blue, E(B2) in red and E(B3) in green.

This construction is a truly local (distance 1) analysis of QA, and computing
the values of $E_{k}^{\mathcal{B}}$ would produce the best possible estimate
of QA’s performances in this setting. It thus seems reasonable to compare this
ratio to one obtained for other truly local algorithms. The other known bounds
in this setting are depth-1 QAOA ($\rho=0.6925$) [8] and Hastings’ (classical)
local algorithm ($\rho=0.6980$) [13]. If our bound is verified, this would
show that a QA in time $T^{*}=3.15$ outperforms depth-1 QAOA. Additionally, if
the bound is tight, Hastings’ classical algorithm still beats QA as analyzed
in this regime.

###  4.2 (Non) Tightness of our LR bound

The analysis of the LR bound tightness or non-tightness depends on the runtime
$T$ and the size of $\Omega$, more precisely on its radius $p$. We study the
dependency in $T$. We can consider the tightness at $T_{mc}$ where we reach
the best ratio using LR bound but we can also wonder why we do not reach
something higher for larger $T$ up to $T^{*}$.

At $T_{mc}$, without considering LR bound, i.e. using the final energy of (5),
we reach an approximation ratio of 0.635 still with $n_{1}=n_{2}=0$, so it
gives a relative error of $6.6\%$. To understand how to improve our ratio up
to $T^{*}$, we are able to point out which lose have the more impact when
deriving the bound. There are two steps where we neglect information. The
first one is when we neglect the initial state $|\psi_{0}\rangle$ at the
beginning of section 2.3 i.e. between
$\delta_{1}(G)=|\langle\psi^{G}|O_{X}|\psi^{G}\rangle-\langle\psi^{\Omega_{3}}|O_{X}|\psi^{\Omega_{3}}\rangle|$
and
$\delta_{2}(G)=\lVert(U_{0,t}^{G})^{\dagger}O_{X}U_{0,t}^{G}-(U_{0,t}^{\Omega_{3}})^{\dagger}O_{X}U_{0,t}^{\Omega_{3}}\rVert$
where here $O_{X}$ represents the observable $M_{ij}$ of an edge in $G$. The
second one is when proving Proposition 1 we use the triangular inequality with
the operator norm and the integral, i.e., between $\delta_{2}(G)$ and
$LR_{O_{X}}^{\Omega_{3}}$.

To illustrate the latter point and the non-tightness of the LR-type bound
used, we plotted in Fig. 4 these three quantities
$\delta_{1}(G)\leq\delta_{2}(G)\leq LR_{O_{X}}^{\Omega_{3}}$ for a non-trivial
example.

12345678910 (a)

(b)

Figure 4: On the left (a), $G_{10}$, worst edge configuration for LR bound
centered on $\langle 1,8\rangle$. On the right, $\delta_{1}$ and $\delta_{2}$
for $G_{10}$ aside with LR3=$LR_{O_{X}}^{\Omega_{3}}$ for $O_{X}=M_{1,8}$ The
dotted lines indicate the time $T_{mc}$ for which we obtain the value of 0.59
and $T^{*}$.

The LR bound used to derived the approximation ratio is interesting up to
$T_{mc}$, where there is a loss of only $6.6\%$. But we cannot evolve longer
than this runtime because it diverges too quickly. We see that $\delta_{2}$
also diverges but not $\delta_{1}$. This means that neglecting the initial
state strongly deteriorates the bound.

##  5 Conclusion

The general method described in this article provides tools to derive
approximation ratios for quantum annealing on combinatorial problems, with
very short running time. The locality in quantum annealing given by the Lieb-
Robinson bound allows combinatorial arguments over the regular (and in
particular cubic) graphs, of the same flavour as the ones used for QAOA. We
emphasize that the theoretical arguments hold for regular graphs of any fixed
degree, and sometimes any bounded degree graphs, although we chose here to
present the numerical results for degree 3 only. E.g., for problem MaxCut on 4
(resp 5) regular graphs we obtain bounds of 0.57 (resp. 0.56), with shorter
annealing times. We applied this technique to MaxCut and MIS to show how it
can be used to access the numerical values of the approximation ratios for
cubic graphs. We then discussed the non-tightness of the Lieb-Robinson bound
using MaxCut and drew some "worst" cases graphs to argue that QA can probably
reach an approximation ratio for this problem, significantly better than the
one we can actually prove.

Let us suggest some further research directions. In this paper, we developed
tools to retrieve locality in the standard formulation of adiabatic quantum
computing and use this relaxed locality to deduce lower bounds on the
performances of QA for MaxCut and MIS on cubic graphs. There are two main
directions to improve upon these results. The first direction would be to
refine the analysis of constant time QA using less restrictive locality
arguments, as we started to do in Appendix 7 for MaxCut.

The other direction would be to improve the algorithm itself as quantum
annealing allows more degrees of freedom to work on the efficiency. This
improvement can take many shapes.

We started our QA with a simple initial state, corresponding to the uniform
superposition of all bitstrings of length $n$. Nevertheless, given that the LR
bound used here does not depend on this initial state, there may be more
suitable choices yet to explore. Similarly, to boost the results of
approximation with QA, one can modify directly the Hamiltonians. We can choose
to work with a different initial Hamiltonian $H_{0}$, e.g., the ones of [5]
who deal with bit swaps, whereas here we used bit flips. We can also change
the target Hamiltonian of the evolution without changing the objective
function. For example, in MIS, one can make a quantum evolution without the
Hamming weight part [7]. Indeed, the state of minimal energy remains the same
and we keep looking at the expected value of the total problem Hamiltonian
reached by the final state of this particular evolution. The approximation
ratio slightly improves up to 0.35.

Another lead which has been suggested by the physics field of Shortcut to
Adiabadicity (STA) [11] encourages the use of a perturbative Hamiltonian to
accelerate the evolution toward the adiabatic, optimal behavior. For example,
it seems that a perturbative Hamiltonian of the form $H_{e}=[H_{0},H_{1}]$ is
a good initial choice as it increases the approximation ratio and decreases
the time at which it is obtained.

Eventually, it is important to notice that one should not compare directly
QAOA and QA developed here because, unlike QAOA, we did not try to optimize
several parameters and degrees of freedom available. If we allow arbitrary
trajectory for QA, QAOA reduces to a particular case of QA. This raises the
natural question of whether QA can beat QAOA for a particular choice of
schedule. Until [4], QAOA trajectory, also called "bang-bang", was thought as
the optimal schedule from the optimal control theory point of view. We know
now that a "bang-anneal-bang" schedule, meaning that the schedule is time
continuous between the two bangs, can be better, but also harder to find. All
this to say that there is still a wide search space to improve QA, and we
strongly believe that these directions can be combined with our LR based
technique in order to obtain better approximation ratios.

## References

  * [1] Tameem Albash and Daniel A. Lidar.  Adiabatic quantum computation.  Reviews of Modern Physics, 90(1), Jan 2018.
  * [2] Boris Altshuler, Hari Krovi, and Jeremie Roland.  Anderson localization makes adiabatic quantum optimization fail.  Proc Natl Acad Sci U S A., 107(28), Jun 2010.
  * [3] B Apolloni, C Carvalho, and D de Falco.  Quantum stochastic optimization.  Stochastic Processes and their Applications, 33(2):233–244, 1989\.
  * [4] Lucas T. Brady, Christopher L. Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V. Gorshkov.  Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems.  Physical Review Letters, 126(7), Feb 2021.
  * [5] A. Childs, E. Farhi, J. Goldstone, and S. Gutmann.  Finding cliques by quantum adiabatic evolution.  Quantum Information and Computation, 2(3), Apr 2002.
  * [6] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda.  A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem.  Science, 292(5516):472–475, Apr 2001.
  * [7] Edward Farhi, David Gamarnik, and Sam Gutmann.  The quantum approximate optimization algorithm needs to see the whole graph: A typical case.  arXiv preprint arXiv:2004.09002, 2020.
  * [8] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm, 2014.
  * [9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser.  Quantum computation by adiabatic evolution, 2000.
  * [10] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery.
  * [11] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J.G. Muga.  Shortcuts to adiabaticity: Concepts, methods, and applications.  Reviews of Modern Physics, 91(4), Oct 2019.
  * [12] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low.  Quantum algorithm for simulating real time evolution of lattice hamiltonians.  SIAM Journal on Computing, Jan 2021.  Published online. Special issue FOCS 2018.
  * [13] M. B. Hastings.  Classical and quantum bounded depth approximation algorithms, 2019.
  * [14] Tadashi Kadowaki and Hidetoshi Nishimori.  Quantum annealing in the transverse ising model.  Physical Review E, 58(5):5355–5363, Nov 1998.
  * [15] Andrew Lucas.  Ising formulations of many NP problems.  Frontiers in Physics, 2:5, 2014.
  * [16] Ali Hamed Moosavian, Seyed Sajad Kahani, and Salman Beigi.  Limits of short-time quantum annealing, 2021.
  * [17] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information: 10th Anniversary Edition.  Cambridge University Press, 2011.
  * [18] Jukka Suomela.  Survey of local algorithms.  ACM Comput. Surv., 45(2):24:1–24:40, 2013.
  * [19] Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov.  Locality and digital quantum simulation of power-law interactions.  Physical Review X, 9(3), Jul 2019.

##  6 Proof of Proposition 1

We note $U_{I}(t)=(U_{0,t}^{\Omega})^{\dagger}U_{0,t}^{G}$, the evolution in
the interaction picture of
$V_{I}(t)=(U_{0,t}^{\Omega})^{\dagger}V(t)U_{0,t}^{\Omega}$ where the
perturbation $V$ is $V(t)=H_{G}(t)-H_{\Omega}(t)$

$\displaystyle\left\lVert(U_{0,t}^{G})^{\dagger}O_{X}U_{0,t}^{G}-(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega}\right\rVert$
$\displaystyle=\left\lVert\int_{0}^{t}ds\frac{d}{ds}\left(U_{I}(s)^{\dagger}(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega}U_{I}(s)\right)\right\rVert$
$\displaystyle=\left\lVert\int_{0}^{t}ds\left(U_{I}(s)^{\dagger}\left[(U_{0,t}^{\Omega})^{\dagger}O_{X}U_{0,t}^{\Omega},V_{I}(s)\right]U_{I}(s)\right)\right\rVert$
$\displaystyle=\left\lVert\int_{0}^{t}ds\left((U^{G}_{0,s})^{\dagger}\left[(U_{s,t}^{\Omega})^{\dagger}O_{X}U_{s,t}^{\Omega},V(s)\right]U^{G}_{0,s}\right)\right\rVert$
$\displaystyle=\left\lVert\int_{0}^{t}ds\frac{s}{T}\left((U^{G}_{0,s})^{\dagger}\left[(U_{s,t}^{\Omega})^{\dagger}O_{X}U_{s,t}^{\Omega},H_{1,\partial\Omega}\right]U^{G}_{0,s}\right)\right\rVert$

The last equality is true because in $V$ we have every term in $\bar{\Omega}$,
all the interactions terms between $\Omega$ and $\bar{\Omega}$ and the terms
between two nodes of $\Omega$ that are not considered in $\Omega$. The only
interactions terms in $\partial\Omega$ lie in $H_{1}$ and we write it
$H_{1,\partial\Omega}$. Thus,
$V(s)=H_{G}(s)-H_{\Omega}(s)=H_{\bar{\Omega}}+\frac{s}{T}H_{1,\partial\Omega}$.
Because $X\subset\Omega$, the left term in the commutator is strictly
supported by $\Omega$, so the term with $H_{\bar{\Omega}}$ cancels out and we
are left with the last line. The factor $\frac{s}{T}$ comes from the linear
interpolation we are working with but it can be any chosen schedule. The final
result uses the triangular inequality with the norm and integral and that
$U_{0,s}^{G}$ is a unitary operator.

##  7 Detailed intuitions

Here we detail the intuition on QA evolution apply to MaxCut. The ratio
obtained is not to be compared to the ones presented in this paper because we
do not restrict the analysis of QA as a local algorithm anymore. We still
investigate what QA can expect to reach in a short constant runtime.

With more informal reasoning, we think that short-constant-runtime QA can
reach an approximation ratio of 0.73. One can try to conduct a similar
reasoning as the one hinted for the cycle in Appendix 8 which presents an easy
and very illustrative case to grasp the notion of locality in short runtime.
This latter case drives us to think that studying only small graphs is enough
to have a clear idea of the approximation ratio for small $T$. We decide to
focus on bipartite, edge-transitive graphs, i.e. the graphs have exactly the
same neighborhood at any distance for each edge. So we look at different
neighborhoods at different distances and experimentally select the "worst"
one. Then, we construct graphs such that each edge has this specific
neighborhoods for different distances. Intuitively speaking, we note that
adding a cycle helps because it reduces the number of nodes lying at a given
distance from an edge. For similar reasons, configurations obtained from
$\Omega_{1}$ or $\Omega_{2}$ do not seem critical for the approximation ratio.
And because we are working with small enough graphs (at small enough $T$), odd
cycles create a non negligible offset at the beginning, i.e. the random guess
is already strictly better than 0.5. In this way, we construct 3-regular
graphs where each edge have a neighborhood similar to a double binary tree of
depth 1,2 and 3. Indeed, experimentally, these neighborhoods produce the
slowest convergence of the middle edge’s energy toward its optimal value (1 in
the case of bipartite graph). These graphs are denoted $G_{6}$, $G_{14}$ and
$G_{30}$, the index corresponding to the number of their nodes (Fig. 5).

123456 (a)

1234567891011121314

(b)

123456789101112131415161718192021222324252627282930

(c)

Figure 5: Worst graphs from a QA point of view in short running time. (a)
$G_{6}$ with minimum cycle size $=4$. (b) $G_{14}$ with minimum cycle size
$=6$. (c) $G_{30}$ with minimum cycle size $=8$. Each edge has exactly the
same neighborhood. Figure 6: Ratio reached by $G_{6}$ (blue line), $G_{14}$
(orange line) and $G_{30}$ (red) against running time $T$. The black dotted
lines shows when there is a difference of at least 0.005.

In Fig. 6, we plot the approximation ratio reached by these graphs as a
function of $T$. Until the first dotted line, all 3-regular graphs up to 20
vertices that we tested have a ratio that is above or equal to the blue and
orange curves. Then between the two dotted lines, we have the first split, QA
had enough time to make the difference between cycles of size 4 and larger
cycles. But still, until the second dotted line, all tested graphs have a
ratio greater or equal than the orange curve (or red). Then, we have the
second split, the quantum system can access information that is at distance 3
in the graph and thus can make the difference between $G_{14}$ and $G_{30}$.

From these observations, we conclude that QA with linear interpolation
probably reaches an approximation ratio for MaxCut on 3-regular graphs of 0.73
(minus an arbitrary $\varepsilon$) at $T_{1}=3.47$ and, moreover, from 0 to
$T_{1}$, the approximation ratio is described by the orange curve. This value
is the same as the middle edge energy of $\Omega_{3}$ minus 0.005 at $T_{1}$.

##  8 Cycle case

The 2-regular graphs represented by cycles is a very illustrative case to get
the intuition of the locality in QA. It also clarifies the construction of the
hardest cubic graphs (bipartite graphs with large even cycles). In Fig. 7, we
plot the approximation ratio against the runtime $T$ for even cycles (left)
and odd cycles (right). The first observation is that odd cycles converge
faster to 1 than even cycles and they start with an offset at $T=0$. Indeed,
they do not have a clean cut so the random guess for a cut gives a ratio above
0.5 starting the evolution at $0.5\frac{n}{n-1}$. We understand that having
odd cycles helps QA to decide faster.

Figure 7: Approximation ratio reached by even cycles (left) and odd cycles
(right). The dotted lines indicate the $5.10^{-3}$ splitting.

###### Remark 1

Because cycles are edge transitives, the ratio plot here is also the
expectation value of the observable on one edge.

Figure 8: Information travel of the observable in shaded blue during time $T$.
After this time, QA can make the difference between these two cycles.

Looking closely at the even cycles, we see that until some time $T$ all ratios
follow the same tract. At some point, the smallest cycle splits to go toward 1
faster, the others keep the same trend. Then this splitting scheme repeats
again with the left cycles. The dotted lines indicate when there is more than
$0.005$ difference between cycles of size $2n$ and $2n+2$. This conveys the
idea that up to some time, QA does not have time to see far in the graph to
make the decision. In this case, we can even tell "illustratively" how deep
the information travels in the graph like in Fig. 8.