domain: info math phys

text:
Marc Bataille
email: marc.bataille1@univ-rouen.fr

Quantum circuits of CNOT gates

published or not. The documents may come

Introduction

The controlled Pauli-X gate, also called the CNOT gate, is a very common and usefull gate in quantum circuits. This gate involves two qubits i and j in a n-qubit system. One of the two qubits (say qubit i) is the target qubit whereas the other qubit plays the role of control. When the control qubit j is in the state |1 then a Pauli-X gate (i.e. a NOT gate) is applied to the target qubit i which gets flipped. When qubit j is in the state |0 nothing happens to qubit i. Actually, CNOT gates are of crucial importance in the fields of quantum computation and quantum information. Indeed, it appears that single qubit unitary gates together with CNOT gates constitute an universal set for quantum computation : any arbitrary unitary operation on a n-qubit system can be implemented using only CNOT gates and single qubit unitary gates (see [START_REF] Nielsen | Quantum Computation and Quantum Information: 10th Anniversary Edition[END_REF]Section 4.5.2] for a complete proof of this important result). As a consequence, many multiple-qubit gates are implemented in current experimental quantum machines using CNOT gates plus other single-qubit gates. In Figure 3 we give a few classical examples of such an implementation : a SWAP gate can be simulated using 3 CNOT gates, a controlled Pauli-Z gate can be implemented by means of 2 Hadamard single-qubit gates and one CNOT gate. These implementations are used for instance in the IBM superconducting transmon device (www.ibm.com/quantum-computing/).

From this universality result it is possible to show that any unitary operation can be approximated to arbitrary accuracy using CNOT gates together with Hadamard, Phase, and π/8 gates (see Figure 2 for a definition of these gates and [START_REF] Nielsen | Quantum Computation and Quantum Information: 10th Anniversary Edition[END_REF]Section 4.5.3] for a proof of this result). This discrete set of gates is often called the standard set of universal gates. Using a discrete set of gates brings a great advantage in terms of reliability because it is possible to apply these gates in an error-resistant way through the use of quantum error-correcting codes (again refer to [START_REF] Nielsen | Quantum Computation and Quantum Information: 10th Anniversary Edition[END_REF]Chapter 10] for further information). Currently, important error rates in CNOT gates implemented on experimental quantum computers are one of the main causes of their unreliability (see [START_REF] Linke | Experimental comparison of two quantum computing architectures[END_REF][START_REF] Wright | Benchmarking an 11-qubit quantum computer[END_REF] and Table 1). So the ability to correct errors on quantum circuits is a key point for successfully building a functional and reliable quantum computer. A complementary approach to the Quantum Error-Correction is to improve reliability by minimizing the number of gates and particularly the number of two-qubit gates used in a given circuit. Our work takes place in this context : we show that a precise understanding of the algebraic structures underlying circuits of CNOT gates makes it possible to reduce and, in some special cases, to minimize the number of gates in these circuits.

In this paper we also study the emergence of entanglement in CNOT gates circuits and we show that these circuits are a convenient tool for creating many types of entangled states. These particular states of a quantum system were first mentionned by Einstein, Podolsky and Rosen in their famous EPR article of 1935 [START_REF] Einstein | Can quantum-mechanical description of physical reality be considered complete ?[END_REF] and in Quantum Information Theory (QIT) they can be considered as a fundamental physical resource (see e.g. [START_REF] Horodecki | Quantum entanglement[END_REF]). Entangled states turn out to be essential in many areas of QIT such as quantum error correcting codes [START_REF] Gour | Entanglement of subspaces and errorcorrecting codes[END_REF], quantum key distribution [START_REF] Ekert | Quantum cryptography based on Bell's theorem[END_REF] or quantum secret sharing [START_REF] Cleve | How to share a quantum secret[END_REF]. Spectacular applications such as super-dense coding 1 [START_REF] Bennett | Communication via one-and twoparticle operators on einstein-podolsky-rosen states[END_REF] or quantum teleportation [START_REF] Vaidman | Teleportation of quantum states[END_REF][START_REF] Furusawa | Unconditional Quantum Teleportation[END_REF][START_REF] Pirandola | Advances in quantum teleportation[END_REF] are based on the use of classical entangled states. This significant role played by entanglement represents for us a good reason to understand how CNOT gates circuits can be used to create entangled states.

The paper is structured as follows. Section 2 is mainly a background section where we recall some classical notions in order to guide non-specialist readers. In Section 3 we investigate the algebraic structure of the group generated by CNOT gates. Section 4 will be dedicated to the optimization problem of CNOT gates circuits in the general case while in Section 5 we deal with optimization in particular subgroups of the group generated by CNOT gates. Finally in Section 6 we study how to use CNOT gates circuits to create certain usefull entangled states. Table 1: Error rates for CNOT gates acting on qubits i and j and for Hadamard gates acting on qubit i, where i, j ∈ {0, 1, 2, 3, 4}. The data comes from ibmq rome 5-qubit quantum computer after a calibration on May 12, 2020 and is publicly avalaible at www.ibm.com/quantum-computing/.

CNOT

2 Quantum circuits, CNOT and SWAP gates

We recall here some definitions and basic facts about quantum circuits and CNOT gates. We also introduce some notations used in this paper and we add some developments about SWAP gates circuits. For a comprehensive introduction to quantum circuits the reader may refer to [START_REF] Nielsen | Quantum Computation and Quantum Information: 10th Anniversary Edition[END_REF]Chapter 4] or, for a shorter but self-contained introduction), to our last article [START_REF] Bataille | Quantum circuits of cZ and SWAP gates: optimization and entanglement[END_REF].

In QIT, a qubit is a quantum state that represents the basic information storage unit. This state is described by a ket vector in the Dirac notation |ψ = a 0 |0 +a 1 |1 where a 0 and a 1 are complex numbers such that |a 0 | 2 + |a 1 | 2 = 1. The value of |a i | 2 represents the probability that measurement produces the value i. The states |0 and |1 form a basis of the Hilbert space H C 2 where a one qubit quantum system evolves.

Operations on qubits must preserve the norm and are therefore described by unitary operators. In quantum computation, these operations are represented by quantum gates and a quantum circuit is a conventional representation of the sequence of quantum gates applied to the qubit register over time. In Figure 1 A quantum system of two qubits A and B (also called a two-qubit register) lives in a 4-dimensional Hilbert space H A ⊗ H B and the computational basis of this space is :

(|00 = |0 A ⊗ |0 B , |01 = |0 A ⊗ |1 B , |10 = |1 A ⊗ |0 B , |11 = |1 A ⊗ |1 B ).
If U is any unitary operator acting on one qubit, a controlled-U operator acts on the Hilbert space H A ⊗ H B as follows. One of the two qubits (say qubit A) is the control qubit whereas the other qubit is the target qubit. If the control qubit A is in the state |1 then U is applied on the target qubit B and if qubit A is in the state |0 nothing is done on qubit B. If U is the Pauli-X operator then CNOT is nothing more than the controlled-X operator (also denoted by c -X) with control on qubit A and target on qubit B. So the action of CNOT on the two-qubit register is described by :

CNOT |00 = |00 , CNOT |01 = |01 , CNOT |10 = |11 , CNOT |11 = |10
(the corresponding matrix is given in Figure 2). Notice that the action of the CNOT gate on the system can be sum up by the following simple formula :

∀x, y ∈ {0, 1}, CNOT |xy = |x, x ⊕ y (1)
where ⊕ denotes the XOR operator between two bits which is also the addition in F 2 .

To emphasize that qubit A is the control and B is the target, CNOT is also denoted CNOT AB . So interchanging the roles played by A and B yields another operator denoted by CNOT BA .

∀x, y ∈ {0, 1},

CNOT BA |xy = |x ⊕ y, y (2)
CNOT : Another useful and common two-qubit quantum gate is the SWAP operator whose action on a basis state vector |xy is given by : SWAP |xy = |yx . The interesting point is that a SWAP gate can be simulated using 3 CNOT gates : This identity can be proved easily using equations ( 1) and ( 2).

A B CNOT AB =     1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0     Phase : S S = 1 0 0 i Hadamard : H H = 1 √ 2 1 1 1 -1 π/8 : T T = 1 0 0 e iπ 4
SWAP = CNOT AB CNOT BA CNOT AB = CNOT BA CNOT AB CNOT BA (3) SWAP : A B ∼ ∼ (5)
CNOT BA : A B ∼ H H H H (6) c -Z : A B ∼ H H ∼ H H (7)
The depth of a quantum circuit is the number of gates composing this circuit and we say that two circuits are equivalent if their action on the basis state vectors is the same in theory, i.e. the two circuits represents the same unitary operator. So Identity (3) is a proof of equivalence (5) in Figure 3. This equivalence can be used to implement a SWAP gate from 3 CNOT gates on an actual quantum machine. Two equivalent circuits generaly do not have the same depth. We use the word equivalent instead of the word equal to emphasize the fact that, due to the errors rate on gates in all current implementations (see Figure 1), two equivalent circuits acting on two qubits registers in the same input state will probably not produce in practice the same output state. This experimental fact is an important technical problem and a good motivation to work on quantum circuits optimization. Equivalence [START_REF] Cleve | How to share a quantum secret[END_REF] in Figure 3 is usefull in practice because the CNOT BA gate may not be native in some implementations, so we need to simulate it : this can be done using the native gate CNOT AB plus 4 Hadamard gates. Finally another classical equivalence of quantum circuits involves the CNOT gate with the controlled Pauli-Z gate (also denoted by c -Z) and the Hadamard gate (equivalence [START_REF] Hondt | The computational power of the W and GHZ states[END_REF] in Figure 3). We already mentionned it in the introduction to emphasize the ubiquity of the CNOT gates in quantum circuits as well as the importance of the universality theorem. Using the definitions of the Pauli-Z gate (Figure 1) and of a controlled-U gate, it is easy to check that the action of the c -Z gate on a basis state vector is defined by

∀x, y ∈ {0, 1}, c -Z |xy = (-1) xy |xy (4)
and that it is invariant by switching the control and the target qubits. Equivalence (7) can be proved using the definition of the Hadamard gate (Figure 1) and Relation (4).

On a system of n qubits, we label each qubit from 0 to n -1 thus following the usual convention. For coherence we also number the lines and columns of a matrix of dimension n from 0 to n -1 and we consider that a permutation of the symmetric group S n is a bijection of {0, . . . , n -1}. The n-qubit system evolves over time in the Hilbert space

H 0 ⊗ H 1 ⊗ • • • ⊗ H n-1
where H i is the Hilbert space of qubit i.

Hence the Hilbert space of an n-qubit system is isomorphic to C 2 n . In this space, a state vector of the standard computational basis is denoted by

|b 0 b 1 • • • b n-1 with b i ∈ {0, 1}.
A CNOT gate with target on qubit i and control on qubit j will be denoted X ij . The reader will pay attention to the fact that our convention is the opposite of the one generaly used in the literature (and in the beginning of this section) where CNOT ij denotes a CNOT gate with control on qubit i and target on qubit j. The reason for this convention is explained in the proof of Theorem 4, Section 3. So, if i < j, the action of X ij and X ji on a basis state vector is given by :

X ij |b 0 • • • b i • • • b j • • • b n-1 = |b 0 • • • b i ⊕ b j • • • b j • • • b n-1 , (8)
X ji |b 0 • • • b i • • • b j • • • b n-1 = |b 0 • • • b i • • • b j ⊕ b i • • • b n-1 . (9)
Notice that the X i,j gates are (represented by) matrices of size 2 n × 2 n in the orthogonal group O 2 n (R) and that they are permutation matrices.

X 02 :

q 0 q 1 q 2            
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0

            Figure 4:
The gate X 02 in a 3-qubit circuit and its matrix in the standard basis.

To represent a permutation of S n , we use the 2-line notation as well as the cycle notation and the n × n permutation matrix whose entry (i, j) is 1 if i = σ(j) and 0 otherwise. As an example, if σ ∈ S 6 is the permutation defined by σ(0

) = 4, σ(1) = 5, σ(2) = 0, σ(3) = 3, σ(4) = 2, σ (
M σ =         0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0        
. The cycle type of a permutation σ ∈ S n is the tuple λ = (n 1 , n 2 , . . . , n p ) of positive integers such that n 1 n 2 . . . n p , n = p i=1 n i and σ is the commutative product of cycles of length n i (including the cycles of length 1). This kind of tuple is called a decreasing partition of n. For instance σ = (204) [START_REF] Daniel | Bell's theorem without inequalities[END_REF](3) = (204) [START_REF] Daniel | Bell's theorem without inequalities[END_REF] has cycle type λ = (3, 2, 1). Notice that the cycle type of the identity is λ = (1, . . . , 1). Two permutations have the same cycle type iff they are in the same conjugacy class. For instance σ = (350) [START_REF] Linke | Experimental comparison of two quantum computing architectures[END_REF] has the same cycle type as σ and σ = γσγ -1 where γ = 0 1 2 3 4 5 5 2 3 1 0 4 .

A SWAP gate between qubit i and qubit j is denoted by S (ij) where (ij) is the cyclic notation for the transposition that exchange i and j. Since the symmetric group S n is generated by the transpositions, it is straightforward to prove that the group generated by the S (ij) is isomorphic to the symmetric group : each SWAP gate S (ij) in a n-qubit circuit corresponds to the transposition (ij) in S n . Notice that the cyclic notation of a transposition (i.e. (ij) = (ji)) implies S (ij) = S (ji) which is coherent with the symmetry of a SWAP gate. More generaly any circuit of SWAP gates maps to a permutation σ (examples in Figure 5 and Figure 13). If we denote by S σ the unitary operator corresponding to that circuit one has :

S σ |b 0 b 1 • • • b n-1 = |b σ -1 (0) b σ -1 (1) • • • b σ -1 (n-1) (10)
σ = (024)(13) S σ = S (02) S (24) S (13) q 0 q 1 q 2 q 3 q 4 We denote by cX n (n 2) the group generated by the n(n -1) gates (i.e. matrices)

X ij . cX n := X ij | 0 i, j < n, i = j (11)
X 12 X 10 X 31 X 03 : Proposition 1. The following identities are satisfied by the generators of cX n .

q 0 q 1 q 2 q 3
Involution :

X 2 ij = I (12) Braid relation : X ij X ji X ij = X ji X ij X ji = S (ij) (13) Commutation : (X ij X k ) 2 = I where i = , j = k (14) Non-commutation : (X ij X jk ) 2 = (X jk X ij ) 2 = X ik (15)
Proof. One checks each identity A = B by showing that the actions of gates A and B on a basis state vector |b 0 • • • b n-1 are the same. Using identities 8 and 9, the results follow from direct computation let to the readers. Using the identities from Proposition 1, one gets easily the conjugacy relations in cX n :

q 0 q 1 q 2 q 3 ∼ ∼ X 03 = X 02 X 23 X 02 X 23 = X 23 X 02 X 23 X 02
X ij X jk X ij = X jk X ik and X ij X ki X ij = X ki X kj . (16)
Let us denote by S n the group generated by the S ij ,

S n := S (ij) | 0 i, j < n (17)
As explained at the end of Section 2, S n is isomorphic to the symmetric group S n and Identity [START_REF] Gour | Entanglement of subspaces and errorcorrecting codes[END_REF] implies that S n is a subgroup of cX n . The action of S n on cX n by conjugation is given by the following proposition :

Proposition 2. For any permutation σ in S n and any i = j, one has :

S σ X ij S σ -1 = X σ(i)σ(j) . (18)
Proof. Since the transpositions generate the symmetric group, it suffices to prove the result when σ is a transposition, i.e. S σ = X k X k X k for some = k. Hence, the result comes straightforwardly from equalities (12), ( 13), ( 14) and [START_REF] Higuchi | How entangled can two couples get?[END_REF].

We denote by SL n (K) the special linear group on a field K and by T ij (n) the matrix I n + nE ij where n ∈ K \ {0}, i = j and E ij is the matrix with 0 on all entries but the entry (i, j) which is equal to 1. Let (e k ) 0 k<n be the canonical basis of the vector space K n and (e * k ) 0 k<n its dual basis. Then the matrix T ij (n) represents in the canonical basis the automorphism t ij (n) : u → u + ne * j (u)e i of K n which is a transvection fixing the hyperplane e k | k = j and directed by the line e i . So T ij (n) is a transvection matrix and this is a well known fact in linear algebra that the transvection matrices generate SL n (K). A simple way to find a decomposition in transvection matrices of any matrix M in SL n (K) is to use the Gauss-Jordan algorithm with M as input. This algorithm is generaly used to compute an inverse of a matrix but it also yields a decomposition of M as a product of transvections (see Figure 11 in Section 4 for an example).

q 0 q 1 q 2 q 3 ∼ ∼ X 03 = S (02) X 23 S (02) = S (23) X 02 S (23)
If K = F 2 then n = 1 and the set {T ij (n)|n ∈ K} is reduced to the n(n -1) transvection matrices T ij := I n + E ij . Moreover, since any invertible matrix of GL n (F 2 ) has determinant 1, one has :

GL n (F 2 ) = T ij | 0 i, j < n, i = j . (19)
We recall that the Gauss-Jordan algorithm is based on the following observation :

Proposition 3. Multiplying to the left (resp. the right) any F 2 -matrix M by a transvection matrix T ij is equivalent to add the jth line (resp. ith column) to the ith line (resp. j column) in M .

In particular, one has

T ij             b 0 . . . b i . . . b j . . . b n-1             =             b 0 . . . b i ⊕ b j . . . b j . . . b n-1             . ( 20
)
The notation

|b 0 b 1 • • • b n-1 used in QIT is a shorthand for the tensor product |b 0 ⊗ |b 1 ⊗ • • • ⊗ |b n-1 and it is convenient to identify the binary label b 0 b 1 • • • b n-1 with the column vector u = [b 0 , b 1 , • • • , b n-1 ] T of F n 2
since the ⊕ (XOR) operation between two bits corresponds to the addition in F 2 . So the computational basis of the Hilbert space H 0 ⊗ H 1 ⊗ • • • ⊗ H n-1 is from now on denoted by (|u ) u∈F n 2 and using Relation [START_REF] Holweck | Entanglement of four-qubit systems: a geometric atlas with polynomial compass II (the tame world)[END_REF] we can rewrite Relation (8) in a much cleaner way as

X ij |u = |T ij u . (21)
The above considerations lead quiet naturally to the following theorem :

Theorem 4. The group cX n generated by the CNOT gates acting on n qubits is isomorphic to GL n (F 2 ). The morphism Φ sending each X ij to T ij is an explicit isomorphism.

Proof. The surjectivity of Φ is due to the fact that GL n (F 2 ) is generated by the transvections T ij . Furthermore, due to Relation [START_REF] Hopcroft | Algorithm 447: Efficient algorithms for graph manipulation[END_REF], a preimage N by Φ of a matrix M in GL n (F 2 ) must satisfy the relation N |u = |M u for any basis vector |u and there is only one matrix N satisfying this relation. So Φ is also injective and the result is proved.

Notice that the image by Φ of a SWAP matrix S (ij) is a transposition matrix

P (ij) := T ij T ji T ij = T ji T ij T ji in GL n (F 2
) and more generaly Φ(S σ ) is the permutation matrix P σ for any permutation σ in S n . From now on we will denote by M σ = P σ M P -1 σ the conjugate of a matrix M in GL n (F 2 ) by a permutation matrix P σ . Using the isomorphism Φ, Relation (18) leads to

T σ ij = P σ T ij P -1 σ = T σ(i)σ(j) . (22)
The order GL n (F 2 ) is classicaly obtained by computing the number of different basis of F n 2 and Theorem 4 implies Corollary 5. If n 3 and K is a finite field, the symbols x ij (t), (1 i, j n, i = j, t ∈ K) subject to the relations :

|cX n | = 2 n(n-1) 2 n i=1 (2 i -1). (23)
(A) x ij (t)x ij (u) = x ij (t + u) (B) (x ij (t), x jk (u)) = x ik (tu) if i, j, k are distinct, (x ij (t), x k (u)) = 1 if j = k, i = define the group SL n (K).
It is straightforward to adapt this presentation to the case K = F 2 and we get so a presentation for the group cX n for any n 3.

Corollary 7. If n 3, a presentation of the group cX n is < S | R > where S is the set of the n(n -1) symbols x ij (0 i, j n -1, i = j) and R is the set of the relations :

x 2 ij = 1, (24)
(x ij x jk ) 2 = x ik , (25)
(x ij x k ) 2 = 1 if i = , j = k. ( 26
)
We remark that all the identities given by Proposition 1 appear in this presentation but Identity [START_REF] Gour | Entanglement of subspaces and errorcorrecting codes[END_REF]. Of course the braid relation ( 13) can be deduced from the presentation relations but the calculation is tricky. First of all, using the above relations we obtain the conjugacy relation x ij x jk x ij = x jk x ik = x ik x jk (as we did to obtain Relation ( 16)). Then we use many times this conjugacy relation to obtain the relation x ij x ji x ij x ji x ij = x ji and finally we get the braid relation x ij x ji x ij = x ji x ij x ji using Relation [START_REF] Linke | Experimental comparison of two quantum computing architectures[END_REF]. The calculation is detailled in Figure 9. A classical result in Group Theory is that the projective special linear group PSL n (K) is simple when n 3 (see e.g. [34, Chapter 3] for a proof). This group is defined as SL n (K)/Z where Z is the subgroup of all scalar matrices with determinant 1, which appears to be the center of SL n (K) . If K = F 2 the identity matrix is is the only scalar matrix that has determinant 1 and the center of SL n (F 2 ) is reduced to the trivial group. Hence SL n (F 2 ) = PSL n (F 2 ) and the group cX n is simple when n 3.

x ji x ij x ji = x ji (x ik x kj ) 2 x ji = (x ji x ik x kj x ji ) 2 = (x ji x ik x ji x ji x kj x ji ) 2 = (x ik x jk x ki x kj ) 2 x ij x ji x ij x ji x ij = x ij (x ik x jk x ki x kj ) 2 x ij = (x ij x ik x jk x ki x kj x ij ) 2 = (x ik x ij x jk x ki x ij x kj ) 2 = (x ik x ik x jk x ki x kj x kj ) 2 = (x jk x ki ) 2 = x ji
If n = 2, cX 2 has order 6 and is isomorphic to S 3 , one possible isomorphism being X 01 (01), X 10 (12), X 01 X 10 (012), X 10 X 01 (021) and X 01 X 10 X 01 (02). So cX 2 is not a simple group since the alternating group is always a normal subgroup of S n .

Identity (15) involves 3 distinct integers i, j, k and can be generalized by induction to an arbitrary number of distinct integers in the following way :

Proposition 8. Let i 1 , i 2 , . . . , i p be distinct integers (p 3) of {0, 1, . . . , n -1}, then : X i 1 ,ip = X i 1 ,i 2 X i 2 ,i 3 . . . X i p-2 ,i p-1 X i p-1 ,ip X i p-2 ,i p-1 . . . X i 2 ,i 3 2 (27)
Proposition 8 provides a simple way to adapt any CNOT gate to the topological constraints of a given quantum computer. These constraints can be represented by a directed graph whose vertices are labelled by the qubits. There is an arrow from qubit i to qubit j when these two qubits can interact to perform an X ij operation on the system. In a device with the complete graph topology, the full connectivity is achieved (see e.g. [START_REF] Linke | Experimental comparison of two quantum computing architectures[END_REF][START_REF] Wright | Benchmarking an 11-qubit quantum computer[END_REF]) and any X ij operation can be performed directly (i.e. without involving other two-qubit operations on other qubits than i and j). In contrast, the constraints in the LNN (Linear Nearest Neighbour) topology are strong as direct interaction is allowed only on consecutive qubits, i.e. only X i,i+1 or X i+1,i [START_REF] Zajac | Scalable gate architecture for a one-dimensional array of semiconductor spin qubits[END_REF]. Of course there are also many intermediate graph configurations as in the IBM superconducting transmon device (www.ibm.com/quantum-computing/). To implement a X ij gate when there is no arrow between i and j, the usual method is to use SWAP gates together with allowed CNOT gates as we did in Figure 8. But, if SWAP gates are implemented on the device using 3 CNOT gates (circuit equivalence ( 5)), this implementation can be done in a more reliable fashion by using less gates : just find a shortest path (i 1 = i, . . . , i p = j) between i and j in the undirected graph, then apply formula [START_REF] Miyake | Multipartite entanglement under stochastic local operations and classical communication[END_REF]. Notice that it can be important to take into account the error rate associated to each arrow (i, j) in the shortest path computation since it may vary from one gate to another (see Figure 1). Case of (i k , i k+1 ) is not an arrow, use the classical equivalence 6 in Figure 3 to invert target and control. Of course this adds two single-qubit gates to the circuit but the impact on reliability is small since on current experimental quantum devices the fidelity of single qubit gates as the Hadamard gate is much higher than any two-qubit gate fidelity (e.g. Figure 1 again). In the example below, we implement a CNOT gate considering the topology of the 15-qubit ibmq 16 melbourne device : Choosen path to implement X 4,7 : (4, 10, 9, 8, 7) X 4,7 = (X 4,10 X 10,9 X 9,8 X 8,7 X 9,8 X 10,9 ) 2

We end this section by remarking that GL p (F 2 ) can be regarded as a subgroup of GL n (F 2 ) if p < n. Indeed, let ϕ be the injective morphism from GL p (F 2 ) into

GL n (F 2 ) defined by ϕ(M ) = M 0 0 I n-p , one has GL p (F 2 ) ϕ(GL p (F 2 )
), so we will consider that GL p (F 2 ) ⊂ GL n (F 2 ) and no distinction will be made between matrices M and ϕ(M ).

Optimization of CNOT gates circuits

A CNOT circuit is optimal if there is not another equivalent CNOT circuit with less gates. In the same way a decomposition of a matrix M ∈ GL n (F 2 ) in product of transvections T i,j is optimal if M cannot be written with less transvections. If the depth of a circuit C is less than the depth of an equivalent circuit C we say that C is a reduction of C (or that C has been reduced to C ) and if C is optimal we say that C is an optimization of C (or that C has been optimized to C ).

For a better readability we denote from now on the transvection matrix T ij by [ij] and the permutation matrix P σ by σ. As a consequence, (ij) denotes the transposition which exchanges i and j as well as the transposition matrix

P (ij) . Notice that (ij) = (ji) but [ij] = [ji] T ([ij] is the transpose matrix of [ji]
). With these notations the braid relation ( 13) becomes

(ij) = (ji) = [ij][ji][ij] = [ji][ij][ji] and Identity (22) becomes σ[ij]σ -1 = [ij] σ = [σ(i)σ(j)]. In particular, (ij)[ij](ij) = [ij] (ij) = [ji].
From Section 3, any CNOT circuit can be optimized using the following rewriting rules.

Proposition 9. Let 0 i, j, k, l n -1 be distinct integers :

[ij] 2 = 1 (28) [ij][jk][ik] = [ik][ij][jk] = [jk][ij] ; [ij][ki][kj] = [kj][ij][ki] = [ki][ij] (29) [ij][jk][ij] = [jk][ik] = [ik][jk] ; [ij][ki][ij] = [ki][kj] = [kj][ki] (30) [ij][kl] = [kl][ij] ; [ij][ik] = [ik][ij] ; [ij][kj] = [kj][ij] (31) σ[ij] = [ij] σ σ = [σ(i)σ(j)]σ ; [ij]σ = σ[ij] σ -1 = σ[σ -1 (i)σ -1 (j)] (32)
In practice one tries to find an ad hoc sequence of the above rules to reduce or to optimize a given circuit (see Figure 10 for an example) but the computation can be tricky even with a few qubits. So it is difficult to build a general reduction/optimization algorithm from Proposition 9.

To optimize a CNOT circuit of a few qubits we use a C ANSI program that builds the Cayley Graph of the group GL n (F 2 ) by Breadth-first search and then find in the graph the group element corresponding to that circuit. This program optimizes in a few seconds any CNOT circuit up to 5 qubits and the source code can be downloaded at https://github.com/marcbataille/cnot-circuits. In the rest of this article we refer to it as "the computer optimization program". However, due to the exponential growth of the group order (for instance Card(cX 6 ) = 20 158 709 760), the computer method fails from 6 qubits with a basic PC. In this context we remark that the Gauss Jordan algorithm mentionned in Section 3 can be used as a heuristic method to reduce a given CNOT gates circuit (see Figure 11 for a detailled example). It works as follows.

• Each X ij gate of a given circuit C corresponds to a transvection matrix [ij]. Multiplying these transvection matrices yields a matrix M in GL n (F 2 ) that we call the matrix of the circuit in dimension n.

• The Gauss-Jordan algorithm applied to the matrix M gives a decomposition of M under the form M = KU where U is an upper triangular matrix and K is a matrix that is a lower triangular matrix if and only if the element of F 2 that appears on the diagonal at each step of the algorithm is 1, so we can choose it as pivot. In this case the matrix M as a LU (Lower Upper ) decomposition Circuit C to reduce :

q 0 q 1 q 2 M = [10](02)[01][12][20][01] (32)
= (02) [START_REF] Israel M Gelfand | Discriminants, Resultants and Multidimensional Determinant[END_REF][01] [12][20][01]

= [02] [START_REF] Hopcroft | Algorithm 447: Efficient algorithms for graph manipulation[END_REF] Optimized circuit C ∼ C :

q 0 q 1 q 2
Figure 10: Optimizing a CNOT circuit using an adhoc sequence of reduction rules.

and this decomposition is unique. If at a given step the bit on the diagonal is 0 then we have to choose another pivot and the matrix K is not triangular anymore. Morevoer the decomposition M = KU is not unique as the matrix K depends on the choice of the pivot at each step, so the algorithm is not deterministic in this case.

• A decomposition of K in product of transvections is directly obtained while executing the algorithm and a simple and direct decomposition of an upper triangular matrix

U = (u ij ) in GL n (F 2 ) is U = 1 j=n-1 0 i=j-1 [ij] u ij .
We call this decomposition the canonical decomposition of U and symmetrically the canonical decomposition of a lower triangular matrix is

L = n-2 j=0 n-1 i=j+1 [ij] l ij .
• Replacing each transvection [ij] in the decomposition of M by the corresponding CNOT gate X ij , we obtain a circuit C equivalent to C. If the depth of C is less than the depth of C then we have successfully reduced the circuit C. If not, the heuristic failed.

We note that the circuit C obtained by this process is generally not optimal even for small values of n. However the Gauss-Jordan algorithm has the great advantage of providing an upper bound on the optimal number of CNOT gates in a circuit.

Proposition 10. Any n-qubit circuit of CNOT gates is equivalent to a circuit composed of less than n 2 gates.

Proof. We apply the Gauss-Jordan elimination algorithm to get a decomposition of M ∈ GL n (F 2 ) in transvections. The first part of the algorithm consists in multiplying M to the left by a sequence of transvections in order to obtain an upper triangular matrix U . For k = 0, 1, . . . , n -1, we consider the column k and the entry of the matrix on the diagonal. If this entry is 1 we choose it as a pivot but if it is 0 we first need to put a 1 on the diagonal. This can be done by swaping row k with a row whose entry ( , k) is 1. However, this will cost 3 transvections and it is more economical to add row to row k, i.e. multiplying to the left by [k, ]. The number of left multiplications by transvections necessary to have a pivot equal to 1 on the diagonal at each step is bounded by n -1 and the number of left multiplications necessary to eliminate the 1's below the pivot is bounded by

n -1 + • • • + 1 = n(n-1)

2

. Hence the number of transvections that appears in the first part of the algorithm is bounded by n(n+1) 2 -1. In the second part of the algorithm we just write the canonical decomposition of U which contains at most

n -1 + n -2 + • • • 1 = n(n-1)
2 transvections. Finally we see that the number of transvections in the resulting decomposition of M is at most n 2 -1. The canonical decomposition of an upper or lower triangular matrix is generally not optimal, so we propose in what follows another algorithm to decompose a triangular matrix in transvections. Applying this algorithm to the matrix U when the decomposition of M is KU or to both matrices L and U when the decomposition of M is LU can often improve the decomposition given by the Gauss-Jordan heuristic, especially when the triangular matrix has a high density of 1's (See Figure 12 for an example). We describe below this algorithm for an upper triangular matrix (UTD algorithm) but it can be easily adapted to the case of a lower triangular matrix (LTD algorithm). We denote by |L i | is the number of 1's in line i of a matrix.

INPUT : C = q 0 q 1 q 2 q 3 M = [02][30][21][23][32][20][23][30][20][03][12][01] M =     0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1     ; [03]M =     1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1     ; [31][20][30][03]M =     1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1     K = [03][30][20][31] ; U = [12] ; M = KU = [03][30][20][31][12] OUTPUT : C = q 0 q 1 q 2 q 3

Algorithm 11. Upper Triangular Decomposition (UTD algorithm)

INPUT : An upper triangular matrix U in GL n (F 2 ). OUTPUT : A sequence S = (t 0 , t 1 , . . . , t p-1 ) of transvections such that U = p-1 j=0 t j . 1 S = (); j = 0; 2 while U = I :

3 for i = 0 to n -2 : 4 if |L i | > 1 : 5 Let E i = {k | i < k n -1 and |L i ⊕ L k | < |L i |}; 6 if E i = ∅ : 7 Choose the smallest k ∈ E i such that |L i ⊕ L k | is minimal; 8 U = [ik]U ; 9 t j = [ik] ; j = j + 1; 10 return S;
The algorithm ends because for each loop (for i = 0 to n -2) the number of 1's in the matrix decreases of at least one. Indeed, there is always at least one couple (i, k) choosen during this loop, namely :

i = max{j | |L j | > 1} and k = max{j | U ij = 0}
. Furthermore, we notice that the number of transvections in the decomposition S is always less than or equal to the number of transvections in the canonical decomposition of the matrix U since each transvection in the canonical decomposition of U contributes to a decrease of exactly one in the initial number of 1's in the matrix U whereas each transvection in S contributes to a decrease of at least one in this initial number of 1's.

Again, the decomposition obtained by applying the Gauss-Jordan algorithm followed by the UTD or LTD algorithm is generally not optimal. In fact we conjecture the following result.

Conjecture 12. Any n-qubit circuit of CNOT gates is equivalent to a circuit composed of at most 3(n -1) gates. The upper bound of 3(n -1) gates is reached only in the special case of SWAP gates circuits S σ where σ is a cycle of length n in S n .

We checked this conjecture up to 5 qubits thanks to a C ANSI program (see the results summarized in Table 2). The source code of the program can be downloaded at https://github.com/marcbataille/cnot-circuits.

Optimization in subgroups of cX n

In this section we describe the structure of some particular subgroups of cX n GL n (F 2 ) and we propose algorithms to optimize CNOT gates circuits of these subgroups. Starting from an input circuit C, we first compute the matrix M of the circuit in dimension n. In some specific cases the matrix M has a particular shape so we can propose an optimal decomposition in transvections for M and output an optimization C of the circuit C. We describe 3 subgroups corresponding to 3 types of matrices with the objective of building step by step a kind of atlas of CNOT gates circuits with specific optimization algorithms. optimal length n = 2 n=3 n = 4

n = 5 l = 0 1 1 1 1 l =

Permutation matrices

The first case considered is when the matrix M ∈ GL n (F 2 ) of the circuit is a permutation matrix P σ . In this case the circuit is equivalent to a SWAP gates circuit and we work in S n , the subgroup of cX n generated by the S (ij) gates which is isomorphic to S n (see example in Figure 13).

Proposition 13. Any permutation matrix P σ can be decomposed as a product of 3(n -p) transvections where p is the number of cycles of the permutation σ.

Proof. Let λ = (n 1 , . . . , n p ) be the cycle type of σ. Any cycle of length n i can be decomposed in the product of n i -1 transpositions and each transposition can be decomposed in a product of 3 transvections, so the total number of transvections used in the decomposition of P σ is 3 p i=1 (n i -1) = 3(n -p). The following conjecture has been checked up to 5 qubits using the computer optimization program.

Conjecture 14. The decomposition in transvections of a permutation matrix P σ given by Proposition 13 is optimal.

Block diagonal matrices

In the second case, we consider that the matrix M of the circuit in dimension n is a block diagonal matrix or the conjugate of a diagonal block matrix by a permutation matrix. Let (n 1 , . . . , n p ) be a tuple of p positive integers such that p i=1 n i = n and OUTPUT : C = q 0 q 1 q 2 q 3 q 4

INPUT : C = q 0 q 1 q 2 q 3 q 4 ( 13
M =       1 1 1 0 0 0 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0       =       1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1       L       1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1       U Canonical decomposition of L : L = [
(8 CNOT) where S = (A 1 , . . . , A p ) is a tuple of

matrices A i in GL n i (F 2 ).
Here M S is a block diagonal matrix and we shall see right after the case of the conjugate of a block diagonal matrix by a permutation matrix.

Clearly

{M S | S ∈ GL n 1 (F 2 ) × • • • × GL np (F 2 )} is a group isomorphic to the direct group product GL n 1 (F 2 ) × • • • × GL np (F 2 ) since M S =      A 1 0 . . . 0 0 I n 2 . . . . . . . . . . . . . . . 0 0 . . . 0 I np      × • • • ×      I n 1 0 . . . 0 0 . . . . . . . . . . . . . . . I n p-1 0 0 . . . 0 A p     
where I α is the identity matrix in dimension α. This equality can be written as M S = p i=1 M i where

q 0 q 1 q 2 q 3 C 1 C 2 ∼ q 0 q 1 q 2 q 3 C 1 C 2 M = P σ =     0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0     ; σ = (3210) = (23)(12)(01)
Figure 13: A cyclic permutation of the qubits between two circuits C 1 and C 2

M i =   I N i-1 0 0 0 A i 0 0 0 I n-N i   and N i = i k=1 n k .
We recall that the conjugation M σ = P σ M P -1 σ of a square matrix M by a permutation matrix P σ has the following effect on M : if we denote by L i (resp. L i ) and C i (resp. C i ) the lines and columns of matrix M (resp. M σ ) then

L i = L σ -1 (i) and C i = C σ -1 (i) , hence if M = (m ij ) and M = (m ij ) then m ij = m σ -1 (i)σ -1 (j)
. So, if we consider now a tuple of p permutations (σ 1 , . . . , σ p ) verifying the conditions σ i (n

1 +n 2 +• • •+n i-1 ) = 0, σ i (n 1 + n 2 + • • • + n i-1 + 1) = 1, . . . , σ i (n 1 + n 2 + • • • + n i-1 + n i -1) = n i -1 then M S = p i=1 (M σ i i ) σ -1 i = p i=1 (M i ) σ -1 i where M i = A i 0 0 I n-n i A i . Moreover,
for Relation [START_REF] Horodecki | Quantum entanglement[END_REF], the number of transvections in an optimal decomposition of any matrix M in GL n (F 2 ) is the same as the number of transvections in an optimal decomposition of M σ for any permutation σ. As a consequence, the product of the conjugates by σ -1 i of any optimal decomposition of the matrix A i yields an optimal decomposition of the matrix M S (see Figure 14 for an example).

The generalization of the previous situation to the case of a matrix M = M σ S where M S is a block diagonal matrix and σ a permutation matrix is straightforward. Indeed, if we have an optimal decomposition of M S in transvections, then we deduce an optimal decomposition for M σ S by conjugating by σ each transvection in the decomposition of M S . This is due to the fact that the number of transvections in an optimal decomposition of any matrix M in GL n (F 2 ) is the same as the number of transvections in an optimal decomposition of M σ (see Relation [START_REF] Horodecki | Quantum entanglement[END_REF]). In fact the problem we adress here is rather the following : how can we efficiently recognize that the matrix M is of type M = M σ S ? To do that we interpret the matrix M of the circuit in dimension n as the adjacency matrix of the directed graph G(M ) whose set of vertices is V = {0, 1, . . . , n -1} and whose set of edges is E = {(i, j) | m ij = 1}. We call G(M ) the graph of the circuit. The graph (G(M )) σ defined by the set of vertices σ(V ) = V and by the set of edges

E σ n = {(σ(i), σ(j)) | m ij = 1} is isomor- phic to G(M ). Besides, E σ n = {(i, j) | m σ -1 (i)σ -1 (j) = 1} and M σ = m σ -1 (i)σ -1 (j) , so (G(M )) σ = G(M σ ). The graph G(M S ) is a disconnected graph whose p con- nected components are V 1 = {0, . . . , n 1 -1}, V 2 = {n 1 , . . . , n 1 + n 2 -1}, . . . , V p = Let M (A 1 ,A 2 ) =          
1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 2 3 4 5 6 3 4 5 6 0 1 2 , then :

          where A 1 =     1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1     and A 2 =   0 0 1 1 1 1 0 1 1   . Let σ 1 = I 7 and σ 2 =
M (A 1 ,A 2 ) =          
1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1

                   
0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1

          σ -1 2 = M 1 σ -1 1 M 2 σ -1 2 .
Using the computer optimization program, one finds

A 1 = [13][01][30][21][13][02][01] , A 2 = [01][12][10][21][01].
Hence an optimal decomposition for M is

M (A 1 ,A 2 ) = [
{n 1 + • • • + n p-1 , . . . , n 1 + • • • + n p-1 + n p -1} , so the graph G(M σ S ) = (G(M S ))
σ is also a disconnected graph whose p connected components are σ(V 1 ), . . . , σ(V p ). By applying a Breadth-first search or a Deepth-first search to the graph G(M ) of a given circuit, one can get the connected components of G(M ) in linear time (see [START_REF] Hopcroft | Algorithm 447: Efficient algorithms for graph manipulation[END_REF] for a detailled description of the algorithm). Suppose that we find more than one connected component, say C 1 , . . . C p and let n i be the cardinal of C i for 1 i p. Let σ be any permutation verifying σ(

C 1 ) = {0, . . . , n 1 -1}, σ(C 2 ) = {n 1 , . . . , n 1 + n 2 -1}, . . . , σ(C p ) = {n 1 + • • • + n p-1 , . . . , n 1 + • • • + n p-1 + n p -1}.
Then the matrix M σ is a block diagonal matrix M S and we obtain an optimal decomposition of M σ as explained before. Finally, we deduce an optimal decomposition of M = (M σ ) σ -1 by conjugating by σ -1 this decomposition (see Figure 15 for an example). Since we can find an optimal decomposition of any matrix of GL n (F 2 ) for n 5 (using the computer optimization program), then we can optimize any CNOT circuit whose graph has connected components of size up to 5.

Bit reverse of permutation matrices

The third and last case we consider in this section is the case of a matrix M of type σ where σ denotes a permutation matrix in even dimension in which all the bits are

INPUT : C = q 0 q 1 q 2 q 3 q 4 q 5 q 6 (14 CNOT) M =           1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1           C 1 = {0, 3, 5, 6}, C 2 = {1, 2, 4}
M σ =           1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1           = M (A 1 ,A 2 )
From example 14,

M (A 1 ,A 2 ) = [13][01][30][21][13][02][01][45][56][54][65][45].
The corresponding circuit is :

q 0 q 1 q 2 q 3 q 4 q 5 q 6 M = M σ -1 (A 1 ,A 2 ) = [30][53][05][63][30][56][53][21][14][12][41][21]
OUTPUT : C = q 0 q 1 q 2 q 3 q 4 q 5 q 6

(12 CNOT) reversed. For instance (02

)(13) =     1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1     and I 4 =     0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0     .
We check that σ = σI. For instance (02

)(13) =     0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0         0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0     .
Lemma 15. Let n 2 be an even integer.

I n ∈ GL n (F 2 ) and I n 2 = I n . ( 33
) ∀σ ∈ S n , σI n σ -1 = I n . (34) ∀σ, γ ∈ S n , σ γ = σγ. ( 35
)
Proof. Let denote by 1 n the matrix of dimension n whose elements are all equal to 1. One has

I n 2 = (I n ⊕ 1 n ) 2 = I 2 n ⊕ 1 2 n = I n ⊕ 1 2 n . If n is even then 1 2 n = 0, hence I n 2 = I n . Besides σI n σ -1 = σ(I n ⊕ 1 n )σ -1 = σI n σ -1 ⊕ σ1 n σ -1 = I n ⊕ 1 n = I n . Finally σ γ = σI n γI n = σγγ -1 I n γI n = σγI n 2 = σγ.
From Lemma 15 we directly deduce the structure of the group < σ, σ > :

Proposition 16. The group generated by the permutation matrices and the matrix I n is isomorphic to the cartesian product S n × (F 2 , ⊕).

The following lemma gives a simple decomposition for the product of [ij][ki]

[jk] by a transposition matrix (ij), (ki) or (jk). We use it in the proof of Proposition 19.

Lemma 17. Let 0 i, j, k n -1 be distinct integers :

R1 : [ij][ki][jk](jk) = [ki][ij][jk] (36) L1 : (ij)[ij][ki][jk] = [ij][jk][ki] (37) R2 : [ij][ki][jk](ki) = [jk][ij][ki][jk] (38) L2 : (ki)[ij][ki][jk] = [ij][ki][jk][ij] (39) R3 : [ij][ki][jk](ij) = [ji][ik][kj] (40) L3 : (jk)[ij][ki][jk] = [ji][ik][kj] (41)
Proof. We prove only (41), the other proofs being similar : Proposition 18. Let n 2 be even and let n = 2q.

(jk)[ij][ki][jk] = [ij] (jk) [ki] (jk) (jk)[jk] = [ik][ji](jk)[jk] (using (22)) = [ik][ji][jk][kj] = [ji][ik][kj] (using ( 29
Let B q = q-2 i=0 [2i + 1 2i + 2 2i + 3] if q > 1 and B 1 = I 2 .
Then

I 2q = B -1 q (01)B q . ( 42
)
Proof. We proove the result by induction on q 1. The initial case follows from I 2 = (01). Induction step : suppose that q 1 and I 2q = B -1 q (01)B q . We use the morphism ϕ already mentionned in the final remark of Section 3 : ϕ is the injective morphism from GL 2q (F 2 ) into GL 2(q+1) (F 2 ) defined by ϕ(M ) = M 0 0 I 2 and we make no distinction between matrices M and ϕ(M ).

So, one has :

ϕ(I 2q ) = I 2q 0 0 I 2 =           0
          and ϕ(I 2q ) = B -1 q (01)B q .
Due to the effect on lines and columns of a mutliplication by a transvection matrix (Proposition 3), we check that :

[2q 2q +1][2q +1 2q -1][2q -1 2q]ϕ(I 2q )[2q -1 2q][2q +1 2q -1][2q 2q +1] = I 2q+2 . Since [2q -1 2q][2q + 1 2q -1][2q 2q + 1] = [2q -1 2q 2q + 1] one has : I 2q+2 = [2q -1 2q 2q + 1] -1 ϕ(I 2q )[2q -1 2q 2q + 1]. I 2q+2 = [2q -1 2q 2q + 1] -1 B -1 q (01)B q [2q -1 2q 2q + 1]. Hence : I 2q+2 = B -1 q+1 (01)B q+1 .
Formula (42) gives a decomposition of I 2q in 3(q -1) + 3 + 3(q -1) = 3(n -1) transvections (where n = 2q). We remark that this decompostion is not optimal if q > 1. Indeed, it can be reduced as follows.

Firstly

B q = q-2 i=0 [2i + 1 2i + 2 2i + 3] = [12][31][23] q-2 i=1 [2i + 1 2i + 2 2i + 3]. Thus B q = [12][31][23]B q , where B q = q-2 i=1 [2i + 1 2i + 2 2i + 3]. Hence I 2q = B -1 q (01)B q = (B q ) -1 [23][31][12](01)[12][31][23]B q . ( 43
)
Then, one has : So, from Equation (43), we now have a decomposition of I 2q in 3(q -2) + 8 + 3(q -2) = 3(n -1) -1 transvections. We remark that this result is coherent with Conjecture 12. Indeed, since I 2q is not a cycle of length n in GL n (F 2 ), it must have a decomposition in striclty less than 3(n -1) transvections. We also conjecture that this decomposition of I n in 3(n -1) -1 transvections is optimal and we checked this conjecture for n = 4 using our computer optimization program.

Actually Proposition 18 is a special case of the following proposition.

Proposition 19. Let n 2 be even and let n = 2q. For any permutation matrix σ of GL n (F 2 ) different from I n there exists q -1 matrices M 1 , . . . , M q-1 of type [xyz] , q -1 integers ε i ∈ {1, -1}, q -1 matrices M 1 , . . . , M q-1 of type [xyz] and q -1 integers ε i ∈ {1, -1} such that :

I n = q-1 i=1 M ε i i σ q-1 i=1 M ε i i (44)
Proof. Let n 2 be an even integer. We denote by P * n the set of decreasing partitions λ of n such that λ = (1, . . . , 1). Any λ ∈ P * n is the cycle type of a permutation different from the identity (see Section 2). If λ ∈ P * n , we denote by α λ the permutation of S n (or equivalently the permutation matrix of GL n (F 2 )) defined by :

α λ = (0 . . . n 1 -1) cycle of length n 1 (n 1 . . . n 1 + n 2 -1) cycle of length n 2 . . . ( p-1 i=1 n i • • • p i=1 n i -1) cycle of length np .
Notice that α λ has cycle type λ and is therefore different from the identity. If n 4 and λ ∈ P * n , we denote by λ -2 the element of P * n-2 obtained from λ as follows. To describe the operation we distinguish the general case (n p > 2) and three specific cases and we write each time the relation between α λ and α λ -2 . Notice that α λ -2 is a permutation in S n-2 or a permutation matrix in GL n-2 (F 2 ) since λ ∈ P * n-2 but we can consider α λ -2 as a permutation in S n (by setting α λ -2 (n -2) = n -2 and α λ -2 (n -1) = n -1) or as a permutation matrix of GL n (F 2 ) (using the injective morphism ϕ from GL n-2 (F 2 ) into GL n (F 2 )). In the general case, λ -2 := (n 1 , . . . , n p -2), so

α λ -2 = α λ (n-2 n-1)(n-3 n-2). If n p = n p-1 = 1 (first specific case), λ -2 := (n 1 , . . . , n p-2 ), hence α λ -2 = α λ . If n p = 1 and n p-1 > 1 (second specific case), λ -2 := (n 1 , . . . , n p-2 , n p-1 -1), hence α λ -2 = α λ (n -3 n -2). If n p = 2 (third specific case), λ -2 := (n 1 , . . . , n p-1 ), hence α λ -2 = α λ (n -2 n -1).
Without loss of generality we can prove Proposition 19 in the case of a permutation σ = α λ where λ ∈ P * n . Indeed, if σ is any permutation (different from the identity) that has cycle type λ, then σ is in the same conjugacy class as α λ since they have the same cycle type and we build a permutation γ such that σ = γα λ γ -1 . Since

I n = q-1 i=1 M ε i i α λ q-1 i=1 M ε i i and I n 34 = I n γ , it follows that I n = q-1 i=1 (M ε i i ) γ σ q-1 i=1 M ε i i γ . ( 45
)
To conclude it is sufficient to notice that ([ijk] ε ) γ = [γ(i)γ(j)γ(k)] ε for any permutation γ and for ε ∈ {-1, 1}. So Equation (45) can easily be writen under the form of Equation ( 44) and this proves Proposition 19 for the permutation σ.

We prove now Proposition 19 for a permutation α λ , by induction on n 2 even. The intial case is clear since there is only one partition of 2 different from (1, 1) namely λ = (2). In this case α λ = (01) = I 2 . Induction step : let n 2 be an even integer, let λ in P * n+2 and α λ in S n+2 . From Proposition 18, one has

I n+2 = [n -1 n n + 1] -1 I n [n -1 n n + 1]. We use the induction hypothesis on α λ -2 ∈ S n : I n = q-1 i=1 M ε i i α λ -2 q-1 i=1 M ε i i , hence I n+2 = [n -1 n n + 1] -1 q-1 i=1 M ε i i α λ -2 q-1 i=1 M ε i i [n -1 n n + 1]. ( 46
)
We consider now the different possible relations between α λ -2 and α λ , starting by the three specific cases and ending by the general case which is more technical.

In the first case α λ -2 = α λ , so Equation ( 46) becomes

I n+2 = [n -1 n n + 1] -1 q-1 i=1 M ε i i α λ q-1 i=1 M ε i i [n -1 n n + 1
] and we are done with the induction step. In the second case α λ -2 = α λ (n -1 n), so Equation (46) becomes

I n+2 = [n -1 n n + 1] -1 q-1 i=1 M ε i i α λ (n -1 n) q-1 i=1 M ε i i [n -1 n n + 1]. ( 47
) Let M = (n -1 n) q-1 i=1 M ε i i [n -1 n n + 1].
One has :

M = q-1 i=1 M ε i i (n-1 n) (n -1 n)[n -1 n][n + 1 n -1][n n + 1] 37 = q-1 i=1 M ε i i (n-1 n) [n -1 n][n n + 1][n + 1 n -1] = q-1 i=1 M ε i i (n-1 n) [n + 1 n -1 n] -1 .
Hence Equation (47) becomes

I n+2 = [n -1 n n + 1] -1 q-1 i=1 M ε i i α λ q-1 i=1 M ε i i (n-1 n) [n + 1 n -1 n] -1
and we are done with the induction step since (

[xyz] ε ) σ = [σ(x)σ(y)σ(z)] ε where σ = (n -1 n).
In the third case α λ -2 = α λ (n n + 1), so Equation (46) becomes

I n+2 = [n -1 n n + 1] -1 q-1 i=1 M ε i i α λ (n n + 1) q-1 i=1 M ε i i [n -1 n n + 1]. ( 48
) Let M = (n n + 1) q-1 i=1 M ε i i [n -1 n n + 1]. One has : M = q-1 i=1 M ε i i (n n+1) (n n + 1)[n -1 n][n + 1 n -1][n n + 1] 41 = q-1 i=1 M ε i i (n n+1) [n n -1][n -1 n + 1][n + 1 n] = q-1 i=1 M ε i i (n n+1) [n + 1 n n -1] -1 .
Hence Equation (48) becomes

I n+2 = [n -1 n n + 1] -1 q-1 i=1 M ε i i α λ q-1 i=1 M ε i i (n n+1) [n + 1 n n -1] -1
and we are done with the induction step since ([xyz] ε ) σ = [σ(x)σ(y)σ(z)] ε where σ = (n n + 1). In the general case, we start by conjugating each member of Equation ( 46) by (n n + 1). Using the invariance of I n by conjugation (Identity ( 34)), we get :

I n+2 = (n n+1)[n-1 n n+1] -1 q-1 i=1 M ε i i α λ -2 q-1 i=1 M ε i i [n-1 n n+1](n n+1). (49)
On one hand, we have :

(n n + 1)[n -1 n n + 1] -1 = (n n + 1)[n n + 1][n + 1 n -1][[n -1 n] 37 = [n n + 1][[n -1 n][n + 1 n -1] = [n n + 1 n -1] On the other hand we have : [n -1 n n + 1](n n + 1) = [n -1 n][n + 1 n -1][n n + 1](n n + 1). 36 = [n + 1 n -1][n -1 n][n n + 1]. = [n n + 1 n -1] -1
So Equation (49) becomes :

I n+2 = [n n + 1 n -1] q-1 i=1 M ε i i α λ -2 q-1 i=1 M ε i i [n n + 1 n -1] -1
In the general case, one has :

α λ -2 = α λ (n n + 1)(n -1 n) = α λ (n -1 n)(n + 1 n -1), hence I n+2 = [n n+1 n-1] q-1 i=1 M ε i i α λ (n-1 n)(n+1 n-1) q-1 i=1 M ε i i [n n+1 n-1] -1 . ( 50
) Let M = (n -1 n)(n + 1 n -1) q-1 i=1 M ε i i [n n + 1 n -1] -1 .
One has :

M = q-1 i=1 M ε i i (n-1 n)(n+1 n-1) (n -1 n)(n + 1 n -1)[n n + 1 n -1] -1 25 = q-1 i=1 M ε i i (n-1 n)(n+1 n-1) (n -1 n)[n + 1 n -1][n n + 1][n -1 n] 41 = q-1 i=1 M ε i i (n-1 n)(n+1 n-1) [n -1 n + 1][n + 1 n][n n -1] = q-1 i=1 M ε i i (n-1 n)(n+1 n-1) [n n -1 n + 1] -1 .
Hence Equation (50) becomes :

I n+2 = [n n + 1 n -1] q-1 i=1 M ε i i α λ q-1 i=1 M ε i i (n-1 n)(n+1 n-1) [n n -1 n + 1] -1
and we are done with the induction step since (

[xyz] ε ) σ = [σ(x)σ(y)σ(z)] ε where σ = (n -1 n)(n + 1 n -1).
Actually the main interest of Proposition 19 is to give a way to compute easily a decomposition of σ in transvections, as described in the following proposition.

Proposition 20. Let n 2 be an even integer. For any permutation matrix σ of

GL n (F 2 ) different from I n there exists n -2 matrices M 1 , . . . , M n-2 of type [xyz] and n -2 integers ε i ∈ {1, -1} such that : σ = n-2 i=1 M ε i i (51)
Proof. Let σ be a permutation matrix of GL n (F 2 ) different from I n . Applying Proposition 19 to σ -1 one has

I n = q-1 i=1 M ε i i σ -1 q-1 i=1 M ε i i . Hence σ = σI n = q-1 i=1 (M ε i i ) σ q-1 i=1 M ε i i .
Since the proof of Proposition 19 is constructive, the method used in the proof of Proposition 20 gives an algorithm to decompose any matrix σ different from I n in 3(n -2) transvections (see Figure 16 for an example). We conjecture that this decomposition is optimal and we checked it for n = 4.

Let n = 6 and σ = (503

)(142) =         1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1         . σ -1 = (305)(241). Let λ 6 = (3, 3) be the cycle type of σ -1 , then α λ 6 = (012)(345). Let λ 4 = (3, 1), then α λ 4 = (012)(3) = α λ 6 (34)(53). Let λ 2 = (2), then α λ 2 = (01) = α λ 4 (12). I 2 = α λ 2 I 4 = [123] -1 I 2 [123] = [123] -1 α λ 2 [123] = [123] -1 α λ 4 (12)[123] I 4 = [123] -1 α λ 4 (12)[12][31][23] = [123] -1 α λ 4 [12][23][31] = [123] -1 α λ 4 [312] -1 I 6 = [345] -1 I 4 [345] = [345] -1 [123] -1 α λ 4 [312] -1 [345] I 6 = [45][53][34][123] -1 α λ 6 (34)(53)[312] -1 [34][53][45] I 6 = (45)[45][53][34][123] -1 α λ 6 (34)(53)[312] -1 [34][53][45](45) I 6 = [45][34][53][123] -1 α λ 6 (34)(53)[312] -1 [53][34][45] I 6 = [453][123] -1 α λ 6 ([312] -1 ) (34)
I 6 = [453][123] -1 α λ 6 [512] -1 (34)[53][45][34] I 6 = [453][123] -1 α λ 6 [512] -1 [35][54][43] I 6 = [453][123] -1 α λ 6 [512] -1 [435] -1
σ -1 = α γ λ 6 where γ = 0 1 2 3 4 5 3 0 5 2 4 1 , hence :

I 6 = (I 6 ) γ = ([453][123] -1 ) γ σ -1 ([512] -1 [435] -1 ) γ = [412][052] -1 σ -1 [105] -1 [421] -1 σ = σI 6 = ([412][052] -1 ) σ [105] -1 [421] -1 = [241][301] -1 [105] -1 [421] -1 σ = [24][12][41][01][13][30][05][51][10][21][14][42]
|GHZ n = 1 √ 2   | ×n 0 • • • 0 + | ×n 1 • • • 1   = 1 √ 2 |0 ⊗n + |1 ⊗n (n 3) (52)
and the W-state [8]

|W n = 1 √ n (|10 • • • 0 + |010 • • • 0 + • • • + |0 • • • 01 ) (n 3). ( 53
)
These two states represent two non-equivalent kind of entanglements : they belong to distinct SLOCC orbits and thus cannot be interconverted into each other by local operations (even probalistically). These states are particularly usefull because they are required as a physical ressource to realize many specific tasks. For instance, in an anonymous network where the processors share the W-state, the leader election problem can be solved by a simple protocol whereas the GHZ-state is the only shared state that allows solution of distributed consensus [START_REF] Hondt | The computational power of the W and GHZ states[END_REF]. The GHZ-state is also used in many protocols in quantum cryptography, e.g. in secret sharing [START_REF] Hillery | Quantum secret sharing[END_REF].

We denote by H i the Hadamard gate (see Figure 2) applied on qubit i. For instance in a 3-qubit system, H 1 = I ⊗ H ⊗ I where I = 1 0 0 1 and

H = 1 √ 2 1 1 1 -1 .
In the following we study the emergence of entanglement when a CNOT gates circuit acts on a fully factorized state.

Creating a GHZ-state

The construction of the GHZ-state for n qubit is straightforward :

|GHZ n = X n-1 n-2 . . . X 21 X 10 H 0 |0 ⊗n . (54)

The group cX 3 and entanglement of a 3-qubit system

We prove that the group cX 3 is powerful enough to generate any entanglement type from a completely factorized state. We use the method pioneered by Klyachko in [START_REF] Klyachko | Coherent states, entanglement, and geometric invariant theory[END_REF] wherein he promoted the use of Algebraic Theory of Invariant. The states of a SLOCC-orbit are characterized by their values on covariant polynomials. Let |ψ = i,j,k∈{0,1} α ijk |ijk be a 3-qubit state. The simplest covariant associated to |ψ is the trilinear form :

A = i,j,k∈{0,1} α ijk x i y j z k . (55)
From A one computes three quadratic forms :

B x (x 0 , x 1 ) = ∂ 2 A ∂y 0 ∂z 0 ∂ 2 A ∂y 0 ∂z 1 ∂ 2 A ∂y 1 ∂z 0 ∂ 2 A ∂y 1 ∂z 1 , (56)
B y (y 0 , y 1 ) =

∂ 2 A ∂x 0 ∂z 0 ∂ 2 A ∂x 0 ∂z 1 ∂ 2 A ∂x 1 ∂z 0 ∂ 2 A ∂x 1 ∂z 1 , (57)
B z (z 0 , z 1 ) = ∂ 2 A ∂x 0 ∂y 0 ∂ 2 A ∂x 0 ∂y 1 ∂ 2 A ∂x 1 ∂y 0 ∂ 2 A ∂x 1 ∂y 1 . ( 58
)
The catalectican is a trilinear form obtained by computing any of the three Jacobians of A with one of the quadratic forms, which turns out to be the same,

C(x 0 , x 1 , y 0 , y 1 , z 0 , z 1 ) = ∂A ∂x 0 ∂A ∂x 1 ∂Bx ∂x 0 ∂Bx ∂x 1 . ( 59
)
The three quadratic forms B x , B y and B z have the same discriminant ∆ which is the last covariant polynomial we need to characterize the SLOCC-orbits : [|ψ ] is sufficient to distinguish between the different orbits (see [START_REF] Holweck | Geometric descriptions of entangled states by auxiliary varieties[END_REF]). Results are summarized in Table 3.

Orbit Symbols Representatives |ψ V [|ψ ] O V I |GHZ 3 [1, 1, 1, 1, 1] O V |W 3 [1, 1, 1, 1, 0] O IV 1 √ 2 (|000 + |110 ) [0, 0, 1, 0, 0] O III 1 √ 2 (|000 + |101 ) [0, 1, 0, 0, 0] O II 1 √ 2 (|000 + |011 ) [1, 0, 0, 0, 0] O I |000 [0, 0, 0, 0, 0]
Table 3: The SLOCC orbits in a 3-qubit system.

For Equation (54) one has |GHZ 3 = X 21 X 10 H 0 |000 (orbit O V ) and it is easy to check that 1

√ 2 (|000 + |011 ) = X 21 H 1 |000 (orbit O II ), 1 √ 2 (|000 + |101 ) = X 20 H 0 |000 (orbit O III ), and 1 √ 2 (|000 + |110 ) = X 10 H 0 |000 (orbit O IV ).
In order to obtain a SLOCC-equivalent to |W 3 we see from Table 3 that one has to construct a state ψ such that ∆(|ψ ) = 0 and C(x 0 , x 1 , y 0 , y 1 , z 0 , z 1 ) = 0. This can be done using only gates of the standard set of universal gates (Figure 2) as explained in Proposition 21 (see Figure 18 for an example of circuit). Note that the construction involves CNOT gates circuits that have matrices of type [ijk] (described in Subsection 5.3). Proposition 21. Let X [ijk] = X ij X ki X jk where i, j, k are distinct integers in {0, 1, 2} and k = 2. The state

X [ijk] (T ⊗ T ⊗ S)H ⊗3 |000 (61)
is SLOCC-equivalent to |W 3 .

Proof. Let q = e iπ 4 and let

|ψ (k 0 ,k 1 ,...,k 7 ) = 1 √ 8 q k 0 |000 + q k 1 |001 + • • • + q k 7 |111
where k i is an integer. A simple calculation shows that (T ⊗ T ⊗ S)H ⊗3 |000 = |ψ (0,2,1,3,1,3,2,4) . Then we compute the values of polynomials ∆ (Formula (60)) and C (Formula (59)) on the state |ψ = X [ijk] |ψ (0,2,1,3,1,3,2,4) for i, j, k ∈ {0, 1, 2}. When k = 2 we find that ∆ = 0 and C = 0 (see results in the table below).

[ijk] X [xyz] |ψ (0,2,1,3,1,3,2,4)

C(x 0 , x 1 , y 0 , y 1 , z 0 , z 1 ) [021] |ψ (0,2,3,3,4,2,1,1)

1 8 ((1 + i)x 0 y 0 z 0 + (1 + i)x 0 y 0 z 1 + (1 -i)x 1 y 0 z 0 + (1 -i)x 1 y 0 z 1 ) [120]
|ψ (0,2,1,3,1,3,2,4)

1 8 ((1 + i)x 0 y 0 z 0 + (1 + i)x 0 y 0 z 1 + (1 -i)x 0 y 1 z 0 + (1 -i)x 0 y 1 z 1 ) [201]
|ψ (0,4,2,2,3,1,3,1)

1 8 ((1 + i)x 0 y 0 z 0 + (1 -i)x 0 y 0 z 1 + (1 + i)x 0 y 1 z 0 + (1 -i)x 0 y 1 z 1 ) [210]
|ψ (0,4,3,1,2,2,3,1)

1 8 ((1 + i)x 0 y 0 z 0 + (1 -i)x 0 y 0 z 1 + (1 + i)x 1 y 0 z 0 + (1 -i)x 1 y 0 z 1 )
Computing ∆ and C for the state X [ijk] (T ⊗ T ⊗ S)H ⊗3 |000 when k = 2, one finds ∆ = 0 and C = 0, thus the resulting state is SLOCC-equivalent to |GHZ 3 .

As the dimension of the Hilbert space H ⊗3 is small, namely 2 3 , one can compute three 2-dimensional matrices A, B, C of determinant 1 and a complex number k such that A ⊗ B ⊗ C |ψ (0,2,3,3,4,2,1,1) = k |W 3 . This can be done by solving an eight algebraic equations system. We check that the values A = 3i 1

1 2 -1 2 i , B = 2 1 4 -i √ 2 2 0 1 2 i , C = i i 1 2 i -1 2 i
and k = 2

The group cX 4 and entanglement of a 4-qubit system

The situation of 4-qubits systems is more complex than for 3-qubits systems. The corresponding Hilbert space H ⊗4 has infinitely many orbits under the action of SLOCC = SL 2 (C) ×4 . These orbits have been classified by Verstraete et al. [START_REF] Verstraete | Four qubits can be entangled in nine different ways[END_REF] into 9 families (6 families are described with parameters). Among these 9 families only one is generic : any state in the more general situation belongs to the family

G abcd = a+d 2 (|0000 + |1111 ) + a-d 2 (|0011 + |1100 ) + b+c 2 (|0101 + |1010 ) + b-c 2 (|0110 + |1001 ) , (62)
for independent parameters a, b, c, and d [START_REF] Verstraete | Four qubits can be entangled in nine different ways[END_REF][START_REF] Holweck | Entanglement of four qubit systems: A geometric atlas with polynomial compass I (the finite world)[END_REF]. More precisely, a generic state of 4 qubits is SLOCC-equivalent, up to permutations of the qubits, to 192 Verstraete states of the G abcd family [START_REF] Holweck | Entanglement of four-qubit systems: a geometric atlas with polynomial compass II (the tame world)[END_REF].

To determine the Verstraete family to which a given state belongs, one can use an algorithm described in a previous paper [START_REF] Holweck | Entanglement of four-qubit systems: a geometric atlas with polynomial compass II (the tame world)[END_REF]. As is the case of 3 qubits, this algorithm is based on the evaluation of some covariants polynomials (see Appendix A). We do not recall the algorithm since it is not usefull to understand the present paper.

Let |ψ = i,j,k, ∈{0,1} α ijk |ijk be a 4-qubit state. The algebra of SLOCC-invariant polynomials is freely generated by the four following polynomials [START_REF] Luque | The polynomial invariants of four qubits[END_REF]:

• The smallest degree invariant

B := 0 i 1 ,i 2 ,i 3 1 (-1) i 1 +i 2 +i 3 α 0i 1 i 2 i 3 α 1(1-i 1 )(1-i 2 )(1-i 3 ) , (63)
• Two polynomials of degree 4

• and a polynomial of degree 6 defined by D xy = -det(B xy ) where B xy is the 3 × 3 matrix satisfying

x 2 0 , x 0 x 1 , x 2 1 B xy   y 2 0 y 0 y 1 y 2 1   = det ∂ 2 ∂z i ∂t j A (66)
with A = i,j,k, ∈{0,1}

α ijk x i y j z k t being the quadrilinear binary form associated to the state |ψ .

Using the generators B, L, M and D xy , one can build ∆, an invariant polynomial of degree 24 that plays an important role in the quantitative and qualitative study of entanglement [START_REF] Miyake | Multipartite entanglement and hyperdeterminants[END_REF][START_REF] Miyake | Classification of multipartite entangled states by multidimensional determinant[END_REF]. As described in [START_REF] Holweck | Entanglement of four qubit systems: A geometric atlas with polynomial compass I (the finite world)[END_REF] and [START_REF] Luque | The polynomial invariants of four qubits[END_REF], ∆ is the discriminant of any of the quartics

Q 1 = x 4 -2Bx 3 y + (B 2 + 2L + 4M )x 2 y 2 + 4(D xy -B(M + 1 2 L))xy 3 + L 2 y 4 , (67)
Q 2 = x 4 -2Bx 3 y + (B 2 -4L -2M )x 2 y 2 + (4D xy -2M B)xy 3 + M 2 y 4 , (68)
and

Q 3 = x 4 -2Bx 3y + (B 2 + 2L -2M )x 2 y 2 -(2(L + M )B -4D xy )xy 3 + N 2 y 4 . (69)
We recall that, for a quartic Q = αx 4 -4βx 3 y+6γx 2 y 2 -4δxy 3 +ωy 4 , the discriminant can be computed as

∆ = I 3 2 -27I 2 3 ( 70
)
where I 2 = αω -4βδ + 3γ In the case of 3 qubits, ∆(|GHZ 3 ) = 0 (see Table 3). Using (60) one checks easily that ∆(|GHZ 3 ) = 1 4 . So the state |GHZ 3 is generically entangled. In the 4 qubits case one computes ∆(|GHZ 4 ) = 0 using (70). Hence, suprisingly, |GHZ 4 is not generically entangled and this result can be generalized : in [START_REF] Bataille | Quantum circuits of cZ and SWAP gates: optimization and entanglement[END_REF] Appendix C we proved that, for any k > 3, ∆(|GHZ k ) = 0. In this context we ask ourselves if it is possible to find a 4-qubit CNOT gates circuit that takes as input a completely factorized state and output a generically entangled state. The following statement answers the question. According to Miyake [START_REF] Miyake | Multipartite entanglement and hyperdeterminants[END_REF], the value of |∆| can be considered as a measure of entanglement. So a state with the most amount of generic entanglement can be defined as a state that maximize |∆|. In the 4-qubits case the maximal value of |∆| is

1 2 8 3 9
1, 98 × 10 -7 [START_REF] Chen | okovi. Proof of the Gour-Wallach conjecture[END_REF] and the mean is around 1.32 × 10 -9 (value based on 10000 random states [START_REF] Alsina | Multipartite entanglement and quantum algorithms[END_REF]). So the amount of generic entanglement in the state |BL is not maximal, although much higher than the mean. A few states are known to maximize |∆| : |L [START_REF] Higuchi | How entangled can two couples get?[END_REF][START_REF] Gour | On symmetric SL-invariant polynomials in four qubits[END_REF][START_REF] Chen | okovi. Proof of the Gour-Wallach conjecture[END_REF], |HD [START_REF] Alsina | Multipartite entanglement and quantum algorithms[END_REF] and |M 2222 (Jaffali, phd thesis). Figure 19 gives the definition of these states. It seems interesting to know if it is possible, starting from a fully factorized state, to reach one of these 3 states by a 4-qubit CNOT gates circuit. To answer this question we proceed as follows. We start from a fully factorized state

|F (u) := (a 0 |0 + a 1 |1 ) ⊗ (b 0 |0 + b 1 |1 ) ⊗ (c 0 |0 + c 1 |1 ) ⊗ (d 0 |0 + d 1 |1 ) (71) where u := [a 0 , a 1 , b 0 , b 1 , c 0 , c 1 , d 0 , d 1 ]
with:

|u 0 = 1 2 (|0000 + |0011 + |1100 + |1111 ) |u 1 = 1 2 (|0000 -|0011 -|1100 + |1111 ) |u 2 = 1 2 (|0101 + |0110 + |1001 + |1010 ) ω = e 2iπ 3 |HD = 1 √ 6 (|0001 + |0010 + |0100 + |1000 + √ 2 |1111 ). ( 73
) |M 2222 = 1 √ 6 |v 1 + √ 6 4 |v 1 + 1 √ 2 |v 3 (74)
with: We examine now whether it is possible to obtain a SLOCC-equivalent to |W 4 = 1 2 (|0001 +|0010 +|0100 +|1000 ) when a CNOT gates circuit acts on a fully factorized state. The SLOCC-orbit of |W 4 belongs to the null cone, which is the algebraic variety defined by the vanishing of all invariants (i.e. B(|ψ ) = L(|ψ ) = M (|ψ ) = D xy (|ψ ) = 0). The null cone contains 31 SLOCC-orbits and the orbit of |W 4 is charaterized, inside the null cone, by the evaluation of a vector of 8 polynomial covariants A, P B , P 1 C , P 2 C , P 1 D , P 2 D , P F , P L whose definitions have been relegated to Appendix A (see [19, Section III] for more details). More precisely, one has the following criterion :

|v 1 = 1 √ 6 (|0000 + |0101 -|0110 -|1001 + |1010 + |1111 ) |v 2 = 1 √ 2 (|0011 + |1100 ) |v 3 = 1 √ 2 (-|0001 +|0010 -|0100 +|0111 +|1000 -|1011 +|1101 -|1110 )
Proposition 23. Let V 1 := [B, L, M, D xy ] and V 2 := [A, P B , P 1 C , P 2 C , P 1 D , P 2 D , P F , P L ] then |ψ is in the SLOCC-orbit of |W 4 if and only if V 1[|ψ ] = [0, 0, 0, 0] and V 2[|ψ ] = [1, 1, 1, 1, 0, 0, 0, 0].
The use of this criterion makes it possible to answer our initial question : C : we check that the polynomial P 2 C (|ψ ij (u) ) is null for any u, C, i, j. We deduce from Proposition 23 that |ψ(u) is not SLOCC-equivalent to |W 4 . The Maple script that implements this algorithm can be downloaded at https://github.com/marcbataille/cnot-circuits and needs a few hours to be executed.

Conclusion and perspectives

The omnipresence and great significance of CNOT gates in quantum computation was our main motivation to better understand the quantum circuits build with these gates. First we described the link between CNOT gates circuits of n qubits and a classical group, namely GL n (F 2 ) = SL n (F 2 ). From there we deduced some simplification rules and applied our results to optimization and reduction problems. In Section 4 we proposed some polynomial heuristics to reduce circuits in the general case and in Section 5 we described a few algorithms to optimize circuits in some special cases. Finally we studied some issues about entanglement and proposed simple constructions to produce some usefull entangled states. Optimization and entanglement are indeed two central topics in QIT since they are related to some important issues on the way to a reliable and functional quantum machine : optimization of circuits for scalable quantum computing and production of entanglement as a physical resource in quantum communication protocols. As far as we know, a complete study of CNOT gates circuits does not exist yet in the litterature and we hope the results and conjectures contained in this paper will contribute to fill a part of this gap. We believe that the subject is rich and deserves certainly further investigations. In what follows we try to sketch some directions that future works on this subject could take.

Regarding to the optimization problem of CNOT gates circuits, it seems to us that the diversity of situations and methods described in Section 5 tends to show that a polynomial optimization algorithm for the general case, if it ever exists, will be hard to find out. In our opinion, a more realistic and feasible approach should be a mix of heuristics for the general case (as the Gauss-Jordan algorithm or the UTD algorithm described in Section 4) combined with a rich atlas of various methods to optimize or to reduce circuits in special cases (as the atlas we started to built in Section 5). Concerning heuristics in the general case, it is clear that the bound of n 2 gates resulting from the Gauss-Jordan algorithm (Proposition 10) has to be improved by the use of another algorithm, since it is still far from the (probably) optimal linear bound of 3(n-1) gates given by Conjecture 12. Certainly, a constructive proof of this conjecture would be a big step towards a better understanding of the optimization problem. We will continue to investigate technics of reduction in future works.

The study of the emergence of entanglement in CNOT gates circuits done in Section 6 highlights the interest and utility of this tool especially in the case of 3 or 4 qubits systems. When the number of qubits is greater than 4, it would be interesting to know whether it is possible to create generic entanglement as in the 4 qubits case (Theorem 22). Unfortunately, from 5 qubits the hyperdeterminant is too huge to be computed in a suitable form. However its nullity can be tested thanks to its interpretation in terms of solution of a system of equations [12, p. 445] : if A = 0 i,j,k,l,n 1 α ijkln x i y j z k t l s n is the ground form associated to the five qubits state |ϕ = 0 i,j,k,l,n 1 α ijkln |ijkln , the condition ∆(|ϕ ) = 0 means that the system

S ϕ := {A = d dx 0 A = d dx 1 A = d dy 0 A = d dy 1 A = • • • = d ds 0 A = d ds 1 A = 0} (75)
has a solution x0 , x1 , ŷ0 , ŷ1 , . . . , ŝ0 , ŝ1 in the variables x 0 , x 1 , y 0 , y 1 , . . . , s 0 , s 1 such that (x 0 , x1 ), (ŷ 0 , ŷ1 ), . . . , (ŝ 0 , ŝ1 ) = (0, 0). Such a solution is called non trivial. Hence a possible approach to show that a state |ψ is generically entangled when n > 4 is to prove that the corresponding system has no solution apart from the trivial solutions.

A Some covariant polynomials associated to 4 qubit systems

In this section, we shall explain how to compute the polynomials which are used to determine the SLOCC-orbit of |W 4 inside the null cone (Section 6.3). We shall first recall the definition of the transvection of two multi-binary forms on the binary variables x (1) = (x

(1) 0 , x (1)
1 ), . . . , x (p) = (x

(p) 0 , x (p)
1 ) (f, g) i 1 ,...,ip = tr Ω i 1

x (1) . . . Ω ip x (p) f (x (1) , . . . , x (p) )g(x (1) , . . . , x (p) ), (76

)
where Ω is the Cayley operator

Ω x = ∂ ∂x 0 ∂ ∂x 0 ∂ ∂x 1 ∂ ∂x 1
and tr sends each variables x , x on x (erases and ). In [START_REF] Holweck | Geometric descriptions of entangled states by auxiliary varieties[END_REF], we give a list of generators of the algebra of covariant polynomials for 4 qubits systems which are obtained by transvection from the ground form A = i,j,k, α i,j,k,l x i y j z k t .

Here we give formulas for some of the polynomials which are used in the paper.

Symbol Transvectant

  we recall the definition of the Pauli gates : notice that the states |0 and |1 are eigenvectors of the Pauli-Z operator respectively associated to the eigenvalues 1 and -1, i.e. Z |0 = |0 and Z |1 = -|1 . Hence the computational standard basis (|0 , |1 ) is also called the Z-basis.

Figure 1 :

 1 Figure 1: The Pauli gates

Figure 2 :

 2 Figure 2: The standard set of universal gates : names, circuit symbols and matrices.

Figure 3 :

 3 Figure 3: Some classical equivalences of circuits involving CNOT gates.

5 )

 5 = 1 then the 2-line notation is notation can be σ = (204)(15) = (51)(420) or σ = (204)(15)(3) if we want to write the one-cycle and the permutation matrix is

Figure 5 :

 5 Figure 5: A 5-qubit quantum circuit of SWAP gates and the corresponding permutation

Figure 6 :

 6 Figure 6: A circuit of cX 4 and the corresponding operator.

Figure 7 :

 7 Figure 7: Example of Identity (15) in a cX 4 circuit.

Figure 8 :

 8 Figure 8: Example of Identity (18) in a cX 4 circuit.

  In his "Lectures on Chevalley Group" [31, Chapter 6], Steinberg gives a presentation of the special linear group on a finite field K in dimension n 3. The notation (a, b) stands here for the commutator of two elements a and b of a group (i.e. a -1 b -1 ab) which is usualy denoted by [a, b]. Theorem 6. (Steinberg)

Figure 9 :

 9 Figure 9: Getting the braid relation x ij x ji x ij = x ji x ij x ji from Corollary 7.

( 30 )

 30 = (02)[01][02][20][01](32) = [21](02)[02][20][01] = [21][02][20][02][02][20][01] (28) = [21][02][01]

Figure 11 :

 11 Figure 11: The Gauss-Jordan algorithm applied to a CNOT gates circuit.

  CNOT) M = [21][32][23][41][20][40][01][31][21][42][43][12][34]

  20][30][40][21][31][41][32][42] Canonical decomposition of U : U = [24][34][23][02][12][01] LTD algorithm -→ L = [42][32][21][20] UTD algorithm -→ U = [01][23][34][12] Hence : M = [42][32][21][20][01][23][34][12]

Figure 12 :

 12 Figure 12: The UTD/LTD algorithms applied to a LU circuit of CNOT gates

2 = [ 13 ]

 213 13][01][30][21][13][02][01]([01][12][10][21][01]) σ -1 [01][30][21][13][02][01][45][56][54][65][45].

Figure 14 :

 14 Figure 14: Decomposition of a matrix using cartesian product of subgroups.

Figure 15 :

 15 Figure 15: Circuit optimization using a cartesian product of subgroups.

  )) One obtains similar rules for matrices of type [ij][jk][ki] by taking the inverse of each member of the identities of Lemma 17. For convenience we denote the product [ij][ki][jk] by [ijk]. With this notation one has [ij][jk][ki] = [kij] -1 .

1 .

 1

[ 23 ] 31 =

 2331 [START_REF] Steinberg | Lectures on Chevalley Groups[END_REF][START_REF] Israel M Gelfand | Discriminants, Resultants and Multidimensional Determinant[END_REF](01)[START_REF] Israel M Gelfand | Discriminants, Resultants and Multidimensional Determinant[END_REF][31][23] = [23][31][12][10][01][10][12][31][23] [23][31][10][12][01][12][10][31][23] 30 = [23][31][10][01][02][10][31][23]. (8 transvections)

  (53) (34)(53)[53][34][45]

Figure 16 :

 16 Figure 16: Decomposition in transvections of a matrix of type σ.

A 1 √ 2 ( 4 Figure 17 :

 12417 Figure 17: Using a circuit of cX 4 to obtain |GHZ 4 .

∆

  (|ψ ) = (α 000 α 111 -α 001 α 110 -α 010 α 101 + α 011 α 100 ) 2 -4 (α 000 α 011 -α 001 α 010 ) (α 100 α 111 -α 101 α 110 ) . (60) The polynomial ∆ is the generator of the algebra of invariant polynomials under the action of SLOCC (i.e ∆(|ψ ) = ∆(M |ψ ) for any M ∈ SL 2 (C) ×3 ). It is also the Cayley hyperdeterminant of the trilinear binary form A [4]. Let V := [B x , B y , B z , C, ∆] be a vector of covariants. We associate the binary vector V [|ψ ] := [[B x (|ψ ], [B y (|ψ )], [B z (|ψ )], [C(|ψ )], [∆(|ψ )]] to any state |ψ , where [P (|ψ )] = 0 if P (|ψ ) = 0 and [P (|ψ )] = 1 if P (|ψ ) = 0. The value of V

3

 3 Output state is :|ψ (0,2,3,3,4,2,1,1) = X [021] |ψ (0,2,1,3,1,3,2,4) = X 02 X 10 X 21 (T ⊗ T ⊗ S)H ⊗3 |000 .

Figure 18 :

 18 Figure 18: A circuit of cX 3 producing a SLOCC-equivalent to |W 3 .

Theorem 22 .

 22 The state |BL := X 01 X 20 X 03 X 10 (T ⊗ S ⊗ S ⊗ S)H ⊗4 |0000 is generically entangled. It is produced by the circuit : Using formula (70) one computes ∆(|BL ) = -1 2 24 -5, 96 × 10 -8 .

Figure 19 :

 19 Figure 19: 4-qubits states for which |∆| is maximal.

Theorem 24 .

 24 The SLOCC-orbit of |W 4 cannot be reached when cX 4 acts on a fully factorized state |F (u) . Proof. We prove that, for any circuit C ∈ cX 4 , the state |ψ(u) = C |F (u) cannot be in the SLOCC-orbit of |W 4 . The algorithm is the following. For each C in cX 4 we solve the system B(|ψ(u) ) = L(|ψ(u) ) = M (|ψ(u) ) = D xy (|ψ(u) ) = 0. The solutions are parametrized vectors |ψ 1 (u) , . . . , |ψ n (u) . Then for each solution |ψ i (u) we solve the system P 1 D (|ψ i (u) ) = P 2 D (|ψ i (u) = P F (|ψ i (u) ) = P L (|ψ i (u) = 0 and for each solution |ψ ij (u) we compute P 2

1 3 1 3 1 3 1 3

 1111 B 2200 ) 1100 + (A, B 0022 ) 0011 C 3111 ((A, B 2200 ) 0100 + (A, B 2020 ) 0010 + (A, B 2002 ) 0001 ) C 1311 ((A, B 2200 ) 1000 + (A, B 0220 ) 0010 + (A, B 0202 ) 0001 ) C 1131 ((A, B 2020 ) 1000 + (A, B 0220 ) 0100 + (A, B 0022 ) 0001 ) C 1113 ((A, B 2002 ) 1000 + (A, B 0202 ) 0100 + (A, B 0022 ) 0010 ) Symbol Transvectant D 2200 (A, C 1 1111 ) 0011 D 2020 (A, C 1 1111 ) 0101 D 2002 (A, C 1 1111 ) 0110 D 0220 (A, C 1 1111 ) 1001 D 0202 (A, C 1 1111 ) 1010 D 0022 (A, C 1111 ) 1100 D 4000 (A, C 3111 ) 0111 D 0400 (A, C 1311 ) 1011 D 0040 (A, C 1131 ) 1101 D 0004 (A, C 1113 ) D 2200 ) 0100 + (A, D 2020 ) 0010 + (A, D 2002 ) 0001 E 1 1311 (A, D 2200 ) 1000 + (A, D 0220 ) 0010 + (A, D 0202 ) 0001 E 1 1131 (A, D 2020 ) 1000 + (A, D 0220 ) 0100 + (A, D 0022 ) 0001 E 1 1113 (A, D 2002 ) 1000 + (A, D 0202 ) 0100 + (A, D 0022 ) 0010

Table 2 :

 2 Number of elements of cX n having an optimal decomposition of length l. The numbers in bold correspond to the (n -1)! cyclic permutations of length n.

6

  Entanglement in CNOT gates circuitsThe notion of entanglement is usually defined through the group of Stochastic Local Operations assisted by Classical Communication denoted by SLOCC which is assimilated to the cartesian group product SL 2 (C) ×n[START_REF] Miyake | Multipartite entanglement under stochastic local operations and classical communication[END_REF][START_REF] Dür | Three qubits can be entangled in two inequivalent ways[END_REF]. Mathematically two states |ψ and |ϕ are SLOCC-equivalent if there existn operators A 1 , . . . , A n in SL 2 (C) such that A 1 ⊗ • • • ⊗ A n |ψ = λ |ϕfor some complex number λ. In other words, |ψ and |ϕ are SLOCC-equivalent if they are in the same orbit of GL 2 (C) ×n acting on the Hilbert spaceC 2 ⊗ • • • ⊗ C 2 .The SLOCC-equivalence of two states |ϕ and |ψ has a physical interpretation as explained in[START_REF] Dür | Three qubits can be entangled in two inequivalent ways[END_REF] : |ϕ and |ψ can be interconverted into each other with non zero probability by n parties being able to coordinate their action by classical communication, each party acting separately on one of the qubits. The SLOCC-equivalence of two states |ϕ and |ψ implies that both states can achiveve the same tasks (for instance in a communication protocol) but with a probability of a success that may differ. In this sense the SLOCC-equivalence can be considered as a qualitative way of separating non equivalent quantum states.

	Some states have a particular interest like the Greenberger-Horne-Zeilinger state
	[15]

  L := α 0000 α 0010 α 0001 α 0011 α 1000 α 1010 α 1001 α 1011 α 0100 α 0110 α 0101 α 0111 α 1100 α 1110 α 1101 α 1111 α 0000 α 0001 α 0100 α 0101 α 1000 α 1001 α 1100 α 1101 α 0010 α 0011 α 0110 α 0111 α 1010 α 1011 α 1110 α 1111 .

	(64)
	and
	M :=

  2 and I 3 = αγω -αδ 2 -ωβ 2 -γ 3 + 2βγδ. It appears that ∆ is the Cayley hyperdeterminant (in the sense of Gelfand et al.[START_REF] Israel M Gelfand | Discriminants, Resultants and Multidimensional Determinant[END_REF]) of A[START_REF] Luque | The polynomial invariants of four qubits[END_REF]. In[START_REF] Miyake | Classification of multipartite entangled states by multidimensional determinant[END_REF], Miyake showed that the more generic entanglement holds only for the states |ψ such that ∆(|ψ ) = 0. Moreover any generically entangled state is equivalent to a state of the Verstraete G abcd family [25, Appendix A]. So one can consider ∆ as a qualitative measure of entanglement : an entangled state (i.e. not factorized state) is generically entangled if ∆ = 0.

  is a vector of complex numbers. Then, for each circuit C in cX 4 , we compute C |F (u) and we check that the equation C |F (u) = |ψ where |ψ ∈ {|L , |HD , |M 2222 } has no solution. This can be done in a few seconds using Maple 2020 (X86 64 LINUX). The corresponding script can be downloaded at https://github.com/marcbataille/cnot-circuits. Hence the answer to our question is negative. Note that the question whether a state different from |L , |HD , or |M 2222 that has maximal generic entanglement can be produced under the same constraints (i.e. factorized state plus 4-qubit CNOT gates circuit) remains open, however. + ω |u 1 + ω 2 |u 2

	|L =	1 √ 3	(|u 0

We use the following polynomials in order to characterize the |W 4 SLOCC-orbit:


Dominique Giraud

Baptiste Ristagno

Denis Netter

Julien Fontchastagner

Nicolas Labbe

Vincent Lanfranchi

Axial claw pole motor: harmonic torque estimation using finite element method

Keywords: Axial flux machines, Finite element method, Mesh generation, Claw pole motor, Mesh

Purpose -This paper aims to propose a method to evaluate the information obtained on harmonics calculations and to estimate the precision of results using finite element method for an innovative motor topology in which some well-known meshing rules are difficult to apply.

Design/Methodology/Approach -The same magnetostatic problem is solved with several mesh sizes using both scalar and vector potentials magnetics formulations on a complex topology, an axial claw pole motor (ACPM). The proposed method lies in a comparison between the two weak formulations to determine what information is obtained on harmonics calculations and to estimate its precision. Moreover, an original mesh method is applied in the air gap to improve the numerical results.

Finding -The precision on harmonics calculations using finite element method on an ACPM is estimated. For the proposed motor and mesh, only the mean value (even with large mesh) and the first harmonic (with fine mesh) of torque are calculated with a good accuracy. This results confirm that the non-respect of the meshing rules have a strong impact on the results and that scalar and vector potentials magnetics formulations do not give exactly the same results. Before using torque harmonics values in vibration calculations, a finite element model has to be validated by using both fomulations.

Research limitations implications -This method is time-consuming and only applied on an ACPM in this work.

Originality/Value -The axial claw pole motor, for which the classic meshing rules cannot be applied, is a complex topology very under-studied. To improve the calculation of space harmonics, the authors proposed to split the airgap into four parts. Then in the two central parts, the meshing step of the structured mesh is equal to the rotating step.

Introduction

Nowadays there is a huge need of precise information about vibrations and acoustics in many fields as in automotive traction. That is why harmonic calculations of physical values, as torque harmonics is widely spreaded [START_REF] Wu | Analysis of torque ripple reduction in a segmented-rotor synchronous reluctance machine by optimal currents[END_REF]). In fact, several studies, both experimental [START_REF] Zhu | Analysis and mitigation of torsional vibration of pm brushless ac/dc drives with direct torque controller[END_REF] [START_REF] Lee | Harmonic torque reduction using adaptive sector-based torque feedforward method for pmsm[END_REF] [START_REF] Beccue | Measurement and control of torque ripple-induced frame torsional vibration in a surface mount permanent magnet machine[END_REF] [START_REF] Nam | Torque ripple reduction of an interior pm synchronous motor by compensating harmonic currents based on flux linkage harmonics[END_REF]) and using finite element method [START_REF] Zhao | Torque pulsation minimization in spoketype interior permanent magnet motors with skewing and sinusoidal permanent magnet configurations[END_REF]) [START_REF] Chaieb | Optimum geometry for torque ripple minimization of permanent magnet motor by the finite element method[END_REF], deal with torsional vibration in electric motor because of torque harmonics. Nevertheless, the results about high-order harmonics using finite element method depend on many parameters and are strongly linked to mesh quality at the air-gap interface. In this paper, a procedure is presented to deal with the influence of the mesh on the results for an axial claw pole motor (ACPM) [START_REF] Labbe | Flux switching rotating electrical machine for traction for a motor vehicle[END_REF]. Indeed, some meshing rules [START_REF] Davat | The movement in field modeling[END_REF] are well known for harmonics calculation but unfortunately, are difficult to apply for this topology. In these case, there is a lack of tools to analyse the confidence about simulation results on high-order harmonics. The authors propose to solve magnetostatic problem for several meshing with both scalar and vector potentials magnetics formulations. Then, output data will be treated to determine what information is obtained on harmonics calculations and to estimate its precision with a comparison between the two weak formulations. Moreover, an original mesh method is applied in the airgap to improve the numerical results. The method is tested on a model using the open-source Onelab interface, linking Gmsh [START_REF] Geuzaine | Gmsh: A three-dimensional finite element mesh generator with built-in pre-and post-processing facilities[END_REF]. and GetDP [START_REF] Dular | GetDP reference manual: the documentation for GetDP, a general environment for the treatment of discrete problems[END_REF] for torque harmonics calculation.

Problem

Meshing rules

In Finite Element Method (FEM)-based simulations, some meshing rules are well known to calculate torque harmonics for radial rotating machines [START_REF] Davat | The movement in field modeling[END_REF]. Stator and rotor must have the same number of elements at airgap interface with a meshing step equals to the rotating step as it can be seen in Figure 1. To apply this rules, the least common multiple is generally used to define the number of mesh element.

Axial claw pole motor

Unfortunately, axial flux machines induce an additional difficulty compared to radial flux machines. In the case of the ACPM, the meshing rules have to be respected on each radius from the internal to external radius as seen in Figure 2. The rotating step can be equal to the meshing step at each radius on stator and rotor only if the geometric lines are through radial axis. For the synchronous axial motor represented in Figure 2 with claw pole inductor and straight slots armature, this rules can not be applied.

Calculations are made with a periodic model meshed with really fine element (Figure 3). The magnetization curve b(h) used in the model is from a standard steel material as shown in Figure 4. The electric conductivity of copper is equal to 59.6 10 6 (S/m). The armature is supplied with three-phase sinusoidal current. The boudary conditions are shown in Figure 5. The double airgap motor has an axial symetry and so the condition b × n is used on an area in the middle of the stator yoke. The torque can be computed by applying the Maxwell stress tensor ( Tm ) on a circular area in the airgap between the stator and the rotor. To reduce numerical noise the torque is calculated using an average of this surface integral on a thickness e along the air gap (Ω e ) as presented in a study by [START_REF] Fontchastagner | Efficient design using successive analytical subproblems method: Application to axial magnetic couplings[END_REF]. Calculation are made on two slot pitches for 32 positions. Instability on results from vector potential formulation is observed with an ordinary tetrahedral mesh in the air gap as seen in Figure 6. This kind of mesh does not allow to estimate high-order harmonics torque: To analyse the confidence about simulation results both formulations will be used. Using both formulations is essential in this study because only one magnetic continuity condition is imposed strongly using FEM [START_REF] Bossavit | How weak is the weak solution in finite elements methods?[END_REF], which can leads to unaccuracies [START_REF] Nam | Torque ripple reduction of an interior pm synchronous motor by compensating harmonic currents based on flux linkage harmonics[END_REF]. In fact, the continuity of the normal component of the magnetic flux density b n is strongly imposed using the vector potential weak formulation and tangential component of the magnetic field strength h t is strongly imposed using the scalar potential weak formulation. This issue is not solved and is still a current research topic [START_REF] Martinez | Strong formulation using fds, weak formulation using fem and experimental data[END_REF]) [START_REF] Lefevre | Magnetic field continuity conditions in finite-element analysis[END_REF].

Torque = 1 e Ωe (r × ( Tm • e z ) dΩ) • e z (1)
To strongly improve the mesh quality, we propose to split the airgap into four parts (see Figure 7). This method replaces a classical moving band. The torque is then calculated with equation ( 1) in the two central parts in which the meshing step of the structured mesh is equals to the rotating step as seen in Figure 8. The two other parts are used to connect the structured mesh on the central parts to the mesh on rotor and stator interface. Even if the problem is meshed for each position, the meshes will be similar in the central air gap for any configuration. With this mesh, torques from both the formulations are well calculated as seen in Figure 9. The differences between the results are mainly because of the weak formulations and much less because of the air-gap meshing problems as shown in Figure 6. However, scalar and vector potential formulations give different results. Facing these difficulties, the authors decided to investigate in the present work the creation of a procedure to evaluate the information contained in output data and to estimate the precision of the results for different meshes.

Proposed approach

The proposed method lies in a comparison between scalar and vector potential formulations. Such comparison between both formulations has already been used in several works [START_REF] Dular | A natural method for coupling magnetodynamic h-formulations and circuit equations[END_REF] [START_REF] Dular | A general and natural method to define circuit relations associated with magnetic vector potential formulations[END_REF]. The aim is to evaluate the confidence level of high-order harmonics torque.

Weak formulations

A finite element magnetostatic problem can be describe with both scalar and vector potential formulations.

• Scalar potential formulation:

To use the magnetic scalar potential ϕ in the weak formulation, a dummy magnetic field h s is calculated to replace the electric current density j in the sources domain Ω s as:

j = ∇ × h s ∇ × (h -h s ) = 0 (h -h s ) = -∇ϕ
Gauss's law for magnetism gives:

Ω ∇ • b dΩ = Ω ∇ • (µ(h s -∇ϕ)) dΩ = 0 (2)
The weak form is:

Ωs µ h s • ∇ϕ dΩ s - Ω µ ∇ϕ • ∇ϕ dΩ = 0 (3)
• Vector potential formulation:

As the magnetic flux density is divergence-free (Gauss's law for magnetism: ∇ • b = 0), a vector magnetic potential a always exists as b = ∇ × a. The Ampere-Maxwell law with j the electric current in the sources domain Ω s gives:

Ω (∇ × ( 1 µ ∇ × a)) dΩ - Ωs j dΩ s = 0 (4)
The weak formulation is:

Ω ( 1 µ ∇ × a) • (∇ × a ) dΩ - Ωs j • a dΩ s - dΩ (( 1 µ ∇ × a) ∧ n) • a dS = 0 (5)

Proposed approach

The aim is to study results consistency versus degrees of freedom (Dofs) number or mesh density. To make a fair comparison, the two calculations use the same mesh. The meshing step in the central air gap exactly equals the rotating step. However, in the motor, the mesh size depends on a reference length l ref . The 15 different meshes, with 15 different l ref , are used on the periodic model. The meshes range from very fine mesh (1390e3 Dofs for vector potential, 232e3 Dofs for scalar potential) to large mesh (185e3 Dofs for vector potential, 32e3 Dofs for scalar potential) as seen in Figure 12. Dofs number of vector potential formulation is 6 time higher than scalar potential in this model. This explains that the CPU time is lower with scalar formulation than with vector formulation as shown in the ratio CpuT imevector CpuT ime scalar plot in red in Figure 12. For each mesh size, the torque is calculated on two slot pitches for 32 positions.

Results

A spectral analysis on time-dependent torque is made using fast fourier transform (FFT).

The study focusses on the mean value and the first four harmonics of torque. Differences between the two formulations and the evolutions of these quantities depending on the mesh size are investigated. To compare the two results, deviation and mean on the modulus coefficient of FFT, Co, for each harmonics and for each mesh are calculated with:

Dev(k) = Co Scalar (k) -Co V ector (k) Co Scalar (k)+Co V ector (k) 2 (6)
and

M ean(k) = Co Scalar (k) + Co V ector (k) 2 (7)
k being the harmonic rank.

All curves are plot with torque in per unit as:

T orque (pu) = T orque actual T orque Base (8)
with

T orque Base = T Scalar + T V ector 2 (9)
T Scalar and T V ector being the mean value of torque from scalar and vector formulations for the finest mesh. Torques calculated with the finest and the lagest mesh are plot in Figure 13. There are differences between the two formulations which decrease with finer meshes. • Torque mean value: The mean value and the deviation of torque versus the Dofs number are shown in Figure 14. With finer mesh, the deviation decrease. The torque mean value is calculated with a good accuracy even with large mesh size with Dev(k = 0) ≤ 7%.

• Torque harmonics: the deviation of the first and third harmonics decreases as Dofs number increases and the mean values of Co between scalar and vector formulations are constant. It can be concluded that the first harmonic is calculated with a ±10% accuracy, with scalar Dofs number = 232 000, up to ±30% with scalar Dofs number = 50 000 (see Figure 15). A compromise has to be found between Dofs number (CPU time) and accuracy. The third harmonic can only be estimated with an accuracy from ±45% with with scalar Dofs number = 232 000 up to ±65% with scalar Dofs number = 70 000 (see Figure 16).

Conclusion

An ACPM is a complex topology to study and leads to complications for FEM simulation. The results on this motor prove the need and the relevance of the method despite the fact that it is time-consuming. In fact, for the proposed motor and mesh, only the mean value (even with large mesh) and the first harmonic (with fine mesh) are calculated with a good accuracy. The non-respect of the meshing rules has a strong impact on the results, which has to be analyzed. Moreover, scalar and vector formulations do not give exactly the same results and a finite elements model has to be validated by using both formulations. An analysis of the results obtained using finite element method is essential before any vibration calculation based on torque harmonics values. The method presented in this paper can be used to better identify harmonics accurately calculated for any kind of topology.

Figure 1 :

 1 Figure 1: Application of meshing rules on 2D FEM example.

FigureFigure 4

 4 Figure 2: Synchronous axial claw pole motor

Figure 6 :

 6 Figure 6: Torque with tetrahedra mesh

Figure 9 :

 9 Figure 9: Torque with structured mesh

  Figure 10 and Figure 11 show, respectively, example with a small and a large l ref .

Figure

  Figure 10: Small lref Figure 11: Large lref

Figure 12 :

 12 Figure 12: Dofs number and CPU time

  Figure 13: Torque

It is more difficult to conclude for Harmonics 2 and 4 (Figure 17, Figure 18). Unlike the previous point, the deviation for the second harmonic does not decrease with mesh size.

Considering Figure 18, we found out the Harmonic 4 value (mean of scalar and vector formulations) continues to increase with Dofs number. As any steady state can be reached, we cannot choose a specific value. It is considered that there is no information on these harmonics with the considered mesh sizes. The Dofs number can not be more reduced because of time and CPU memory issues.