On discrete structures in finite Hilbert spaces
Ingemar Bengtsson Karol Zyczkowski




^1Fysikum, Stockholm University, Sweden


^2Jagiellonian University, Cracow, Poland 


^3Center for Theoretical Physics, 
  Polish Academy of Sciences Warsaw, Poland



 


  We present a brief review of discrete structures in a finite Hilbert space, 
  relevant for the theory of quantum information.
  Unitary operator bases, mutually unbiased bases,
  Clifford group and stabilizer states, discrete Wigner function, 
  symmetric informationally complete measurements,
  projective and unitary t–designs are discussed. Some recent results in the 
  field are covered and several important open questions are
  formulated. We advocate a geometric approach to the subject and
  emphasize numerous links to various mathematical problems 






On discrete structures in finite Hilbert spaces
    Ingemar Bengtsson^1 and Karol Życzkowski^2,3
    January 27, 2017
================================================





e-mail:   ingemar@physto.se   karol@cft.edu.pl









§ INTRODUCTION


These notes are based on a new chapter written to the second edition
of our book  Geometry of Quantum States.
An introduction to Quantum Entanglement <cit.>.
The book is written 
at the graduate level for a reader familiar with the principles of quantum mechanics.
It is targeted first of all for readers who 
do not read the mathematical literature everyday, but 
we hope that students of mathematics and of the information sciences will find it useful as well, since they also may wish to learn about 
quantum entanglement.

Individual chapters of the book are to a large extent
independent of each other. For instance, we hope
that the new chapter presented here
might become a source of information 
on recent developments on discrete structures 
in finite Hilbert space also for experts working in the field.
Therefore we have compiled these notes, which aim to present
an introduction to the subject as well as an up to date
review on basic features of objects belonging to the Hilbert space
and important for the field of quantum information processing.

Quantum state spaces are continuous, but they have some intriguing 
realizations of discrete structures hidden inside. We will discuss some of 
them, starting from unitary operator bases, a notion of strategic importance 
in the theory of entanglement, signal processing, quantum computation, and 
more. The structures we are aiming at are known under strange acronyms such 
as `MUB' and `SIC'. They will be spelled out in due course, but in most of 
the chapter we let the Heisenberg groups occupy the centre stage. It seems 
that the Heisenberg groups understand what is going on. 

All references to equations or the numbers of section refers
to the draft of the second edition of the book.
To give a reader a better orientation on the topics
covered we provide its contents in Appendix A.
The second edition of the book includes also 
a new chapter 17 on multipartite entanglement <cit.>
and several other new sections.







§ UNITARY OPERATOR BASES AND THE HEISENBERG GROUPS



Starting from a Hilbert space H of dimension N we have another 
Hilbert space of dimension N^2 for free, namely the Hilbert-Schmidt space 
of all complex operators acting on H, canonically 
isomorphic to the Hilbert space H⊗ H^*. It was introduced 
in Section 8.1 
and further explored in Chapter 9. 
Is it possible to find an orthonormal basis in H⊗ H^* 
consisting solely of unitary operators? A priori this looks doubtful, since 
the set of unitary matrices has real dimension N^2, only one half the 
real dimension of H⊗ H^*. But physical observables 
are naturally associated to unitary operators, so if such bases exist they 
are likely to be important. They are called 
unitary operator bases, 
were introduced by Schwinger (1960) <cit.>, 
and heavily used by him <cit.>.

In fact unitary operator bases do exist, in great abundance.
 And we can ask for  more <cit.>. 
We can insist that the elements of the basis form a group. More 
precisely, let G̅ be a finite group of order N^2, with identity element e. 
Let U_g be unitary operators giving a projective representation of G̅, 
such that 


1. U_e is the identity matrix.



2. g≠ e  ⇒  TrU_g = 0. 



3. U_gU_h = λ (g,h)U_gh, where |λ (g,h)| = 1. 


(So λ is a phase factor.) Then this collection of unitary 
matrices is a unitary operator basis. 
To see this, observe that


    U_g^† = λ (g^-1,g)^-1U_g^-1 .


It follows that 


    g^-1h ≠ e ⇒U_g^† U_h = 0  ,


and moreover that TrU_g^† U_g = U_e = N. Hence these 
matrices are orthogonal with respect to the Hilbert-Schmidt inner product from 
Section 8.1. 
Unitary operator bases arising from a group in this way 
are known as unitary operator bases of group 
type, or as nice error bases—a name that comes from the theory of 
quantum computation (where they are used to discretize errors, thus making the 
latter correctable—as we will see in Section 17.7).

The question of the existence of nice error bases is a question in group theory. 
First of all we note that there are two groups involved in the construction, 
the group G which is faithfully represented by the above formulas, and the 
collineation group G̅ which is the group G with all phase 
factors ignored. 
group!collineation
The group G̅ is 
also known, in this context, as the index group. 
group!index
Unless N is a prime number (in which case the nice error bases are 
essentially unique), there is a long list of possible index groups. An 
abelian index group is necessarily of the form H× H, where H 
is an abelian group. Non-abelian index groups are more difficult to 
classify, but it is known that every index group must be 
soluble. The classification problem has been studied by 
Klappenecker and Rötteler <cit.>, making use of the 
classification of finite groups. They also maintain an on-line catalogue.
Soluble groups will reappear in Section <ref>; 

for the moment let us just mention that all abelian groups are soluble.  

The paradigmatic example of a group G giving rise to a unitary operator basis
is the Weyl–Heisenberg group H(N).
This group appeared in many different 
contexts, starting in nineteenth century algebraic geometry, and in the beginnings 
of matrix theory <cit.>. In the twentieth century it took on a major role 
in the theory of elliptic curves <cit.>. Weyl (1932) <cit.> studied 
its unitary representations in his book on quantum mechanics. 

 The group H(N) can be presented as follows.
 Introduce three group elements X, Z, and ω. 
Declare them to be of order N: 


    X^N = Z^N = ω^N =  1 .


Insist that ω belongs to the centre of the group (it 
commutes with everything): 


    ω X = X ω , ω Z = Zω ,


Then we impose one further key relation:


    ZXZ^-1X^-1 = ω⇔ 
    ZX = ω XZ  .


The Weyl–Heisenberg group consists of all `words' that can be written down 
using the three `letters' ω, X, Z, subject to the above relations. It requires 
no great effort to see that it suffices to consider N^3 words of the form 
ω^tX^rZ^s, where t,r,s are integers modulo N. 

The Weyl–Heisenberg group admits an essentially unique unitary representation in 
dimension N. First we represent ω as multiplication with a phase factor  
which is a primitive root of unity, conveniently chosen to be 


    ω = e^2π i/N .


If we further insist that Z be represented by a diagonal operator we 
are led to the clock-and-shift representation


    Z|i⟩ = ω^i|i⟩ ,  X|i⟩ 
    = |i+1⟩ .


The basis kets are labelled by integers modulo N. A very important area 
of application for the Weyl–Heisenberg group is that of time-frequency analysis of 
signals; then the operators X and Z may represent time delays and Doppler 
shifts of a returning radar wave form. But here we stick to the language of quantum 
mechanics and  refer to Howard et al. <cit.> for an introduction to 
signal processing and radar applications.

To orient ourselves we first write down the matrix form of the generators for N = 3, 
which is a good choice for illustrative purposes: 


    Z = ( [   1   0   0;   0   ω   0;   0   0 ω^2 ])  ,   X = ( [ 0 0 1; 1 0 0; 0 1 0 ])  .


In two dimensions Z and X become the Pauli matrices σ_z and 
σ_x respectively. 
 We note 
the resemblance between eq. (<ref>) and a special case of the equation that 
defines the original Heisenberg group, eq. (6.4). This explains why Weyl 
took this finite group as a toy model of the latter. We also note that although 
the Weyl–Heisenberg group has order N^3 its collineation group—the group modulo 
phase factors, which is the group acting on projective space—has order 
N^2. In fact the collineation group is an abelian product of two cyclic groups, 
Z_N× Z_N. 
The slight departure from commutativity ensures an interesting representation theory.

There is a complication to notice at this point: because Z = X = 
(-1)^N+1, it matters if N is odd or even. If N is odd the Weyl–Heisenberg 
group is a subgroup of 
SU(N), but if N is even it is a subgroup of U(N) only. Moreover, if N is 
odd the Nth power of every group element is the identity, but if N is even 
we must go to the 2Nth power to say as much. (For N = 2 we find X^2 = Z^2 
=  1 but (ZX)^2 = (iσ_y)^2 = -  1.) These annoying 
facts make even dimensions significantly more difficult to handle, and leads to 
the definition


    N̅ = {[  N     N; 2N     N ].


Keeping the complication in mind we turn to the problem of choosing suitable phase 
factors for the N^2 words that will make up our nice error basis. The peculiarities 
of even dimensions suggest an odd-looking move. 
We introduce the phase factor


    τ≡ - e^π i/N = - √(ω) , 
    τ^N̅ = 1  .


Note that τ is an Nth root of unity only if N is odd. 
Then we define the displacement operators 


    D_ p≡ D_r,s = 
    τ^rsX^rZ^s  ,  0 ≤ r,s ≤N̅-1  .


These are the words to use in the error basis. The double notation—using 
either D_ p or D_r,s—emphasizes 
that it is convenient to view r,s as the two components of a `vector' p. 
Because of the phase factor τ the displacement operators are not actually 
in the Weyl–Heisenberg group, as originally defined, if N is even. So there 
is a price to pay for this, but in return we get the group law in the form 


    D_r,sD_u,v = ω^us-vrD_u,vD_r,s = 
    τ^us-vrD_r+u,s+v
    ⇔
     
    D_ pD_ q = ω^Ω ( p, q)D_ qD_ p 
    = τ^Ω ( p, q)D_ p +  q .


The expression in the exponent of the phase factors is anti-symmetric 
in the `vectors' that label the displacement operators. In fact Ω ( p, 
 q) is a symplectic form (see Section 3.4), 

and a very nice object to encounter.

A desirable by-product of our conventions is 


    D^-1_r,s = D_r,s^† = D_-r,-s .


Another nice feature is that the phase factor ensures that all displacement 
operators are of order N.  
On the other hand we have D_r+N,s = τ^NsD_r,s. This means that we have to live 
with a treacherous sign if N is even, since the displacement operators 
are indexed by integers modulo 2N in that case. Even dimensions are unavoidably 
difficult to deal with. 
(We do not know who first commented that “even dimensions 
are odd”, but he or she had a point.)

Finally, and importantly, we observe that 


    D_r,s = τ^rs∑_i=0^N-1ω^si⟨ 
    i|i+r⟩ = Nδ_r,0δ_s,0 .


Thus all the displacement operators except the identity are represented 
by traceless matrices, which means that the Weyl–Heisenberg group does indeed 
provide a unitary operator basis of group type, a nice error basis. Any complex 
operator A on H_N can be written, uniquely, in the form 


    A = ∑_r=0^N-1∑_s=0^N-1a_rsD_r,s ,


where the expansion coefficients 
a_rs are complex numbers given by 


    a_rs = 1/ND_r,s^† A = 
    1/ND_-r,-sA  .


Again we are using the Hilbert-Schmidt scalar product from Section 8.1.

Such expansions were called `quantum 
Fourier transformations' in Section 6.2. 
 


§ PRIME, COMPOSITE, AND PRIME POWER DIMENSIONS



The Weyl–Heisenberg group cares deeply whether the dimension N is given by a 
prime number (denoted p), or by a composite number (say N = p_1p_2 or N = p^K). 
If N = p then every element in the group has order N (or N̅ if N = 2), 
except of course for the identity element. If on the other hand N = p_1p_2 then 
(Z^p_1)^p_2 =  1, meaning that the element Z^p_1 has order p_2 
only. This is a striking difference between prime and composite dimensions. 

The point is that we are performing arithmetic modulo N, which means that we regard 
all integers that differ by multiples of N as identical. With this understanding, we 
can add, subtract, and multiply the integers freely. We say that integers modulo N 
form a ring, just as the ordinary integers do.
ring
If N is composite it can happen that xy = 0 modulo N, 
even though the integers x 
and y are non-zero. For instance, 2· 2 = 0 modulo 4. As Problem 
12.2 
should make clear, a ring is all we need to define 
a Heisenberg group, so we can proceed anyway. However, things work more smoothly if 
N equals a prime number p, because of the striking fact that every non-zero integer 
has a multiplicative inverse modulo p. Integers modulo p form a field, which 
by definition is a ring whose non-zero 
field
members form an abelian group under multiplication, so that we can perform division 
as well. In a field—the set of rational numbers is a standard example—we can 
perform addition, subtraction, multiplication, and division. In a ring—such as 
the set of all the integers—division sometimes fails. The distinction becomes 
important in Hilbert space once the latter is being organized by the Weyl–Heisenberg group.   

The field of integers modulo a prime p is denoted ℤ_p. When the 
dimension N = p the 
operators D_ p can be regarded as indexed by elements p of a two 
dimensional vector space. (We use the same notation for arbitrary N, but in 
general we need quotation marks around the word `vector'. In a true vector space 
the scalar numbers must belong to a field.) Note that this vector space contains p^2 
vectors only. Now, whenever we encountered a vector space 
in this book, we tended to focus on the set of lines through its origin. This 
is a fruitful thing to do here as well. Each such line consists of all vectors 
p obeying the equation a· p = 0 for some fixed vector 
a. Since a is determined only up to an overall factor we obtain 
p+1 lines in all, given by 


    a = ( [ a_1; a_2 ]) 
    ∈{( [ 0; 1 ]) , 
     ( [ 1; 0 ]) ,  ( [ 1; 1 ]) ,  … ,  ( [   1; p-1 ]) } .


This set of lines through the origin is a projective space with only 
p+1 points. Of more immediate interest is the fact that these lines through 
the origin correspond to cyclic subgroups of the Weyl–Heisenberg group, and 
indeed to its maximal abelian subgroups. (Choosing a = (1,x) gives the 
cyclic subgroup generated by D_-x,1.)  
The joint eigenbases of such subgroups are related in an interesting 
way, which will be the subject of Section <ref>. 

Readers who want a simple story are advised to ignore everything we say about 
non-prime dimensions. With this warning, we ask: 
What happens when the dimension is not prime? On the physical side this 
is often the case: we may build a Hilbert space of high dimension by taking 
the tensor product of a large number of Hilbert spaces which individually 
have a small dimension (perhaps to have a Hilbert space suitable for describing 
many atoms). This immediately suggests that it might be interesting to study the 
direct product H(N_1)× H(N_2) of two Weyl–Heisenberg groups, acting 
on the tensor product space H_N_1⊗ H_N_2. (Irreducible 
representations of a direct product of groups always act on the tensor product of 
their representation spaces.) Does this give something new?

On the group theoretical side it is known that the cyclic groups Z_N_1N_2 and 
Z_N_1× Z_N_2 are isomorphic if and only if the integers N_1 and N_2 
are relatively prime, that is to say if they do not contain any common factor. To see 
why, look at the examples N = 2· 2 and N = 2· 3. Clearly Z_2× Z_2 
contains only elements of order 2, hence it cannot be isomorphic to Z_4. On the other 
hand it is easy to verify that Z_2× Z_3 = Z_6. This observation carries over 
to the Weyl–Heisenberg group: the groups H(N_1N_2) and H(N_1)× H(N_2) 
are isomorphic if and only if N_1 and N_2 are relatively prime. Thus, in many 
composite dimensions including the physically interesting case N = p^K we have a 
choice of more than one Heisenberg group to play with. They all form nice error bases. 
In applications to signal processing one sticks to H(N) also when 
N is large and composite, but in many-body physics and in the theory of quantum 
computation—carried out on tensor products of K qubits, say—it is the 
multipartite Heisenberg group 
group!multipartite Heisenberg
H(p)^⊗ K = H(p)× H(p)×…× H(p) that comes to the fore.

There is a way of looking at the group H(p)^⊗ K which is quite analogous to 
our way of looking at H(p). It employs finite fields with p^K elements, and 
de-emphasizes the tensor product structure of the representation space—which in 
some situations is a disadvantage, but it is worth explaining anyway, especially since 
field!finite
we will be touching on the theory of fields in Section <ref>.
We begin by recalling how the field of complex numbers is 
constructed. One starts from the real field R, now called the 
ground field, and observes that the polynomial equation P(x) ≡ x^2+1 = 0 
does not have a real solution. To remedy this the number i is introduced as a 
root of the equation P(x) = 0. With 
this new number in hand the complex number field C is constructed as a 
two-dimensional vector space over R, with 1 and i as basis vectors. 
To multiply two complex numbers together we calculate modulo the polynomial P(x), 
which simply amounts to setting i^2 equal to -1 whenever it occurs. The finite 
fields GF(p^K) are defined in a similar way using the finite field Z_p 
as a ground field. (Here `G' stands for Galois. For 
a lively introduction to finite fields we refer to Arnold <cit.>. For quantum 
mechanical applications we recommend the review by Vourdas <cit.>).

For an example, we may choose p = 2. The polynomial P(x) = x^2+x+1 
has no zeros in the ground field Z_2, so we introduce an `imaginary' 
number α which is declared to obey P(α ) = 0. Adding and multiplying in all 
possible ways, and noting that α^2 = α +1 (using binary 
arithmetic), we obtain a larger field having 
2^2 elements of the form x_1+x_2α, where x_1 and x_2 are integers modulo 2. 
This is the finite field GF(p^2). Interestingly its three non-zero elements can also 
be described as α, α^2 = α + 1, and α^3 = 1. The first 
representation is convenient for addition, the second for multiplication. We have a 
third description as the set of binary sequences { 00, 01, 10, 11}, and consequently 
a way of adding and multiplying binary sequences together. This is very useful in the 
theory of error-correcting codes <cit.>. But this is by the way.

By pursuing this idea it has been proven that there exists a finite field GF(N) 
with N elements if and only if N=p^K is a power of prime number 
p, and moreover that this finite field is unique for a given N (which is by no means 
obvious because there will typically exist several polynomials of the same degree 
having no solution modulo p). These fields can be regarded as K dimensional vector 
spaces over the ground field Z_p, which is useful when we do addition. 
When we do multiplication it is helpful to observe the (non-obvious) fact that 
finite fields always contain a primitive element in terms of which every 
non-zero element of the field can be written as the primitive 
element raised to some integer power, so the non-zero elements form a cyclic group. Some 
further salient facts are: 




  * Every element obeys x^p^K = x.


  * Every non-zero element obeys x^p^K-1 = 1.


  * GF(p^K_1) is a subfield of GF(p^K_2) if and only if K_1 divides K_2.



The field with 2^3 elements is presented in Table <ref>, 
and the field with 3^2 elements is given as Problem 12.4. 



By definition the field theoretic trace is 


    x = x + x^p + x^p^2 + … + x^p^K-1 .


If x belongs to the finite field F_p^K its trace belongs to 
the ground field Z_p. Like the trace of a matrix, the field theoretic 
trace enjoys the properties that tr(x+y) =  x +  y and trax = 
a x for any integer a modulo p. It is used to define the concept of 
dual bases for the field. A basis is simply a set of elements such that any 
element in the field can be expressed as a linear combination of this set, using 
coefficients in Z_p. Given a basis e_i the dual basis ẽ_j is 
defined through the equation


    (e_iẽ_j) = δ_ij .


For any field element x we can then write, uniquely, 


    x = ∑_i=1^Kx_ie_i  
    x_i = (xẽ_i)  .


From Table <ref> we can deduce that the basis (1,α, α^2) 
is dual to (1,α^2, α), while the basis (α^3, α^5, 
α^6) is dual to itself.

Let us now apply what we have learned to the Heisenberg groups.
(For more details 
see Vourdas <cit.>, Gross <cit.>, and Appleby <cit.>).
Let x, u,v be elements of the finite field GF(p^K). Introduce 
an orthonormal basis and label its vectors by the field elements, 


    |x⟩ :  |0⟩ ,  |1⟩ , 
     |α⟩ ,  … , 
    |α^p^K -2⟩ .


Here α is a primitive element of the field, so there are p^K 
basis vectors altogether. Using this basis we define the operators X_u, Z_u by 


    X_u|x⟩ = |x+u⟩ ,  Z_u|x⟩ 
    = ω^tr(xu)|x⟩ , ω = e^2π i/p .


Note that X_u is not 
equal to X raised to the power u—this would 
make no sense, while the present definition does. In particular the phase 
factor ω is raised to an exponent that is just an ordinary integer modulo 
p. Due to the linearity of the field trace it is easily checked that 


    Z_uX_v = ω^ tr(vu)X_vZ_u  .


Note that it can happen that X and Z commute—it does happen for GF(2^2), 
for which tr(1) = 0—so the definition takes 
some getting used to.

We can go on to define displacement operators 


    D_ u = τ^ tru_1u_2X_u_1Z_u_2 , τ = -e^iπ/p ,  u = ( [ u_1; u_2 ])  .


The phase factor has been chosen so that we obtain the desirable properties 


    D_ uD_ v = τ^⟨ u, v⟩
    D_ u+ v ,  D_ uD_ v = 
    ω^⟨ u, v⟩D_ vD_ u D_ u^† = D_-  u .


Here we introduced the symplectic form 


    ⟨ u,  v⟩ =  tr(u_2v_1 - u_1v_2)  .


So the formulas are arranged in parallel with those used to describe H(N). 
It remains to show that the resulting group is isomorphic to the one obtained by 
taking K-fold products of the group H(p). 

There do exist isomorphisms between the two groups, but there does not exist a 
canonical isomorphism. Instead we begin by choosing a pair of dual bases for the field, 
obeying tr(e_iẽ_j) = δ_ij. We can then expand a given element of the 
field in two different ways, 


    x = ∑_i=1^Kx_ie_i = ∑_r=1^Kx̃_iẽ_i ⇔{[     x_i =  tr(xẽ_i); x̃_i =  tr(xe_i)  . ].
 

We then introduce an isomorphism between H_p^K and H_p⊗…⊗ H_p, 


    S|x⟩ = |x_1⟩⊗ |x_2⟩⊗…⊗ 
    |x_K⟩ .


In each p dimensional factor space we have the group 
H(p) and the displacement operators 


    D^(p)_i,j = τ^rsX^rZ^s  ,  r,s ∈ℤ_p  .


To set up an isomorphism between the two groups we expand 


    u = ( [ u_1; u_2 ]) = 
    ( [ ∑_iu_1ie_i; ∑_iũ_2iẽ_i ])  .


Then the isomorphism is given by 


    D_ u = S^-1( D^(p)_u_11,ũ_21⊗ 
    D^(p)_u_12,ũ_22⊗…⊗ D^(p)_u_1K,ũ_2K) S  .


The verification consists of a straightforward calculation showing that 


    D_ uD_ v = τ^∑_i(ũ_2iv_1i - u_1iṽ_2i) D_ u +  v = τ^⟨ u,v⟩D_ u +  v .

 
It must of course be kept in mind that the isomorphism inherits the 
arbitrariness involved in choosing a field basis. Nevertheless this  
reformulation has its uses, notably because we can again regard the set of displacement 
operators as a vector space over a field, and we can obtain N+1 = p^K + 1 maximal 
abelian subgroups from the set of lines through its origin. However, unlike in the 
prime dimensional case, we do not obtain every maximal abelian subgroup from this 
construction <cit.>. 



§ MORE UNITARY OPERATOR BASES



Do all interesting things come from groups? For unitary operator bases the answer 
is a resounding `no'. We begin with a slight reformulation of the problem. Instead 
of looking for special bases in the ket/bra Hilbert space H⊗ H^* we look for them in the ket/ket Hilbert space 
H⊗ H. We relate the two spaces with a map that 
interchanges their computational bases, |i⟩⟨ j| ↔ 
|i⟩ |j⟩, while leaving the components of the vectors unchanged. 
A unitary operator U with matrix elements U_ij then corresponds to the state


    |U⟩ = 1/√(N)∑_i,j = 0^N-1U_ij|i⟩ |j⟩ ∈  H⊗ H .


States of this form are said to be maximally entangled, and we will return 
to discuss them in detail in Section 16.3.
A special example, obtained 
by setting U_ij = δ_ij, appeared already in eq. (11.21).

For now we just observe that the task of finding a unitary operator basis for 
H⊗ H^* is equivalent to that of finding a maximally 
entangled basis for H⊗ H.    

A rich supply of maximally entangled bases can be obtained using two concepts 
imported from discrete mathematics: Latin squares and (complex) Hadamard matrices. 
We explain the construction for N = 3, starting with the special state  


    |Ω⟩ = 1/√(3)(|0⟩ |0⟩ + 
    |1⟩ |1⟩ + |2⟩ |2⟩ )  .


Now we bring in a Latin square. 

By definition this is an array of 
N columns and N rows containing a symbol from an alphabet of N letters in 
each position, subject to the restriction that no symbol occurs twice in any row or 
in any column. The study of Latin squares goes back to Euler; Stinson 
<cit.> provides a good account. If the reader has spent time on sudokos she 
has worked within this tradition already. Serious applications of Latin squares, 
to randomization of agricultural experiments, 
were promoted by Fisher <cit.>.
 
We use a Latin square to expand our maximally 
entangled state into N orthonormal maximally entangled states. An example with 
N = 3 makes the idea transparent:


    [ 0 1 2; 1 2 0; 2 0 1;   ]→[    |Ω_0 ⟩ = 1/√(3)(|0⟩ |0⟩ + |1⟩ |1⟩ + 
    |2⟩ |2⟩ );                                                  ;    |Ω_1 ⟩ = 1/√(3)(|0⟩ |1⟩ + 
    |1⟩ |2⟩ + |2⟩ |0⟩ );                                                  ; |Ω_2 ⟩ = 1/√(3)(|0⟩ |2⟩ + 
    |1⟩ |0⟩ + |2⟩ |1⟩ )  . ]


The fact that the three states (in H_9) are mutually orthogonal is an 
automatic consequence of the properties of the Latin square. But we want 3^2 
orthonormal states. To achieve this we bring in a complex Hadamard matrix, 

that is to say a unitary matrix each of whose elements have the same 
modulus. The Fourier matrix F, whose matrix 

elements are 


    F_jk = 1/√(N)ω^jk = 
    1/√(N)(e^2π i/N)^jk ,  0 ≤ j,k ≤ N - 1  .
  

provides an example that works for every N. For N = 3 
it is an essentially unique example.
For complex Hadamard matrices in general, see Tadej and Życzkowski <cit.>, and Szöllősi <cit.>.
 We use such a matrix to 
expand the vector |Ω_0⟩ according to the pattern 


    1/√(3)[ [   1   1   1;   1   ω ω^2;   1 ω^2   ω ]] →[    |Ω_00⟩ = 1/√(3)(|0⟩ |0⟩ +   |1⟩ |1⟩ + 
      |2⟩ |2⟩ );                                                      ;   |Ω_01⟩ = 1/√(3)(|0⟩ |0⟩ + 
    ω |1⟩ |1⟩ + ω^2|2⟩ |2⟩ );                                                      ; |Ω_02⟩ = 1/√(3)(|0⟩ |0⟩ + 
    ω^2|1⟩ |1⟩ + ω|2⟩ |2⟩ )  . ]


The orthonormality of these states is guaranteed by the properties of  
the Hadamard matrix, and they are obviously maximally entangled. Repeating the 
construction for the remaining states in (<ref>) yields a full orthonormal 
basis of maximally entangled states. In fact for N = 3 we obtained nothing new; we 
simply reconstructed the unitary operator basis provided by the Weyl–Heisenberg 
group. The same is true for N = 2, where the analogous basis is known as the 
Bell basis, and will reappear in eq. (16.1). 


The generalization to any N should be clear, especially if we formalize the 
notion of Latin squares a little. This will also provide some clues how the set 
of all Latin squares can be classified. First of all Latin squares exist for any 
N, because the multiplication table of a finite group is a Latin square. But most 
Latin squares do not arise in this way. So how many Latin squares are there? 
To count them one may first agree to present them in reduced form, which means 
that the symbols appear in lexicographical order in the first row and the first 
column. This can always be arranged by permutations of rows and columns. But there 
are further natural equivalences in the problem. A Latin square can be presented as 
N^2 triples (r,c,s), for `row, column, and symbol'. The rule is that in this 
collection all pairs (r,c) are different, and so are all pairs (r,s) and 
(s,c). So we have N non–attacking rooks on a cubic chess board of size N^3. 
In this view the symbols are on the same footing as the rows and columns, and can 
be permuted. A formal way of saying this is to introduce a map λ :   Z_N × Z_N → Z_N, where Z_N denotes 
the integers modulo N, such that the maps


    i →λ (i,j)  ,  i →λ (j,i)  ,


are injective for all values of j. Two Latin squares are said to be 
isotopic if they can be related by permutations within the three copies of 
Z_N involved in the map. The classification of Latin squares under 
these equivalences was completed up to N = 6 by Fisher and his collaborators <cit.>, 
but for higher N the numbers grow astronomical. See Table <ref>. 



The second ingredient in the construction, complex Hadamard matrices, also raises 
a difficult classification problem. 

The appropriate equivalence relation for this 
classification includes permutation of rows and columns, as well as acting with 
diagonal unitaries from the left and from the right. Thus we adopt the equivalence relation


    H' ∼ PDHD'P'  ,


where D,D' are diagonal unitaries and P,P' are permutation matrices. 
For N = 2,3, and 5, all complex Hadamard matrices are equivalent to the Fourier matrix. 
For N = 4 there exists a one-parameter family of inequivalent examples, including a purely real Hadamard matrix –
 see Table <ref>, and also Problem 12.3.
 

The  freely adjustable phase factor was discovered by Hadamard <cit.>. 
It was adjusted in experiments performed many years later <cit.>. 
Karlsson wrote down a three parameter family of N = 6 complex Hadamard matrices 
in fully explicit and remarkably elegant form <cit.>. Karlsson's family is qualitatively more interesting than the N = 4 example.

Real Hadamard matrices (having entries ± 1) can exist only if N = 2 or 

N = 4k. Paley conjectured <cit.> that in 
these cases they always exist, but his conjecture remains open.
The smallest unsolved 
case is N = 668. Real Hadamard matrices have many uses, and discrete 
mathematicians have spent much effort constructing them <cit.>.

With these ingredients in hand we can write down the vectors in a maximally 
entangled basis as


    |Ω_ij⟩ = 1/√(N)∑_k=0^N-1
    H_jk|k⟩ |λ (i,k)⟩ ,


where H_ik are the entries in a complex Hadamard matrix and 
the function λ defines a Latin square. 
(A quantum variation on the 
theme of Latin squares, giving an even richer supply, is known 
<cit.>).
The construction above is due to Werner <cit.>. 
Since it relies on arbitrary Latin squares 
and arbitrary complex Hadamard matrices we get an enormous supply 
of unitary operator bases out of it.

 This many groups do not exist, so most of these bases cannot 
be obtained from group theory. Still some nice error bases—in 
particular, the ones coming from the Weyl-Heisenberg group—do 
turn up (as, in fact, it did in our N = 3 example). The converse 
question, whether all nice error bases come from Werner's construction, has an 
answer, namely `no'. The examples constructed in this section are all monomial, 

meaning that the unitary operators can be represented by matrices having only one 
non-zero entry in each row and in each column. Nice error bases not of 
this form are known. Still it is interesting to observe that the operators 
in a nice error basis can be represented by quite sparse matrices—they 
always admit a representation in which at least one half of the matrix elements 
equal zero <cit.>.



§ MUTUALLY UNBIASED BASES



Two orthonormal bases { |e_i⟩}_i=0^N-1 and 
{ |f_j⟩}_j=0^N-1 
are said to be complementary or unbiased if 


    |⟨ e_i|f_j⟩ |^2 = 1/N


for all possible pairs of vectors consisting of one vector 
from each basis. If a system is prepared in a state belonging to one 
of the bases, then no information whatsoever is available about the 
outcome of a von Neumann measurement using the complementary basis. 
The corresponding observables are complementary in the sense of Niels 
Bohr, whose main concern was with the complementarity between position 
and momentum as embodied in the formula 


    |⟨ x|p⟩ |^2 = 1/2π .


The point is that the right hand side is a constant. Its actual value 
is determined by the probabilistic interpretation only when the dimension 
of Hilbert space is finite.

To see why a set of mutually unbiased bases may be a desirable thing to 
have, suppose we are given an unlimited supply of identically prepared 
N level systems, and that we are asked to determine the N^2-1 
parameters in the density matrix ρ. 
That is, we are asked to perform quantum state tomography on ρ. 
Performing the same von Neumann measurement on every copy will determine  
a probability vector with N-1 parameters. But 


    N^2-1 = (N+1)(N-1)  .


Hence we need to perform N+1 different measurements to fix ρ. 
If—as is likely to happen in practice—each measurement can be performed 
a finite number of times only, then there will be a statistical spread, 
and a corresponding uncertainty in the determination 
of ρ. Figure <ref> is intended to suggest (correctly as it 
turns out) that the best result will be achieved if the N+1 measurements 
are performed using Mutually Unbiased Bases (abbreviated MUB 
from now on). 



MUB have numerous other applications, notably to quantum 
cryptography. The original BB84 protocol for quantum key distribution 
<cit.> used a pair of qubit MUB. Going to larger sets of MUB in 
higher dimensions yields further advantages <cit.>. The bottom line 
is that MUB are of interest when one is trying to find or hide 
information. Further applications 
include entanglement detection in the laboratory <cit.>, a famous 
retrodiction problem <cit.>, and more.

Our concern will be to find out how many MUB exist in a given dimension N. 
The answer will tell us something about the shape of the convex body of mixed 
quantum states. To see this, note that when N = 2 the pure states making up 
the three MUB form the corners of a regular octahedron inscribed in the 
Bloch sphere. See Figure <ref>. 
Now let the dimension of Hilbert space be N. The set of mixed 
states has real dimension N^2-1, and it has the maximally mixed state as its 
natural origin. An orthonormal basis corresponds to a regular simplex 
Δ_N-1 centred at the origin. It spans an (N-1)-dimensional plane 
through the origin. Using the trace inner product we find that 


    |⟨ e_i|f_j⟩ |^2 = 1/N⇒( |e_i⟩⟨ e_i| - 1/N 1) 
    ( |f_j⟩⟨ f_j| - 1/N 1) = 0  .


Hence the condition that two such simplices represent a pair of MUB 
translates into the condition that the two (N-1)-planes be totally orthogonal, in 
the sense that every Bloch vector in one of them is orthogonal to every Bloch vector in 
the other. But the central equation of this section, namely (<ref>), implies 
that there is room for at most N+1 totally orthogonal (N-1)-planes. 
It follows that there can exist at most N+1 MUB. But it does not 
at all follow that this many MUB actually exist. Our collection of N+1 
simplices form an interesting convex polytope with N(N+1) vertices, and what 
we are asking is whether this complementarity polytope can be inscribed
polytope!complementarity 
into the convex body M^(N) of density matrices. In fact, given our 
caricature of this body, as the stitching found on a tennis ball (Section 8.6), 

this does seem a little unlikely (unless N = 2). 

Anyway a set of N+1 MUB in N dimensions is referred to as a complete 
set. Do such sets exist? If we think of a basis as given by the column vectors 
of a unitary matrix, and if the basis is to be unbiased relative to the 
computational basis, then that unitary matrix must be a complex Hadamard matrix. 
Classifying pairs of MUB is equivalent to classifying such matrices. In Section 
<ref> we saw that they exist for all N, often in 
abundance. To be specific, let the identity matrix and the Fourier matrix 
(<ref>) represent a pair of MUB. Can we find a third basis, 
unbiased with respect to both? 
Using N = 3 as an illustrative example we find that Figure 4.10 
gives the story away. A column vector in a complex Hadamard matrix corresponds 
to a point on the maximal torus in the octant picture. The twelve column vectors 


    [ [   1   0   0   1 ω^2 ω^2   1   ω   ω   1   1   1;   0   1   0 ω^2   1 ω^2   ω   1   ω   1   ω ω^2;   0   0   1 ω^2 ω^2   1   ω   ω   1   1 ω^2   ω ]]


form four MUB, and it is clear from the picture that this is the 
largest number that can be found. (For convenience we did not normalize the 
vectors. The columns of the Fourier matrix F were placed on the right.) 

We multiplied the vectors in the two bases in the middle with phase 
factors in a way that helps to make the pattern memorable. Actually there is 
a bit more to it. They form circulant matrices of size 3, meaning that

they can be obtained by cyclic permutations of their first row. Circulant 
matrices have the nice property that F^† CF is a diagonal matrix for 
every circulant matrix C.   



The picture so far is summarized in Figure <ref>. The key observation 
is that each of the bases is an eigenbasis for a cyclic subgroup of the 
Weyl–Heisenberg group. As it turns out this generalizes straightforwardly 
to all dimensions such that N = p, where p is an odd prime. We gave a 
list of N+1 cyclic subgroups in eq. 
(<ref>). Each cyclic subgroup consists of a complete set of commuting 
observables, and they determine an eigenbasis. We denote 
the a-th vector in the x-th eigenbasis as |x,a⟩, 
and we have to solve 


    D_0,1|0,a⟩ = ω^a|0,a⟩ ,  
    D_x,1|x,a⟩ = ω^a|x,a⟩ ,  D_-1,0|∞ , a⟩ 
    = ω^a|∞ , a⟩ .


Here x = 1, … , p-1, but in the spirit of projective geometry we can 
extend the range to include 0 and ∞ as well. The solution, with 
{ |e_r⟩}_r=0^p-1 denoting the computational basis, is  


    |0,a⟩ = |e_a⟩ ,  
    |x,a⟩ = 1/√(p)∑_r=0^p-1ω^(r-a)^2/2x |e_r⟩ ,
     |∞ , a⟩ = 1/√(p)∑_r=0^p-1ω^ar|e_r⟩ .
 

It is understood that if `1/2' occurs in an exponent it denotes the 
inverse of 2 in arithmetic modulo p (and similarly for `1/x'). There are p-1 bases 
presented as columns of circulant matrices, and we use ∞ to label the Fourier 
basis for a reason (Problem 12.5) 
One can  show directly (as done in 1981  by Ivanović <cit.>, 
whose interest was in state tomography)
 that these bases form a complete set of MUB 
(Problem 12.6),
but a simple and remarkable theorem will save us from this effort.

Interestingly there is an alternative way to construct the complete set. 
When N = 2 it is clear that we can start with the eigenbasis of 
the group element Z (say), choose a point on the equator, and 
then apply all the transformations effected by the Weyl–Heisenberg 
group. The resulting orbit will consist of N^2 points, and if the 
starting point is judiciously chosen they will form N MUB, all of 
them unbiased to the eigenbasis of Z. Again the construction works 
in all prime dimensions N = p, and indeed the resulting complete set 
is equivalent to the previous one in the sense that there exists a 
unitary transformation taking the one to the other.
This 
construction is due to Alltop (1980), 
whose interest was in radar applications 
<cit.>. Later references have made the construction more transparent 
and more general <cit.>.

The central theorem about MUB existence is due to 
Bandyopadhyay, Boykin, Roychowdhury, and Vatan <cit.>.


The BBRV theorem. A complete set of MUB exists 
in ℂ^N if and only if there exists a unitary operator basis which 
can be divided into N+1 sets of N commuting operators such that 
the sets have only the unit element in common. 


Let us refer to unitary operator bases of this type as flowers, 
and the sets into which they are divided as petals. Note that it is eq. (<ref>) 
that makes flowers possible. There can be at most N mutually commuting orthogonal 
unitaries since, once they are diagonalized, the vectors defined by their diagonals 
must form orthogonal vectors in N dimensions. The Weyl–Heisenberg 
groups are flowers if and only if N is a prime number—as exemplified 
in Figure <ref>. So the fact that (<ref>) gives a complete 
set of N+1 MUB whenever N is prime follows from the theorem. 

We prove the BBRV theorem one way. Suppose a complete set of MUB exists.  
We obtain a maximal set of commuting Hilbert-Schmidt orthogonal unitaries by carefully 
choosing N unitary matrices U_r, with r between 0 and N-1:


    U_r = ∑_rω^ri|e_i⟩⟨ e_i| ⇒U_r^† U_s = ∑_iω^i(r-s) = 
    Nδ_rs .


If the bases { |e_i⟩}_i=0^N-1 and 
{ |f_i⟩}_i=0^N-1 are unbiased we can form two such sets, 
and it is easy to check that 


    V_r = ∑_rω^ri|f_i⟩⟨ f_i| ⇒V_r^† U_s = 1/N∑_i,jω^-irω^js = Nδ_r,0δ_s,0 .
 

Hence U_r ≠ V_s unless r = s = 0. It may seem as if we 
have constructed two cyclic subgroups of the 
Weyl-Heisenberg group, but in fact we have not since we have said nothing about
the phase factors that enter into the scalar products ⟨ e_i|f_j⟩. 
But this is as may be. It is still clear that if we go in this way, 
we will obtain a flower from a collection of N+1 MUB. Turning this into an `if 
and only if' statement is not very hard <cit.>.



We have found flowers in all prime dimensions. What about N = 4? At this 
point we recall the Mermin square (5.61).
It defines (as it must, if one looks at the proof of the BBRV theorem) two distinct triplets 
of MUB. It turns out, however, that these are examples of unextendible 
sets of MUB, that cannot be completed to complete sets (a fact that can be 
ascertained without calculations, if the reader has the prerequisites needed 
to solve Problem 12.7. 
A more constructive observation is that the operators occurring 
in the square belong to the 
2–partite Heisenberg group H(2)× H(2). This group is also a unitary 
operator basis, and it contains no less than 
15 maximal abelian subgroups, or petals in our language. Denoting the elements 
of the collineation group of H(2) as X = σ_x,  Y = σ_y,  Z= σ_z, 
and the elements of the 2–partite group as (say) XY = X⊗ Y, we label 
the petals as  


    [   1 = { 1Z, Z 1, ZZ} 2 = { X 1,  1 X, XX}   3 = { XZ, ZX, YY };   4 = { 1Z, X 1, XZ} 5 = 
    { Z 1,  1X, ZX}   6 = { ZZ, XX, YY } ]


(these are the petals occurring in the Mermin square), and


    [    7 = { 1Z, Y 1, YZ}  8 = { Z 1,  1Y, ZY }  9 = { X 1,  1Y, XY };  10 = { 1X, Y 1, YX } 11 = 
    { 1Y, Y 1, YY }   12 = { XY, YX, ZZ };   13 = { XZ, YX, ZY }  14 = 
    { XY, YZ, ZX } 15 = { XX, YZ, ZY } . ]


After careful inspection one finds that the unitary operator basis can 
be divided into disjoint petals in 6 distinct ways, namely


    [     { 1,2,11,13,14 }      { 4,6,8,10,15 }       { 2,3,7,8,12 };      { 1, 3,9,10,15}     { 4,5,11,12,14 } { 5, 6, 7, 9, 13 } . ]


So we have six flowers, each of which contains exactly two Mermin petals 
(not by accident, as Problem 12.7 
reveals). The pattern 
is summarized in Figure <ref>.



This construction can be generalized to any prime power dimension N = p^K, The 
multipartite Heisenberg group H(p)^⊗ K gives many interlocking flowers,  
and hence many complete sets of MUB. The finite Galois fields are useful here: the 
formulas can be made to look quite similar to (<ref>), except that the 
field theoretic trace is used in the exponents of ω. We do not go into details here, but mention only that
Complete sets of MUB were constructed for prime power dimensions by Wootters 
and Fields (1989) <cit.>. Calderbank et al. <cit.> gave a more complete list, still relying on Heisenberg groups. 
All known constructions are unitarily equivalent 
to one on their list <cit.>.

The question whether all complete sets of MUB 
can be transformed into each other by means of some unitary transformation arises 
at this point. It is a difficult one. For N ≤ 5 one can show that all complete 
sets are unitarily equivalent to each other, but for N = 2^5 this is no longer 
true. In this case the 5–partite Heisenberg group can be partitioned into flowers 
in several unitarily inequivalent ways.
This was noted by Kantor, who has also reviewed the full story <cit.>.

What about dimensions that are not prime powers? Unitary operator bases exist in 
abundance, and defy classification, so it is not easy to judge whether there may 
be a flower among them. Nice error bases are easier to deal with (because groups 
can classified). There are Heisenberg groups in every dimension, and if the dimension is 
N = p_1^K_1p_2^K_2… p_n^K_n one can use them to construct 
min_i(p_i^K_i)+1 MUB in the composite dimension N 
<cit.>. 
What is more, it is known that this is the 
largest number one can obtain from the partitioning of any nice error basis into 
petals <cit.>. However, the story does not end there, because—making use 
of the combinatorial concepts introduced in the next section—one can show that 
in certain square dimensions larger, but still incomplete, sets do exist. 
In particular, in dimension N = 26^2 = 2^213^2 group theory would suggest at most 
5 MUB, but Wocjan and Beth found a set of 6 MUB. Moreover, in square dimensions 
N = m^2 the number of MUB grows at least as fast as m^1/14.8 (with finitely 
many exceptions) <cit.>. 

This leaves us somewhat at sea. We do not know whether a complete set of MUB exists 
if the dimension is N = 6, 10, 12, …. How is the question to be settled? 
Numerical computer searches with carefully defined error bounds could settle the 
matter in low dimensions, but the only case that has been investigated 
in any depth is that of N = 6. In this case there is convincing evidence 
that at most 3 MUB can be found, but still no 
proof. (Especially convincing evidence was found by Brierley and Weigert 
<cit.>, Jaming et al. <cit.>, and Raynal et al. <cit.>. See 
also Grassl <cit.>, who studies the set of vectors unbiased relative to 
both the computational and Fourier basis. There are 48 such vectors).
And N = 6 may be a very special case. 

A close relative of the MUB existence problem arises in Lie algebra theory, and 
is unsolved there as well.
But at least it received 
a nice name: the Winnie–the–Pooh problem. The reason cannot be fully rendered 
into English <cit.>.

 One can imagine that it has do with harmonic (Fourier) 
analysis 
<cit.>. Or perhaps with symplectic topology: there exists an elegant 
geometrical theorem which says that given any two bases in ℂ^N, 
not necessarily unbiased, there always exist at least 2^N-1 vectors that are 
unbiased relative to both bases. But there is no information about whether 
these vectors form orthogonal bases (and in non–generic cases the vectors may 
coincide). (See <cit.> for a description of this theorem, and 
<cit.> for a description of this area of mathematics).
 We offer these 
suggestions as hints, and return to a brief summary of known facts at the 
end of Section <ref>. Then we will have introduced some 
combinatorial ideas which—whether they 
have any connection to the MUB existence problem or not—have a number of 
applications to physics.



§ FINITE GEOMETRIES AND DISCRETE WIGNER FUNCTIONS
 


A combinatorial structure underlying the usefulness of mutually unbiased 
bases is that of finite affine planes. A finite plane is just like 
an ordinary plane, but the number of its points is finite. A finite affine 
plane contains lines too, which by definition are subsets of the set of 
points. It is required that for any pair of points there is a unique line 
containing them. It is also required that for every point not contained 
in a given line there exists a unique line having no point in common with 
the given line. (Devoted students of Euclid will recognize this as the 
Parallel Axiom, and will also recognize that disjoint lines deserve to 
be called parallel.) Finally, to avoid degenerate cases, it is required 
that there are at least two points in each line, and that there are at 
least two distinct lines. With these three axioms one can prove that two 
lines intersect either exactly once or not at all, and also that for every 
finite affine plane there exists an integer N such that



(i) there are N^2 points, 

(ii) each line contains N points,

(iii) each point is contained in N+1 lines, 

(iv) and there are altogether N+1 sets of N disjoint lines.



The proofs of these theorems are exercises in pure combinatorics <cit.>, 
and appear at first glance quite unconnected to the geometry of quantum states. 

It is much harder to decide whether a finite affine plane of order N actually 
exists. If N is a power of a prime number finite planes can be constructed 
using coordinates, just like the ordinary plane (where lines are defined by 
linear equations in the coordinates that label the points), with the difference 
that the coordinates are elements of a finite field of order N. Thus a point 
is given by a pair (x,y), where x, y belong to the finite field, and a 
line consists of all points obeying either y = ax+b or x = c, where a,b,c 
belong to the field. 

This is not quite the end of the story of the finite affine planes because examples 
have been constructed that do not rely on finite fields, but the order N 
of all these examples is a power of some prime number. Whether there exist finite 
affine planes for any other N is not known. 

Let us go a little deeper into the combinatorics, before we explain what it has 
to do with us. A finite plane can clearly be thought of as a grid of N^2 points, 
and its rows and columns provide us with two sets of N disjoint or parallel lines, 
such that each line in one of the sets intersect each line in the other set exactly 
once. But what of the next set of N parallel lines? We can label its lines with 
letters from an alphabet containing N symbols, and the requirement that any two 
lines meet at most once translates into the observation that finding the third set 
is equivalent to finding a Latin square. As we saw in Section <ref>, 
there are many Latin squares to choose from. The difficulty comes in the next 
step, when we ask for two Latin squares describing two different sets of parallel 
lines. Use Latin letters as the alphabet for the first, and Greek letters for 
the second. Then each point in the array will be supplied with a pair of letters, 
one Latin and one Greek. Since two lines are forbidden to meet more than once 
a given pair of letters, such as (A, α) or (B, γ ), 
is allowed to occur only once in the array. In other words the letters from the 
two alphabets serve as alternative coordinates for the array. Pairs of Latin 
squares enjoying this property are known as Graeco-Latin or orthogonal 
Latin squares. For N = 3 it is easy to find Graeco-Latin pairs, such as  


    (   [ A B C; B C A; C A B;   ] ,  [ α β γ; γ α β; β γ α;   ]  )
     =  [ Aα Bβ Cγ; Bγ Cα Aβ; Cβ Aγ Bα;    ] .


An example for N = 4, using alphabets that may appeal to bridge players, 
is


    [ A K Q J; K A J Q; Q J A K; J Q K A;   ] .


Graeco-Latin pairs can be found for all choices of N>2 except 
(famously) N = 6. 
This is so even though Table <ref> shows that there 
is a very large supply of Latin squares for N = 6. 
The story behind these non-existence results goes back to Euler, who was concerned with arranging 36 officers
 belonging to 6 regiments, 6 ranks, and 6 arms, in a square.

To define a complete affine plane, with N+1 sets of parallel 
lines, requires us to find a set of N-1 mutually orthogonal Latin 
squares, or MOLS.  

For N = 6 and N = 10 this is impossible, and in fact an 
infinite number of possibilities (beginning with N = 6) are ruled out by the 
Bruck-Ryser theorem, which says that if an affine plane of order N exists, 

and if N = 1 or 2 modulo 4, then N must be the sum of two squares. Note that 
10 is a sum of two squares, but this case has been ruled out by different 
means. Lam describes the computer based non-existence proof for N = 10 in a 
thought-provoking way <cit.>.

 If N = p^k 
for some prime number p a solution can easily be found using analytic geometry 
over finite fields. There remain an infinite number of instances, beginning 
with N = 12, for which the existence of a finite affine plane is an open 
question.
See the books by Bennett <cit.>, and Stinson <cit.>, for more 
information, and for proofs of the statements we have made so far.

At this point we recall that complete sets of MUB exist when N = p^k, but 
quite possibly not otherwise. Moreover such a complete set is naturally described 
by N+1 sets of N vectors. The total number of vectors is the same as the 
number of lines in a finite affine plane, so the question is if we can somehow 
associate N^2 `points' to a complete set of MUB, in such a way that the 
incidence structure of the finite affine plane becomes useful. One way to do this 
is to start with the picture of a complete set of MUB as a polytope in Bloch space. 
We do not have to assume that a complete set of MUB exists. We simply introduce 
N(N+1) Hermitian matrices P_ν of unit trace, 
polytope!complementarity 
denoted P_v, and obeying


    P_vP_v' = {[      1        v = v';    1/N        v   v';      0        v ≠ v' ].


The condition that TrP_v^2 = 1 ensures that P_v lies on the outsphere of the 
set of quantum states. If their eigenvalues are non-negative these are projectors, and 
then they actually are quantum states, but this is not needed for the definition of the 
polytope. To understand the face structure of the polytope 
we begin by noting that the 
convex hull of one vertex from each of the N+1 individual simplices forms a face.  
(This is fairly obvious, and anyway we are just about to prove it.) Using the 
matrix representation of the vertices we can then form the Hermitian unit trace matrix 


    A_f = ∑_ face P_v -  1 ,


where the sum runs over the N+1 vertices in the face. This is called a 
face point operator (later to be subtly renamed as a phase point operator). 
If N = 3 we can think of it pictorially as 
^∙ ^∙ ^∙ ^∙, say—each triangle represents a basis. 
See Figure <ref>. It is easy to see that 0 ≤ρ A_f≤ 1 
for any matrix ρ that lies in the complementarity polytope, which means that the 
latter is confined between two parallel hyperplanes. There is 
a facet defined by ρ A_f = 0 (pictorially, this would be 
_∙ _∙ _∙ _∙ _∙ _∙ _∙ _∙) 
and an opposing face containing one 
vertex from each simplex. Every vertex is included in one of these two faces. 
There are N^N+1 operators A_f altogether, and equally many facets.   

The idea is to select N^2 phase point 
operators and use them to represent the points of an affine plane. The N+1 
vertices P_ν that appear in the sum (<ref>) are to be regarded as the N+1 
lines passing through the point A_f. A set of N parallel lines in the affine plane 
will represent a complete set of orthonormal projectors.  



To do so, recall that each A_f is defined by picking one P_v from each basis. 
Let us begin by making all possible choices from the first two, and arrange 
them in an array:


    [ ^∙ _∙       _∙ _∙       _∙ _∙;                              ; ^∙ _∙       _∙ _∙       _∙ _∙;                              ; ^∙ ^∙       _∙ ^∙       _∙ ^∙ ]


We set N = 3—enough to make the idea come through—in this illustration. 
Thus the N+1 simplices in the totally orthogonal (N-1)-planes appear as 
four triangles, two of which have been used up to make the array. We use the vertices 
of the remaining N-1 simplices to label the lines in the remaining N-1 
pencils of parallel lines. To ensure that non-parallel lines intersect exactly 
once a pair such as _∙ _∙ (picked from any two out of the four 
triangles) must occur exactly once in the array. This problem can be solved 
because  an affine plane of order N is presumed to exist. One solution is  


    [ ^∙ _∙ _∙ _∙             _∙ _∙ _∙ ^∙             _∙ _∙ ^∙ _∙;                                                            ; ^∙ _∙ _∙ _∙             _∙ _∙ ^∙ _∙             _∙ _∙ _∙ ^∙;                                                            ; ^∙ ^∙ ^∙ ^∙             _∙ ^∙ _∙ _∙             _∙ ^∙ _∙ _∙ ]


We have now singled out N^2 face point operators for attention, 
and the combinatorics of the affine plane guarantees that any pair of them 
have exactly one P_v in common. Equation (<ref>) then enables us 
to compute that 


    A_fA_f' = Nδ_f,f' .


This is a regular simplex in dimension N^2-1. 

We used only N^2 out of the N^N+1 face point operators for this construction, 
but a little reflection shows that the set of all of them can be divided into 
N^N-1 disjoint face point operator simplices. In effect we have inscribed 
the complementarity polytope into this many regular simplices, which is an 
polytope!complementarity
interesting datum about the former. Each such simplex forms an orthogonal operator 
basis, although not necessarily a unitary operator basis. Let us focus on one of them, 
and label the operators occurring in it as A_i,j. It is easy to see that eq. 
(<ref>) can be rewritten (in the language of the affine plane), and supplemented, 
so that we have the two equations 


    P_v = 1/N∑_ line v A_i,j ,  
    A_i,j = ∑_ point (i,j)P_v -  1 .


The summations extend through all points on the line, respectively all lines passing 
through the point. Using the fact that the phase point operators form an operator 
basis we can then define a discrete Wigner function by 


    W_i,j = 1/NA_i,jρ .


Knowledge of the N^2 real numbers W_i,j is equivalent to knowledge of the 
density matrix ρ. Each line in the affine plane is now associated with the number 


    p_v = ∑_ line vW_i,j = P_vρ .


Clearly the sum of these numbers over a pencil of parallel lines equals unity. 
However, so far we have used only the combinatorics of the complementarity polytope, and 
we have no right to expect that the operators P_v have positive spectra. They will be 
projectors onto pure states if and only if the complementarity polytope has been 
inscribed into the set of density matrices, which is a difficult thing to achieve. If it 
is achieved we conclude that p_v ≥ 0, and then we have an 
elegant discrete Wigner function—giving all the correct marginals—on 
our hands <cit.>. It will receive further polish 
in the next section. 

Meanwhile, now that we have the concepts of mutually orthogonal Latin squares 
and finite planes on the table, we 
can discuss some interesting but rather abstract analogies to the MUB existence 
problem. Fix N=p_1^K_1p_2^K_2… p_n^K_n. Let #_ MUB be the 
number of MUB, and let #_ MOLS be the number of MOLS.

(We need only N-1 MOLS to construct a finite affine plane.) Then 


    [    min_i(p_i^K_i) -1 ≤#_ MOLS≤ N-1;                                   ; min_i(p_i^K_i) + 1 ≤#_ MUB≤ N+1  . ]


The lower bound for MOLS is known as the MacNeish bound <cit.>. 
Moreover, if N = 6, we know that Latin squares cannot occur in orthogonal pairs, 
and we believe that there exist only three MUB. Finally, it is known that if there exist 
N-2 MOLS there necessarily exist N-1 MOLS, and if there exist N MUB there 
necessarily exist N+1 MUB <cit.>. This certainly encourages the speculation that 
the existence problem for finite affine planes is related to the existence 
problem for complete sets of MUB in some unknown way. However, the idea fades 
a little if one looks carefully into the details <cit.>. 




§ CLIFFORD GROUPS AND STABILIZER STATES



To go deeper into the subject we need to introduce the Clifford group. 
group!Weyl–Heisenberg
group!Clifford
We use the displacement operators D_ p from Section <ref> to 
describe the Weyl–Heisenberg group. By definition the Clifford group consists 
of all unitary operators U such that 


    UD_ pU^-1∼ D_f( p) ,


where ∼ means `equal up to phase factors'. (Phase factors will 
appear if U itself is a displacement operator, which is allowed.) Thus we ask 
for unitaries that permute the displacement operators, so that the conjugate of 
an element of the Weyl-Heisenberg group is again a member of the Weyl–Heisenberg 
group. The technical term for this is that the Clifford group is the 
normalizer of the Weyl-Heisenberg group within 
the unitary group, or that the Weyl–Heisenberg group is an invariant subgroup

of the Clifford group. If we change H(N) into a non-isomorphic multipartite 
Heisenberg group we obtain another Clifford group, but at first we stick with 
H(N).
(The origin of the name `Clifford group' is a little unclear to us. It 
seems to be connected to Clifford's gamma matrices rather than to Clifford 
himself <cit.>).

The hard part of the argument is to show that 


    U_GD_ pU^-1_G ∼ D_G p ,


where G is a two-by-two matrix with entries in Z_N̅, the point 
being that the map p→ f( p) has to be linear <cit.>. We take 
this on trust here. To see the consequences we 
return to the group law (<ref>). In the exponent of 
the phase factor we encounter the symplectic form 


    Ω ( p, q) = p_2q_1 - p_1q_2  .


When strict equality holds in eq. (<ref>) it follows from the group law that  


    U_GD_ pD_ qU^-1_G = τ^Ω ( p, q)
    UD_ p +  qU^-1_G ⇒ 
    D_G pD_G q = τ^Ω ( p, q)D_G( p+ q) .


On the other hand we know that 


    D_G pD_G q = τ^Ω (G p,G q)D_G( p+ q) .


Consistency requires that 


    Ω ( p, q) = Ω (G p,G q)  N̅ .


The two by two matrix G must leave the symplectic form invariant. 
The arithmetic in the exponent is modulo N̅, where N̅ = N if N is odd and 
N̅ = 2N if N is even. We deplored this unfortunate complication in even 
dimensions already in Section <ref>.

Let us work with explicit matrices 


    Ω = ( [   0 - 1;   1   0 ])  ,  
    G = ( [ α β; γ δ ]) 
     , α , β , γ , δ∈ Z_N̅ .


Then eq. (<ref>) says that 


    ( [  0 -1;  1  0 ]) = 
    ( [        0 -αδ + βγ;  αδ - βγ        0 ])  .


Hence the matrix G must have determinant equal to 1 modulo N̅. 
Such matrices form the group SL(2,  Z_N̅), where Z_N̅ 
stands for the ring of integers modulo N̅. It is also known as a symplectic 
group, because it leaves the symplectic form invariant. 
group!symplectic

The full structure of the Clifford group C(N) is complicated 
by the phase factors, and rather difficult to describe in general. 
Things are much simpler when N̅ = N is odd, so let us restrict 
our description to this case.
(A complete, and clear, account 
of the general case is given by Appleby <cit.>).
 Then the symplectic 
group is a subgroup of the Clifford group. Another subgroup is evidently 
the Weyl–Heisenberg group itself. Moreover, if we consider the Clifford 
group modulo its centre, C(N)/I(N), that is to say if we identify group 
elements differing only by phase factors—which we would naturally do if 
we are interested only in how it transforms the quantum states—then we 
find that C(N)/I(N) is a semi-direct product of the symplectic rotations 
given by SL(2,  Z_N) and the translations given by H(N) 
modulo its centre. 

In every case—also when N is even—the unitary representation of the Clifford group is 
uniquely determined by the unitary representation of the Weyl-Heisenberg group.
The easiest case to describe is that when N is an odd prime number p. Then the 
symplectic group is defined over the finite field Z_p consisting of integers 
modulo p, and it contains p(p^2-1) elements altogether. Insisting that there exists 
a unitary matrix U_G such that U_G D_ p U_G^-1 = D_G p we are led to the 
representation 


    G = ( [ α β; γ δ ]) →{[ U_G = e^iθ/√(p)∑_i,jω^1/2β
    (δ i^2 - 2ij + α j^2)|i⟩⟨ j|                                                    β≠ 0;                                                        ;                            U_G = ±∑_jω^αγ/2j^2|α j⟩⟨ j|                                                β = 0  . ].
    

In these formulas `1/β' stands for the multiplicative inverse 
of the integer β in arithmetic modulo p (and since 1/2 occurs it is 
obvious that special measures must be taken if p=2). An 
overall phase factor is left undetermined: it can be pinned down by insisting on 
a faithful representation of the group <cit.>, but in many situations 
it is not needed. It is noteworthy that the representation matrices are either 
complex Hadamard matrices, or monomial matrices. 


It is interesting to see how they act on the 
set of mutually unbiased bases. In the affine plane a symplectic transformation 
takes lines to lines, and indeed parallel lines to parallel lines. If one works 
this out one finds that the symplectic group acts like Möbius transformations 
transformation!Möbius
on a projective line whose points are the individual bases. See Problem 12.5.


Even though N = 2 is even, it is the easiest case to understand. The collineation group C(2)/I(2) 
is just the group of rotations that transforms the polytope formed by the MUB states into itself, 
or in other words it is the symmetry group S_4 of the octahedron. In higher prime dimensions the 
Clifford group yields only a small subgroup of the symmetry group of the complementarity polytope. 

When N is a composite number, and especially if N is an even composite 
number, there are some significant complications for which we refer elsewhere <cit.>. 
These complications do sit in the background in Section <ref>, where 
the relevant group is the extended Clifford group

obtained by allowing also two-by-two matrices of determinant ± 1. In Hilbert space this 
doubling of the group is achieved by representing the extra group elements by anti-unitary transformations <cit.>. 


To cover MUB in prime power dimensions we need to generalize in a different 
direction. The relevant Heisenberg group is the multipartite Heisenberg group. 

We can still define the Clifford group as 
the normalizer of this Heisenberg group. We recall that the latter contains many 
maximal abelian subgroups, and we refer to the joint eigenvectors of these 
subgroups as stabilizer states. The Clifford group acts by permuting the 

stabilizer states, and every such permutation can be built as a sequence of 
operations on no more than two qubits (or quNits as the case may be) at a time. 
In one standard blueprint for universal quantum computing <cit.>, the quantum 
computer is able to perform such permutations in a fault–tolerant way, and the 
stabilizer states play a role reminiscent of that played by the separable 
states (to be defined in Chapter 16) 
in quantum communication.

The total number M of stabilizer states in N = p^K dimensions is 


    M = p^K∏_i=1^K(p^i+1)  .


Dividing out a factor p^K we obtain the number of maximal abelian subgroups 
of the Heisenberg group. In dimension N = 2^2 there are altogether 60 stabilizer 
states forming 15 bases and 6 interlocking complete sets of MUB, 
because there are 6 different ways in which the group H(2)× H(2) 
can be displayed as a flower. See Figure <ref>. 

The story in higher dimensions 
is complicated by the appearance of complete sets that fail to be unitarily equivalent 
to each other. We must refer elsewhere for the details <cit.>, but it is 
worth remarking that, for the `canonical' choice of a complete set written down by 
Ivanović <cit.> and by Wootters and Fields <cit.>, there exists 
a very interesting subgroup of the Clifford group leaving this set invariant. 
It is known as the restricted Clifford group <cit.>, and has an elegant 
description in terms of finite fields. 
group!restricted Clifford
Moreover (with an exception in dimension 3) the set of vectors that make up this set of 
MUB is distinguished by the property that it provides the smallest orbit under 
this group <cit.>. 
For both Clifford groups, the quotient of their collineation groups with the discrete 
translation group provided by their Heisenberg groups is a symplectic group. If we start 
with the full Clifford group the symplectic group acts on a 
2K-dimensional vector space over Z_p, while in the case of the  
restricted Clifford group it can be identified with the group 
SL(2, F_p^K) acting on a 2-dimensional vector space over the 
finite field F_p^K = GF(p^K) <cit.>.  

Armed with these group theoretical facts we can return to the subject of discrete Wigner 
functions. If we are in a prime power dimension it is evident that we can produce 
a phase point operator simplex by choosing any phase point operator A_f, and act 
on it with the appropriate Heisenberg group. But we can ask for more. We can ask 
for a phase point operator simplex that transforms into itself when acted on by 
the Clifford group. If we succeed, we will have an affine plane that behaves like 
a true phase space, since it will be equipped with a symplectic structure. This turns 
out to be possible in odd prime power dimensions, but not quite possible when the 
dimension is even. We confine ourselves to odd prime dimensions here. Then the Clifford 
group contains a unique element of order two, whose unitary representative 
we call A_0,0 <cit.>. Using eq. (<ref>) it is   


    G = ( [ -1  0;  0 -1 ]) 
    ⇒ 
    A_0,0 = U_G = ∑_i=0^N-1 |N-i⟩⟨ i|  .


By the way we observe that A_0,0^2 = F, where F is the Fourier matrix. 
Making use of eqs. (<ref>-<ref>) we find  


    A_0,0 = ∑_r,sD_r,s .


To perform this sum, split it into a sum over the N+1 maximal abelian 
subgroups and subtract 1 to avoid overcounting. Diagonalize 
each individual generator of these subgroups, say


    D_0,1 = Z = ω^a∑_a |0,a⟩⟨ 0,a| ⇒∑_i=0^N-1Z^i = N|0,0⟩⟨ 0,0|  .


All subgroups work the same way, so this is enough. We conclude that 
 

    A_0,0 = 
    ∑_z|z,0⟩⟨ z,0| -  1 .


(The range of the label z is extended to cover also the 
bases that we have labelled by 0 and ∞.) Since we are picking one projector 
from each of the N+1 bases this is in fact a phase point operator.

Starting from A_0,0 we can build a set of N^2 order two phase point operators 


    A_r,s = D_r,sAD_r,s^-1 .


Their eigenvalues are ± 1, so these operators are both Hermitian and 
unitary. The dimension N is odd, so we can write N = 2m-1. Each phase 
point operator splits Hilbert space into a direct sum of eigenspaces, 


    H_N =  H_m^(+)⊕ H_m-1^(-) .


Altogether we have N^2 subspaces of dimension m, each of 
which contain N+1 MUB vectors. Conversely, one can show that each of the N(N+1) 
MUB vectors belongs to N such subspaces. This intersection pattern was said to be 
“une configuration très-remarquable” when it was first discovered
(By Segre (1886) <cit.>, who was studying elliptic normal curves. 
From the present 
point of view it was first discovered by Wootters (1987) <cit.>).

The operators A_r,s form a 
phase point operator simplex which enjoys the twin advantages of being both a unitary 
operator basis and an orbit under the Clifford group. A very satisfactory 
discrete Wigner function can be obtained from it <cit.>. The situation 
in even prime power dimensions is somewhat less satisfactory since covariance 
under the full Clifford group cannot be achieved in this case.

The set of phase point operators forms a particularly interesting unitary operator 
basis, existing in odd prime power dimensions only. Its symmetry group acts on it in 
such a way that any pair of elements can be transformed to any other pair. This is 
at the root of its usefulness: from it we obtain a discrete Wigner function 
on a phase space lacking any kind of scale, just as the ordinary symplectic 
vector spaces used in classical mechanics lack any kind of scale. Moreover (with 
two exceptions, one in dimension two and and one in dimension eight) it is 
uniquely singled out by this property <cit.>.



§ SOME DESIGNS



To introduce our next topic let us say something obvious. 
We know that 


    1_N = 1/N∑_i=1^N|e_i⟩⟨ e_i| 
    = ∫_ C P^n dΩ_Ψ |Ψ⟩⟨Ψ |  ,


where dΩ_Ψ is the unitarily invariant Fubini–Study measure.  
Let A be any operator acting on C^N. It follows that 


    1/N∑_i=0^N-1⟨ e_i|A|e_i⟩ = 
    ∫_ C P^n dΩ_Ψ⟨Ψ|A|Ψ⟩ = 
    ⟨⟨Ψ|A|Ψ⟩⟩_ FS .


On the right hand side we are averaging an (admittedly special) 
function over all of C P^N-1. On the left hand side we take 
the average of its values at N special points. In statistical 
mechanics this equation allows us to evaluate the average expectation value 
of the energy by means of the convenient fiction that the system is in an energy 
eigenstate—which at first sight is not obvious at all. 

To see how this can be generalized we recall the mean value theorem, which 
says that for every continuous function defined on the closed 
interval [0,1] there exists a point x in the interval such that 


    f(x) = ∫_0^1 dsf(s)  .


Although it is not obvious, this can be generalized to the case of 
sets of functions f_i <cit.>. Given such a set of functions one can always 
find an averaging set consisting of K different points x_I such that, for 
all the f_i,   


    1/K∑_I=1^Kf_i(x_I) = ∫_0^1 ds f_i(s)  .
  

Of course the averaging set (and the integer K) will depend on the 
set of functions { f_i} one wants to average. 
We can generalize even more by replacing the interval with a 
connected space, such as C P^N-1, and by replacing the real 
valued functions with, say, the set Hom(t,t) of all complex valued functions 
homogeneous of order t in the homogeneous coordinates and their complex 
conjugates alike. (The restriction on the functions is needed in order to 
ensure that we get functions on C P^N-1. Note that the expression 
⟨ψ|A|ψ⟩ belongs to Hom(1,1).) This too can 
always be achieved, with an averaging set being a 
collection of points represented by the unit vectors |Ψ_I⟩, 
1≤ I ≤ K, for some sufficiently large integer K <cit.>. 
We define a complex projective t–design, or t–design for short, 
as a collection of unit vectors { |Ψ_I⟩}_I=1^K such that 


    1/K∑_I=1^Kf(|Ψ_I⟩ ) = 
    ∫_ C P^n dΩ_Ψ f(|Ψ⟩ )


for all polynomials f ∈(t,t) with the components 
of the vector, and their complex conjugates, as arguments. 
Formulas like this are called 
cubature formulas, since—like quadratures—they give explicit solutions 
of an integral, and they are of practical interest—for many signal processing and 
quantum information tasks—provided that K can be chosen to be reasonably small. 

Eq. (<ref>) shows that orthonormal bases are 1–designs. More generally, 
every POVM 
POVM
is a 1–design. Let us also note that functions f ∈ Hom(t-1,t-1) 
can be regarded as special cases of functions in Hom(t,t), since they can be rewritten 
as f = ⟨Ψ|Ψ⟩ f ∈ Hom(t,t). Hence a t–design is automatically 
a (t-1)–design. But how do we recognize a t–design when we see one?

The answer is quite simple. 
In eq. (7.69) 
we calculated the Fubini–Study average of 
|⟨Φ|Ψ⟩|^2t for a fixed unit vector |Φ⟩. 
Now let { |Ψ_I⟩}_I = 1^K be a t–design. It follows that 


    1/K∑_J |⟨Ψ_I|Ψ_J ⟩ |^2t = 
    ⟨ |⟨Ψ_I|Ψ⟩ |^2t⟩_ FS = t!(N-1)!/(N-1+t)! .
 

If we multiply by 1/K and then sum over I we obtain 


    1/K^2∑_I,J|⟨Ψ_I|Ψ_J⟩ |^2t = 
    t!(N-1)!/(N-1+t)! .
 
 
We have proved one direction of the following 



theorem!Design
Design theorem. The set of unit vectors { |Ψ⟩}_I=1^K 
forms a t–design if and only if eq. (<ref>) holds. 



In the other direction a little more thought is needed <cit.>. 
Take any vector |Ψ⟩ in C^N and construct a vector in 
( C^N)^⊗ t by taking the tensor product of the 
vector with itself t times. Do the same with |Ψ̅⟩, a vector whose components 
are the complex conjugates of the components, in a fixed basis, of the given vector. A final 
tensor product leads to the vector


    |Ψ⟩^⊗ t⊗ |Ψ̅⟩^⊗ t∈ 
    ( C^N)^⊗ 2t .


In the given basis the components of this vector are 


    (z_0… z_0z̅_0…z̅_0, z_0… z_0z̅_1…z̅_1, …… , 
    z_n… z_nz̅_n…z̅_n)  .


In fact the components consists of all possible monomials in Hom(t,t). Thus, to show that 
a set of unit vectors forms a t–design it is enough to show that the vector 


    |Φ⟩ = 1/K∑_I|Ψ_I⟩^⊗ t⊗ 
    |Ψ̅_I⟩^⊗ t - ∫ dΩ_Ψ|Ψ⟩^⊗ t⊗ 
    |Ψ̅⟩^⊗ t


is the zero vector. This will be so if its norm vanishes. We observe preliminarily that 


    ⟨Ψ_I^⊗ t|Ψ_J^⊗ t⟩ = ⟨Ψ_I|Ψ_J⟩^t 
     .


If we make use of the ubiquitous eq. (7.69)
we find precisely that 


    ||Φ ||^2 = 1/K^2∑_I,J|⟨Ψ_I|Ψ_J⟩ |^2t - 
    t!(N-1)!/(N-1+t)! .


This vanishes if and only if eq. (<ref>) holds. But 
|Φ⟩ = 0 is a sufficient condition for a t–design, and the 
theorem is proven. 

This result is closely related to the Welch bound <cit.>, 

which holds for every collection of K vectors in 
ℂ^N. For any positive integer t 


    N+t-1t∑_I,J|⟨ x_I|x_J⟩ |^2t≥( ∑_I ⟨ x_I|x_I⟩^t)^2  .


Evidently a collection of unit vectors forms a t-design if and only if 
the Welch bound is saturated. 
The binomial coefficient occurring here is the number of ways in which t identical objects 
can be distributed over N boxes, or equivalently it is the dimension of the symmetric 
subspace H_ sym^⊗ t of the t–partite Hilbert space 
H_N^⊗ t. This is not by accident. Introduce the operator 


    F = ∑_I|Ψ_I^⊗ t⟩⟨Ψ_I^⊗ t|  .


It is then easy to see, keeping eq. (<ref>) in mind, that 


    F = ∑_I⟨Ψ_I^⊗ t|Ψ_I^⊗ t⟩ = K



    F^2 = ∑_I,J⟨Ψ_I^⊗ t|
    Ψ_J^⊗ t⟩⟨Ψ_J^⊗ t|Ψ_I^⊗ t⟩  = 
    ∑_I,J|⟨Ψ_I|Ψ_J⟩|^2t .


Now we can minimize TrF^2 under the constraint that TrF = K. In fact this 
means that all the eigenvalues λ_i of F have to be equal, namely equal to 


    λ_i = K/( H^⊗ t_ sym) .


So we have rederived the inequality


    ∑_I,J|⟨Ψ_I|Ψ_J⟩|^2t = F^2 ≥K^2/( H^⊗ t_ sym) .


Moreover we see that the operator F projects onto the symmetric subspace.

Although t–designs exist in all dimensions, for all t, it is not so easy to find 
examples with small number of vectors. A lower bound on the number of vectors needed is 
<cit.>  


    ≥( [ N+(t/2)_+ -1;      (t/2)_+ ]) ( [ N+(t/2)_- - 1;       (t/2)_- ])  ,


where (t/2)_+ is the smallest integer not smaller than t/2 and 
(t/2)_- is the largest integer not larger than t/2. The design is said to be 
tight if the number of its vectors saturates this bound. Can the bound 
be achieved? For dimension N = 2 much is known <cit.>. A tight 2–design 
is obtained by inscribing a regular tetrahedron in the Bloch sphere. A tight 3–design is 
obtained by inscribing a regular octahedron, and a tight 5–design by inscribing a regular 
icosahedron. The icosahedron is also the smallest 4–design, so tight 4–designs do not
exist in this dimension. A cube gives a 3-design and a dodecahedron gives a 5-design. 
For dimensions N > 2 it is known that tight t–designs can exist at most for t=1,2,3. 
Every orthonormal basis is a tight 1–design. A tight 2–design needs N^2 vectors, and 
the question whether they exist is the subject of Section <ref>.

 Meanwhile 
we observe that that the N(N+1) vectors in a complete set of MUB saturate 
the Welch bound for t = 1,2. Hence complete sets of MUB are 2–designs, and much of 
their usefulness stems from this fact. Tight 3–designs 
exist in dimensions 2, 4, and 6. In general it is not known how many vectors that 
are needed for minimal t–designs in arbitrary dimensions, which is why the 
terminology `tight' is likely to be with us for some time.
A 
particularly nice account of all these matters is in the University of 
Waterloo Master's thesis by Belovs (2008) <cit.>. 
For more results, and references that we have omitted, see Scott <cit.>. 

The name `design' is used for more than one concept. One example, closely related 
to the one we have been discussing, is that of a 
unitary t–design.
(Although there was a prehistory, the name seems to stem from 
a University of Waterloo Master's thesis by Dankert (2005) <cit.>. The idea was further 
developed in papers to which we refer for proofs, applications, and details <cit.>).

By definition this is a set of unitary 
operators { U_I}_I=1^K with the property that 


    1/K∑_IU_I^⊗ tA(U_I^⊗ t)^† = ∫_U(N) dU 
     U^⊗ tA(U^⊗ t)^† ,


where A is any operator acting on the t–partite Hilbert space and dU is 
the normalized Haar measure on the group manifold. In the particularly interesting case t = 2 
the averaging operation performed on the right hand side is known as twirling.

Condition (<ref>) for when a collection of vectors forms a projective t–design 
has a direct analogue: the necessary and sufficient condition for a collection of K unitary 
matrices to form a unitary t–design is that  


    1/K^2∑_I,J|U_I^† U_J|^2 = ∫_U(N) dU 
    |U|^2t = {[ (2t)!/t!(t+1)! ,                             N = 2;            t!  ,                          N ≥ t  . ].


When t > N the right hand side looks more complicated. 

It is natural to ask for the 
operators U_I to form a finite group. The criterion for (a projective unitary representation 
of) a finite group to serve as a unitary t–design is that it should have the same number of 
irreducible components in the t–partite Hilbert space as the group U^⊗ t itself. 
Thus a nice error basis, such as the Weyl–Heisenberg group, is always a 1–design because 
any operator commuting with all 
the elements of a nice error basis is proportional to the identity matrix. When t = 2 the 
group U⊗ U splits the bipartite Hilbert space into its symmetric and its anti-symmetric 
subspace. 

In prime power dimensions both the Clifford group and the restricted Clifford group 

are unitary 2-designs <cit.>. In fact, 
it is enough to use a particular subgroup 
of the Clifford group <cit.>. 
For qubits, the minimal unitary 2-design is the 
tetrahedral group, which has only 12 elements. In even prime power dimensions 2^k 
the Clifford group, but not the restricted Clifford group, is a unitary 3–design 
as well <cit.>. Interestingly, every 
orbit of a group yielding a unitary t–design is a projective t–design. 
This gives an alternative proof that a complete set of MUB is a 2–design 
(in those cases where it is an  orbit under the restricted Clifford group). 
In even prime power dimensions the set of all 
stabilizer states is a 3–design.
 In dimension 4 it consists of 60 vectors, while a tight 
3–design (which actually exists in this case) has 40 vectors only.



§ SICS


 
At the end of Section 8.4 
we asked the seemingly innocent question: 
Is it possible to inscribe a regular simplex of full dimension into the 
convex body of density matrices? A tight 2–design in dimension N, if it exists, 
has N^2 vectors only, and our question can be restated as: Do tight 2–designs 
exist in all dimensions? 

In Hilbert space language the question is: Can we find an informationally complete POVM 

made up of equiangular vectors? Since absolute values of the scalar products are taken 
the word `vector' really refers to a ray (a point in C P^n). That is, 
we ask for N^2 vectors |ψ_I⟩ such that 


    1/N∑_I=1^N^2|ψ_I⟩⟨ψ_I| =  1
 


    |⟨ψ_I|ψ_J⟩ |^2 = {[        1             I = J;         ;    1/N+1          I ≠ J  . ].


We need N^2 unit vectors to have informational completeness (in the sense of 
Section 10.1), 
and we are assuming that the mutual fidelities are equal. 
The precise number 1/(N+1) follows by squaring 
the expression on the left hand side of eq. (<ref>), and then taking the trace. Such a collection 
of vectors is called a SIC, so the final form of the question is: Do SICs 
exist?
(The acronym is short for Symmetric Informationally 
Complete Positive Operator Valued Measure <cit.>, and is rarely spelled out. We 
prefer to use `SIC' as a noun. When pronounced as `seek' it serves to remind 
us that the existence problem may well be hiding their most important message).

If they exist, SICs have some desirable properties. First of all they saturate 
the Welch bound, and hence they are 2-designs with the minimal number 
of vectors. Moreover, also for other reasons, they are theoretically 
advantageous in quantum state tomography <cit.>, and they provide a 
preferred form for informationally complete POVMs. Indeed an entire philosophy 
can be built around them <cit.>.

But the SIC existence problem is unsolved. 
Perhaps we should begin by noting that there is a crisp non-existence result 
for the real Hilbert spaces R^N. 
Then Bloch space has dimension N(N+1)/2-1, so the number of equiangular 
vectors in a real SIC is N(N+1)/2. For N = 2 the rays of a real SIC 
pass through the vertices of a regular triangle, and for N = 3 the 
six diagonals of an icosahedron will serve. However, for N > 3 it 
can be shown that a real SIC cannot exist unless N+2 is a square of 
an odd integer. In particular N = 4 is ruled out. In fact SICs do not 
exist in real dimension 47 = 7^2-2 either, so there are further 
obstructions. The non-existence result is due to 
Neumann, and reported by Lemmens and Seidel (1973) <cit.>. 
Since then more has been learned <cit.>. Incidentally the SIC 
in R^3 has been proposed as an ideal configuration for 
an interferometric gravitational wave detector <cit.>.

In C^N exact solutions are available in all 
dimensions 2≤ N ≤ 21, 
and in a handful of dimensions higher than that. Numerical solutions to high 
precision are available in all dimensions given by two-digit numbers and a bit 
beyond that. (Most of these results, many of them unpublished, are due 
to Gerhard Zauner, Marcus Appleby, Markus Grassl, and Andrew Scott. For the 
state of the art in 2009, see Scott and Grassl <cit.>. The first two 
parts of the conjecture are due to Zauner (1999) <cit.>, the third to 
Appleby at al. (2013) <cit.>. We are restating it a little for 
convenience).
 The existing solutions support a three-pronged conjecture:


1. In every dimension there exists a SIC which is an orbit of the Weyl–Heisenberg group.



2. Every vector belonging to such a SIC is invariant under a Clifford group 

element of order 3.



3. When N > 3 the overlaps of the SIC vectors are algebraic units in 
an abelian 

extension of the real quadratic field Q(√((N-3)(N+1))).


Let us sort out what this means, beginning with the easily understood part 1. 

In two dimensions a SIC forms a tetrahedron inscribed in the Bloch sphere. If we orient it so that its 
corners lie right on top of the faces of the octahedron whose corners are the stabilizer states it is easy to see (look at Figure <ref>a) that the Weyl–Heisenberg 
group can be used to reach any 
corner of the tetrahedron starting from any fixed corner. In other words, when N = 2 
we can always write the N^2 SIC vectors in the form 


    |ψ_r,s⟩ = D_r,s|ψ_0⟩ ,  0 ≤ 
    r,s < N-1  ,


where |ψ_0⟩ is known as the fiducial vector for the SIC (and has 
to be chosen carefully, in a fixed representation of the Weyl–Heisenberg 
group). Conjecture 1 says that it is possible to find such a fiducial vector in every 
dimension. Numerical searches are based on this, and basically proceed by minimizing the function 


    f_ SIC = ∑_r,s( |⟨ψ_0|ψ_r,s⟩|^2 
    - 1/N+1)^2  ,


where the sum runs over all pairs (r,s) ≠ (0,0). The arguments of the 
function are the components of the fiducial vector |ψ_0⟩. This is a 
fiducial vector for a SIC if and only if f_ SIC = 0. Solutions have been found 
in all dimensions that have been looked at—even though the presence 
of many local minima of the function makes the task difficult. SICs arising 
in this way are said to be covariant under the Weyl–Heisenberg group. 
It is believed that the numerical searches for such WH-SICs are exhaustive up to 
dimension N = 50 <cit.>. They necessarily fall into orbits of the 
Clifford group, extended to include anti-unitary symmetries.
group!extended Clifford 
For N ≤ 50 there are six cases where there is only one such orbit 
(namely N =2, 4, 5, 10, or 22), 
while as many as ten orbits occur in two cases (N = 35 or 39). 

Can SICs not covariant under a group exist? The only publicly available answer to 
this question is that if N ≤ 3 then all SICs are orbits under the 
Weyl–Heisenberg group <cit.>. Can any other group serve the purpose? 
If N = 8 there exists an elegant SIC covariant under H(2)^⊗ 3 
<cit.>, as well as two Clifford orbits of SICs covariant under the 
Weyl–Heisenberg group H(8). No other examples of a SIC not covariant 
under H(N) are known, and indeed it is known that for prime N 
the Weyl–Heisenberg group is the only group that can yield SICs <cit.>. 
Since the mutually unbiased bases rely on the multipartite Heisenberg group 
this means that there can be no obvious connection between MUB and SICs, 
except in prime dimensions. In prime dimensions it is known that the 
Bloch vector of a SIC projector, when projected onto any one of the MUB 
eigenvalue simplices, has the same length for all the N+1 simplices defined 
by a complete set of MUB <cit.>. If N = 2, 3, every state having this 
property is a SIC fiducial <cit.>, but when N ≥ 5 this is far from 
being the case. The two lowest dimensions have a very special status. 

The second part of the conjecture is due to Zauner. It clearly holds if N = 2. 
Then the Clifford group, the group that permutes the stabilizer states, is the 
symmetry group of the octahedron. This group contains elements of order 3, and 
by inspection we see that such elements leave some corner of the SIC-tetrahedron 
invariant. The conjecture says that such a symmetry is shared by all SIC vectors 
in all dimensions, and this has been found to hold true for every solution found so far. The sizes of the Clifford orbits shrink accordingly. In many dimensions—very 
much so in 19 and 48 dimensions—there are SICs 
left invariant by larger subgroups of the Clifford group, but the order 3 
symmetry is always present and appears to be universal. 
There is no understanding of why this should be so. 

To understand the third part of the conjecture, and why it is interesting, 
it is necessary to go into the methods used to produce solutions in the first place.  
Given conjecture 1, the straightforward way to find a SIC is to solve the 
equations  


    |⟨ψ_0|D_rs|ψ_0⟩|^2 =  
    1/N+1


for (r,s) ≠ (0,0). Together with the normalization this is a set 
of N^2 multivariate quartic polynomial equations in the 2N 
real variables needed to specify the fiducial vector. To solve them 
one uses the method of Gröbner bases to reduce the set of equations to a single 
polynomial equation in one variable <cit.>. This is a task for computer 
programs such as MAGMA, and a clever programmer. The number of equations greatly 
exceeds the number of variables, so it would not be surprising if they did not have a 
solution. But solutions do exist. 

As an example, here is a fiducial vector for a SIC in 4 
dimensions <cit.>:


    ψ_0 =  ( [                        1-τ/2√(5+√(5)/10); 1/20( i√(50-10√(5)) + (1+i)√(5(5+3√(5)));                       -1+τ/2√(5+√(5)/10); 1/20( i√(50-10√(5)) - (1-i)√(5(5+3√(5))) ])


(with τ = -e^iπ/4). This does not look memorable at first sight. 
Note though that all components can be expressed in terms of nested square roots. 
This means that they are numbers that can be constructed by means of rulers and 
compasses, just as the ancient Greeks would have wished. This is not at all what 
one would expect to come out from a Gröbner basis calculation, which in the end 
requires one to solve a polynomial equation in one variable but of high degree. 
Galois showed long ago that generic polynomial equations cannot be solved 
by means of nested root extractions if their degree exceeds four. 

And we can simplify the expression. Using the fact that the Weyl–Heisenberg 
group is a unitary operator basis, eqs. (<ref>-<ref>) we can 
write the fiducial projector as 


    |ψ_0⟩⟨ψ_0| = 1/N∑_r,s=0^N-1 
    D_r,s⟨ψ_0|D_r,s^† |ψ_0⟩ .


But the modulus of the overlaps is fixed by the SIC conditions, so 
we can define the phase factors 


    e^iθ_r,s = √(N+1)⟨ψ_0|D_r,s|ψ_0⟩ ,  (r,s) ≠ (0,0)  .


These phase factors are independent of the choice of basis in ℂ^N, 
and if we know them we can reconstruct the SIC. The 
number of independent phase factors is limited by the Zauner symmetry (and 
by any further symmetry that the SIC may have). For the N = 4 example we find 


    [ [        × e^iθ_0,1 e^iθ_0,2 e^iθ_0,3; e^iθ_1,0 e^iθ_1,1 e^iθ_1,2 e^iθ_1,3; e^iθ_2,1 e^iθ_2,1 e^iθ_2,2 e^iθ_2,3; e^iθ_3,0 e^iθ_3,1 e^iθ_3,2 e^iθ_3,3 ]]  = [ 
    [    ×    u   -1  1/u;    u  1/u -1/u  1/u;   -1   -u   -1  1/u;  1/u    u    u    u ]] ,


where 


    u = √(5)-1/2√(2)+i√(√(5)+1)/2 .


The pattern in eq. (<ref>) is forced upon us by the Zauner symmetry, 
so once we know the number u it is straightforward to reconstruct the entire SIC. 

What is this number? To answer this question one computes (usually by means of 
a computer) the minimal polynomial, the lowest degree polynomial with 
coefficients among the integers satisfied by the number u. In this case it is


    p(t) = t^8 -2t^6 - 2t^4 - 2t^2 +1  .


Because the minimal polynomial exists, we say that u is an 
algebraic number. Because its leading coefficient equals 1, we say that u 
is an algebraic integer. Algebraic integers form a ring, just as the ordinary 
integers do. (Algebraic number theorist refer to ordinary integers as 
`rational integers'. This is the special case when the polynomial is of first 
order.) Finally we observe that 1/u is an algebraic integer too—in fact it 
is another root of the same equation—so we say that u is an algebraic 
unit.
Neither algebraic number theory nor Galois theory (which we are 
coming to) lend themselves to thumbnail sketches. For first encounters we recommend 
the books by Alaca and Williams <cit.> and by Howie <cit.>, respectively.

Hence u is a very special number, and the question arises what number field it 
belongs to. This is obtained by adding the roots of (<ref>) to the field of 
rational numbers, ℚ. We did give a thumbnail sketch of field extensions 
in Section <ref>, but now we are interested in fields with an 
infinite number of elements. When we adjoined a root of the equation x^2 +1 = 0 
to the real field R we obtained the complex field R( i) = 
 C. In fact there are two roots of the equation, and there is a group—in 
this case the abelian group Z_2—that permutes them. This group is called the 
Galois group 

of the extension. It can also be regarded as the group of automorphisms of the extended field 
C that leaves the ground field R invariant. A Galois group arises 
whenever a root of an irreducible polynomial is added to a field. Galois proved that 
a polynomial with rational coefficients can be solved with root extractions if and only 
if the Galois group is soluble 
group!soluble
(as is the case for a generic quartic, but not for a generic quintic). This is 
the origin of the name `soluble'. For a group to be soluble it must have a particular 
pattern of invariant subgroups. 

What one finds in the case at hand is that the Galois group is non-abelian, but only barely 
so. The field for the N = 4 SIC can be obtained by first extending ℚ to 
ℚ(√(5)), that is to say to consider the real quadratic field 
consisting of all numbers of the form x + √(5)y, where x,y are rational. A further 
extension then leads to the field ℚ(u,r), where r is an additional (real) 
root of (<ref>). The Galois group arising in the second step, considered by itself, 
is abelian, and the second extension is therefore said to be an abelian extension.
  
Thus the mysterious number u does not only belong to the field whose construction we sketched, 
it has a very special status in it, and moreover the field is of an especially important 
kind, technically known as a ray class field.

Things are not quite so simple in higher dimensions, but almost so—in 
terms of principles that is, not in terms of the calculations that need to be 
done.
(The number theory of SICs, so far as it is known, was developed by 
Appleby, Flammia, McConnell, and Yard (2016) <cit.>). 
The SIC overlaps, and the SIC vectors themselves if expressed in the natural basis, are still 
given by nested radicals, although no longer by square roots only so they are not 
constructible with ruler and compass. Indeed the third part of the SIC conjecture 
holds in all cases that have been looked at. What is more, the SIC overlaps 
continue to yield algebraic units. But it is not understood why the polynomial 
equations that define the SICs have this property. 

A field extension is said to be abelian whenever its Galois group is abelian. 
In the nineteenth century Kronecker and Weber studied 
abelian extensions of the rational field Q, and they proved that all such 
extensions are subfields of a cyclotomic field, which is what one obtains by 
adjoining a root of unity to the rational numbers. (It will be observed that MUB vectors 
have all their overlaps in a cyclotomic field.) 
field!cyclotomic
Kronecker's Jugendtraum was to 
extend this result to much more general ground fields. For instance, there are quadratic 
extensions of the rationals such as Q(√(5)), consisting of all numbers 
of the form x_1 + x_2√(5), where x_1,x_2 are rational numbers. More generally 
one can replace the square root of two with the square root of any integer. If that integer 
is negative the extension is an imaginary quadratic extension, otherwise it is a real 
quadratic extension. 

For the case of abelian extensions of an imaginary quadratic extension 
of ℚ Kronecker's dream led to brilliant successes, with deep connections to—among 
other things—the theory of elliptic curves. Such numbers turn up for special choices of the 
arguments of elliptic and modular functions, much as the numbers in a cyclotomic field turn 
up when the function e^iπ x is evaluated at rational values of x.  
As the 12th on his famous list of problems for 
the twentieth century, Hilbert asked for the restriction to imaginary quadratic fields 
to be removed.
(For an engaging account of this piece of history see 
the book by Gray <cit.>). The natural first step in solving the 12th 
problem would seem to be to find a framework for the abelian extensions 
of the real quadratic fields. This remains unsolved, but it seems to be in these deep waters that the SICs are swimming. 

 *  *  *     


This chapter may have left the reader a little bewildered, and appalled by equations 
like (<ref>). In defence of the chapter, we observe that practical applications 
(to signal processing, adaptive radar, and more) lie close to it. But the last word goes 
to Hilbert <cit.>:  

There still lies an abundance of priceless treasures hidden in this domain, belonging 
as a rich reward to the explorer who knows the value of such treasures and, with love, 
pursues the art to win them. 





§ CONCLUDING REMARKS





The aim of these notes is literally to present
a concise introduction to the broad subject of
discrete structures in a finite Hilbert space.
We are convinced that such a knowledge is useful 
while investigating numerous problems motivated by 
the theory of quantum information processing.
Even for small dimensions of the Hilbert space
several intriguing questions remain open,
so we are pleased to encourage the 
reader to contribute to this challenging field.



We are indebted to  Marcus Appleby, 
Dardo Goyeneche, Marcus Grassl,
David Gross and Huangjun Zhu, for reading some fragments 
of the text and providing us with valuable remarks. 









Financial support by Narodowe Centrum Nauki 
under the grant number DEC-2015/18/A/ST2/00274
is gratefully acknowledged.






§ CONTENTS OF THE II EDITION OF THE BOOK "GEOMETRY OF QUANTUM STATES. 
         AN INTRODUCTION TO QUANTUM ENTANGLEMENT"
         BY I. BENGTSSON AND K. ŻYCZKOWSKI




 1 Convexity, colours and statistics 
 
  1.1 Convex sets                                

  1.2 High dimensional geometry

  1.3 Colour theory

  1.4 What is “distance”? 

  1.5 Probability and statistics

2  Geometry of probability distributions  

  2.1 Majorization and partial order

  2.2 Shannon entropy

  2.3 Relative entropy

   2.4 Continuous distributions and measures

  2.5 Statistical geometry and the Fisher–Rao metric

   2.6 Classical ensembles

  2.7 Generalized entropies


 3 Much ado about spheres
 
  3.1 Spheres

  3.2 Parallel transport and statistical geometry

   3.3 Complex, Hermitian, and Kähler manifolds

  3.4 Symplectic manifolds

  3.5 The Hopf fibration of the 3-sphere

  3.6 Fibre bundles and their connections

  3.7 The 3-sphere as a group

  3.8 Cosets and all that

 4  Complex projective spaces

  4.1 From art to mathematics

  4.2 Complex projective geometry

  4.3 Complex curves, quadrics and the Segre embedding

  4.4 Stars, spinors, and complex curves

  4.5 The Fubini-Study metric

  4.6 ℂ P^n illustrated

  4.7 Symplectic geometry and the Fubini–Study measure

  4.8 Fibre bundle aspects

  4.9 Grassmannians and flag manifolds

  

 5 Outline of quantum mechanics

   5.1 Quantum mechanics

   5.2 Qubits and Bloch spheres

   5.3 The statistical and the Fubini-Study distances

   5.4 A real look at quantum dynamics

   5.5 Time reversals

   5.6 Classical & quantum states: a unified approach

   5.7 Gleason and Kochen-Specker 


 6 Coherent states and group actions 

   6.1 Canonical coherent states

   6.2 Quasi-probability distributions on the plane

   6.3 Bloch coherent states

   6.4 From complex curves to SU(K) coherent states

   6.5 SU(3) coherent states

 7 The stellar representation

   7.1 The stellar representation in quantum mechanics

   7.2 Orbits and coherent states

   7.3 The Husimi function

   7.4 Wehrl entropy and the Lieb conjecture

   7.5 Generalised Wehrl entropies

   7.6 Random pure states

   7.7 From the transport problem to the Monge distance


 8 The space of density matrices

   8.1 Hilbert–Schmidt space and positive operators

   8.2 The set of mixed states

   8.3 Unitary transformations

   8.4 The space of density matrices as a convex set

  8.5 Stratification

  8.6 Projections and cross–sections 

   8.7 An algebraic afterthought

   8.8 Summary

 9 Purification of mixed quantum states

   9.1 Tensor products and state reduction

  9.2 The Schmidt decomposition

  9.3 State purification & the Hilbert-Schmidt bundle

  9.4 A first look at the Bures metric

   9.5 Bures geometry for N=2

   9.6 Further properties of the Bures metric

 10 Quantum operations 

   10.1 Measurements and POVMs

   10.2 Algebraic detour: matrix reshaping and reshuffling

   10.3 Positive and completely positive maps

  10.4 Environmental representations

  10.5 Some spectral properties

  10.6 Unital & bistochastic maps

  10.7 One qubit maps

 11 Duality: maps versus states

   11.1 Positive & decomposable maps

  11.2 Dual cones and super-positive maps

   11.3 Jamiołkowski isomorphism

   11.4 Quantum maps and quantum states


 12  Discrete structures in Hilbert space 

  12.1  Unitary operator bases and the Heisenberg groups

  12.2 Prime, composite, and prime power dimensions

  12.3  More unitary operator bases 

  12.4 Mutually unbiased bases

  12.5 Finite geometries and discrete Wigner functions

  12.6 Clifford groups and stabilizer states

  12.7 Some designs

  12.8 SICs


13  Density matrices and entropies 

   13.1 Ordering operators

   13.2 Von Neumann entropy

  13.3 Quantum relative entropy

  13.4 Other entropies

   13.5 Majorization of density matrices

  13.6 Proof of the Lieb conjecture

  13.7 Entropy dynamics

 14 Distinguishability measures

  14.1 Classical distinguishability measures

  14.2 Quantum distinguishability measures

  14.3 Fidelity and statistical distance

 15 Monotone metrics and measures

  15.1 Monotone metrics

  15.2 Product measures and flag manifolds

   15.3 Hilbert-Schmidt measure

   15.4 Bures measure

   15.5 Induced measures

   15.6 Random density matrices

  15.7 Random operations

  15.8 Concentration of measure


 16 Quantum entanglement

   16.1 Introducing entanglement

   16.2 Two qubit pure states: entanglement illustrated

   16.3 Maximally entangled states

   16.4 Pure states of a bipartite system

  16.5 A first look at entangled mixed states 

  16.6 Separability criteria

  16.7 Geometry of the set of separable states

   16.8 Entanglement measures

   16.9 Two qubit mixed states 


17 Multipartite entanglement

   17.1 How much is three larger than two? 

   17.2 Botany of states

  17.3 Permutation symmetric states

  17.4 Invariant theory and quantum states 

  17.5 Monogamy relations and global multipartite entanglement

  17.6 Local spectra and the momentum map

  17.7 AME states and error–correcting codes 

  17.8 Entanglement in quantum spin systems

Epilogue 

  Appendix 1 Basic notions of differential geometry 

  Appendix 2 Basic notions of group theory 

  Appendix 3  Geometry do it yourself 

  Appendix 4  Hints and answers to the exercises
 







References

AW04
S. Alaca and K. S. Williams.
Introductory Algebraic Number Theory.
Cambridge UP, 2004.

Al80
W. O. Alltop.
Complex sequences with low periodic correlations.
IEEE Trans. Inform. Theory., 26:350, 1980.

ABBD15
D. Andersson, I. Bengtsson, K. Blanchfield, and H. B. Dang.
States that are far from being stabilizer states.
J. Phys., A 48:345301, 2015.

AB15
O. Andersson and I. Bengtsson.
Clifford tori and unbiased vectors.
preprint arXiv:1506.09062.

App09
D. M. Appleby.
Properties of the extended Clifford group with applications to
  SIC-POVMs and MUBs.
preprint arXiv:0909.5233.

App05
D. M. Appleby.
Symmetric informationally complete-positive operator measures and the
  extended Clifford group.
J. Math. Phys., 46:052107, 2005.

ADF14
D. M. Appleby, H. B. Dang, and C. A. Fuchs.
Symmetric informationally-complete quantum states as analogues to
  orthonormal bases and minimum-uncertainty states.
Entropy, 16:1484, 2014.

AFMY16
D. M. Appleby, S. Flammia, G. McConnell, and J. Yard.
Generating ray class fields of real quadratic fields via complex
  equiangular lines.
preprint arXiv:1604.06098.

AYZ13
D. M. Appleby, H. Yadsan-Appleby, and G. Zauner.
Galois automorphisms of a symmetric measurement.
Quant. Inf. Comp., 13:672, 2013.

Ar00
V. I. Arnold.
Symplectic geometry and topology.
J. Math. Phys., 41:3307, 2000.

Arn11
V. I. Arnold.
Dynamics, Statistics, and Projective Geometry of Galois
  Fields.
Cambridge University Press, 2011.

Asc07
M. Aschbacher, A. M. Childs, and P. Wocjan.
The limitations of nice mutually unbiased bases.
J. Algebr. Comb., 25:111, 2007.

BBRV02
S. Bandyopadhyay, P. O. Boykin, V. Roychowdhury, and F. Vatan.
A new proof for the existence of mutually unbiased bases.
Algorithmica, 34:512, 2002.

Bel08
A. Belovs.
Welch bounds and quantum state tomography.
MSc thesis, Univ. Waterloo, 2008.


BZ06
I. Bengtsson and K. Życzkowski.
Geometry of Quantum States. An Introduction to Quantum  Entanglement.
Cambridge University Press, 2006. Second Edition, CUP, 2017.


BZ16
I. Bengtsson and K. Życzkowski.
A brief introduction to multipartite entanglement.
preprint arXiv:1612.07747.



BB84
C. H. Bennett and G. Brassard.
Quantum cryptography: public key distribution and coin tossing.
In Int. Conf. on Computers, Systems and Signal
  Processing, Bangalore, page 175. IEEE, 1984.

Ben95
M. K. Bennett.
Affine and Projective Geometry.
Wiley, 1995.

Bl14
K. Blanchfield.
Orbits of mutually unbiased bases.
J. Phys., 47:135303, 2014.

BRW60
B. Bolt, T. G. Room, and G. E. Wall.
On the Clifford collineation, transform and similarity groups I.
J. Austral. Math. Soc., 2:60, 1960.

BoZh15
A. Bondal and I. Zhdanovskiy.
Orthogonal pairs and mutually unbiased bases.
preprint arXiv:1510.05317.

Boy10
L. Boyle.
Perfect porcupines: ideal networks for low frequency gravitational
  wave astronomy.
preprint arXiv:1003.4946.

BrW08
S. Brierley and S. Weigert.
Maximal sets of mutually unbiased quantum states in dimension six.
Phys. Rev., A 78:042312, 2008.

CCKS97
A. R. Calderbank, P. J. Cameron, W. M. Kantor, and J. J. Seidel.
Z_4-Kerdock codes, orthogonal spreads, and extremal Euclidean
  line sets.
Proc. London Math. Soc., 75:436, 1997.

CBKG02
N. J. Cerf, M. Bourennane, A. Karlsson, and N. Gisin.
Security of quantum key distribution using d-level systems.
Phys. Rev. Lett., 88:127902, 2002.

Cha05
H. F. Chau.
Unconditionally secure key distribution in higher dimensions by
  depolarization.
IEEE Trans. Inf. Theory, 51:1451, 2005.

Dan05
C. Dankert.
Efficient Simulation of Random Quantum States and Operators.
MSc thesis, Univ. Waterloo, 2005.

DiVLeTe02
D. DiVincenzo, D. W. Leung, and B. Terhal.
Quantum data hiding.
IEEE Trans. Inf. Theory, 48:580, 2002.

EA01
B.-G. Englert and Y. Aharonov.
The mean king's problem: Prime degrees of freedom.
Phys. Lett., 284:1, 2001.

Fis35
R. A. Fisher.
The Design of Experiments.
Oliver and Boyd, 1935.

FuSc13
C. A. Fuchs and R. Schack.
Quantum-Bayesian coherence.
Rev. Mod. Phys., 85:1693, 2013.

GoRo09
C. Godsil and A. Roy.
Equiangular lines, mutually unbiased bases, and spin models.
Eur. J. Comb., 30:246, 2009.

Go97
D. Gottesman.
Stabilizer Codes and Quantum Error Correction.
PhD thesis, California Institute of Technology, 1997.

Gr04
M. Grassl.
On SIC-POVMs and MUBs in dimension 6.
preprint quant-ph/040675.

Gray00
J. Gray.
The Hilbert Challenge.
Oxford UP, 2000.

Gro06
D. Gross.
Hudson's theorem for finite-dimensional quantum systems.
J. Math. Phys., 47:122107, 2006.

GrAuEi07
D. Gross, K. Audenaert, and J. Eisert.
Evenly distributed unitaries: on the structure of unitary designs.
J. Math. Phys., 48:052104, 2007.

Had93
J. Hadamard.
Résolution d'une question relative aux déterminants.
Bull. Sci. Math., 17:240, 1893.

HaSl96
R. H. Hardin and N. J. A. Sloane.
McLaren's improved snub cube and other new spherical designs in
  three dimensions.
Discrete Comput. Geom., 15:429, 1996.

Hog82
S. G. Hoggar.
t-designs in projective spaces.
Europ. J. Combin., 3:233, 1982.

Hog98
S. G. Hoggar.
64 lines from a quaternionic polytope.
Geometriae Dedicata, 69:287, 1998.

Hor07
K. J. Horadam.
Hadamard Matrices and Their Applications.
Princeton University Press, 2007.

HCM06
S. D. Howard, A. R. Calderbank, and W. Moran.
The finite Heisenberg-Weyl groups in radar and communications.
EURASIP J. Appl. Sig. Process., 2006:85865, 2006.

Ho06
J. M. Howie.
Fields and Galois Theory.
Springer, 2006.

HuSa15
L. P. Hughston and S. M. Salamon.
Surverying points on the complex projective plane.
Adv. Math., 286:1017, 2016.

Iv81
I. D. Ivanović.
Geometrical description of quantal state determination.
J. Phys., A 14:3241, 1981.

JMMSW09
P. Jaming, M. Matolsci, P. Móra, F. Szöllősi, and M. Weiner.
A generalized Pauli problem an infinite family of
  MUB-triplets in dimension 6.
J. Phys., A 42:245305, 2009.

Kan12
W. K. Kantor.
MUBs inequivalence and affine planes.
J. Math. Phys., 53:032204, 2012.

Kar11
B. R. Karlsson.
Three-parameter complex Hadamard matrices of order 6.
Linear Alg. Appl., 434:247, 2011.

Kh08
M. Khatirinejad.
On Weyl–Heisenberg orbits of equiangular lines.
J. Algebra. Comb., 28:333, 2008.

Kla02
A. Klappenecker and M. Rötteler.
Beyond stabilizer codes I: Nice error bases.
IEEE Trans. Inform. Theory, 48:2392, 2002.

KlaRoe04
A. Klappenecker and M. Rötteler.
Constructions of mutually unbiased bases.
Lect. Not. Computer Science, 2948:137, 2004.

KlaRoe05
A. Klappenecker and M. Rötteler.
Mutually Unbiased Bases are complex projective 2–designs.
In Proc ISIT, page 1740. Adelaide, 2005.

Kla05
A. Klappenecker and M. Rötteler.
On the monomiality of nice error bases.
IEEE Trans. Inform. Theory, 51:1084, 2005.

KRBSS09
A. Klimov, J. L. Romero, G. Björk, and L. L. Sanchez-Soto.
Discrete phase space structure of n-qubit mutually unbiased bases.
Ann. Phys., 324:53, 2009.

Kni96
E. Knill.
Group representations, error bases and quantum codes.
preprint quant-ph/9608049.

KT94
A. I. Kostrikin and P. I. Tiep.
Orthogonal Decompositions and Integral Lattices.
de Gruyter, 1994.

KuGr15
R. Kueng and D. Gross.
Qubit stabilizer states are complex projective 3-designs.
preprint arXiv:1510.02767.

Lai12
A. Laing, T. Lawson, E. M. López, and J. L. O'Brien.
Observation of quantum interference as a function of Berry's phase
  in a complex Hadamard network.
Phys. Rev. Lett., 108:260505, 2012.

Lam91
C. W. H. Lam.
The search for a finite projective plane of order 10.
Amer. Math. Mon., 98:305, 1991.

LeSe73
P. W. H. Lemmens and J. J. Seidel.
Equiangular lines.
J. Algebra, 24:494, 1973.

Ma21
H. F. MacNeish.
Euler squares.
Ann. Math., 23:221, 1921.

Ma12
M. Matolcsi.
A Fourier analytic approach to the problem of unbiased bases.
Studia Sci. Math. Hungarica, 49:482, 2012.

Mum83
D. Mumford.
Tata Lectures on Theta.
Birkhäuser, Boston, 1983.

MV15
B. Musto and J. Vicary.
Quantum Latin squares and unitary error bases.
preprint arXiv:1504.02715.

Neu02
M. Neuhauser.
An explicit construction of the metaplectic representation over a
  finite field.
Journal of Lie Theory, 12:15, 2002.

Pal33
R. E. A. C. Paley.
On orthogonal matrices.
J. Math.and Phys., 12:311, 1933.

PPGB10
T. Paterek, M. Pawłowski, M. Grassl, and Č. Brukner.
On the connection between mutually unbiased bases and orthogonal
  Latin squares.
Phys. Scr., T140:014031, 2010.

Pl82
V. Pless.
Introduction to the Theory of Error–Correcting Codes.
Wiley, 1982.

RLE11
P. Raynal, X. Lü, and B.-G. Englert.
Mutually unbiased bases in dimension 6: The four most distant
  bases.
Phys. Rev., A 83:062303, 2011.

Re70
C. Reid.
Hilbert.
Springer, 1970.

ReWe07
M. Reimpell and R. F. Werner.
A meaner king uses biased bases.
Phys. Rev., A 75:062334, 2008.

RBSC04
J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves.
Symmetric informationally complete quantum measurements.
J. Math. Phys., 45:2171, 2004.

RS09
A. Roy and A. J. Scott.
Unitary designs and codes.
Des. Codes Cryptogr., 53:13, 2009.

Schw60
J. Schwinger.
Unitary operator bases.
Proc. Natl. Acad. Sci., 46:570, 1960.

Schw03
J. Schwinger.
Quantum Mechanics—Symbolism of Atomic Measurements.
Springer, 2003.

Sco06
A. J. Scott.
Tight informationally complete measurements.
J. Phys., A 39:13507, 2006.

ScGr10
A. J. Scott and M. Grassl.
SIC-POVMs: A new computer study.
J. Math. Phys., 51:042203, 2010.

Se86
C. Segre.
Remarques sur les transformations uniformes des courbes elliptiques
  en elles-mèmes.
Math. Ann, 27:296, 1886.

SeZa84
P. D. Seymour and T. Zaslawsky.
Averaging sets: a generalization of mean values and spherical
  designs.
Adv. Math., 52:213, 1984.

SHBAH12
C. Spengler, M. Huber, S. Brierley, T. Adaktylos, and B. C. Hiesmayr.
Entanglement detection via mutually unbiased bases.
Phys. Rev., A 86:022311, 2012.

Sti04
D. R. Stinson.
Combinatorial Designs: Constructions and Analysis.
Springer, 2004.

STDH07
M. A. Sustik, J. Tropp, I. S. Dhillon, and R. W. Heath.
On the existence of equiangular tight frames.
Lin. Alg. Appl., 426:619, 2007.

Syl82
J. J. Sylvester.
A word on nonions.
John Hopkins Univ. Circulars., 1:1, 1882.

Szo11
F. Szöllősi.
Construction, classification and parametrization of complex
  Hadamard matrices.
PhD thesis, CEU, Budapest, 2011.

Szo12
F. Szöllősi.
Complex Hadamard matrices of order 6: a four-parameter family.
J. London Math. Soc., 85:616, 2012.

TaZ06
W. Tadej and K. Życzkowski.
A concise guide to complex Hadamard matrices.
Open Sys. Inf. Dyn., 13:133, 2006.

Vou04
A. Vourdas.
Quantum systems with finite Hilbert space.
Rep. Prog. Phys., 67:267, 2004.

Web15
Z. Webb.
The Clifford group forms a unitary 3-design.
preprint arXiv:1510.02769.

WD10
S. Weigert and T. Durt.
Affine constellations without mutually unbiased counterparts.
J. Phys., A43:402002, 2010.

We13
M. Weiner.
A gap for the maximum number of mutually unbiased bases.
Proc. Amer. Math. Soc., 141:1963, 2013.

Wel74
L. R. Welch.
Lower bounds on the maximum cross correlation of signals.
IEEE Trans. Inf. Theory., 20:397, 1974.

Wer01
R. F. Werner.
All teleportation and dense coding schemes.
J. Phys., A 34:7081, 2001.

Wey32
H. Weyl.
Group Theory and Quantum Mechanics.
E. P. Dutton, New York, 1932.

WoBe05
P. Wocjan and T. Beth.
New construction of mutually unbiased bases in square dimensions.
Quantum Inf. Comp., 5:93, 2005.

Wo87
W. K. Wootters.
A Wigner function formulation of finite-state quantum mechanics.
Ann. Phys. (N.Y.), 176:1, 1987.

WF89
W. K. Wootters and B. F. Fields.
Optimal state determination by mutually unbiased measurements.
Ann. Phys. (N.Y.), 191:363, 1989.

Zau99
G. Zauner.
Quantendesigns.
PhD thesis, Univ. Wien, 1999.

Zhu15
H. Zhu.
Multiqubit Clifford groups are unitary 3–designs.
preprint arXiv:1510.02619.

Zhu10
H. Zhu.
SIC-POVMs and Clifford groups in prime dimensions.
J. Phys., A 43:305305, 2010.

Zh15
H. Zhu.
Mutually unbiased bases as minimal Clifford covariant 2–designs.
Phys. Rev., A 91:060301, 2015.

Zh16
H. Zhu.
Permutation symmetry determines the discrete Wigner function.
Phys. Rev. Lett., 116:040501, 2016.






