CUBO A Mathematical Journal Vol.11, No¯ 04, (73–86). September 2009 Circulant Matrices, Gauss Sums and Mutually Unbiased Bases, I. The Prime Number Case Monique Combescure Institut de Physique Nucléaire de Lyon (IPNL), 4 rue Enrico Fermi F-69622 Villeurbanne Cedex, France. email: mcombe@ipnl.in2p3.fr ABSTRACT In this paper, we consider the problem of Mutually Unbiased Bases in prime dimension d. It is known to provide exactly d + 1 mutually unbiased bases. We revisit this problem using a class of circulant d × d matrices. The constructive proof of a set of d + 1 mutually unbiased bases follows, together with a set of properties of Gauss sums, and of bi-unimodular sequences. RESUMEN En este artículo consideramos el problema de bases insesgadas mutuamente en dimen- sión prima d. Se sabe cómo obtener exactamente d + 1 bases insesgadas mutuamente. Revisamos el problema usando una clase de matrices circulantes d×d. La demostración constructiva obtiene un conjunto de d + 1 bases insesgadas mutuamente junto con un conjunto de propiedades de sumas gausianas y de sucesiones biúnimodulares. Key words and phrases: Mutually unbiased bases, circulant matrices, Gauss sums. Math. Subj. Class.: 81P68, 15A30, 11T23 1 Introduction Mutually Unbiased Bases (MUB’s) are a set {B0, ...,BN} of orthonormal bases of Cd such that the scalar product in Cd of any vector in Bj with any vector in Bk, ∀j 6= k is of modulus d−1/2. Starting 74 Monique Combescure CUBO 11, 4 (2009) from the natural base B0 consiting of vectors v1 = (1, 0, ...0), v2 = (0, 1, 0, ..., 0), ...,vd = (0, 0, ..., 1), it is known that this problem reduces to find N unitary Hadamard matrices Pj such that P ∗ j Pk is also a unitary Hadamard matrix ∀j 6= k. (A unitary matrix is Hadamard if all its entries are of modulus d−1/2). The problem has been solved in prime power dimension d = pn, p,n ∈ N,p prime, and yields exactly d+1 MUB’s which is the maximum number of MUB’s ( [2] and references herein contained). If d is factorizable in pm1 1 p m2 2 ... with pi 6= pj prime numbers, it is known that one has at least N = min p mi i [5]. In this paper we show that in prime dimension d = p, the Discrete Fourier Transform F together with a suitable circulant matrix C allow to construct a set of d + 1 MUB’s. In addition this construction allows to obtain, as a by-product, a set of properties of Gauss sums of the following form : ∣∣∣∣∣ d−1∑ k=0 exp ( 2iπ d [ lk(k + 1) 2 + jk ])∣∣∣∣∣ = √ d, ∀j ∈ Fd, l ∈ Fd coprime with d, d ≥ 3 (1.1) (Fd is the field of residues modulo d). A direct proof of this property is given in [12]. Similar results on generalized Gauss Sums appear in [1]. The definition of F and of circulant matrices is given below. The natural role played by circulant matrices in this context is a new result. The circulant unitary matrices are known to be in one-to-one correspondence with the bi-unimodular sequences c = (c1,c2, ...,cd) [4], namely sequences such that |cj| = |(Fc)j| = 1, where F is the discrete Fourier transform. Not surprisingly Gauss sums appear naturally in this context, since suitable Gauss sequences are examples of bi-unimodular sequences. At the end of this paper, we consider the case of non-prime dimension, and show that Gauss sums properties can be deduced in the odd and in the even dimension cases. In a forthcoming work we shall consider the case of prime power dimensions and show that the theory of block-circulant matrices with circulant blocks solve the MUB problem in that case. A d × d matrix is Hadamard if all its entries have equal moduli [7], and H ∗ H = d 1l Definition 1. A d×d matrix H is Hadamard if |Hj,k| is constant ∀j,k = 1, ...,d, and H∗H = d 1l. We call H a “unitary Hadamard matrix” if |Hj,k| = d−1/2, ∀j,k = 1, ...,d, and d∑ l=1 H ∗ j,lHl,k = δj,k Definition 2. A d × d matrix C is called circulant [6], and denoted circ(c0,c1, ...,cd−1), if all its CUBO 11, 4 (2009) Circulant Matrices, Gauss Sums and Mutually Unbiased Bases ... 75 rows and columns are successive circular permutations of the first. It is of the form C =    c0 cd−1 . . c1 c1 c0 . . c2 . . . . . cd−1 cd−2 . . c0    Proposition 1.1. (i) The set C of all d × d circulant matrices is a commutative algebra. (ii) C is a subset of normal matrices (ii) Let V = circ(0, 0, ..., 1). Clearly V d = 1l. Then C is circular if and only if it commutes with V , and one has for any sequence c = (c1, ...,cd) ∈ Cd, C = circ(c1, ...,cd) : C = Pc(V ) = c01l + cd−1V + ... + c1V d−1 where Pc is the polynomial Pc(x) = d∑ k=0 ckx −k Proof : See [6] For the product of two circulant matrices C, C′ (that therefore commute with V ), one has V CC ′ = CV C ′ = CC ′ V which establishes that CC′ is indeed circulant. Moreover it is well-known that there is a close link between the circulant matrices and the discrete Fourier transform. Namely the latter diagonalizes all the circulant matrices. The Discrete Fourier Transform is defined by the following d × d unitary matrix F with matrix elements : Fj,k = d −1/2 exp ( 2iπjk d ) , j,k = 0, 1, ...,d − 1 (1.2) Proposition 1.2. (i) The circulant matrix V = circ(0, 0, ..., 1) is such that F ∗ V F = U ≡ diag(1,ω,ω2, ...,ωd−1) where ω = exp ( 2iπ d ) (1.3) (ii) Let C = circ(c0,c1, ...,cd−1) be a circulant d × d matrix. Then F ∗ CF = √ d diag(ĉ0, ĉ−1, ..., ĉ−(d−1)) where ĉl = 1√ d d−1∑ k=0 ckω kl (1.4) 76 Monique Combescure CUBO 11, 4 (2009) Proof : (i) It is enough to check that vk, the k-th column vector of F which has components (vk)j = ω jk √ d , j,k = 0, 1, ...,d − 1 is eigenvector of V with eigenvalue ωk, which is immediate since (V vk)j = ω k(j+1) √ d = ω k (vk)j (ii) One has (Proposition 1.3(ii)) C = d−1∑ k=0 ckV −k Thus F ∗ CF = d−1∑ k=0 ck(F ∗ V F) −k = d−1∑ k=0 ckU −k = diag(d0, ...,dd−1) with dl = d−1∑ k=0 ckω −lk = √ d ĉ−l Lemma 1.3. For any k ∈ N, we denote by [k] the rest of the division of k by d. Given any sequence c = (c0, ...,cd−1) ∈ Cd its autocorrelation function obeys d−1∑ k=0 c̄kc[j+k] = d−1∑ l=0 |ĉl|2ω−jl where the Fourier transform ĉ of c has been defined in (1.4). Proof : For any j = 0, ...,d − 1, one has d−1∑ l=0 |ĉl|2ω−jl = 1 d d−1∑ l=0 ω −jl d−1∑ k=0 c̄kω −lk d−1∑ k′=0 ck′ω k′l = d−1∑ k,k′=0 c̄kck′ 1 d d−1∑ l=0 ω l(k′−k−j) = d−1∑ k=0 c[j+k]c̄k since d −1 d−1∑ l=0 ω l(k′−j−k) = δk′,[j+k] It is known ( [4], [13]) that circulant unitary Hadamard matrices are in one-to-one correspon- dance with bi-unimodular sequences c = (c0,c1, ...,cd−1). Definition 3. A sequence c = (c0,c1, ...,cd−1) is called bi-unimodular if one has |cj| = |ĉj| = 1, ∀j = 1, ...,d, where ĉj is defined by (1.4). CUBO 11, 4 (2009) Circulant Matrices, Gauss Sums and Mutually Unbiased Bases ... 77 Proposition 1.4. Let (c0, ...,cd−1) be a bi-unimodular sequence. Then the circulant matrix C = d −1/2 circ(c0,c1, ...,cd−1) is an unitary Hadamard matrix. Proof : This is a standard “if and only if” statement. One uses Lemma 1.5 : d−1∑ k=0 c̄kc[j+k] d−1∑ l=0 |ĉl|2ω−jl But since |ĉl| = 1, ∀l = 0, ...,d − 1, the RHS is simply dδj,0, and therefore d−1∑ k=0 c̄kc[k+j] = d δj,0 which proves the unitarity of the circulant Hadamard matrix C. In all that follows we call indifferently F or P0 the discrete Fourier transform. In [8], the authors introduce for any dimension d being the power of a prime number a set of operators called “rotation operators” which can be viewed as “circulant matrices” (this property is however not put forward explicitely by the authors). In this paper, restricting ourselves to the prime number case, we show that these operators can be used to define a set of d + 1 Mutually Unbiased Bases in dimension d. Mutually Unbiased bases are extensively studied in the framework of Quantum Information Theory. They are defined as follows : Definition 4. A set {B1,B2, ...,Bm} of orthonormal bases of Cd is called MUB if for any vector b (k) j ∈ Bk and any b (k′) j′ ∈ Bk′ one has |b(k)j · b (k′) j′ | = d −1/2 , ∀k 6= k′ = 1, ...,m, ∀j,j′ = 1, ...,d where the dot represents the Hermitian scalar product in Cd. Remark 1.5. It is trivial to show that if the orthonormal bases Bk are the column vectors of an unitary matrix Ak, then the property that must satisfy the Ak’s in order that {1l,B1, ...,Bm} are MUB’s is that all Ak, k = 1, ...,m and A∗kAk′, k 6= k′ = 1, ...,m are unitary Hadamard matrices. Namely if uj, vk are column vectors for unitary matrices A, A′ respectively, then u j · vk = (A∗A′)j,k Thus unitary Hadamard matrices play a major role in the MUB problem. It is known that the maximum number of MUB’s in any dimension d is d + 1, and that this number is attained if d = pm, p being a prime number. In this paper, restricting ourselves to 78 Monique Combescure CUBO 11, 4 (2009) m = 1, we revisit the proof of this property, using circulant matrices introduced by [8]. We then show that it implies beautiful properties of Gauss sums, namely the following ( [12]) : Proposition 1.6. Let d ≥ 3 be an odd number. Then ∀k = 1, ...,d−1 coprime with d the sequences g (k) := ( exp ( iπkj(j + 1) d )) j=0,...,d−1 (1.5) are bi-unimodular. Thus (1.1) holds true. This property will appear as a subproduct of our study of MUB’s for d a prime number ≥ 3 via the circulant matrices method. As stressed above, the link between circulant matrices and bi-unimodular sequences is well established. What is new here is the fact that the MUB problem via a circulant matrix method allows to recover the bi-unimodularity of Gauss sequences. The crucial role played by the Gauss sequence is due to the crucial role played by the Discrete Fourier Transform (or in other therms the Fourier-Vandermonde matrices) in the MUB problem for prime numbers. Let us introduce it now explicitely. It is known since Schwinger ( [11]) that a simple toolbox of unitary d × d matrices sometimes refered to as “generalized Pauli matrices” U,V allows to find MUB’s. U, V generate the discrete Weyl-Heisenberg group [14]. Denote by ω the primitive root of unity (1.3). The matrix U is simply U = diag(1,ω,ω 2 , ...,ω d−1 ) which generalizes the Pauli matrix σz to dimensions higher than two. The matrix V generalizes σx : V = circ(0, 0, ..., 1) =    0 1 0 . . 0 0 0 1 . . 0 . . . . . . 0 0 0 . . 1 1 0 0 . . 0    Then one has the following result : Theorem 1.7. (i) The U, V matrices obey the ω-commutation rule : V U = ωUV (ii) The Discrete Fourier Transform matrix P0 = F defined by (1.2), namely P0 = 1√ d    1 1 1 . . 1 1 ω ω 2 . . ω d−1 1 ω 2 ω 4 . . ω 2(d−1) . . . . . . 1 ω d−1 ω 2(d−1) . . ω (d−1)(d−1)    CUBO 11, 4 (2009) Circulant Matrices, Gauss Sums and Mutually Unbiased Bases ... 79 diagonalizes V , namely V = P0UP ∗ 0 = P ∗ 0 U ∗ P0 (iii) One has P 4 0 = 1l (ii) is simply Proposition 1.4(i). For the proof of (iii) reminiscent to the properties of contin- uous Fourier transform, it is enough to check that P 2 0 = W =    1 0 0 0 . . 0 0 0 0 0 . . 1 . . . . . . . . . . . . . . 0 0 1 0 . . 0 0 1 0 0 . . 0    Thus W = 1l in dimension d = 2, and W 2 = 1l, ∀d ≥ 3. In [5] we have shown that for d odd one can add to the general toolbox of unitary Schwinger matrices U, V a diagonal matrix D of the form D = diag(1,ω,ω 3 , ...,ω k(k+1)/2 , ..., 1) so that the MUB problem for odd prime dimension reduces to properties of U, V, D, and that certain properties of quadratic Gauss sums follow as a by-product. 2 The d=2 Case We have U = σz and V = σx, σz, σx being the usual Pauli matrices. Since UV = σy, finding MUB’s in dimension d = 2 amounts to diagonalize σx, σy. One has : σx = P0σzP ∗ 0 σy = P1σzP ∗ 1 with P0 = 1√ 2 ( 1 1 1 −1 ) , P1 = 1√ 2 ( 1 i i 1 ) P1 is circulant. Proposition 2.1. The set {1l,P0,P1} defines three MUB’s in dimension 2. Since the matrices P0, P1 are trivially unitary Hadamard matrices, it is enough to check that P ∗ 0 P1 is itself a unitary Hadamard matrix, which holds true since P ∗ 0 P1 = e iπ/4 √ 2 ( 1 1 −i −i ) 80 Monique Combescure CUBO 11, 4 (2009) 3 The Prime Dimension d ≥ 3 d being prime, we denote by Fd the Galois field of integers mod d. Let us recall the definition of the “rotation operator” of [8], which, as already stressed in nothing but a circulant matrix in the odd prime dimension d. Definition 5. Define R as an unitary operator commuting with V and diagonalizing V U. Proposition 3.1. (i) R is a circulant matrix. (ii) Rk is also circulant ∀k ∈ Z. This follows from Proposition 1.3. Therefore we are led to consider a subclass of circulant matrices that are unitary. They must satisfy : ∀k = 0, ...,d − 1 |ck| = d−1/2 and ∀k = 1, ...,d − 1 ∑d−1 j=0 c̄jc[d−k+j] = 0 (orthogonality condition). Now it remains to show that such a matrix R exists. In [5] we have constructed a unitary matrix P1 that diagonalizes V U. It is defined as P1 = D −1 P0 for any d odd integer (not necessarily prime). We have established the following result : Proposition 3.2. (i) For any odd integer d, the matrix P∗ 0 P1 is a unitary Hadamard matrix. (ii) For d ≥ 3 odd integer, let Pk := D−kP0. Then P∗0 Pk is a unitary Hadamard matrix for all k coprime with d. (iii) The matrix D defined above is such that |TrDk| = √ d, ∀k ∈ Fd coprime with d For the simple proof of this result see [5]. (iii) is a simple consequence of (i) and(ii). Namely the eigenvector of V U belonging to the eigenvalue 1 has components vj = d −1/2 ω − j(j+1) 2 Since P∗ 0 P1 is unitary Hadamard matrix, the element of P ∗ 0 P1 of the first row and first column is simply d −1 d−1∑ j=0 ω − j(j+1) 2 CUBO 11, 4 (2009) Circulant Matrices, Gauss Sums and Mutually Unbiased Bases ... 81 and since its modulus must be d−1/2 we obtain (iii) for k = 1. The proof for any k coprime with d can be obtained similarly using (ii). The “problem” is that P1 is not circulant. However the circulant matrix R is obtained from P1 by multiplying the kth column vector of P1 by a phase which is ω − k(k−1) 2 This operation preserves the fact that it is unitary and that it diagonalizes V U. We thus have : V U = P1UP ∗ 1 = RUR ∗ (3.1) Proposition 3.3. Let R be the matrix : R = d −1/2 circ (1,ω −1 ,ω −3 , ...,ω −k(k+1)/2 , ..., 1) It is a unitary Hadamard matrix. Proof : By construction it is a unitary Hadamard matrix, since P1 is. To prove the fact that it is circulant, it is enough to know that (P1)j,k = d −1/2 ω jk− j(j+1) 2 thus Rjk = d −1/2 ω jk− j(j+1) 2 − k(k−1) 2 = d −1/2 ω − (j−k)(j−k+1) 2 (3.2) since jk − j(j + 1) 2 − k(k − 1) 2 = −(j − k)(j − k + 1) 2 Thus all column vectors are obtained from the first by the circularity property. Furthermore the Rk have the property that they diagonalize V kU, ∀k = 1, ...,d − 1: Theorem 3.4. (i) R = αP0DP∗0 where α := d −1/2 ∑d−1 k=0 ω −k(k+1)/2 is a complex number of modulus 1. (ii) Rd = αd1l where 1l denotes the unity d × d matrix. (iii) R k U(R ∗ ) k = V k U, ∀k = 0, ...,d The proof is extremely simple : (i) We have shown that cj = ω −j(j+1) 2 is a bi-unimodular sequence, thus α is a complex number of modulus one. Moreover from Proposition 1.4 (ii), the unitary matrix R = d−1/2circ(cj) is such that R̂ = P ∗ 0 RP0 = diag(ĉ−k) 82 Monique Combescure CUBO 11, 4 (2009) But ĉ−k = 1√ d d−1∑ j=0 ω −jk− j(j+1) 2 αω k(k+1) 2 since d−1∑ j=0 ω − j(j+1) 2 = d−1∑ j=0 ω − (j+k)(j+k+1) 2 = d−1∑ j=0 ω −jk− j(j+1) 2 − k(k+1) 2 Therefore R̂ = αdiag(ω k(k+1) 2 ) = αD (ii) is simply a consequence of (i) since Dd = 1l. (iii) is obtained by recurrence. Namely it is true for k = 1 by (3.1). For k ≥ 2 one has : R k U(R ∗ ) k = RV k−1 UR ∗ = V k−1 RUR ∗ since R commutes with V . But V k−1 RUR ∗ = V k−1 (V U) = V k U There is a direct link between the matrices Pk that diagonalize V U k and the Rk that diagonalize V k U : Theorem 3.5. α being the complex number of modulus one defined above, we have for any k = 0, ...,d − 1 Pk = α k P ∗ 0 R −k P 2 0 Proof : In [5] we have proven that Pk = D −k P0 diagonalizes V U k. But one has D −k = D d−k = α k−d P ∗ 0 R d−k P0 so the result follows immediately. Corollary 3.6. For any k = 1, ...,d − 1, Rk is a unitary Hadamard circulant matrix when d ≥ 3 is prime. Proof : Rk is circulant and unitary since R is. Therefore we have only to check that it is Hadamard. We have : R −k = α −k P 2 0 P ∗ 0 PkP 2 0 But we recall that P 2 0 equals the permutation matrix W . Thus all matrix elements of Rk equal, up to a phase, some matrix elements of P∗ 0 Pk. But we have established in [5] that the matrix P ∗ 0 Pk is unitary Hadamard ∀k = 1, ...,d − 1, thus all its matrix elements are equal in modulus to d−1/2. This completes the proof. Now we show how this property of the matrix R reflects itself in Gauss sums properties. CUBO 11, 4 (2009) Circulant Matrices, Gauss Sums and Mutually Unbiased Bases ... 83 Proposition 3.7. (i) Let d be an odd prime. Then for any k = 1, 2, ...,d − 1 Rk is an unitary Hadamard matrix if and only if one has ∣∣∣∣∣∣ d−1∑ j=0 exp ( iπ d [kj 2 + j(k + 2m)] ) ∣∣∣∣∣∣ = √ d, ∀m = −d + 1, ...,d − 1 (ii) Under the same conditions Rk is a unitary Hadamard matrix if and only if ∣∣∣∣∣∣ k−1∑ j=0 exp ( iπ k dj 2 + (k + 2m)j ) ∣∣∣∣∣∣ = √ k Proof : Since Rk = αkP0D k P ∗ 0 , the matrix elements of Rk are (R k )m,l = α k d d−1∑ j=0 ω j(m−l)+k j(j+1) 2 Since Rk is circulant, it is unitary Hadamard matrix if and only if the matrix elements of the first column (l=0) are of modulus d−1/2, thus if and only if ∣∣∣∣∣∣ d−1∑ j=0 exp ( iπ d [kj 2 + j(k + 2m)] ) ∣∣∣∣∣∣ = √ d which proves (i). (ii) Using the reciprocity theorem for Gauss sums ( [3]), we have for all integers a,b with ac 6= 0 and ac + d even that the quantity S(a,b,d) := d−1∑ j=0 exp ( πi d (aj 2 + bj) ) obeys S(a,b,d) = ∣∣∣∣ d a ∣∣∣∣ 1/2 exp ( πi 4 [sgn(ad) − b2/ad] ) S(−d,−b,a) Thus |S(a,b,d)| = √ d if and only if |S(−d,−b,a)| = √ a. Applying if to a = k = 1, ...,d − 1 coprime with d and b = 2m + k, and taking the complex conjugate yields the result. Namely ad + b = dk + k + 2m is even for all k = 0, ...,d − 1 since d is odd. Corollary 3.8. Let d ≥ 3 be a prime number. Then for any k = 1, 2, ...,d − 1 the sequences g (k) := ( ω k j(j+1) 2 ) j=0,...,d−1 are bi-unimodular. Remark 3.9. This property is known, but has an extension in the non prime odd dimensions. See next section. 84 Monique Combescure CUBO 11, 4 (2009) It is known that the diagonalization of V Uk, k = 0, ...,d− 1 provides a set of d + 1 MUB’s for a prime p. Here we show that the same is true with the diagonalization of V kU, k = 0, ...,d − 1. Theorem 3.10. Let d ≥ 2 be a prime dimension. Then the orthonormal bases defined by the unitary matrices 1l,P0,R,R2, ...,Rd−1 provide a set of d + 1 MUB’s. Proof : For d = 2 this has been already proven in Section 2. For d ≥ 3 (thus odd, since it is prime), it is enough to check that : (i) P0,R k , k = 1, ...,d − 1 are unitary Hadamard matrices, together with (ii) P∗ 0 R k , k = 1, ...,d − 1 and (Rk′ )∗Rk, 1 ≤ k′ < k ≤ d − 1. Since (i) has been already established, it remains to show (ii). Since Rk = αkP0D k P ∗ 0 we have P ∗ 0 R k = α k D k P ∗ 0 which is trivially an unitary Hadamard matrix (since P0 is, α is of modulus 1 and D is diagonal and unitary). For (R∗)k ′ R k it is trivial since (R ∗ ) k′ R k = R k−k′ which is unitary Hadamard for any k 6= k′, k,k′ = 1, ...,d − 1. 4 The Case of Arbitrary Odd Dimension We have shown in [5] that for any odd dimension d ≥ 3 the matrices P∗ 0 Pk is an unitary Hadamard matrix provided k is co-prime with d. This can be transfered to a similar property for the matrix R−k, and therefore to the bi-unimodularity of the sequence g(k) defined in (1.5). Proposition 4.1. Let d ≥ 3 be an odd integer, and k be any number coprime with d. Then (i) Rk is an unitary Hadamard matrix. (ii) The sequence g(k) is bi-unimodular. (iii) Both properies are equivalent. This implies Proposition 1.10. Theorem 4.2. Let d be odd and k > 2 be the smallest divisor of d. Then the orthonormal bases defined by the unitary matrices { 1l,F,R,R 2 , ...,R k−1 } provide a set of k + 1 MUB’s in dimension d. 5 The Case of Arbitrary Even Dimension Let d be even and ω = exp ( 2iπ d ) CUBO 11, 4 (2009) Circulant Matrices, Gauss Sums and Mutually Unbiased Bases ... 85 We denote ω1/2 = eiπ/d. One defines the Discrete Fourier Transform F as usually. The theory of circulant matrices is also pertinent for even dimensions d ≥ 4. Namely in that case the matrix D ′ = diag(1,ω −1/2 , ...,ω −k2/2 , ...,ω −1/2 ) has been shown ( [5]) to be such that the unitary Hadamard matrix P1 = D ′ F diagonalizes V U. But the circulant matrix R obtained by multiplying the k-th column vector of P1 by ω −k2/2 also diagonalizes V U : Proposition 5.1. The circulant matrix whose matrix elements are Rj,k = 1√ d ω −(j−k)2/2 diagonalizes V U and is such that F∗R is an unitary Hadamard matrix. Proof : (P1)j,k = 1√ d ω − j2 2 +jk thus Rj,k = 1√ d ω − (j−k)2 2 Rj,k only depends on j − k thus is circulant (and unitary). Therefore it is diagonalized by F , namely there exists an unitary diagonal matrix D′′ such that F ∗ RF = D ′′ Again this implies that F∗R is an unitary Hadamard matrix. Corollary 5.2. (i) The orthonormal bases defined by the unitary matrices {1l,F,R} provide a set of 3 MUB’s in arbitrary even dimension d. (ii) One has the following property of quadratic Gauss sums for d even : ∣∣∣∣∣ d−1∑ k=0 exp ( ik 2 π d )∣∣∣∣∣ = √ d Remark 5.3. R2 is circulant, unitary, but not Hadamard. Thus it does not help to find more than 3 MUB’s in even dimensions. In dimensions d = 2n, another method is necessary to prove that there exists d + 1 MUB’s. Acknowledgments : It is a pleasure to thank B. Helffer for his interest in this work, and to Bahman Saffari for interesting discussions and for providing to me reference [12]. Received: August 2008. Revised: September 2008. 86 Monique Combescure CUBO 11, 4 (2009) References [1] Albouy, O. and Kibler, M., SU2 nonstandard bases : the case of mutually unbiased bases, Symmetry, Integrability and Geometry : Methods and Applications, (2007) [2] Bandyopadhyay, S. Boykin, P. O. Roychowdhury, V. and Vatan, F., A new proof of the existence of mutually unbiased bases, Algorithmica, 34, 512-528, (2002) [3] Berndt, B. C. Evans, R. J. and Williams, K. S., Gauss and Jacobi Sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, Vol 21, Wiley, (1998) [4] Bjrck, G. and Saffari, B., New classes of finite unimodular sequences with unimodular Fourier transforms. Circulant Hadamard matrices with complex entries, C. R. Acad. Sci. Paris, 320 Serie 1, (1995), 319-324 [5] Combescure, M., The Mutually Unbiased Bases Revisited, Contemporary Mathematics, (2007), to appear [6] Davis, P. J., Circulant matrices, Wiley, (1979) [7] Hadamard, J., Rsolution d’une question relative aux dterminants, Bull. Sci. Math. 17, 2460- 246 (1893) [8] Klimov, A. B. Muoz, C. and Romero, J. L., Geometrical approach to the discrete Wigner function, arXiv:quant-ph/0605113, (2006) [9] Klimov, A. B. Sanchez-Soto, L. L. and de Guise, H., Multicomplementary operators via finite Fourier Transform, Journal of Physics A 38, 2747–2760 (2005) [10] Planat, M. and Rosu, H., Mutually unbiased phase states, phase uncertainties, and Gauss sums, Eur Phys. J. D 36, 133-139, (2005) [11] Schwinger, J., Unitary Operator Bases, Proc Nat. Acad. Sci. U.S.A. 46, 560 (1960) [12] Saffari, B., Quadratic Gauss Sums, to appear [13] Turyn, R., Sequences with small correlation, In Error correcting codes, H. B. Mann Ed., Wiley (1968), 195-228 [14] Weyl, H., Gruppentheorie and Quantenmechanik, Hirzel, Leipzig, (1928) Articulo 6