Mutually unbiased bases

Cite this problem as Problem 13.


Determine the maximal number k of orthonormal bases in a d-dimensional Hilbert space, which are mutually unbiased in the following sense: If e_{ik} denotes the ith vector of the kth basis, all scalar products \langle e_{ik},e_{jn}\rangle with k\neq n have the same absolute value (namely d^{-1/2}).

It is known that if d is the power of a prime, k=d+1 can be achieved, but this is not known for any other composite number. So the problem is already to decide whether there exist k=7 mutually unbiased bases in d=6 dimensions (up to now only a set of three MUBs is known).


The problem comes up in at least three (related) contexts:

(1) State determination [1][2]

Suppose we want to determine the density operator of a source by measuring k observables (with d one-dimensional projections each). Each such measurement allows us to determine d-1 independent parameters, so we can determine k(d-1) out of d^2-1 parameters in the density operator. Hence k=d+1 should suffice. In order to achieve best estimation results, the measurements should duplicate no information already contained in other measurements, i. e., the observables should be pairwise complementary, or the bases mutually unbiased in the above sense.

(2) Cryptography

Suppose Alice sends a d-level systems prepared in one of the d pure states e_{ik} belonging to a set of k orthonormal bases agreed between Alice and Bob. If Bob measures in the same basis, he can decode the value i perfectly. In cryptography one also wants that if an eavesdropper measures the system in any one of the other bases, she can extract no information whatsoever about i. This requires the bases to be mutually unbiased.<br/> It is known that a higher error level can be tolerated in the channel for protocols using maximal families of mutually unbiased bases (e. g., the “six state protocol”, D=2, K=3) rather than non-maximal ones (e. g., BB84, using D=2, K=2).

(3) The Mean King [3]

A ship-wrecked physicist gets stranded on a far-away island that is ruled by a mean king who loves cats and hates physicists since the day when he first heard what happened to Schrödinger’s cat. A similar fate is awaiting the stranded physicist. Yet, mean as he is, the king enjoys defeating physicists on their own turf, and therefore he maliciously offers an apparently virtual chance of rescue. He takes the physicist to the royal laboratory, a splendid place where experiments of any kind can be performed perfectly. There the king invites the physicist to prepare a certain silver atom in any state she likes. The king’s men will then measure one of the three cartesian spin components of this atom – they’ll either measure \sigma_x, \sigma_y, or \sigma_z without, however, telling the physicist which one of the measurements is actually done. Then it is again the physicist’s turn, and she can perform any experiment of her choosing. Only after she’s finished with it, the king will tell her which spin component had been measured by his men. To save her neck, the physicist must then state correctly the measurement result that the king’s men had obtained. Much to the king’s frustration, the physicist rises to the challenge – and not just by sheer luck: She gets the right answer any time the whole procedure is repeated. How does she do it?  More generally, the king’s men might be allowed to perform one out of k complete von Neumann measurements on a d-dimensional system. This is also known as the “Meaner King Problem”, which is the topic of [4]. The problem first came up in [5], together with a solution for d=2. Solutions involving mutually unbiased bases are presented in [3] [6] [7] [8]. The solutions can used to generate a secret key shared by Alice and the King, if they choose to cooperate [9]. Confer also the experimental realization in [10].

Partial Results

  • Barnum [11] points out a close connection of this problem with “spherical 2-designs, which are collections of pure states such that the average of a polynomial of degree 2 on these states equals the integral of the polynomial over all pure states.
  • For the case d=6 there are a number of different but equivalent formulations of this problem, but until today no approach is known, which leads to more than three MUBs.
  • Pittenger and M. Rubin [12] give a constructive proof for the case of prime power dimension [2]. They also adress the question of separabilty and provide an appendix on the necessary parts of algebraic field extensions. Another proof can be found in [13].
  • Archer [14] shows that even generalizations of these constructions do not extend the results beyond prime power dimension.
  • M.Weiner gives in [15] a proof, that if a collection of d MUBs is found, one can always construct the complete collection.
  • The close connection between the number of non-equivalent Hadamard matrices and the number of MUBs is shown in an extensive recent review [16]. This review also includes construction of MUBs in a prime power dimension and deals with the corresponding Bell states.


[1] I. D. Ivanovic, »Geometrical description of quantal state determination«, J. Phys. A 14, 3241 (1981).

[2] W.K. Wootters, B.D. Fields, »Optimal state-determination by mutually unbiased measurements«, Ann. Phys. 191, 363 (1989).

[3] Y. Aharonov, B.-G. Englert, »The mean king’s problem: Spin 1«, Z. Naturforsch. 56a, 16 (2001) and quant-ph/0101065 (2001).

[4] M.Reimpell, R.F.Werner, »A Meaner King uses Biased Basess«, Phys. Rev. A 75, 062334 , quant-ph/0612035 (2006).

[5] L. Vaidman, Y. Aharonov, and D. Z. Albert, »How to ascertain the values of σx, σy and σz of a spin-1/2 particle«, Phys. Rev. Lett. 58, 1385 (1987).

[6] P.K. Aravind, »Solution to the King’s Problem in prime power dimensions«, Z. Naturforsch. 58a, 2212 (2003) and quant-ph/0210007 (2002).

[7] P.K. Aravind, »Best conventional solutions to the King’s Problem«, quant-ph/0306119 (2003).

[8] B.-G. Englert, Y. Aharonov, »The mean king’s problem: Prime degrees of freedom«, Phys. Lett. A 284, 1 (2001) and quant-ph/0101134 (2001).

[9] A.H. Werner, T.Franz, R.F. Werner, »Quantum cryptography as a retrodiction problem «,Phys. Rev. Lett. 103, 220504 , quant-ph/0909.3375 (2009).

[10] O. Schulz, R. Steinhübl, M. Weber, B.-G. Englert, C. Kurtsiefer, H. Weinfurter, »Ascertaining the Values of σx, σy and σz of a Polarization Qubit«, quant-ph/0209127 (2002).

[11] H. Barnum, »Information-disturbance tradeoff in quantum measurement on the uniform ensemble and on the mutually unbiased bases«, quant-ph/0205155 (2002).

[12] A. O. Pittenger and M. H. Rubin, »Mutually unbiased bases, generalized spin matrices and separability«, quant-ph/0308142 (2003).

[13] A. Klappenecker, M. Roetteler, »Constructions of Mutually Unbiased Bases«, quant-ph/0309120 (2003).

[14] C. Archer, »There is no generalization of known formulas for mutually unbiased bases«, quant-ph/0312204 (2003).

[15] M. Weiner, »A gap for the maximum number of mutually unbiased bases «,arXiv:0902.0635v1 (2009).

[16] T. Durt, B.G. Englert, I. Bengtsson, K. Zyczkowski, »On mutually unbiased bases «, quant-ph/1004.3348 (2010).