domain: info math

text:
Geoffroy Caillat-Grenier

Spectral bound for random Schreier graphs of GL k (F 2 )

In this paper we discuss potentially practical ways to construct expander graphs with good spectral properties and a compact description. We consider variations of a constructions that is simple to implement in practice, and develop techniques that seem to be applicable to graphs of feasible size. More specifically, we focus on expander graphs defined as random Schreier graphs of the general linear group over the finite field of size two. We perform numerical experiments and observe that such constructions produce with high probability Ramanujan graphs that can be useful for practical applications.

To find a theoretical explanation of the observed experimental results and prove an upper bound for the expected second largest eigenvalue of the sampled graphs, we use the method of moments. We focus on the settings for which it seems difficult to study the asymptotic behaviour of large graphs but it is possible to provide non-trivial bounds for graphs of relatively small size (interesting for practical applications).

The main contribution of this work is twofold. First, we study families of expander graphs that are, so to speak, pseudo-random (i.e., each graph can be efficiently reconstructed from a short random seed); this approach takes an intermediate position between explicit (deterministic) constructions and the conventional theory of random graphs. Second, we adjust and optimise theoretical bounds not for the limiting behaviour of graphs but for the values of parameters that become meaningful in practical applications (when the whole graph or at least the indices of its vertices can be stored in computer memory).

Introduction

The regular expander graphs have been extensively studied for several decades and applications can be found in a wide variety of fields, see [START_REF] Hoory | Expander graphs and their applications[END_REF]. It is remarkable that the expansion properties, which are of combinatorial nature, are connected to some spectral properties of the adjacency matrix of the graph, namely the gap between the two largest magnitude eigenvalues (the spectral gap). A large spectral gap means "good" expansion, mixing, and connectivity properties. Observe also that the second largest eigenvalue for some particular graph can be computed efficiently, while a direct computation of the Cheeger constant (as well as other combinatorial parameters characterising the properties of expansion and connectivity) would require an exponential search over all subsets of the graph's vertices. At the same time, we should notice that the spectral technique has its limitations, and computing the second largest eigenvalue cannot give better guarantee than an expansion ratio greater than half of the degree ( [START_REF] Kahale | Eigenvalues and expansion of regular graphs[END_REF]).

In a regular graph of degree d (called d-regular graph) with n vertices, the largest magnitude eigenvalue of its adjacency matrix is always d. Since the graph is undirected, the matrix is symmetric, hence all eigenvalues are real. We ). A famous result due to Friedman ( [START_REF] Friedman | A proof of alon's second eigenvalue conjecture[END_REF], see also [START_REF] Bordenave | A new proof of Friedman's second eigenvalue theorem and its extension to random lifts[END_REF] for a shorter proof) states that almost all d-regular graphs have second largest eigenvalue smaller than 2 √ d -1 + ϵ. This upper bound matches asymptotically the lower bound which makes it optimal in some sense. Thus, most graphs have second largest eigenvalue as small as one can hope for.

The aforementioned results suggest that in practice one can produce a random expander graphs and use it in applications. However, producing such a graph, keeping it in memory and manipulations with it may require much resources. Explicit constructions constructions of expanders (see e.g. [START_REF] Alexander Lubotzky | Ramanujan graphs[END_REF], [START_REF] Dinitz | Explicit expanding expanders[END_REF], [START_REF] Alon | Explicit expanders of every degree and size[END_REF], [START_REF] Morgenstern | Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q[END_REF], [START_REF] Reingold | Entropy waves, the zig-zag graph product, and new constant-degree expanders[END_REF], [START_REF] Mohanty | Explicit near-Ramanujan graphs of every degree[END_REF]) may seem more attractive since we don't need to keep such a graph in memory: neighbours of each vertex can be computed from scratch when needed. However, this approach has its own disadvantages. Some explicit constructions of graph of expanders lack optimality of parameters; they often imply constraints on the degree and the implementation can be difficult in practice. Besides, "polynomial time" algorithms and "asymptotic bounds" involved in these constructions may be good in theory but less successful in practice, for graphs of reasonably small size.

To overcome the mentioned difficulties, in this paper we use an approach that is intermediate between explicit constructions of expanders and purely random graphs. We consider families of graphs that are in some sense pseudo-random. Such a graph can be specified by a "seed" that is rather short compared with the size of the graph; the efficiency of the construction means that given the seed we can compute very efficiently the list of neighbours for every given vertex. More specifically, we take for this purpose some families of Schreier graphs, see below. We start our work with numerical experiments and show that typical graphs in these families enjoy good spectral properties. Then we analyse the properties of these graphs with theoretical tools, which allows us to explain partially the observed results.

Our theoretical analysis also has certain peculiarities. Unlike most works on expander graphs, we pay little attention to asymptotic estimates. Indeed, are ultimate aim to explain eventually the behaviour of (pseudo)random graphs of graspable size, while the remainder terms in typical asymptotic bounds become reasonably small only for astronomically large graphs. Instead, we focus on the techniques that can be used for graphs of comparatively small size (mostly with 2 10 to 2 200 vertices, which seems to be relevant for most practical applications). While asymptotic bounds need to be somewhat elegant (otherwise they would be too hard to analyse), we can afford to use complex and hideous formulas that still allow to do calculations for specific values of the parameters.

Models of random and pseudo-random graphs

Now we proceed with a more formal description of random graph models. There exist several such models, see, e.g. [START_REF] Wormald | Models of Random Regular Graphs[END_REF]. Our interest will focus on the permutation model. Definition 1.1 (Permutation model). Select randomly and independently d elements {π 1 , . . . π d } of the symmetric group over the set {1, . . . , n}. A 2d-regular graph on n vertices in the permutation model is then constructed as follows: connect every vertex i with the vertex π j (i) for every j ∈ [ [1, d]].

The obtained graph is undirected, and every vertex i will be connected to π j (i) and π -1 j (i) for all j ≤ d. We allow multiple edges and self-loops. Observe that a randomly chosen permutation π i requires O(log(n!)) bits to keep it in the memory of a computer. A description of a random graph sampled in the permutation model occupies Θ(dn log n) bits of information (substantially, we have to store for each vertex the list of its neighbours, and in general there is no way to compress such a naive representation).

In this model, it is known that most of graphs have a nearly optimal spectral gap (in [START_REF] Friedman | A proof of alon's second eigenvalue conjecture[END_REF] it is proven that almost all graphs have second largest magnitude eigenvalue smaller than 2 √ 2d -1 + ϵ). Thus, the procedure of sampling a random graph will give us with high probability an expander. The argument that we suggest in this paper is inspired by the proof of a similar but weaker statement by Broder and Shamir: Proposition 1 ( [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF]). Let G be a 2d-regular undirected graph on n vertices in the permutation model. Let λ 2 be the second largest magnitude eigenvalue of its symmetric adjacency matrix. Then

E(|λ 2 |) = O(d 3 4 )
as n goes to infinity.

In what follows we deal with a more algebraic model of random graphs (which seems to be more convenient from the practical view point). Let us proceed with the definition of a Schreier graph. Definition 1.2 (Random Schreier graphs). Let H be a group acting transitively on a set X. We denote h.x ∈ X the product of the action of h ∈ H on x ∈ X. Let S be a random multiset of elements of H of d elements. Then the Schreier (undirected) graph

G = Sch(H ⟲ X, S)
is a 2d-regular graph of size |X| whose edges are (x, s.x) for x ∈ X and s ∈ S.

One can notice that a graph from the permutation model is also a Schreier graph of the symmetric group on n elements.

We are motivated by the result about random Schreier graphs expansion properties in [START_REF] Christofides | Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales[END_REF], which generalises the theorem on Cayley graphs proven in [START_REF] Alon | Random cayley graphs and expanders[END_REF]. A similar result was proven recently in [START_REF] Sabatini | Random schreier graphs and expanders[END_REF]: Proposition 2 ( [START_REF] Sabatini | Random schreier graphs and expanders[END_REF]). Let H be a group, X a set on which H is acting transitively and S a multiset of d randomly chosen elements of H and their inverses. Let G = Sch(H ⟲ X, S). The second largest eigenvalue of the associated normalised adjacency matrix is denoted µ 2 . For every ϵ > 0, there exist a constant c ϵ such that for d = c ϵ log |X| we get

E(|µ 2 |) < ϵ
where the expectation is taken over all random multisets S.

The bound in Proposition 2 may look too weak (ideally, we would like to bound |µ 2 | for a d-regular graph by (2

√ d -1 + ϵ)/d).
However, it applies to a very large class of Schreier graphs. One may hope to prove stronger bound for a more restricted family of graphs.

The main construction. We will focus on Schreier graphs of H = GL k (F 2 ) acting on X = (F k 2 ) * by matrix-vector multiplication. This construction is, in some ways, similar to the permutation model -it is actually the permutation model restricted to the permutations that can be represented by an invertible matrix over F 2 . Observe that this construction is very simple and convenient for practical applications. Indeed, vertices of this graph are all strings of k zeros and ones (except for the single string that consist of k zeros). The elements of S are d non-singular (invertible) matrices sampled uniformly and independently from H and their inverses. To find a neighbour of a vertex v induced by s ∈ S, we simply multiply the column-vector v by the matrix s.

Let us observe that a representation of a random Schreier graph is much more compact than a representation of a random graph from the general permutation model. Indeed, in order to specify a permutation on n vertices, O(n log n) bits are needed, whereas only O(k 2 ) = O(log 2 n) bits are necessary to specify an invertible matrix in our finite field. By analogy with pseudo-random generators, one may call these graphs pseudo-random, since the random seed determining the entire graph is much shorter than the size of incidence matrix or the list of all edges.

It remains to verify that graphs from the presented constructions are typically good spectral expanders. We will see that, due to numerical experiments, this is indeed the case for most graphs from these families (with reasonably chosen parameters). For relatively small graphs (e.g., with n ∼ 10 4 vertices, when we are able to produce completely the matrix of a graph and compute its eigenvalues with a computer) the experimental results might be quite enough for application. Indeed, we can sample a random set S, then verify numerically that the graph corresponding to this S is indeed a good expander, and then plug this instance of a graph in the application.

However, most of this paper is devoted to the attempts to get theoretical bounds for the families of graphs discussed above. Why do we need theoretical bounds for the spectral gap of these (pseudo)random graphs? One reason is purely theoretical: we would like to eventually explain the phenomena that we observe in numerical experiments. Another reason is more practical. In applications we may need "strongly explicit" expanders with pretty large number of vertices (e.g., with n ∼ 2 200 ), so that we cannot produce the entire matrix of the graph, but we still can keep in the memory of a computer an index of one vertex and we can compute efficiently indices of its neighbours. In this case, we cannot compute numerically the spectrum of the graph. So it would be helpful to have a theoretical result saying that a randomly chosen graph from the family G with a very high probability has a small enough second eigenvalue. Although our theoretical results only apply to finite fields of size 2, experimental results show that the construction can be suitable for bigger fields (see Figures 2 and3).

All of this led us to try to adapt the proof in [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF] (though it ended up being quite different) to get a bound on the expected second largest eigenvalue of the adjacency matrix of the graphs obtained. We prove the following statement:

Theorem 1. Let G = Sch(GL k (Z 2 ) ⟲ (Z k
2 ) * , S) be a graph of size n = 2 k -1 and whose degree is 2d = 2|S|, with k ≤ 2. Let µ 2 be the second largest eigenvalue of its normalised adjacency matrix. Consider the following recursive relation:

X q (c, l, d) =        1 if c = 0 and l = 0 0 if q > l ⌊ l q ⌋ i=c d i 2 q q! i l! (l-qi)! X q+1 (0, l -qi, d -i) otherwise. We set x 3 (i) = X 3 (1, 2m -2i, d -i) and x 4 (i) = X 4 (0, 2m -2i, d -i).
Then, for all integer m,

E(|µ 2 |) ≤ 1 2d 2m n m i=1 d i (2m)! (2m -2i)! (2 i -1)(x 3 (i) + x 4 (i)) 2 n + (x 3 (i) + x 4 (i)) 1 n + 2 i (i + 1)! x 3 (i) 5 n + x 4 (i) + X 1 (1, 2m, d) 1 n + x 3 (0) 5 n + x 4 (0) -1 1 2m
.

The bound (1) looks messy, and the asymptotic analysis may be difficult. However, this formula becomes useful when we need to calculate (with help of a computer) a bound for a specific graph of relatively small size (e.g., less than 2 200 vertices). For a specific graph G, we choose m in such a way that (1) gives the strongest bound possible for E(|µ 2 |). Though this big formula is fairly hard to analyse, it is easy to compute it numerically. We have been able to check that this gives a meaningful and non trivial bound for 2m close to k. This result is less general than Proposition 2, but it gives stronger and more explicit bounds for certain specific values of parameters. Nevertheless, an asymptotic study of its behaviour might be interesting. However, this is not done in this paper.

A construction of pseudo-random bipartite expanders

The construction explained above can easily be adapted to obtain bipartite dregular graphs of 2n vertices (n in each partition, n = 2 k -1). In such a graph, each vertex of the first partition is labeled the same way that of the second, by a vector in (F k 2 ) * . We have two ways of constructing the edges. The first way is the following. We select uniformly at random d matrices of GL k (F p ) that form a multiset D. Then we connect each vertex x from the first partition to two vertices of the second partition: s.x and s -1 .x, with s ∈ D. This way, we obtain a bipartite 2d-regular graph. Here the degree of the graph needs to be even, as in non bipartite graphs from our construction. The main interest of this approach is that we can obtain the same bound for the second largest eigenvalue as in Theorem 1 with very little additional work.

In order to obtain bipartite regular graphs of odd degree, we can take a slightly different setting. Once we have our multiset D, we connect every x in the first partition to s.x in the second one. This gives a d regular bipartite graph denoted

G = Sch BP (GL k (F 2 ) ⟲ (F k 2 ) * , D).
For this family of graphs the proof of Theorem 1 does not apply directly, but we can adapt it in order to get similar bounds. We prove the following statement: and|(F k 2 ) * | = n. Let µ 2 be the second largest magnitude eigenvalue of its normalised adjacency matrix. Consider the relation

Theorem 2. Let G = Sch BP (GL k (F 2 ) ⟲ (F k 2 ) * , D) with k ≤ 2, |D| = d,
Y q (c, l, d) =      1 if c = 0 and l = 0 0 if q > l ⌊ l q ⌋ i=c d i (q!) -i l! (l-qi)! Y q+1 (0, l -qi, d -i) otherwise. We set y 3 (i) = Y 3 (1, 2m -2i, d -i), y 4 (i) = Y 4 (0, 2m -2i, d -i). Then, E(|µ 2 |) ≤ 1 d 2m n 1 d 2m m i=1 d i 1 2 i (2m!) (2m -2i)! 2 i (i + 1)! y 3 (i) 5 n + y 4 (i) + Y 1 (1, 2m, d) 1 n + Y 2 (1, 2m, d) 2 n + y 3 (0) 5 n + y 4 (0) -1 1 2m
.

And again, the expression in (2) is difficult to analyse, but it helps to compute concrete bounds for graphs with some specific values of parameters. The expression in (2) is only slightly weaker than that in (1) (see Section 2). Moreover, it seems that the optimal value of 2m is the same in both theorems.

So far we discussed regular bipartite graphs, where all vertices have the same degree. In bipartite biregular graphs, the degree is the same for every vertex in the same partition, but it can be different from one partition to the other. These graphs are of interest for many applications in computer science and in coding theory (see, e.g., [START_REF] Sipser | Expander codes[END_REF], [START_REF] Zemor | On expander codes[END_REF]), and good spectral properties are often needed. We can adapt the construction above to get such graphs. Assume we need a graph with degree d 1 in the left partition whose size is n 1 , and d 2 in the right one, of size n 2 , such that n 1 d 1 = n 2 d 2 and n 2 ≤ n 1 . To achieve that, construct a graph as previously and merge every γ = d 2 /d 1 vertex on the right side (taking them in an arbitrary order). We denote such a graph

G = Sch BP (GL k (F p ) ⟲ (F k p ) * , D, γ). √ d 1 -1 + √ d 2 -1:
it has been proven that the second largest magnitude eigenvalue cannot be much smaller than this quantity ( [START_REF] Ing | Spectra of regular graphs and hypergraphs and orthogonal polynomials[END_REF]) and not much larger in most of the cases ( [START_REF] Brito | Spectral gap in random bipartite biregular graphs and applications[END_REF]). We prove the following statement, which is a corollary of Theorem 2:

Corollary 1. Let G ′ = Sch BP (GL k (F 2 ) ⟲ (F k 2 ) * , D, γ) with |D| = d 1 .
Let d 2 = γd 1 and let λ 2 be the second largest magnitude eigenvalue of its adjacency matrix.

E(|λ 2 |) ≤ d 1 d 2 α.
where α is the minimum over m of the bound applied to regular bipartite Schreier graphs of odd (Theorem 2) or even (Theorem 1) degree.

A simple asymptotic bound

In this work we do not focus on asymptotic behaviour of large graphs. However, we observe that at least in some setting, the used technique easily gives some asymptotic bounds. This bound applies to the construction of a Schreier graph GL k (F) with any dimension k and with any finite field F, which is not the case of the previous ones (in Theorem 1 and Theorem 2 we use very substantially the fact that the group is not abelian, which is false in dimension one). The bound applies to graphs with a pretty large degree, d = Ω(ln n) (see next section for an estimate of the constant hidden in the Ω notation).

Theorem 3. Let G = Sch(GL k (F p ) ⟲ (F k p ) * , S
) graph of size n = p k -1 and whose degree is 2d = 2|S|. Let µ 2 be the second largest eigenvalue of its normalised adjacency matrix. Then,

E(|µ 2 |) ≤ e ln n d
where ln is the natural logarithm and e its base.

Experimental results

We have conducted numerical experiments which showed that the spectral properties of the Schreier graphs in our constructions for regular and bipartite graphs are pretty close to the optimal values achieved by "truly random" graphs (much closer than what one could expect from Theorem 1 and Theorem 2, see Figures 2 and 3 below). The main motivation of our work was to explain this results theoretically. With the help of a computer, we applied our bounds from Theorems 1, 2 and 3 to some specific parameters of graphs. This calculations are shown in Figure 1. We can observe that the theoretical results that we obtain give non trivial bounds for the second eigenvalue but do not explain completely our numerical experiments.

Results of the experiments. We show below (Figures 2 and3)the experimental results we have got for the eigenvalues of randomly sampled graphs.

For each of the following curves, we computed the second largest magnitude eigenvalues of 5000 graphs and display the probability distribution. In order to (k, d)

Th 1: This table shows the computed bounds from our three theorems for different parameters (the dimension k and the degree d). These values are compared with the best asymptotic bound known ( [START_REF] Friedman | A proof of alon's second eigenvalue conjecture[END_REF]) and to the bound from [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF]). calculate these eigenvalues, we used the C++ library Spectra1 that implements the Lanczos algorithm ( [START_REF] Calvetti | An implicitly restarted lanczos method for large symmetric eigenvalue problems[END_REF]).

One can observe that the second largest eigenvalues are likely to be much closer to the optimal asymptotic value (2

√ 2d -1 and √ d 1 -1+ √ d 2 -1 respec- tively
) than what we have shown theoretically. In addition, the variances of the distributions decrease when the dimensions of the matrices grow. The degrees of the graphs do not seem to have an effect on the probability distribution of the normalised value of the second largest eigenvalue.

A partial theoretical explanation. These experimental observations show that the second eigenvalue of a random Schreier graph from our construction is very close to the theoretical optimum (among all regular graphs). This phenomenon remains unexplained. What is even more frustrating, and we cannot guarantee that (pseudo)random graphs from similar families but with a large number of vertices (e.g., with n ∼ 2 200 ) posses good spectral properties. However, Theorem 1, Theorem 2 and Theorem 3 imply some nontrivial bound for the second eigenvalues of those graphs. The values in Figure 1 allow to illustrate the behaviour of our bounds.

Let us start with the bound from Theorem 3. We apply this theorem with d = ck = O(log n) (where c is a constant). The theorem gives a non-trivial bound (a constant that is below 1) when c is around 6 or above.

Theorem 1 implies a stronger bound: this resulting bound becomes meaningful with d ≥ 2 3 k, which means that it becomes useful with a smaller degree (for large enough k). With d = k, this theorem gives a bound that seems to converge to a value around 0.7 (we have tested this observation up to k = 400). This bound is always smaller than that of Theorem 3.

The bound from Theorem 2 is very similar to that of Theorem 1. Their respective values can be easily compared in the table (1. The natural conjecture that raises from this observation would then be that for d = O(log n), the bounds from Theorems 1 and 2 converge to a value between 0 and 1 (exclusive). This would imply that those theorems improve the 0.996 0.998 1.000 1.002 1.004 1.006 0 n=16806, 5dim n=15624, 6dim n=16383, 14dim n=16000, perm n=15000, SW

Figure 2: This is the observed distribution of the second largest eigenvalues of 2d-regular graphs (not normalised) adjacency matrix from our construction with different parameters. Here, d = 15, and n is the size of the graph. We represent the probability distribution with k = 5, 6 and 14, (where k is the matrix dimension) and adapt the size of the field so that all graphs have roughly the same size. We show the measured value of the second largest eigenvalue in the normalised form, i.e., s divided by 2 √ 2d -1. We compare the random Schreier graphs with "truly" random regular graphs: in the figure, "Perm" refers to the graphs obtained from the permutation model (see above) and "SW" refers to graphs obtained from the Steger-Wormald algorithm ( [START_REF] Steger | Generating random regular graphs quickly[END_REF]) which provides random regular graphs without loops and multiple edges. 0.997 0.998 0.999 1.000 1.001 1.002 1.003 0 n1=16128,d1=20,d2=40,2dim n1=15624,d1=20,d2=40,5dim n1=19682,d1=20,d2=40,9dim n1=8191,d1=40,d2=40,13dim n1=16383,d1=10,d2=30,14dim

√ d 1 -1 + √ d 2 -1, which is the analogous of 2 √ d -1 for bipartite biregular graphs ([3]).
bound from Theorem 3 by a constant factor. Therefore, those bounds would be asymptotically O( log n d ).

Practical implementation. We now briefly explain how our construction of "pseudo-random" (and, therefore, "almost explicit") graphs can be implemented. The main task that needs to be done is obviously sampling the d matrices from GL k (F p ). One way of doing so is simply picking uniformly and independently all k2 coefficients of the matrix and reject the matrix if its determinant is zero (modulo p). Computing the determinant is polynomial in k = O(log n). In order to estimate the expected value of the numbers of tries we need to get an invertible matrix, we can estimate the following quantity:

|GL k (F p )| |M k,k (F p )| = k-1 i=0 p k -p i p k 2 = k-1 i=0 1 -p i-k = k i=1 1 -p -i
where M k,k (F p ) is the set of all k × k matrices whose coefficients are in F p . One can show 2 that this product is convergent and always bigger than 1 4 . From this, we can conclude that we need generally less than four tries so we get a non-singular matrix. Once we have our d matrices, it is enough to apply them to all vectors. This can be done in O(k 2 ) steps. This way, the whole graph can be produced in time O(nd log 2 n).

3 Proofs of the main results

Proofs of Theorems 1 and 3

Let p be a prime, k a natural integer and G = Sch(GL k (Z p ) ⟲ (Z k p ) * , S) be a Schreier graph with S a random subset of d elements of GL k (Z p ) and their inverses. Hence, we obtain a 2d regular graph whose size is n = p k -1. By mapping every element of (Z k p ) * to an element of [[1, p k -1]] (e.g. with f : (x 1 , . . . , x k ) → k-1 i=0 x i p i ), we can associate every pair of vertices with a coordinate of a matrix. This way, we can define M , the normalised adjacency matrix of G.

Let 1 = |µ 1 | ≥ |µ 2 | ≥ ... ≥ |µ n |
be its eigenvalues (which are real since the matrix is symmetric). Consider a random walk of 2m steps starting at vertex i. Then the (i, i) coordinate of M 2m corresponds to the number of closed walks starting at vertex i of size 2m divided by (2d) 2m , since (2d) 2m is the number of paths of size 2m starting at i. Therefore, this is the probability (denoted P ii ) of returning to the vertex i after 2m steps of the random walk. Since T race(M 2m ) is equal to the sum of all of these quantities and since the expected (i, i) coordinate of M 2m is the same for every i we get

E(T race(M 2m )) = nE(P 11 ).
On the other hand, we have

n i=1 µ 2m i = T race(M 2m ).
Thus, since µ 2m i ≥ 0 and µ 1 = 1, we get |µ 2 | ≤ (T race(M 2m ) -1) 1/2m , which implies by Jensen's inequality

E(|µ 2 |) ≤ (nE(P 11 ) -1) 1/2m (3)
Given the starting vertex (say v 1 = f -1 (1)), the random walk can be seen as the product of 2m elements of S chosen uniformly and independently at random. We denote this product ω = w 2m .w 2m-1 . . . w 2 .w 1 and each of its matrices represents the choice of a particular neighbour for all vertices. Hence, if the first vertex on the path is v 1 , the second will be v 2 = s i1 .v 1 (where s i1 is the value of w 1 ), the third v 3 = s i2 .v 2 (where s i2 is the value of w 2 ) and so on; the last vertex of the path is then ω.v 1 .

We reuse here the main conceptual idea of the proof in [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF]. The value of ω.v 1 depends on two types of random choices: on the random choice of the word ω = w 2m .w 2m-1 . . . w 2 .w 1 where each letter is chosen at random in {s 1 , s -1 1 , . . . , s d , s -1 d }, and the random choice of a matrix in GL k (F p ) for each s i . These two choices are independent. We may sample at first the words ω and only then choose the matrices s j . We prefer not to sample the entire value of each s j in "one shot" but reveal the values of these matrices (better to say, the values of the linear operators corresponding to these matrices) little by little, as it is needed. Thus, starting at vertex v 1 , instead of choosing at random in GL k (F p ) the entire matrix w 1 = s i1 , we only determine the result of the product v 2 = s i1 .v 1 . This choice does not determine completely the matrix s i but imposes a linear constraint on the matrix elements of s i1 . The same letter w 1 may appear in the word ω several times. Each time the same letter w 1 appears in the word ω and, therefore, the matrix s i1 is encountered on the path, we must define the action of this matrix on some new vector x. We choose the result of s i1 .x by extending the partial definition of s i1 , which means an extension of the linear constraints on s i fixed earlier. In a similar way, we define step by step the other matrices s j that are involved in ω. We need to understand the distribution of the vector v 2m = ω.v 1 that we obtain at the end of this procedure (and the probability of the event v 2m = v 1 ). In the next paragraphs we analyse this distribution. Consider a matrix s ∈ S that has been already encountered on the path refined by ω, and we have already defined the action of s on t different vertices. Assume that we encounter the same matrix s once again, and we must define the product s.x for some one more vector x ∈ (F k p ) * ). In the permutation model, as stated in [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF] this would be a uniform distribution over the n -t vertices that have not been earlier assigned to the partially defined permutation s. However, in our construction, even if x is totally new to s, the result of s.x may not be necessarily undetermined. Indeed, if x is linearly dependent from the vectors that we have already met, we would have

x = t i=1 α i x i ,
which is a sum of vectors whose result, when multiplied by s, is already known. Thus, s.x = t i=1 α i s.x i would be completely determined by our previous random choices, and would not give any new information about s. Intuitively, we would say that the step that leads from x to s.x is not free. In order characterise formally what it means for a step to be free, we need to introduce the following set: let s be a matrix of S, ω = w 2m . . . w 1 , v 1 the starting vertex and v j+1 = w j v j . Then we define Σ s (i) = span({v j : j < i, w j = s} ∪ {v j+1 : j < i, w j = s -1 }). This is the set of vector on which the action of s is determined at step i. The image set is thus

s.Σ s (i) = span({v j+1 : j < i, w j = s} ∪ {v j : j < i, w j = s -1 }).
This leads to the analogous definition that is presented in [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF]. Definition 3.1 (free and forced step). We consider the i-th step in the path. Let s = w i . We say that step i is forced when v i ∈ Σ s (i). In the opposite case, we say that the step i is free.

Alternatively, instead of saying that a step i is free, we will say that the vector obtained after this step is free (namely the i + 1-th vector, w i .v i ). The following lemma justifies this terminology, and will be used systematically in the rest of the paper. Lemma 3.1.1. Let s = w i for a step i and t be the dimension of Σ s (i). Then, if v i / ∈ Σ s , v i+1 = s.v i can be chosen uniformly at random among the p k -p t vectors that do not belong to s.Σ s (i).

Proof. The choice of a non degenerate matrix s of size k × k is the same as the choice of an bijective linear operator from F k p to F k p . To specify a linear operator, we only need to define it on vectors of any basis in F k p . Let x 1 , . . . , x t be a basis of Σ s (i). By the assumption of the lemma, vector v i is linearly independent with x 1 , . . . , x t . Therefore, we can let x t+1 = v i and then extend x 1 , . . . , x t , x t+1 to a basis in the space F k p with some x t+2 , . . . , x k . To define s, we should specify one by one linearly independent vectors y 1 = s.x 1 , y 2 = s.x 2 , . . . , y k = s.x k . We have p k -1 possibilities to choose y 1 (any non zero vector), p k -p possibilities to choose y 2 (any vector linearly independent with the fixed y 1 ), p k -p 2 possibilities to choose y 3 (any vector linearly independent with y 1 and y 2 ), and so on. In particular, if we have fixed the values y i = s.x i for i = 1, . . . , t, then it remains p k -p t available options to choose y t+1 (which is the same as v i+1 in our notation).

Remark. This implies a sort of transitivity of the group action which is stronger than the simple transitivity, but weaker than the k-transitivity: for all t ≤ k, if (x 1 , . . . , x t ) and (y 1 , . . . , y t ) are two families of linearly independent elements of F k p then, there exists an element s of GL k (F p ) such that for all i ≤ t, s.x i = y i .

As a direct consequence of this lemma, we can formulate the following corollary:

Corollary 2. If a matrix s appears only once in ω at step i, s.v i = v i+1 is chosen uniformly at random among every vertex of the graph.

Proof. Indeed, when this happens, we can rewrite ω as AsB with A and B some invertible matrices. Then we can expose the coefficients of A and B.

The key point is that those matrices are independent from s, which means that we still have no information about s. This way, since v i = B.v 1 , we have

P(ω.v 1 = v 1 ) = P(s.v i = A -1 v 1 ) = 1
n . The probability we have just found is conditioned by the structure of ω, hence it needs to be multiplied by the probability of the condition. This is only dependent on the properties of ω which can be seen as an element of a free group generated by the set {s 1 , . . . s d }. Let us remind that ω can be seen as a words whose letters are taken from {s 1 , s -1 1 , . . . s d , s -1 d }. In order to estimate the total probability of having a closed walk, we subdivide the space of such words in a few events whose probabilities will be determined. Those events are chosen so the conditional probability is more convenient to estimate. This will be done later. Let us define our events:

• X 1 : "at least one letter appears exactly once"

• X 2 : X 1 ∧ "at least one letter appears exactly twice with same sign"

• X 3 : "no letter appears once or twice, at least one letter appears exactly three times"

• X 4 : "no letter appears once, twice, nor three times"

• X ′ 2 : X 1 ∧ X 3 ∧ X 4
∧ "all letters that appear exactly twice have different sign"

These events form a partition of the set of all possible words, whose size is (2d) 2m . In order to finish the proof of Theorem 3, let us leave aside all the events but X 1 and consider its complementary. We bound their probability using an argument similar to that of [START_REF] Alon | Random cayley graphs and expanders[END_REF]. We observe that a word that belongs to X 1 has at most m different letters in it, hence we have at most d m ways of choosing those letters in the alphabet. When choosing each letter at random, the probability that all of them are in the right set is ( m d ) 2m . Hence

P(X 1 ) ≤ d m m d 2m ≤ e d m m m d 2m = e m d m .
The probability we are looking for is then

P(ω.v 1 = v 1 ) = P(ω.v 1 = v 1 |X 1 )P(X 1 ) + P(ω.v 1 = v 1 |X 1 )P(X 1 ) ≤ P(ω.v 1 = v 1 |X 1 ) + P(X 1 ) ≤ 1 n + e m d m .
We set m = ln n to minimise the bound. Substituting the above quantity back into equation 3 completes the proof of Theorem 3.

In order to find a tighter bound, we use a more careful analysis. We consider again all of our events. We are going to represent the probability P (ω.v 1 = v 1 ) as the sum

P (ω.v 1 = v 1 | ω ∈ X 1 ) • P (X 1 ) + . . . + P (ω.v 1 = v 1 | ω ∈ X 4 ) • P (X 4 ) + P (ω.v 1 = v 1 | ω ∈ X ′ 2 ) • P (X ′ 2 ).
For i = 1, 2, 3 and 4 we estimate separately P (X i ) and

P (ω.v 1 = v 1 | ω ∈ X i ),
and we estimate the value of the product

P (ω.v 1 = v 1 | ω ∈ X ′ 2 ) • P (X ′
2 ) as a whole. The sum of these bounds result in the proof of Theorem 1.

The events X ′ 2 and X 4 together involve one particular event that implies a closed walk with probability 1. This event is the "collapse" of the whole word to the identity matrix. It happens when iterating the reduction operation (Ass -1 B → AB for all invertible matrices A, s and B) ends up with the identity matrix. The probability of this event denoted C is analysed in [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF] (lemma 2):

P(C) = 2m + 1 m (2d) m 2m + 1 1 2d 2m ≤ 2 d m .
This is proven by counting the number of well parenthesized words of size 2m (Catalan number) with d different type of parenthesis. We wish to bound the probability of having a closed walk when ω's structure is such that this event cannot happen. We express the size of these sets using a more general recursive formula. Let X q (c, l, d) be the size of the set of all words of length l, on the alphabet that consists of d letters and its negations, such that at least c letters appear (with the positive or negative sign) in this word q times, and the other letters that appear in it have more occurrences. Then

X q (c, l, d) = ⌊ l q ⌋ i=c d i i-1 j=0 2 q l -qj q X q+1 (0, l -qi, d -i)
Indeed, 2 q ℓ q is the number of ways to place q times the same letters in a word of size ℓ (each letter can have positive or negative sign). Thus, i-1 j=0 2 q l-qj q is the number of ways of repeating i times this operation while removing at every step q free places. It simplifies as follows

i-1 j=0 2 q l -qj q = 2 q q! i i-1 j=0 (l -qj)! (l -qj -q)! = 2 q q! i l! (l -qi)!
Note that X q (0, 0, d) = 1 because we only have one way of placing no letters in a word of size 0. Moreover, if q > l then X q (c, m, d) = 0, since the q letters cannot fit in the word. Using these observations, we have a complete recursive definition of X q (c, l, d),

X q (c, l, d) =        1 if c = 0 and l = 0 0 if q > l ⌊ l q ⌋ i=c d i 2 q q! i l! (l-qi)! X q+1 (0, l -qi, d -i) otherwise.
Then we get

|X 1 | = X 1 (1, 2m, d), |X 3 | = X 3 (1, 2m, d) and |X 4 | = X 4 (0, 2m, d).
One can notice that

|X 3 ⊔ X 4 | = |X 3 | + |X 4 | = X 3 (0, 2m, d).
Since there are 4 i -2 i possibilities for choosing the sign of i pairs so that the letters of at least one of them have same sign, the number of ways of placing these pairs in the word is

d i (4 i -2 i ) i-1 j=0 2m-2j 2 = d i (2 i -1) (2m)! (2m-2i)! . Hence |X 2 | = m i=1 d i (2 i -1) (2m)! (2m -2i)! X 3 (0, 2m -2i, d -i).
Similarly, there are 2 i ways of choosing the sign of i pairs of letter so that all pairs are of different sign. Thus we get

|X ′ 2 | = m i=1 d i (2m)! (2m -2i)! X 3 (0, 2m -2i, d -i).
This can be summarized with the relation

X 2 (1, 2m, d) = |X 2 | + |X ′ 2 |. We have already explained that P(ω.v 1 = v 1 |X 1 ) = 1
n . It remains to bound this probability conditioned to the other events. In what is next, we will set p = 2. Taking a bigger field might weaken the bounds and complicate the analysis. We start with X 2 .

Lemma 3.1.2. P(ω.v 1 = v 1 |X 2 ) ≤ 2 n .
Proof. Let s be the matrix that appears twice with same sign. The word is then of the form AsBsC.v 1 = v 1 with A, B and C some invertible matrices of known coefficients. We can rewrite this equation as sBs.x = y with x and y two determined vectors (x = C.v 1 and y = A -1 .v 1 ). It is useful to name the different vectors of the product:

s x ′ B s.x y ′ y ′′ = y.
Since we are in the field of size two there is no non-trivial pairs of parallel vectors. Hence the step that leads to y ′′ is free only if x ′ ̸ = x. In a larger field (p > 2), for y ′′ to be free, it is necessary that x ̸ = αx ′ for all non zero α ∈ F p . By taking p = 2, a lot of case-by-case analysis is avoided. Because y ′ is necessarily free and since x and x ′ = B.y ′ are independent, P(x ′ = x) = 1 n . Then, if x ′ = x, we have y ′′ = y ′ . This is the probability that y ′′ is forced. If this is not the case, namely if x ′ ̸ = x (which happens with probability n-1 n ), then the probability for y ′′ to be equal to y is at most 1 n-1

(y ′′ cannot be equal to y ′ since both steps are free). Therefore,

P(ω.v 1 = v 1 |X 2 ) ≤ 1 n + n -1 n 1 n -1 = 2 n .
Now we bound the probability P(ωv 1 = v 1 |X 3 ). We proceed the same way as above, by distinguishing the cases where the final step is free or not. We prove the following claim: In particular, we have

P(ω.v 1 = v 1 |X 3 ) ≤ 5 n .
Proof. Under the X 3 condition, the word can take four forms that will be analysed separately:

• sBsCs.x = y • s -1 BsCs.x = y • sBs -1 Cs.x = y • sBsCs -1 .x = y
Any other form can be turned into one of the above by switching s with s -1 , which does not change the argument. The different possibilities can be summarized by writing s 1 Bs 2 Cs 3 .x = y; at most one of s 1 , s 2 , s 3 is s -1 and the others are s. We will use the notation below to treat all four cases:

s 1 x ′′ B s 2 x ′ C s 3 .x y ′ y ′′ y ′′′ = y.
We start with the case in which there is no s -1 in ω. Here, the step that leads to y ′′′ is free only if x ′′ ̸ = x, x ′′ ̸ = x ′ and x ′′ ̸ = x ′ + x ′′ (that is, x ′′ is not a linear combination of x ′ and x). Since x ′ and x are independent, P(x ′ = x) = 1 n . Hence, with probability n-1 n we get that y ′′ is free, which means that x ′′ = B.y ′′ is uniformly distributed among the n -1 vectors different from B.y ′ . There are three values for x ′′ that make the final step forced and they are equally likely, thus P(y ′′′ is forced |x ′ ̸ = x) ≤ 3 n-1 . The opposite case happens with probability n-4 n-1 . Then P(y ′′′ = y) ≤ 1 n-3 . To illustrate the reasoning, we can represent those probabilities by a tree:

x ′ = x x ′ ̸ = x x ′′ = x x ′′ ̸ = x x ′′ = x ′ x ′′ ̸ = x ′ x ′′ = x + x ′ x ′′ ̸ = x + x ′ 1 n n-1 n 1 n-1 n-2 n-1 1 n-2 n-3 n-2 1 n-3 n-4 n-3
The rightmost leaf corresponds to y ′′′ being free which gives a probability 1 n-3 of having a closed walk. Therefore,

P(sBsCs.x = y) ≤ 1 n + n -1 n 3 n -1 + n -4 n -1 1 n -3 ≤ 5 n . Now, consider s 3 = s -1 .
Then y ′′ is forced if x ′ = y ′ , but those two vectors are correlated, so we cannot bound the probability of this event. We will consider both cases and take the probability of the most likely event as a bound. If y ′ = x ′ , then y ′′ is forced, which implies that y ′′ = x. In this case, if x ′′ = y ′ we have y ′′′ = x. However, x ′′ = B.x, which is independent from y ′ (which is from a free step). Hence, the probability for them to be equal is 1 n . In the opposite case, y ′′′ is free, which gives a total probability of this branch of 2 n . We now suppose that y ′′ is free. Then, with probability 3 n-1 , y ′′′ is forced. In the other case, y ′′′ is equal to y with probability at most 1 n-3 . Here is the probability tree:

x ′ = y ′ x ′′ ̸ = y ′ x ′′ = y ′ x ′ ̸ = y ′ x ′′ = x ′ x ′′ ̸ = x ′ x ′′ = y ′ x ′′ ̸ = y ′ x ′′ = y ′ + x ′ x ′′ ̸ = y ′ + x ′ n-1 n 1 n 1 n-1 n-2 n-1 1 n-2 n-3 n-2 1 n-3 n-4 n-3
The branches whose probabilities are close to 1 corresponds to the cases when y ′′′ is free. Thus we have

P(sBsCs -1 .x = y) ≤ max 2 n , 3 n -1 + n -4 n -1 1 n -3 ≤ 4 n -1 .
When s 2 = s -1 the choice of y ′′ is forced if x ′ = y ′ , which implies x ′′ = B.x. Then s is defined only on x. If B.x = x then, since y ′ is free, P(y ′′′ = y) = P(y ′ = y) = 1 n . Otherwise, y ′′′ is free, and therefore P(y ′′′ = y) = 1 n-1 . On the other hand, if y ′′ is free, then s is defined on x and y ′′ . Since y ′′ is free, x ′′ and x are independent, thus P(

x ′′ = x) = 1 n-1 . Moreover, if x ′′ = y ′′ , P(y ′′′ = y) = P(x ′ = y) = 1 n . If x ′′ = y ′′ + x, we have y ′′′ = x ′ + y ′ = (C + Id k )y ′ which is independent from y. Hence, P(y ′′′ = y) = 1
n . Otherwise, since three vectors are excluded, y ′′′ is free with probability at most n-3 n . If so, P(y ′′ = y) = 1 n-3 . As before, the case study can be illustrated with a tree:

x ′ = y ′ x ′′ ̸ = x x ′′ = x x ′ ̸ = y ′ x ′′ = x x ′′ ̸ = x x ′′ = y ′′ x ′′ ̸ = y ′′ x ′′ = y ′′ + x x ′′ ̸ = y ′′ + x 1 n-1 n-2 n-1 1 n-2 n-3 n-2
Thus, we get

P(sBs -1 Cs.x = y) ≤ max 2 n -1 , 3 n -1 + n -2 n -1 n -3 n -2 1 n -3 = 4 n -1 .
Lastly, we consider the case s 1 = s -1 . Here, y ′′ is forced when x ′ = x. Those are not correlated, so this event happens with the probability 1 n . In the other case, s -1 is defined on y ′′ and y ′ , which are random. If x ′′ = y ′′ , we have y ′′′ = x ′ which is equal to y with probability less than 1 n-1 . Since y ′′ is free, y ′ and y ′′ are independent, hence P(x ′′ = y ′ ) = P(x ′′ = y ′ + y ′′ ) = 1 n-1 . If y ′′′ is free, it can take any value with probability 1 n-3 . The last probability tree is then

x ′ = x x ′ ̸ = x x ′′ = y ′′ x ′′ ̸ = y ′′ x ′′ = y ′ x ′′ ̸ = y ′ x ′′ = y ′ + y ′′ x ′′ ̸ = y ′ + y ′′ 1 n n-1 n 1 n-2 n-3 n-2 1 n-3 n-4 n-3
Hence we have

P(s -1 BsCs.x = 1) ≤ 1 n + n -1 n max 1 n -2 , 1 n -2 + n -4 n -2 1 n -3 ≤ 5 n .
By taking the maximum of all these bounds, we conclude the proof.

It remains to bound

P(ω.v 1 = v 1 |X ′ 2 )P(X ′ 2 ).
To simplify the notations we set

x 3 (i) = X 3 (1, 2m -2i, d -i) and x 4 (i) = X 4 (0, 2m -2i, d -i).
We need to prove the following statement. Lemma 3.1.4.

P(ω.v 1 = v 1 |X ′ 2 )P(X ′ 2 ) ≤ 1 2d 2m m i=1 d i (2m)! (2m -2i)! x 3 (i) + x 4 (i) n + 2 i (i + 1)! 5 n x 3 (i) + x 4 (i) . ( 4
)
Proof. Before we proceed with the proof of this lemma we stress again that in this statement we do not bound separately P(X ′ 2 ) and P(ω.v 1 = v 1 |X ′ 2 ), we estimate directly the product of these two probabilities, which equals to the probability of the event

P(ω.v 1 = v 1 and ω ∈ X ′
2 ). The probability is taken, as usual, over the random choice of a word ω of 2m letters and the random choice of invertible matrices assigned to the letters of this alphabet.

We start the proof with two claims. Claim 1: Assume that the word ω contains letters t and s exactly twice, and each of these letters appears once with the positive and once with the negative sign, and these letters interleave:

ω = . . . t . . . s . . . t -1 . . . s -1 . . . ( 5
)
Then the probability to get a closed walk corresponding to the path ω (probability taken over the choice of matrices for each letter in the alphabet) is equal to 1/n. The claim remains true if we swap the positions of the pair of letters s and s -1 and/or of the pair of letters t and t -1 .

Proof of the claim. Words from X ′ 2 are all of the form AsBs -1 C with A, B and C some invertible matrices. Hence, we wish to estimate the probability of the event sBs -1 .x = y, with x = C.v 1 , and y = A -1 .v 1 . We use the notation

s x ′ B s -1 .x y ′ y ′′ = y.
Here, the matrix t is a factor of B (hence B = . . . t . . . ). We first suppose that x = y. Then, if x ′ = y ′ we have y ′′ = x = y. Since t appears in B, x ′ is independent of y ′ , and thus P(y ′ = x ′ ) = 1 n (because this is the first time t is used in the path). In the opposite case, we have y ′′ ̸ = y, and the path cannot be closed. Now we suppose x ̸ = y. Then if y ′ = x ′ we have y ′′ = x ̸ = y. If y ′ ̸ = x ′ (which happens with probability n-1 n , y ′′ is free, and its value is uniformly distributed among the n -1 remaining vectors. Therefore, when we have this configuration of random matrices in ω, the probability of having a closed walk is 1 n .

It can be noticed that here, the fact that t appears with different sign is not used. Claim 2: Let us take the set of 2i literals

{s 1 , s -1 1 , . . . , s i , s -1 i }
and consider the set of all words of length (2i) composed of these literals (each one should be used exactly once). We claim that the fraction of words that represent a well formed structure of i pairs of parentheses, where each pairs is associated with some pair of literals (s j , s -1 j ) or (s -1 j , s j ), is equal to 2 i (i+1)! .

Proof of claim. In general, we have (2i)! different ways to distribute (2i) literals among (2i) positions. Let us count the fraction of permutations where the literals form a structure of i pairs of parentheses. The number of well parenthesized words (with one type of parentheses) of size 2i is the Catalan number 2i+1 i 1 2i+1 . We have i! ways to assign each pair of parentheses with one of i types of literals, and 2 i to chose the signs in each pairs (. . . s j . . . s -1 j . . . or . . . s -1 j . . . s j . . . for each of i pairs). Hence, the proportion of the well parenthesized words is

2i+1 i 1 2i+1 i!2 i (2i)! = (2i + 1)!i!2 i (2i + 1)!i!(i + 1)! = 2 i (i + 1)! .
It is easy to see that the absence of pattern 5 is equivalent to having such well formed structure of parenthesis.

Let us proceed with the proof of the lemma. By definition, in each word ω ∈ X ′ 2 all letters that appear exactly twice must have different signs. In what follows we denote i that number of letters that appear in ω exactly twice. For a fixed i, to specify a word ω where i letters appear twice (with opposite signs) and the other letters appear at least three times, we should • choose i letters among d (those who appear exactly twice), which gives d i combinations;

• choose 2i positions in the word ω of length 2m where we place the letters that appear twice, which gives 2m 2i combination; • fix a permutations of the (2i) literals on the chosen (2i) positions, which gives (2i)! combinations;

• fill the remaining (2m -2i) positions of ω with other letters, using each letter at least three times; we subdivide these combinations into two subcases:

there is at least one letter that is used exactly three times; we have

x 3 (i) = X 3 (1, 2m -2i, d -i) possibilities to do it;
there is no letter that is used exactly three times, i.e., each letter (besides the i letters that were used twice) must be used at least four times; we have x 4 (i) = X 4 (0, 2m -2i, d -i) possibilities to fill in this way the remaining (2m -2i) positions.

The i pairs of letters in ω contain the pattern (5) may contain or not contain the pattern [START_REF] Bordenave | A new proof of Friedman's second eigenvalue theorem and its extension to random lifts[END_REF]. By Claim 2, the latter is the case for the fraction 2 i (i+1)! of all ω (with i pairs) and, respectively, the former is the case for the fraction 1 -2 i (i+1)! of these words.

If the i pairs of letters in ω contain the pattern (5), then by Claim 1 the probability that ω provides a closed path is at most 1 n (probability taken over the choice of matrices for each letter in the alphabet). Since we have in total (2d) 2m words ω, this case contributes to the resulting probability P(ω.v 1 = v 1 and ω ∈ X ′ 2 ) at most 1 2d

2m d i 2m 2i (2i)! 1 - 2 i (i + 1)! (x 3 (i) + x 4 (i)) • 1 n
(in what follows we bound 1 -2 i (i+1)! by 1). If the i pairs of letters in ω do not contain the pattern (5) but one of other letters appear in ω exactly thee times, then the probability to have a closed path is at most 5 n , as shown in Lemma 3.1.3. This case contributes to the resulting probability at most 1 2d

2m d i 2m 2i (2i)! • 2 i (i + 1)! • x 3 (i) • 5 n
At last, if ω does not contain the pattern ( 5) and all other letters appearing in ω are used more than three times, then we trivially bound the probability to have a closed path by 1. This contributes to the resulting probability 1 2d

2m d i 2m 2i (2i)! • 2 i (i + 1)! • x 4 (i).
Summing these quantities for all possible values of i and observing that 2m 2i (2i)! = (2m)! (2m-2i)! , we obtain the statement of the lemma.

We proceed with similar bounds for the other sets of words:

P(ω.v 1 = v 1 |X 1 )P(X 1 ) ≤ 1 n 1 2d 2m |X 1 |, P(ω.v 1 = v 1 |X 2 )P(X 2 ) ≤ 2 n 1 2d 2m |X 2 |, P(ω.v 1 = v 1 |X 3 )P(X 3 ) ≤ 5 n 1 2d 2m |X 2 |, and
P(ω.v 1 = v 1 |X 4 )P(X 4 ) ≤ 1 2d 2m |X 4 |.
The sum of these expressions is larger than P 11 defined at the beginning of this section. By replacing it in equation 3, we complete the proof. It is easy to see that the rough bounding used in the proof of Theorem 3 gives a larger bound than that of Theorem 2.

Proof of Theorem 2

We now can adapt this proof to get a similar bound for d-regular bipartite graphs.

Let G = Sch BP (Gl k (Z 2 ) ⟲ (Z k 2 ) * , D)
and M be its normalised adjacency matrix. In order to associate its coordinate to vertices we can proceed as in the preceding section by mapping surjectively [[1, 2(2 k -1)]] to (Z k 2 ) * , taking care of distinguishing the vectors of the first and the second partition. Here, we set 2n = 2(2 k -1), the number of vertices in the graph. Let us start by adapting the trace method to the bipartite graphs. One can remark that the adjacency matrix of G is of the form

M = 0 A t A
2µ 2m 2i+1 = T race(M 2m ).
In order to study the spectral gap, the relevant quantity to estimate is then

|µ 3 | = |µ 4 |. Since |µ 1 | = |µ 2 | = 1, we thus obtain 2µ 2m 3 ≤ n-1 i=1 2µ 2m 2i+1 = T race(M 2m ) -2.
As we have seen in section 3.1, the expected value of T race(M 2m ) is the sum of the probability of getting of closed path of size 2m, starting on each vertex.

We note this probability P ii for the vertex i. It is the same for every vertex, hence we get, by using Jensen's inequality

E(|µ 3 |) ≤ 1 2 (E(T race(M 2m )) -2) 1 2m
= (nP 11 -1)

1 2m . (6)
One can notice that here, n is the size of the partition, not the size of the graph. Indeed, with an even number of steps, the path must end in the same partition as it started, which eliminates half of the vertices. We first explain why the construction for even degree regular bipartite graphs gives the same bound as Theorem 1. Here, a random walk can be represented as a sequence of matrices of D ∪ D -1 . This is because every vertex x is connected to s.x and s -1 .x. Each element of the sequence is chosen independently of the others. It is then easy to see that the structure of the walk is exactly the same as in the non bipartite case: a uniformly random sequence of 2m matrices from D ∪ D -1 . The same proof can then be applied to this sequence, the elements of the sequence will then behave the same way as in the preceding section.

However, some work needs to be done for graphs of odd degree. In order to apply here a similar reasoning as in the previous section, we need to understand what a random walk in G looks like in terms of the matrices of D. In a bipartite regular graph obtained by our construction, a random walk of size 2m is a sequence ω of elements of D chosen independently at random. As usual, every edge in the graph corresponds to some invertible matrix. In the case of a bipartite graph we assume that the multiplication by the matrices transforms the vertices in the left part into the vertices of the right part. Thus, in a random walk on such a graph, the matrices that appear in an odd position in ω are taken with the positive sign, while the matrices that appear in an even step are taken with the negative sign, see Fig. 4.

We wish to proceed as in the preceding section, by partitioning the set of possible sequences (words) so that we can analyse the probability of having a closed walk conditioned to the sets this partition. In order to reuse the results above, we choose a similar partitioning. There is a minor difference: now the signs of matrices appearing in ω are fixed (positive for odd position and negative for the others). Hence, the number of possible words is d 2m . We define the sets before determining their size:

• Y 1 : "at least one letter appears exactly once"

• Y 2 : Y 1 ∧ "at least one letter appears exactly twice"

• Y 3 : "no letter appear once or twice, at least one letter appears exactly three times"

• Y 4 : "no letter appear once, twice, nor three times"

Up to this point, it is not hard to understand why the bound of Theorem 3 holds. Indeed, the sign of the matrices do not play any role in the proof, so the probability of Y 1 can be bounded by the same quantity as in the previous section. In addition, the probability of having a closed walk conditioned to Y 1 is also 1 n (n is the size of a partition). Therefore, Theorem 3 applies to bipartite regular graphs.

We can define the analogous recursive relation used in the preceding part. Since this formula represents a quantity that does not depend on the sign of the letters (they are determined by the parity of the positions), we can just ignore them:

Y q (c, l, d) =      1 if c = 0 and l = 0 0 if q > l ⌊ l q ⌋ i=c d i (q!) -i l! (l-qi)! Y q+1 (0, l -qi, d -i) otherwise.
As before, Y q (c, l, d) is the number of words of size l on alphabet of size d that have at least c different letters that appear q times and whose other present letters have more occurrences. The only difference with X q (c, l, d) is that we do not deal with signs. For the same reason, we have

|Y 1 | = Y 1 (1, 2m, d), |Y 2 | = Y 2 (1, 2m, d), |Y 3 | = Y 3 (1, 2m, d)
and

|Y 4 | = Y 4 (0, 2m, d).
We have already shown that when one letter appears exactly once, the probability of having a closed walk is 1 n . Similarly, when a letter appears exactly three times, the probability of getting a closed walk is less than 5 n . Indeed, in the proof of Lemma 3.1.3, all possible configurations of signs for the letter that appears three times are considered (e.g. ω = . . . s . . . s -1 . . . s . . . or . . . s . . . s . . . s -1 . . . ). No assumption is done on their respective probabilities to occur. These probabilities may or may not be different in the bipartite setting. Since this bound ( 5n ) is the maximum over all the probabilities of getting a closed walk with each configuration of signs, the resulting bound for the probability of getting a closed walk in the bipartite case remains the same. Hence we get

P(ω.v 1 = v 1 |Y 1 )P(Y 1 ) ≤ 1 d 2m Y 1 (1, 2m, d) 1 n and P(ω.v 1 = v 1 |Y 3 )P(Y 3 ) ≤ 1 d 2m Y 3 (1, 2m, d) 5 n .
As before, we do not bound the probability of getting a closed walk under condition Y 4 . Then

P(ω.v 1 = v 1 |Y 4 )P(Y 4 ) ≤ 1 d 2m Y 4 (0, 2m, d).
We now estimate P(ω.v

1 = v 1 |Y 2 )P(Y 2 ). We set y 3 (i) = Y 3 (1, 2m -2i, d -i) and y 4 (i) = Y 4 (0, 2m -2i, d -i). Lemma 3.2.1. P(ω.v 1 = v 1 |Y 2 )P(Y 2 ) ≤ Y 2 (1, 2m, d) 2 n + m i=1 d i 1 2 i (2m!) (2m -2i)! 2 i (i + 1)! y 3 (i) 5 n + y 4 (i) (7)
Proof. We proceed in a similar way as in the proof of lemma 3.1.4. Consider we have i pairs of matrices that appear exactly twice in ω. In the bipartite setting, the signs are forced by the parity of the position of each letter. We thus choose to ignore them. Then, the probability of having no pair (s, t) such that we have the pattern ω = . . . s . . . t . . . s . . . t . . . is 2 i (i+1)! . The proof is the same as that of claim 2 in Lemma 3.1.4, except that the numerator and the denominator of the fraction are both divided by 2 i (because we ignore the signs).

Using the proof of Lemma 3.1.2, we conclude that, if a letter appears twice with the same sign, the probability of having a closed walk is less than 2 n . If there is a pair (s, t), ω = . . . s . . . t . . . s -1 . . . t -1 . . . , then, by using the argument from lemma 3.1.4 (claim 1), the probability of getting a closed walk is 1 n . If those cases do not happen, we still can bound the probability of getting a closed walk using lemma 3.1.3 when at least a letter appears three times. The conditional probability of getting a closed walk is then less than 5 n . Let us combine together all these bounds.

• The union of the event in which a letter appears exactly twice with same sign, and the event where the letters that appear twice form a bad parenthesized word (if we forget about the signs) has size smaller than Y 2 (1, 2m, d). The probability of getting a closed walk in this case is not greater than 2 n . • The size of the event in which this bound does not apply, but we can apply the bound from lemma 3.1.3 (which is 5 n ) can be computed as follows. (2i)! 2m 2i is the number of ways of placing i pairs of letters with different sign in 2m positions. Since we ignore the sign, this quantity has to be divided by 2 i which gives ( 12 ) i (2m!) (2m-2i)! . A fraction 2 i (i+1)! of them are well formed. y 3 (i) is the numbers of ways of filling the remaining gaps so that no letter appear once nor twice, and at least letter appears three times. Choosing the i pairs among the d possible ones and summing over all i ≤ 2m, we get

m i=1 d i 1 2 i (2m!) (2m -2i)! 2 i (i + 1)! y 3 (i).
• Similarly, the number of remaining words that correspond to walks whose probability of being closed is not estimated is

m i=1 d i 1 2 i (2m!) (2m -2i)! 2 i (i + 1)! y 4 (i).
Summing all theses quantities, multiplying them by their respective probabilities of getting a closed walk and dividing the whole expression by the number of possible words (that is d 2m ), we can conclude. Summing all the above probabilities and substituting this in 6 finishes the proof of Theorem 2.

Proof of Corollary 1

We now turn to bound the second largest eigenvalue for biregular graphs. Let

G = Sch BP (GL k (Z p ) ⟲ (Z k p ) * , D, γ).
We note n 1 = p k -1, the size of the first partition, n 2 = n1 γ the size of the second one, and γ = d2 d1 , thus d 1 and d 2 are the respective degrees of each partition of the graph. Let

P = 0 M t M 0 be its adjacency matrix. Hence M has dimension n 1 × n 2 . Let Q = 0 A t A 0 the adjacency matrix of G ′ = Sch BP (GL k (Z p ) ⟲ (Z k p ) * , D),
which is the bipartite regular graph before merging the vertices of the right partition. We set J such that M. t M = A.J. t A, thus J = I n2 ⊗ J γ , where J γ is the γ × γ matrix whose entries are only ones and ⊗ is the Kronecker product. An example of resulting paths is shown in Fig. 5.

We set A = (a ij ) i,j∈[ [1, n1]] . All A's columns and rows sum up to d 1 -so does t A. We can show that for every x = (x 1 , . . . , x n1 ) orthogonal to e 1 = 1 √ n1 (1, . . . , 1), Ax is also orthogonal to e. Indeed, the coordinates of such an x sum up to zero. We denote Ax = (y 1 , . . . , y n1 ). Then

n1 i=1 y i = n1 i=1 n1 j=1 a ij x j = n1 j=1 x j n1 i=1 a ij = d 1 n1 j=1 x j = 0.
Therefore, Ax is orthogonal to e. The same is true for t Ax.

On the other hand, it is easy to see that the spectrum of J is (γ, ..., γ, n2 0, ..., 0)

n1-n2 . t A J A
Figure 5: Traveling three steps starting from the left in this directed graph is equivalent to doing two steps in the bipartite graph (starting from the left as well) with merged vertices on the right. The merging operation is represented by J which corresponds to the complete bipartite graphs in the middle.

Here

n 1 = 6, n 2 = 2, d 1 = 1, d 2 = 3.
Let λ 2 (X) be the second largest eigenvalue of some square matrix X and let x be the normalised eigenvector associated to λ 2 (M. t M ). For every positive number q, we have

|λ 2 (M. t M ) q | = ||(A.J. t A) q .x|| = ||A(J. t A.A) q-1 J. t A.x|| ≤ γd 1 ||A(J. t A.A) q-1 x ′ ||
with x ′ a normalised vector orthogonal to e (because of the preceding fact). Hence ||(J. t A.A) q-1 x ′ || ≤ γ q-1 |λ q-1 2 ( t A.A)|.

We conclude that

|λ 2 (M. t M ) q | ≤ d 2 1 γ q |λ 2 ( t A.A) q-1 | = d 1 d 2 (γ|λ 2 ( t A.A)|) q-1 .
Since this is a positive quantity, its q-th root is defined:

λ 2 (M. t M ) ≤ d 1 d 2 (γ|λ 2 ( t A.A)|) q-1 1 q = d 1 d 2 (γ|λ 2 ( t A.A)|) q |λ 2 ( t A.A)| 1 q which gives λ 2 (M. t M ) ≤ d 1 d 2 |λ 2 ( t A.A)| 1 q γ|λ 2 ( t A.A)|
By taking the limits when q goes to infinity, we obtain is also an eigenvector with associated eigenvalue -λ. Thus, v -v ′ is an eigenvector of P 2 of eigenvalue λ 2 and this vector has n 2 zeros on the right. Because P 2 represents a disconected graph, if we reduce the dimension of this vector by n 2 (removing the zeros on the right corresponding to one connected component) we get an eigenvector of M. t M of eigenvalue λ 2 . Therefore, M. t M has the same eigenvalues -denoted µ 1 ≥ µ 2 ... ≥ µ n1 -as P , but squared.

The proof works the same with Q (taking n 1 = n 2 ). We note α the bound for |µ 3 (Q)| proven in the preceding section. α might refer to the bound from Theorem 1 if the graph is obtained from a bipartite regular graph of even degree or to the bound from Theorem 2 if its degree is odd. In

Final comments

In section 3.1, we have seen that the probability for the random walk to collapse to the identity sequence is less than ( 2 d ) m . If so, the probability of getting a closed walk (conditioned by the collapsing event) is then 1. When the collapse does not happen, we cannot hope for a smaller probability than 1 n to get a closed path in the graph. This is the smallest probability of a closed walk one can get in a random graph. The trace method gives then

E(|µ 2 |) ≤ n 1 n + 2 d m - 1
1 2m = n 1 2m 2 d .
With m = Ω(ln n), we get

E(|µ 2 |) = O(d - 1
2 ), which is bigger than the bound from [START_REF] Friedman | A proof of alon's second eigenvalue conjecture[END_REF] only by a constant factor. This suggests that this technique can be improved by a subtler subdivision of the probability space of ω, as well as a more careful analysis of the probability of having a closed walk (specially with the condition X ′ 2 ∩ X 4 for X ′ 2 and X 4 defined on page 14). Let us observe that the term n 1 2m is getting close to 1 only when m = Ω(log n). This is why in [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF] or [START_REF] Alon | Random cayley graphs and expanders[END_REF], the length of the random walk (2m) is logarithmic in the number of vertices. Our computations show that the optimal size of the walk should be a bit smaller; this might be because it allows us to assume that, with the overwhelming probability, at least one letter appears in ω exactly one time (the event X 1 in the proof of Theorems 1 and 3). Clearly, we cannot keep m small and at the same time make the factor n 1 2m close to 1. This is an important limitation of our technique.

Our experimental results show that the second largest eigenvalue distribution measured for these graphs is much closer to that we can observe in the permutation model, at least in high dimension, and with a small field. A reasonable conjecture might be the following:

Conjecture 1. Let G k = Sch(GL k (Z p ) ⟲ (Z k p ) * , S
) with S a random subset of GL k (Z p ) and p a prime number. Let G ′ k be a 2|S|-regular graph from the permutation model of size p k -1. Then, as k grows, the second largest eigenvalue distribution of G converges to that of G ′ .

We believe that similar statements are true for bipartite regular and biregular graphs from our construction.

Conclusion.

In this paper we study a pseudo-random construction of spectral expanders represented as Schreier graphs. The experimental results suggest that these graphs have nearly optimal value for the second largest eigenvalues (not only when the size of the graph goes to infinity but also for graspable sizes relevant for practical applications). Theoretical results proven above are the first step to explain these experimental results. Instead of more traditional asymptotic bounds, we focused on theoretical bound that can be calculated (possibly with help of computer) for graphs of rather small size involved in our numerical experiments. We observe the limitations of the method of moments used in our proof which often leads to dealing with too many cases. A more precise theoretical explanation of the behaviour of random Schreier graphs Sch(GL k (Z p ) ⟲ (Z k p ) * , S) will require a subtler analysis. Another possible direction of the future research is a reduction of the number of random bits used to produce each graph. It would be interesting to reduce the number of these bits from O(d log 2 n) to O(d log n), which would bridge the gap between (pseudo)random and deterministic constructions. We would also like to draw attention to the theoretical bounds and estimates obtained with the help of "hideous" formulas combined with computer calculations. We believe that such an approach can be justified when studying properties of relatively small graphs.

  then denote them d = |λ 1 | ≥ |λ 2 | ≥ . . . ≥ |λ n |. If we consider the normalised adjacency matrix (whose entries are divided by the degree), we note its eigenvalues 1 = |µ 1 | ≥ • • • ≥ |µ n |. The Alon-Boappana bound refers to the lower bound |λ 2 | ≥ 2 √ d -1 -ϵ ([15]

Figure 3 :

 3 Figure 3: We display here the observed distribution of the second eigenvalue for bipartite biregular graphs. The measured value of the second largest eigenvalues is normalised by division by √ d 1 -1 + √ d 2 -1, which is the analogous of 2 √ d -1 for bipartite biregular graphs ([3]).

Lemma 3 .

 3 1.3. P(ω.v 1 = v 1 |"at least a letter appears exactly three times") ≤ 5 n .

Figure 4 :

 4 Figure 4: The steps of the random walk work by pairs of matrices of D; the first one brings us on a vertex of the right hand side, the other is for the way back.

λ 2 (

 2 M. t M ) ≤ γ|λ 2 ( t A.A)|To finish the proof, we show the following:Lemma 3.3.1. If λ is an eigenvalue of P then λ 2 is an eigenvalue of M. t M .Proof. P 2 , whose entries represents the paths of size two in the graph, is the matrix of a disconnected d 1 d 2 -regular graph. Indeed, we can remark thatP 2 = M. t M 0 0 t M.M and M. t M is symmetric. Let v = (v 1 , v 2 , . . . , v n1+n2 )be an eigenvector of P with eigenvalue λ. Thenv ′ = (-v 1 , -v 2 , . . . , -v n1 , v n1+1 , . . . , v n1+n2 )

  t A.A, the second largest magnitude eigenvalue is thus |λ 2 ( t A.A)| = (d 1 |µ 3 (Q)|) 2 ≤ d 2 1 α 2 . Hence we have |λ 2 (P )| = |λ 2 (M. t M )| ≤ γ|λ 2 (A. t A)| ≤ d 1 d 2 α.

  0 where t A is the transposition of A. In a bipartite graph, it is known that the spectrum |µ 1 | ≥ • • • ≥ |µ 2n | is symmetric with respect to zero. Hence for 1 ≤ i ≤ n, we have |µ 2i+1 | = |µ 2(i+1) |. This way we get

	n-1
	i=0

In such a graph, the greatest eigenvalue of its adjacency matrix is√ d 1 d 2 .For this kind of graphs, the analogous of the Alon-Boppana bound 2 √ d -1 is

Spectra's home page: spectralib.org.

See e.g. math.stackexchange.com/questions/491948.

Acknowledgments. The author thanks his PhD adviser, Andrei Romashchenko for providing several ideas and useful remarks on this work.


Eric Bourreau
email: eric.bourreau@lirmm.fr

Gérard Fleury
email: gerard.fleury@isima.fr

Philippe Lacomme
email: philippe.lacomme@isima.fr

Adiabatic based Algorithm for SAT: a comprehensive algorithmic description

This paper concerns quantum heuristics able to extend the domain of quantum computing, defining a promising way in the large number of well-known classical algorithms. Quantum approximate heuristics take advantage of alternation between a Hamiltonian defining the problem to solve and a mixing Hamiltonian. The adiabatic theorem initially defined in quantum physic allows to compute a solution for the Schrödinger equation, but the foundation of this methods requires strong skill in physics and mathematics. Our main objectives in this paper are at first to provide an algorithm-based presentation (as close as possible of the classical computer science community in operational research practice) of the adiabatic optimization and secondly to give a comprehensive resolution of the well-known SAT problem. This gives opportunities to provide a concise but explicit analysis of the adiabatic capability to define a new efficient operational research trend. Our experiments encompass numerical evaluations on both simulator and on real quantum computer provided by IBM. Numerical experiments on simulator have been achieved on both Qiskit and MyQLM.

Introduction

A wide majority of Operational Research problems can be defined by the minimization of an objective function with the satisfaction of problem dependent constraints. Resolution approaches are based on exact methods, heuristic or metaheuristics depending on the problem and on the computation time available to provide one solution. From a practical point of view, heuristic and metaheuristic are commonly used in large instances resolutions and they address the following key-points during the search space investigation: 1. generation of initial solutions by powerful constructive heuristics dedicated to the problem; 2. application of a local search to obtain local minima and by consequence favor convergence; 3. diversification mechanisms to avoid premature convergence and search space trap; 4. Indirect representation of solutions to relax constraints and alternate between several search spaces. Adiabatic based quantum approaches can be seen as a new promising local search heuristic. It uses gradually decreasing quantum fluctuations to traverse the barriers in the energy landscape. In fact, minimization of the objective function does not exist in the variable search space but in the representation space as the combinatorial problem is described as an operator. Exploration of the "Operator Search Space" allows gradually to compute better cost function. More precisely Adiabatic Quantum Optimization (AQO) (Fahri, 2000) takes advantage of alternating between the cost function modeled by the Hamiltonian H p and a mixing Hamiltonian operator H D . In this paper, our goal is to give a complete understanding of the origin of the adiabatic optimization and deliver to the reader all the necessary mathematical basis to understand the main idea behind the scenes. Starting from the Schrödinger equation, we will gradually explain how to use the solution of this equation as a guess for an optimization problem described as a Hamiltonian. Deriving from an easy to define initial state, we will give the algorithm to reach the best solution (i.e. final ground state of the Hamiltonian, i.e. state with the minimum energy of the system). To well understand the full process in action, we will define one by one all the building block necessary to express a SAT Hamiltonian. In this paper, in section 2 we will describe the adiabatic approach from the initial principles of Schrodinger equation to generic ideas behind the AQO algorithm. Section 3 will be dedicated to SAT Model and specific experiments on simple instances. Finally, we will focus on conclusion and perspectives.

Adiabatic approaches

Principles

To find a solution (of a combinatorial problem specifically here), quantum algorithms require to solve the Schrödinger equation And by consequence:

|𝜓 𝑇 ⟩ = 𝑒 -𝑖 ℏ .∫ 𝐻(𝑢) 𝑇 𝑜 .𝑑𝑢 . |𝜓 0 ⟩ ≃ 𝑒 -𝑖 ℏ .∑ ∫ 𝐻(𝑢).𝑑𝑢 (𝑘+1).Δ𝑡 𝑘.Δ𝑡 𝑛-1 𝑘=0 . |𝜓 0 ⟩
For Hermitian operators it has been proven by (Suzuki, 1976) that lim 𝑛→∞ (𝑒 𝑖.𝐴.𝑡/𝑛 . 𝑒 𝑖.𝐵.𝑡/𝑛 ) 𝑛 = 𝑒 𝑖.(𝐴+𝐵).𝑡

Note that a more concise and understandable demonstration has been introduced lately by (Barthel et Zhang, 2019).

The previous remark shows that we get a good approximate expression for 𝑒 𝑖.(𝐴+𝐵).𝑡 considering: 𝑒 𝑖.(𝐴+𝐵).𝑡 ≈ 𝑒 𝑖.(𝐴).𝑡 . 𝑒 𝑖.(𝐵).𝑡 Now we can define: According to the (Farhi, 2002) the 𝐻(𝑡) Hamiltonian can defines as a linear combination of 𝐻 𝐷 to 𝐻 𝑃 where 𝐻 𝐷 is referred to as the "Hamiltonian Driver" and 𝐻 𝑃 models the combinatorial problem.

|𝜓 𝑇 ⟩ ≃ 𝑒 - 𝑖 ℏ .∫ 𝐻(𝑢
At the first step, the system must be tuned in the ground state of one Hamiltonian 𝐻 𝐷 commonly referred to the "Hamiltonian Driver" that must be defined in such a way that it does not commute with the Hamiltonian modelling the combinatorial problem. The adiabatic quantum optimization requires a Hamiltonian which is slowly tuned from 𝐻 𝐷 to 𝐻 𝑃 using an interpolation based on one parameter 𝑠(𝑡) . Let us assume this parameter is smoothly decreasing from 1 to 0, we will define 𝐻(𝑡) as 𝑠(𝑡). 𝐻 𝐷 + [1 -𝑠(𝑡)]. 𝐻 𝑃 (see Fig. 2).

Fig. 2. Typical curve of on adiabatic process

The Ising model [START_REF] Kadowaki | Quantum annealing in the transverse Ising model[END_REF] The adiabatic theorem [START_REF] Kato | On the adiabatic theorem of quantum mechanics[END_REF]) ensures that the system stays in the ground state if the 𝑠(𝑡) time dependent evolution is achieved slowly enough to ensure that |𝜓 𝑡 ⟩ is a state close to the ground state.

Algorithm

Preliminaries remarks

To derive an algorithm, considering the previous remarks, for each interval [𝑡; 𝑡 + Δ𝑡]:

|𝜓 𝑡+Δ𝑡 ⟩ = 𝑒 -𝑖 ℏ .Δ𝑡.𝐻(𝑡) |𝜓 𝑡 ⟩ |𝜓 0 ⟩ = |

Key-points

One proposal to compute this adiabatic process can be achieved (Farhi et al., 2000) (Farhi et al., 2002) and (Farhi et al., 2014) All the previous key points (initial state, recurrence form, small value of Δ𝑡) can help us to derive a computation of |𝜓⟩ as described in Algorithm 1.

Thus 𝐻(𝑡 + Δ𝑡). |𝜓 𝑡+Δ𝑡 ⟩ = [𝐻(𝑡) + Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 )]. [(1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 )] 𝐻(𝑡 + Δ𝑡). |𝜓 𝑡+Δ𝑡 ⟩ = 𝐻(𝑡). (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 ). (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 ) Assuming |𝜓 𝑡 ⟩ is an eigenvector of 𝐻 𝑡 with an eigenvalue 𝜆 𝑡 : 𝐻(𝑡 + Δ𝑡). |𝜓 𝑡+Δ𝑡 ⟩ = 𝝀 𝒕 . (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 ). (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 ) 𝐻(𝑡 + Δ𝑡). |𝜓 𝑡+Δ𝑡 ⟩ = 𝝀 𝒕 . (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 )|𝜓 𝑡 ⟩ -Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 ). 𝑖. 𝜆 𝑡 |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 ) 𝐻(𝑡 + Δ𝑡). |𝜓 𝑡+Δ𝑡 ⟩ = 𝝀 𝒕 . (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 ). |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 ) Since Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 ). 𝑖. 𝜆 𝑡 |𝜓 𝑡 ⟩ is in the order to Δ𝑡: 𝐻(𝑡 + Δ𝑡). |𝜓 𝑡+Δ𝑡 ⟩ = 𝜆 𝑡 . |𝜓 𝑡+Δ𝑡 ⟩ + 𝑂(Δ𝑡)

Initialization and iterations

The initial state is obtained by application of the Hadamard gate 𝐻 to |0⟩ ⨂𝑛 and the initial state is

|𝜓 0 ⟩ = 𝐻. |0⟩ ⨂𝑛 One knows that 𝑋| +⟩ = | +⟩ 𝑋| -⟩ = -| -⟩ meaning that
𝐻 𝐷 = ∑ -𝑋 𝑖 𝑛 𝑖=1
with a strength that varies with respect to time and where 𝑋 𝑖 is the 𝑋 operator acting on the 𝑖 𝑡ℎ qubit where the ground state 𝐻 0 is the superposition of all possible states in the eigenbasis of 𝐻 𝑃 .

The eigenvalues of 𝐻 𝐷 are 1 and -1 and the state | +⟩ ⨂𝑛 refers to the eigenvalue -1 defining the fundamental ground state 𝐻 𝐷 .

One iteration 𝑗 consists in operator 𝑒 -𝑖.(1-𝑠 𝑗 ).𝐻 𝑃 . 𝑒 -𝑖.𝑠 𝑗 .𝐻 𝐷 where 𝑠 𝑗 is a parameter smoothly varying from 1 ( 𝑠 0 = 1) to 0. Subsequently, on first iteration the algorithm generates from initial state |𝜓 0 ⟩ = 𝐻. |0⟩ ⨂𝑛 a new state |𝜓 1 ⟩ by application of operator 𝑒 -𝑖.∆t.𝐻 𝑃 . 𝑒 -𝑖.(1-∆t).𝐻 𝐷 to |𝜓 0 ⟩.

From 𝑡 = 0 the new state is:

|𝜓 1 ⟩ = 𝑒 -𝑖.0.∆𝑡.𝐻 𝑃 . 𝑒 -𝑖.(1-0).𝐻 𝐷 . |𝜓 0 ⟩ |𝜓 1 ⟩ = 𝑒 -𝑖.𝐻 𝐷 . |𝜓 0 ⟩
Similarly, at the second iteration, the algorithm generates from |𝜓 1 ⟩ a new state |𝜓 2 ⟩ by application of the operator 𝑒 -𝑖.(1.∆t).𝐻 𝑃 . 𝑒 -𝑖.(1-.1.∆t).𝐻 𝐷 to |𝜓 1 ⟩ leading to |𝜓 2 ⟩ = 𝑒 -𝑖.∆t.𝐻 𝑃 . 𝑒 -𝑖.(1-∆t).𝐻 𝐷 . |𝜓 1 ⟩ And so one until we reach the last iteration where |𝜓 𝑇 ⟩ = 𝑒 -𝑖.1.𝐻 𝑃 . 𝑒 -𝑖.0.𝐻 𝐷 . |𝜓 𝑇-1 ⟩ Algorithm 1: Adiabatic Quantum Algorithm

SAT model and resolution

SAT problem was the first decision problem to be demonstrated as NP-complete. The 3-SAT problem is a subproblem of deciding whether a given propositional Boolean formula expressed as a conjunction of clauses consisting of at most three literals is satisfiable. The Max-SAT problem for a formula 𝜑 is the problem of finding an assignment of values to variables that minimizes the number of unsatisfied clauses in 𝜑.

We propose to analyze the process of the adiabatic algorithm on SAT instances to challenge conviction in the advantage of such quantum algorithms. Note that numerical experiments will be focused only on very small size to favor explanation of the model and analysis of the results. However, the current experiments have been achieved on the simulator provided by IBM that allow useful abstraction for dealing with quantum computers and achieving state-of-the-art results.

The Hamiltonian of a system fully describes the dynamics. As the Hamiltonian is a Hermitian operator it has a spectral decomposition: 𝐻 = ∑ 𝜆 𝑖 𝑖 |𝑒 𝑖 ⟩⟨𝑒 𝑖 | which means: 𝐻 is a diagonalized operator (where 𝜆 𝑖 are the eigenvalues and |𝑒 𝑖 ⟩ are the basis vectors, representative of the observable measure).

Projections and Operators

A SAT formula is modeled with a Hamiltonian where we use for each clause a Hamiltonian connected with controlled-unitary operator. It computes function value in a qubit register. Boolean functions are modeled by a linear combination of Pauli 𝑍 operators. Every operator can be described in a tensor representation or a combination of projectors, or in a geometric view.

We have the operator 𝑍 𝑗 (𝑗 = 1, 𝑛) by definition:

𝑍 𝑗 = 𝐼𝑑 ⊗ 𝐼𝑑 … ⊗ 𝐼𝑑 ⏞ 𝑗-1 ⊗ 𝑍 ⊗ 𝐼𝑑 ⊗ 𝐼𝑑 … ⊗ 𝐼𝑑 ⏞ 𝑛-𝑗
and let us consider a state:

|𝑢⟩ = |𝑢 1 ⟩ ⊗ |𝑢 2 ⟩ ⊗ … ⊗ |𝑢 𝑗-1 ⟩ ⏞ 𝑗-1 ⊗ |0⟩ ⊗ |𝑢 𝑗+1 ⟩ ⊗ … ⊗ |𝑢 𝑛 ⟩ ⏞ 𝑛-j Hence 𝑍 𝑗 . |𝑢⟩ = |𝑢 1 ⟩ ⊗ |𝑢 2 ⟩ ⊗ … ⊗ |𝑢 𝑗-1 ⟩ ⏞ 𝑗-1 ⊗ 𝑍. |0⟩ ⊗ |𝑢 𝑗+1 ⟩ ⊗ … ⊗ |𝑢 𝑛 ⟩ ⏞ 𝑛-𝑗 𝑍 𝑗 . |𝑢⟩ = |𝑢 1 ⟩ ⊗ |u⟩ ⊗ … ⊗ |𝑢 𝑗-1 ⟩ ⏞ 𝑗-1 ⊗ |0⟩ ⊗ |𝑢 𝑗+1 ⟩ ⊗ … ⊗ |𝑢 𝑛 ⟩ ⏞ 𝑛-𝑗 𝑍 𝑗 . |𝑢⟩ = |𝑢⟩ Similarly with |𝑢⟩ = |𝑢 1 ⟩ ⊗ |𝑢 2 ⟩ ⊗ … ⊗ |𝑢 𝑗-1 ⟩ ⏞ 𝑗-1 ⊗ |1⟩ ⊗ |𝑢 𝑗+1 ⟩ ⊗ … ⊗ |𝑢 𝑛 ⟩ ⏞ 𝑛-j
We have:

𝑍 𝑗 . |𝑢⟩ = |𝑢 1 ⟩ ⊗ |𝑢 2 ⟩ ⊗ … ⊗ |𝑢 𝑗-1 ⟩ ⏞ 𝑗-1 ⊗ 𝑍. |1⟩ ⊗ |𝑢 𝑗+1 ⟩ ⊗ … ⊗ |𝑢 𝑛 ⟩ ⏞ 𝑛-j 𝑍 𝑗 . |𝑢⟩ = |𝑢 1 ⟩ ⊗ |𝑢 2 ⟩ ⊗ … ⊗ |𝑢 𝑗-1 ⟩ ⏞ 𝑗-1 ⊗ (-|1⟩) ⊗ |𝑢 𝑗+1 ⟩ ⊗ … ⊗ |𝑢 𝑛 ⟩ ⏞ 𝑛-j
That is 𝑍 𝑗 . |𝑢⟩ = -|𝑢⟩ illustrating that 𝑍 𝑗 swap the qubit in the 𝑗 𝑡ℎ position if the qubit value is |1⟩.

The operators 𝑍 𝑗 can be described using projectors |𝑒 𝑖 ⟩⟨𝑒 𝑖 | that are the projection on the 𝑖 𝑡ℎ basis vector.

In the specific situation where 𝑛 = 1 Consequently, for example with 𝑛 = 2, for 𝑍 = 𝑑𝑖𝑎𝑔(1, -1) :

𝑍 1 = 𝑍 ⊗ 𝐼𝑑 = 𝑑𝑖𝑎𝑔(1,1, -1, -1) and 𝑍 2 = 𝐼𝑑 ⊗ 𝑍 = 𝑑𝑖𝑎𝑔(1, -1,1, -1) With 𝑛 = 3, 𝑍 1 = (𝑍 ⊗ 𝐼𝑑) ⊗ 𝐼𝑑 = 𝑑𝑖𝑎𝑔(1,1, -1, -1) ⊗ 𝐼𝑑 𝑍 1 = (𝑍 ⊗ 𝐼𝑑) ⊗ 𝐼𝑑 = 𝑑𝑖𝑎𝑔(1,1,1,1, -1, -1, -1, -1) 𝑍 2 = 𝐼𝑑 ⊗ (𝑍 ⊗ 𝐼𝑑) = 𝐼𝑑 ⊗ 𝑑𝑖𝑎𝑔(1,1, -1, -1) 𝑍 2 = 𝐼𝑑 ⊗ (𝑍 ⊗ 𝐼𝑑) = 𝑑𝑖𝑎𝑔(1,1, -1, -1,1,1, -1, -1) and 𝑍 3 = 𝐼𝑑 ⊗ (𝐼𝑑 ⊗ 𝑍) = 𝐼𝑑 ⊗ 𝑑𝑖𝑎𝑔(1, -1,1, -1) 𝑍 3 = 𝐼𝑑 ⊗ (𝐼𝑑 ⊗ 𝑍) = 𝑑𝑖𝑎𝑔(1, -1,1, -1,1, -1,1, -1)
In the qubit base |𝑒 𝑘 ⟩ 1≤𝑘≤𝑞 , for any |𝑥⟩ = ∑ 𝑥 𝑘 . |𝑒 𝑘 ⟩ 𝑞 𝑘=1

we have |𝑒 𝑗 ⟩. ⟨𝑒 𝑗 |. |𝑥⟩ = |𝑒 𝑗 ⟩. ⟨𝑒 𝑗 |𝑥⟩ = |𝑒 𝑗 ⟩. 𝑥 𝑗 By consequence, 𝑍 𝑗 is an operator that can be defined considering the next formula where 𝑞 = 2 𝑛 :

𝑍 𝑗 = 2 ∑ ∑ |𝑒 𝑢×( 2 𝑛 2 𝑗-1 )+𝑣-1 ⟩ ⟨𝑒 𝑢×( 2 𝑛 2 𝑗-1 )+𝑣-1 | ( 2 𝑛 2 𝑗 ) 𝑣=1 2 𝑗-1 𝑢=1 -𝐼𝑑 ⊗𝑛 𝑍 𝑗 = 2 ∑ ∑|𝑒 𝑢×2 𝑛-𝑗+1 +𝑣-1 ⟩⟨𝑒 𝑢×2 𝑛-𝑗+1 +𝑣-1 | 2 𝑛-𝑗 𝑣=1 2 𝑗-1 𝑢=1 -𝐼𝑑 ⊗𝑛 𝑍 𝑗 = 2 ∑ ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 | (𝑘-1)×2 𝑛-𝑗+1 +2 𝑛-𝑗 -1 𝑣=(𝑘-1)×2 𝑛-𝑗+1 ) 2 𝑗-1 𝑘=1 -𝐼𝑑 ⊗𝑛
For example, when 𝑛 = 4 (𝑞 = 2 𝑛 = 2 4 = 16) we have:

𝑍 1 = 2 ∑ (∑|𝑒 𝑗 ⟩⟨𝑒 𝑗 | 7 𝑗=0 ) 1 𝑘=1 -𝐼𝑑 ⊗𝑛
and by consequence

𝐷𝑖𝑎𝑔(𝑍 1 ) = (1,1,1,1,1,1,1,1, -1, -1, -1, -1, -1, -1, -1, -1) 𝑍 2 = 2 ∑ ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 | (𝑘-1)×(2 3 )+(2 2 )-1 𝑣=(𝑘-1)×(2 3 ) ) 2 𝑘=1 -𝐼𝑑 ⊗𝑛 𝑍 2 = 2 ((∑|𝑒 𝑗 ⟩⟨𝑒 𝑗 | 3 𝑣=0 ) + ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 | 8+3=11 𝑣=8
)) -𝐼𝑑 ⊗4

and by consequence -𝐼𝑑 ⊗4 and by consequence and by consequence

𝐷𝑖𝑎𝑔(𝑍 2 ) = (1,1,1,1, -1, -1, -1, -1,1,1,1,1, -1, -1, -1, -1)
𝐷𝑖𝑎𝑔(𝑍 3 ) = (1,1, -1, -1,1,1, -1, -1,1,1, -1, -1,1,1, -1, -1) 𝑍 4 = 2 ∑ ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 | (𝑘-1)×(2 1 )+(2 0 )-1 𝑣=(𝑘-1)×(2 1 ) ) ( 2
𝐷𝑖𝑎𝑔(𝑍 4 ) = (1, -1,1, -1,1, -1,1, -1,1, -1,1, -1,1, -1,1, -1)
To conclude we can confirm that 𝑍 𝑗 transforms |𝑥⟩ into a new symmetric state:

𝑍 𝑗 = 2 ∑ ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 |𝑥⟩ (𝑘-1)×2 𝑛-𝑗+1 +2 𝑛-𝑗 -1 𝑣=(𝑘-1)×2 𝑛-𝑗+1 ) 2 𝑗-1 𝑘=1 -|𝑥⟩
achieving an orthogonal projection of |𝑥⟩ on the direction of |𝑒 𝑣 ⟩

where 𝑣 = (𝑘 -1) × (

2 𝑛 2 𝑗-1 ) . . (𝑘 -1) × ( 2 𝑛 2 𝑗-1 ) + ( 2 𝑛
2 𝑗 ) -1 and for all value of 𝑘 such that 𝑘 = 1 …2 𝑗-1 . This formula can be rewritten

𝑍 𝑗 = 2 ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 |𝑥⟩ 𝑣∉𝐸 𝑍 𝑗 -|𝑥⟩ With 𝐸 𝑍 𝑗 = { 𝑗 / 𝑘 ∉ [1. . 2 𝑛 2 𝑛-𝑗+1 ] or 𝑣 ∉ 𝑖 [(𝑘 -1) × ( 2 𝑛 2 𝑗-1 ) , (𝑘 -1) × ( 2 𝑛 2 𝑗-1 ) + ( 2 𝑛 2 𝑗 ) -1] } 𝑍 𝑗 . |𝑥⟩ is referred to as 𝑃 ⊥𝑍 𝑗 (|𝑥⟩) = 2 ∑ ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 |𝑥⟩ (𝑘-1)×2 𝑛-𝑗+1 +2 𝑛-𝑗 -1 𝑣=(𝑘-1)×2 𝑛-𝑗+1 ) 2 𝑗-1 𝑘=1
and by consequence

|𝑥⟩ -𝑃 ⊥𝑍 𝑗 (|𝑥⟩) = |𝑥⟩ -2 ∑ ( ∑ |𝑒 𝑣 ⟩⟨𝑒 𝑣 |𝑥⟩ (𝑘-1)×2 𝑛-𝑗+1 +2 𝑛-𝑗 -1 𝑣=(𝑘-1)×2 𝑛-𝑗+1 ) 2 𝑗-1 𝑘=1
is the difference between |𝑥⟩ and the projection of |𝑥⟩ on all the orthogonal planes.

To conclude

𝑍 𝑗 |𝑒 𝑘 ⟩ = { -1 𝑖𝑓 𝑘 ∈ 𝐸 𝑍 𝑗 +1 𝑖𝑓 𝑘 ∉ 𝐸 𝑍 𝑗 with 𝐸 𝑍 𝑗 = {𝑗 / 𝑘 ∉ [1. . 2 𝑛 2 𝑛-𝑗+1 ] or 𝑣 ∉ 𝑖 [(𝑘 -1) × ( 2 𝑛 2 𝑗-1 ) , (𝑘 - 1) × ( 2 𝑛 2 𝑗-1 ) + ( 2 𝑛 2 𝑗 ) -1]}.
In other words, 𝐸 𝑍 𝑗 is the set of positions where the eigenvalue is -1 . For example we have 𝐸 𝑍 3 = {2; 4; 6; 8}. We can state that 𝑍 𝑗 operator over any basis state will revert every 𝑒 𝑘 /𝑘 ∈ 𝐸 𝑍 𝑗 .

Specific Hamiltonian with 2 qubits.

Is:

|𝜓 𝑡 ⟩ = 𝑒 -𝑖.𝜔.𝑡.𝐼𝑑-𝑖.𝑡.𝛼.𝑍 𝑖 -𝑖.𝑡.𝛽.𝑍 𝑗 -𝑖.𝑡.𝛾.𝑍 𝑖 .𝑍 𝑗 . |𝜓 0 ⟩ |𝜓 𝑡 ⟩ = 𝑒 -𝑖.𝑡.𝜔.𝐼𝑑 . 𝑒 -𝑖.𝑡.𝛼.𝑍 𝑖 . 𝑒 -𝑖.𝑡.𝛽.𝑍 𝑗 . 𝑒 -𝑖.𝑡.

Matrix expression and circuits

For any operator 𝑈 such 𝑈 2 = 𝐼𝑑 we have:

𝑒 𝑖.𝛼.𝑈 = ∑ (𝑖. 𝛼. 𝑈) 𝑘 𝑘! 𝑘=∞ 𝑘=0
𝑒 𝑖.𝛼.U = cos(𝛼) . 𝐼𝑑 + 𝑖. sin(𝛼) . 𝑈 and by consequence, over 2 qubits when Application of 𝑍 = ( 1 0 0 -1 ) on the first qubit of |𝜙⟩ ⊗ |𝜓⟩ is defined by the operator 𝑍 1 = 𝑍 ⊗ 𝐼𝑑 and the application of 𝑍 on the qubit 2 is 𝑍 2 = 𝐼𝑑 ⊗ 𝑍, we have : 𝑒 -𝑖.𝑡.𝛼.𝑍 1 = cos(𝑡. 𝛼) . 𝐼𝑑 -𝑖. sin(𝑡. 𝛼) . 𝑍 1 𝑒 -𝑖.𝑡.𝛼.𝑍 1 = cos(𝑡. 𝛼) . ( 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) -𝑖. sin(𝑡. 𝛼) . ( 1 0 0 0 0 1 0 0 0 0 -1 0 0 0 0 -1 ) and 𝑒 -𝑖.𝑡.𝛼.𝑍 2 = cos(𝑡. 𝛼) . ( 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) -𝑖. sin(𝑡. 𝛼) . ( 1 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 -1 ) Because (𝑍 1 . 𝑍 2 ) 2 = 𝐼𝑑 ⊗2 𝑒 -𝑖.𝑡.𝛾.𝑍 1 .𝑍 2 = cos(𝑡. 𝛾) . 𝐼𝑑 -𝑖. sin(𝑡. 𝛾) . 𝑍 1 . 𝑍 2 𝑒 -𝑖.𝑡.𝛾.𝑍 1 .𝑍 2 = cos(𝑡. 𝛾) . ( 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) -𝑖. sin(𝑡. 𝛾) . ( 1 The circuit 𝐶𝑋 1,2 . 𝑅 𝑍 2 (2𝑡. 𝛾). 𝐶𝑋 1,2 is the modelization of 𝑒 -𝑖.𝑡.𝛾.𝑍 1 .𝑍 2 . It can be easily verified by applying definition of 𝐶𝑋 over first and second qubits and 𝑅 𝑍 2 . Similarly we can see than the quantum circuit 𝐶𝑋 1,2 . 𝐶𝑋 2,3 . 𝑅 𝑍 2 (2𝑡. 𝛾). 𝐶𝑋 2,3 . 𝐶𝑋 1,2 performs 𝑒 -𝑖.𝑡.𝛾.𝑍 1 .𝑍 2 .𝑍 3

Specific Hamiltonian for Boolean expressions.

An efficient methodological way to represent basic Boolean features (literal) of SAT must permit to model both conjunctions (AND) and disjunctions (OR). One function 𝑓 = 0 and 𝑓 = 1 can be modeled with the Hamiltonian:

𝐻 𝑥 𝑗 = 1 2 (𝐼𝑑 ⊗𝑛 -𝑍 𝑗 )
A basic application of propositional logic law, permits to derive rules for composing Hamiltonians representing clauses and to construct representations of clauses or functions including Boolean formulas. The recursive construction rules have been first defined by (Hadfield, 2021) but it is possible to have an intuitive way to understand the model based on 1 2 (𝐼𝑑 ⊗𝑛 -𝑍 𝑗 ) by a cautious analysis of the operator. Note that in the very specific situation where 𝑛 = 1, we have:

1 2 (𝐼𝑑 -Z)
Let us consider 𝑓 such that, for 𝑘 ∈ 𝐸 𝑍 𝑗 , 𝑓(𝑒 𝑘 ) = 1 else 𝑓(𝑒 𝑘 ) = 0

with 1 2 (𝐼𝑑 ⊗𝑛 -𝑍 𝑗 ) Because 𝑍 𝑗 |𝑒 𝑘 ⟩ = { -1 if 𝑘 ∈ 𝐸 𝑍 𝑗 +1 if 𝑘 ∉ 𝐸 𝑍 𝑗
we have The formal rules that define the correct combinations of Hamiltonian to model Boolean functions have been lately introduced in (Hadfield, 2018) and they permit to defined a set of basic Hamiltonians. For each combination of simple expression with one literal or two literals, we apply tensor product and express the associated H, giving the expression as a Diag form and the associated minimal eigenvalue(s).

(𝐼𝑑 ⊗𝑛 -𝑍 𝑗 )|𝑒 𝑘 ⟩ = { 2 if 𝑘 ∈ 𝐸 𝑍 𝑗 0 if 𝑘 ∉ 𝐸 𝑍 𝑗 and ( 𝐼𝑑 ⊗𝑛 -𝑍 𝑗 2 ) |𝑒 𝑘 ⟩ = { 1 if 𝑘 ∈ 𝐸 𝑍 𝑗 0 if 𝑘 ∉ 𝐸 𝑍 𝑗
Application of the rules to two binary variables can be achieved considering that: 𝑍 1 = 𝑍⨂𝐼𝑑 = Diag(1,1, -1, -1) 𝑍 2 = 𝐼𝑑⨂𝑍 = Diag(1, -1,1, -1) And by consequence 𝑍 1 + 𝑍 2 = Diag(2,0,0, -2), -𝑍 1 -𝑍 2 = Diag(-2,0,0,2), 𝑍 1 -𝑍 2 = Diag(0,2, -2,0) 𝑍 1 . 𝑍 2 = 𝑍⨂𝑍 = Diag(1, -1, -1,1). Thus for example the operator 𝐻 = -𝑍 1 -𝑍 2 + 𝑍 1 . 𝑍 2 = Diag(-1, -1, -1,3) has two eigenvalues ( 3 and -1 ) and the ground states are |00⟩, |10⟩, |01⟩ corresponding to 𝑞 1 . 𝑞 2 = 0 with 𝑞 1 and 𝑞 2 being the two binary variables. All basic Boolean operations can be simulated in a similar way.

Because the Pauli 𝑍 gate commutes, circuits for individual terms in the Hamiltonians can be applied in sequence to simulate their sum.

SAT example

Let us consider the following SAT problem 𝜑 composed of 4 clauses and 3 variables:

(𝑥 1 ∨ 𝑥 2 ∨ 𝑥 3 ̅̅̅) (𝑥 1 ̅̅̅ ∨ 𝑥 2 ̅̅̅ ∨ 𝑥 3 ̅̅̅) (𝑥 1 ̅̅̅ ∨ 𝑥 2 ∨ 𝑥 3 ) (𝑥 1
̅̅̅ ∨ 𝑥 2 ∨ 𝑥 3 ̅̅̅) Let us consider the following assignments that define solutions of the problem: (0,1,0), (0,0,0), (1,1,0), (0,1,1). In the ket basis |0⟩ is used to model true (1 in the classical binary representation) and |1⟩ is used to model false (0 in the classical binary representation). By consequence, the 4 solutions of the 3-SAT problem refer to

(|1⟩ |0⟩ |1⟩), (|1⟩ |1⟩ |1⟩), (|0⟩ |0⟩ |1⟩), (|1⟩ |0⟩ |0⟩).
Modeling of the SAT derives from the previous rules and permits mapping from 𝜑 to Pauli 𝑍 gate allows us to obtain the Hamiltonians corresponding to the 𝜑 clauses. A full detailed description in available in chapter 6 page 322 [START_REF] Bourreau | Introduction à l'informatique quantique[END_REF]. Finally, the Hamiltonian that ensures that the four clauses simultaneously hold is:

𝐶 1 = 1 8 𝐼𝑑 + 1 8 (-𝑍 1 -𝑍 2 + 𝑍 3 + 𝑍 1 . 𝑍 2 -𝑍 1 . 𝑍 3 -𝑍 2 . 𝑍 3 + 𝑍 1 . 𝑍 2 . 𝑍 3 ) 𝐶 2 = 1 8 𝐼𝑑 + 1 8 ( 𝑍 1 + 𝑍 2 + 𝑍 3 + 𝑍 1 . 𝑍 2 + 𝑍 1 . 𝑍 3 + 𝑍 2 . 𝑍 3 + 𝑍 1 . 𝑍 2 . 𝑍 3 ) C 3 = 1 8 𝐼𝑑 + 1 8 (𝑍 1 -𝑍 2 -𝑍 3 -𝑍 1 . 𝑍 2 -
𝐻 𝑃 = 1 2 𝐼𝑑 + 1 4 𝑍 1 - 1 4 𝑍 2 + 1 4 𝑍 3 + 1 4 𝑍 1 . 𝑍 2 . 𝑍 3
A large enough value of 𝑇 must be used in the adiabatic algorithm to deflect probabilities on states modeling solutions. In the specific numerical experiments used for 𝑇 = 10, the algorithm permits to have more than 62+11+11+12=94% of the distribution which is concentrated on states modeling solution (table 1).These results push us into considering that the deflection of the wave function complied with the theoretical considerations and permits to identify all the optimal solution in this specific example. Similar results have been obtained using both Qiskit and MyQLM library. The results prove that relatively small values of 𝑇 permits to deflect probabilities on solution states and larger 𝑇 parameters significantly improve the convergence.

The previous results were done on simulator and have been endorsed by experiments performed on the 27 qubits IBM quantum computer referred to as ibmq_montreal which is composed of 27 qubits and has an average CNOT error about 1.2.10 -2 and an average readout error about 1.8.10 -2 with gates time about 426ns.

The Qiskit library is used to transpile and assign gates to the qubits (due to the fact that no triplet of qubits are directly fully entangled).

The results of table 2 prove the capacity of the ibmq_montreal to solve this 4-clauses and 3 variables SAT problem. 82.4% of the distribution is on the 4 solutions of the SAT problem proving that the quantum computer provides a solution that meets the theory and that the average CNOT and average readout error permits to execute the circuit. However, the number of gates involved in such a circuit increases with 𝑛 and 𝑇 and large values force such circuits to be only executed on the simulator. Note that circuit quickly becomes cumbersome as the number of iterations increases with the number of gates that quickly grows, to permit execution on the current noisy quantum computers. Clearly low 𝑇 implementations are the most suitable for early quantum computers.

Concluding remarks

In this paper we give an explicit algorithm formalization of the adiabatic algorithm which can be considered as a new paradigm in a similar but quite different approach from the well-known simulated annealing. The recent advances in quantum physics help us to define an efficient way to encode Boolean functions as the ground state of a Hamiltonian. The 𝑍 gate and the 𝑍 𝑖 . 𝑍 𝑖 … 𝑍 𝑘 operators combined with the Hadfield's construction rules, can be used to explicitly define a problem mapping for Boolean function.

The programmable noisy intermediate-scale quantum computers now available are limited to the resolution of small SAT instances but the number of qubits in quantum computers has vastly increased during the last 5 years and noise probability has decreased.

The SAT resolution with adiabatic algorithm is a good pedagogical direction and can be seen as a first step into the design and analysis of quantum algorithms for more complex problems in Operation

Research. Derived from quantum physics, adiabatic paradigm embeds problems into physical quantum hardware and permits to solve SAT and prove that applications of quantum theory should be of interest including complexity and eigenvalue problem computation. The class of simulated quantum annealing based approaches defined a new trend to solve the well-known difficulties in search space examination including diversification and local search intensification.

0 Fig. 1 .

 01 Fig. 1. |𝝍 𝒕 ⟩ can be assumed as constant An approximation of ∫ 𝐻(𝑢) 𝑇 𝑜

  +⟩ ⨂𝑛 And at step 𝑘: |𝜓 𝑘+1 ⟩ = 𝑒 -𝑖 ℏ .Δ𝑡.𝐻(𝑘.Δ𝑡) |𝜓 𝑘 ⟩ |𝜓 0 ⟩ = | +⟩ ⨂𝑛 For convenience a new system of units (that could present advantages) is introduced assuming that Δ𝑡 ℏ = 1 and leading to more compact expressions: |𝜓 𝑘+1 ⟩ = 𝑒 -𝑖.𝐻(𝑘.Δ𝑡) |𝜓 𝑘 ⟩ |𝜓 𝑘 ⟩ = 𝑒 -𝑖.𝐻((𝑘-1).Δ𝑡) |𝜓 𝑘-1 ⟩ |𝜓 0 ⟩ = | +⟩ ⨂𝑛 that also can be rewritten as: |𝜓 𝑡+Δ𝑡 ⟩ = 𝑒 -𝑖.𝐻(𝑡) |𝜓 𝑡 ⟩ |𝜓 𝑡 ⟩ = 𝑒 -𝑖.𝐻(𝑡-Δ𝑡) |𝜓 𝑡-1 ⟩ |𝜓 0 ⟩ = | +⟩ ⨂𝑛 The expression |𝜓 𝑡+Δ𝑡 ⟩ = 𝑒 -𝑖 ℏ .Δ𝑡.𝐻(𝑡) |𝜓 𝑡 ⟩ can be rewritten considering that 𝑒 𝑥 = 1 + 𝑥 + 𝑂(𝑥 2 ): |𝜓 𝑡+𝛥𝑡 ⟩ = 𝑒 -𝑖.𝐻(𝑡) |𝜓 𝑡 ⟩ |𝜓 𝑡+𝛥𝑡 ⟩ = [1 -𝑖. 𝐻(𝑡) + 𝑂([-𝑖. 𝐻(𝑡)] 2 )]|𝜓 𝑡 ⟩ |𝜓 𝑡+𝛥𝑡 ⟩ = [1 -𝑖. 𝐻(𝑡)]. |𝜓 𝑡 ⟩ + 𝑂(𝛥𝑡 2 ) |𝜓 𝑡+𝛥𝑡 ⟩ = |𝜓 𝑡 ⟩ -𝑖. 𝐻(𝑡). |𝜓 𝑡 ⟩ + 𝑂(𝛥𝑡 2 ) Let us assume that |𝜓 𝑡 ⟩ is the eigenvector of 𝐻(𝑡) with the eigenvalue 𝜆 𝑡 : |𝜓 𝑡+Δ𝑡 ⟩ = |𝜓 𝑡 ⟩ -𝑖. 𝜆 𝑡 . |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 ) |𝜓 𝑡+Δ𝑡 ⟩ = (1 -𝑖. 𝜆 𝑡 ). |𝜓 𝑡 ⟩ + 𝑂(Δ𝑡 2 ) Here we introduce a way to compute each piece of |𝜓 𝑇 ⟩ by recurrence from the previous piece. Knowing an initial state and this relation we can now derive an algorithm. This last expression proves that |𝜓 𝑡+Δ𝑡 ⟩ is a combination of |𝜓 𝑡 ⟩ minus 𝑖. 𝜆 𝑡 . |𝜓 𝑡 ⟩ which is orthogonal to |𝜓 𝑡 ⟩ since 𝑖 is a rotation of 90°. 𝑂(Δ𝑡 2 ) is the difference between |𝜓 𝑡+Δ𝑡 ⟩ and |𝜓 𝑡 ⟩ as stressed in the figure 3.

  by considering only very specific Hamiltonians 𝐻(𝑡) = 𝑠(𝑡). 𝐻 𝐷 + [1 -𝑠(𝑡)]. 𝐻 𝑃 where 𝑠(𝑡) = 𝑡 and where 𝑡 refers to the intervals of figure 2. 𝐻(𝑡) = 𝑡. 𝐻 𝐷 + (1 -𝑡). 𝐻 𝑃 with 𝐻(𝑡 + Δ𝑡)= (𝑡 + Δ𝑡). 𝐻 𝐷 + (1 -𝑡 -Δ𝑡). 𝐻 𝑃 𝐻(𝑡 + Δ𝑡) = 𝐻(𝑡) + Δ𝑡. (𝐻 𝐷 -𝐻 𝑃 )

Fig. 3 .

 3 Fig. 3. Typical curve of on adiabatic process |𝜓 𝑡+Δ𝑡 ⟩ is an eigenvector of 𝐻(𝑡 + Δ𝑡) with the eigenvalue 𝜆 𝑡 if 𝑂(Δ𝑡) is small enough meaning that |𝜓 𝑡+Δ𝑡 ⟩ and |𝜓 𝑡 ⟩ lead to the same energy level (related to minimal spectral gap).

  the eigenvalue 1 refers to the eigenvector | +⟩ and that the eigenvalue -1 refers to the eigenvector | -⟩ considering | +⟩ = 𝐻|0⟩ and | -⟩ = 𝐻|1⟩. Because the initial Hamiltonian is only directed on 𝐻 𝐷 the minimal eigenvalue -1 must be assigned to | +⟩. The usual local transverse-field Hamiltonian is

  𝑍 = 𝑍 1 = 2. |𝑒 1 ⟩. ⟨𝑒 1 | -𝐼𝑑 In the specific situation where 𝑛 = 2 𝑍 1 = 2. |𝑒 1 ⟩. ⟨𝑒 1 | + 2. |𝑒 2 ⟩. ⟨𝑒 2 | -𝐼𝑑 ⊗2 𝑍 2 = 2. |𝑒 1 ⟩. ⟨𝑒 1 | + 2. |𝑒 3 ⟩. ⟨𝑒 3 | -𝐼𝑑 ⊗2 In the specific situation where 𝑛 = 3 𝑍 1 = 2. |𝑒 1 ⟩. ⟨𝑒 1 | + 2. |𝑒 2 ⟩. ⟨𝑒 2 | + 2. |𝑒 3 ⟩. ⟨𝑒 3 | + 2. |𝑒 4 ⟩. ⟨𝑒 4 | -𝐼𝑑 ⊗3 𝑍 2 = 2. |𝑒 1 ⟩. ⟨𝑒 1 | + 2. |𝑒 2 ⟩. ⟨𝑒 2 | + 2. |𝑒 5 ⟩. ⟨𝑒 5 | + 2. |𝑒 6 ⟩. ⟨𝑒 6 | -𝐼𝑑 ⊗3 𝑍 3 = 2. |𝑒 1 ⟩. ⟨𝑒 1 | + 2. |𝑒 3 ⟩. ⟨𝑒 3 | + 2. |𝑒 5 ⟩. ⟨𝑒 5 | + 2. |𝑒 7 ⟩. ⟨𝑒 7 | -𝐼𝑑 ⊗3 When 𝑛 = 1, 𝑍 1 is the Pauli operator applied to |𝑥⟩ is illustrated on figure 4.

Fig. 4 .

 4 Fig. 4. Visualization of 𝒁. |𝒙⟩ (𝒏 = 𝟏) Let us denote 𝑀 = 𝑑𝑖𝑎𝑔(𝑚 1 , 𝑚 2 , … , 𝑚 𝑛 ) the diagonal matrix 𝑀 where diagonal terms are 𝑚 1 , 𝑚 2 , … , 𝑚 𝑛 . But, if 𝐼𝑑 = 𝑑𝑖𝑎𝑔(1,1) then 𝐼𝑑 ⊗ 𝑀 = 𝑑𝑖𝑎𝑔(𝑚 1 , 𝑚 2 , … , 𝑚 𝑛 , 𝑚 1 , 𝑚 2 , … , 𝑚 𝑛 ) and 𝑀 ⊗ 𝐼𝑑 = 𝑑𝑖𝑎𝑔(𝑚 1 , 𝑚 1 , 𝑚 2 , 𝑚 2 , … , 𝑚 𝑛 , 𝑚 𝑛 )

Fig 5 .

 5 Fig 5. Quantum circuit performing 𝒆 -𝒊.𝒕.𝜸.𝒁 𝟏 .𝒁 𝟐

  .e. for 𝑥 𝑘 = 0 if 𝑘 ∈ 𝐸 𝑍 𝑗 .Proposition 1In the qubit basis |0⟩ is used to model true and |1⟩ to model false. By consequence, a binary variable which can have only two values (true and false) is modelized by |0⟩ and |1⟩. A true binary variable is efficiently modeled by 𝐻 = -𝑍 = 𝐷𝑖𝑎𝑔 𝐻 (-1,1) which has 2 eigenvalues 1 and -1 . Because the minimal eigenvalue is concerned with the eigenvector |0⟩, one can conclude that -𝑍 is the correct modelization of a binary variable assigned to true. Similarly a false binary variable is efficiently modeled by 𝐻 = 𝑍 = Diag H (1, -1) with the eigenvalue 1 assigned to |0⟩ and the eigenvalue 1 assigned to |1⟩ , proving that 𝑍 is the correct modelization of a binary variable which value false.The construction of Hamiltonian dedicated to Boolean function is the direct consequence of the proposition 1. The mapping to the binary variable is obtained considering 𝐻

  is composed of longitudinal 𝐻 𝑃 and transverse field 𝐻 𝐷 where 𝑠(𝑡) is the amplitude that meets the natural dynamics modeled by the Schrödinger equation. Let us note that the temperature state commonly used in Simulated Annealing (SA) and the amplitude 𝑠(𝑡) of the Adiabatic Approach play a central and similar role. A high temperature in the Simulated Annealing refers to quite similar probabilities to transition from one state to a new one without any consideration of the function landscape that leads to a mixture of states into a uniform wave function. For the adiabatic optimization, large values of 𝑠(𝑡) (close to 1) define a linear combination of states with equal amplitude. However, the quantum adiabatic evolution is quite different from cooling principles since quantum evolution enforces the system to remain in the ground state contrary to SA that generates stochastic distribution proportional to the function landscape barriers.

	The solution of an optimization problem must be encoded in the
	ground state of a problem Hamiltonian 𝐻 𝑝 that encodes the
	problem into the Ising model to meet the physical interpretation.

  The Hamiltonian dependent problem 𝐻 𝑃 can be decomposed with 𝑍 𝑖 gates leading to, for example, 𝐻 𝑃 = 𝜔. 𝐼𝑑 + 𝛼. 𝑍 𝑖 + 𝛽. 𝑍 𝑗 + 𝛾. 𝑍 𝑖 . 𝑍 𝑗 . Considering 𝑍 𝑖 gate only, we have 𝑖. (𝜔. 𝐼𝑑 + 𝛼. 𝑍 𝑖 + 𝛽. 𝑍 𝑗 + 𝛾. 𝑍 𝑖 . 𝑍 𝑗 )]. |𝜓 𝑡 ⟩ 𝑑|𝜓 𝑡 ⟩ 𝑑𝑡 = (-𝑖𝜔. 𝐼𝑑 -𝑖. 𝛼. 𝑍 𝑖 -𝑖. 𝛽. 𝑍 𝑗 -𝑖. 𝛾. 𝑍 𝑖 . 𝑍 𝑗 ). |𝜓 𝑡 ⟩ 𝑖𝜔. 𝐼𝑑 -𝑖. 𝛼. 𝑍 𝑖 -𝑖. 𝛽. 𝑍 𝑗 -𝑖. 𝛾. 𝑍 𝑖 . 𝑍 𝑗 ). |𝜓 𝑡 ⟩

		𝑑|𝜓 𝑡 ⟩ 𝑑𝑡 = [-The solution of
		𝑑|𝜓 𝑡 ⟩ 𝑑𝑡	= (-
	𝑑|𝜓 𝑡 ⟩ 𝑑𝑡	= -𝑖. 𝐻. |𝜓 𝑡 ⟩
	that can be rewritten:

  𝛾.𝑍 1 .𝑍 𝑗 . |𝜓 0 ⟩ |𝜓 𝑡 ⟩ = 𝑒 -𝑖.𝑡.𝜔 . 𝑅 𝑍 𝑖 (𝑡. 𝛼). 𝑅 𝑍 𝑗 (𝑡. 𝛽). 𝑒 -𝑖.𝑡.𝛾.𝑍 𝑖 .𝑍 𝑗 . |𝜓 0 ⟩ Because 𝑒 -𝑖.𝑡.𝜔 does not impact |𝜓 𝑡 ⟩, then 𝑒 -𝑖.𝑡.𝜔 can be removed to obtain a more compact expression: |𝜓 𝑡 ⟩ = 𝑅 𝑍 𝑖 (𝑡. 𝛼). 𝑅 𝑍 𝑗 (𝑡. 𝛽). 𝑒 -𝑖.𝑡.𝛾.𝑍 𝑖 .𝑍 𝑗 . |𝜓 0 ⟩

	If 𝑖 = 1 and 𝑗 = 2 then we can note 𝑅 𝑍 1 (𝑡. 𝛼). 𝑅 𝑍 2 (𝑡. 𝛽) that leads to
	the formula:
	𝑅 𝑍 1 (𝑡. 𝛼). 𝑅 𝑍 2 (𝑡. 𝛽) = [𝑅

𝑍 (𝑡. 𝛼) ⊗ 𝑖𝑑]. [𝑖𝑑 ⊗ 𝑅 𝑍 (𝑡. 𝛽)] = 𝑅 𝑍 (𝑡. 𝛼) ⊗ 𝑅 𝑍 (𝑡. 𝛽).

  The following Hamiltonian ensures that clause 3 is true with clause 1 and 2 (𝐻 12 ).

					𝐻 12 =	1 4	𝐼𝑑 +	1 4	𝑍 3 +	1 4	𝑍 1 . 𝑍 2 +	1 4	𝑍 1 . 𝑍 2 . 𝑍 3
					𝐻 123 =	3 8	𝐼𝑑 +	1 8	𝑍 1 -+	1 8 1 8	𝑍 2 + 𝑍 2 . 𝑍 3 + 1 8 𝑍 3 + 3 8 𝑍 1 . 𝑍 2 . 𝑍 3 1 8 𝑍 1 . 𝑍 2 -	1 8	𝑍 1 . 𝑍 3
					𝑍 1 . 𝑍 3 + 𝑍 2 . 𝑍 3
					+ 𝑍 1 . 𝑍 2 . 𝑍 3 )
	C 4 =	1 8	𝐼𝑑 +	1 8	(𝑍 1 -𝑍 2 + 𝑍 3 -𝑍 1 . 𝑍 2 + 𝑍 1 . 𝑍 3 -𝑍 2 . 𝑍 3
					-𝑍 1 . 𝑍 2 . 𝑍 3 )
	Because clause 1 and clause 2 must hold simultaneously (𝐻 12 =
	(𝐶 1 + 𝐶 2 )) the Hamiltonian is:

Table 1 . Adiabatic optimization with

 1

		Percentage	Percentage	Percentage
		T=10	T=100	T=1000
	|111⟩	12.7%	16.7%	16.6%
	|100⟩	11.8%	17.3%	15.8%
	|101⟩	62.8%	50.5%	51.8%
	|001⟩	11.6%	15.5%	15.8%

𝑻 = 𝟏𝟎, 100 and 1000

Table 2 . Adiabatic optimization with T=20 and 2048 shots

 2