Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Mutually Unbiased Bases

Maximally complementary measurements and where they come from.

Know a qubit's spin along zz perfectly and you know nothing about it along xx. Mutually unbiased bases make that complementarity exact in every dimension, and whether a complete set of them exists in dimension six is one of the most stubborn open problems in quantum information.

What you’ll learn

  • Define mutually unbiased bases (MUBs) and interpret unbiasedness operationally.
  • Prove that at most d+1d+1 MUBs exist in Cd\C^d.
  • Construct complete sets of MUBs in odd prime dimensions with quadratic Gauss sums, and for qubits by partitioning the Pauli operators.
  • Derive the MUB tomography formula ρ=∑k,jpkj∣ejk⟩ ⁣⟨ejk∣−I\rho = \sum_{k,j}p_{kj}\dyad{e^k_j} - \id and the identity ∑k,jpkj2=1+Tr⁡ρ2\sum_{k,j}p_{kj}^2 = 1+\Tr\rho^2.
  • Describe the open existence problem in dimensions that are not prime powers, starting with d=6d = 6.

Unbiasedness

Operationally: prepare any vector of one basis, measure in the other, and every outcome is equally likely. Perfect knowledge of one measurement's outcome means total ignorance of the other's.

For a qubit, ∣⟨n^∣m^⟩∣2=12(1+n^⋅m^)\abs{\braket{\hat n|\hat m}}^2 = \tfrac12(1+\hat n\cdot\hat m), which equals 12\tfrac12 exactly when the two Bloch axes are perpendicular. The ZZ, XX and YY eigenbases are therefore mutually unbiased, and there can be no fourth, because R3\R^3 has only three mutually orthogonal axes.

In any dimension the Fourier basis is unbiased to the computational basis: ∣⟨j∣F∣k⟩∣2=∣ωjk/d∣2=1/d\abs{\bra{j}F\ket{k}}^2 = \abs{\omega^{jk}/\sqrt d}^2 = 1/d. More generally, a basis is unbiased to the computational basis exactly when the unitary whose columns are its vectors has all entries of modulus 1/d1/\sqrt d: a rescaled complex Hadamard matrix.

At most d + 1 bases

DerivationProof by counting dimensions
  1. ∣e⟩  ⟼  Qe:=∣e⟩ ⁣⟨e∣−1dI  ∈  Td,dim⁡RTd=d2−1\ket{e}\;\longmapsto\; Q_e := \dyad{e} - \tfrac1d\id \;\in\; \mathfrak{T}_d, \qquad \dim_\R\mathfrak{T}_d = d^2-1

    Map each basis vector to a traceless Hermitian operator. Td\mathfrak T_d is the real vector space of traceless Hermitian d×dd\times d matrices, with the Hilbert–Schmidt inner product Tr⁡(XY)\Tr(XY).

  2. Tr⁡(QejQek)=δjk−1d,∑jQej=0\Tr\big(Q_{e_j}Q_{e_k}\big) = \delta_{jk} - \tfrac1d, \qquad \sum_j Q_{e_j} = 0

    Within one basis the Gram matrix I−J/d\id - J/d (JJ the all-ones matrix) has rank d−1d-1, so the dd operators span a (d−1)(d-1)-dimensional subspace.

  3. Tr⁡(QeQf)=∣⟨e∣f⟩∣2−1d=0\Tr\big(Q_eQ_f\big) = \abs{\braket{e|f}}^2 - \tfrac1d = 0

    For vectors from two different bases, unbiasedness is exactly Hilbert–Schmidt orthogonality.

  4. m(d−1)  ≤  d2−1  ⟹  m  ≤  d+1■m(d-1) \;\le\; d^2 - 1 \;\Longrightarrow\; m \;\le\; d+1 \qquad\blacksquare

    mm MUBs give mm mutually orthogonal (d−1)(d-1)-dimensional subspaces of a (d2−1)(d^2-1)-dimensional space.

A complete set, with m=d+1m = d+1, therefore splits the traceless operators into orthogonal pieces, one per basis. That is exactly what makes complete sets ideal for tomography, as you will see in a moment.

Constructions

Ivanović (1981) first constructed complete sets in prime dimensions. In the now-standard quadratic-phase form: for an odd prime pp, let ω=e2πi/p\omega = e^{2\pi i/p} and take the computational basis together with the pp bases a∈Zpa \in \Z_p made of the vectors

∣ψb(a)⟩=1p∑j=0p−1ω aj2+bj∣j⟩,b∈Zp\ket{\psi^{(a)}_b} = \frac{1}{\sqrt p}\sum_{j=0}^{p-1}\omega^{\,aj^2 + bj}\ket{j}, \qquad b\in\Z_p
Basis aa consists of ∣ψ0(a)⟩,…,∣ψp−1(a)⟩\ket{\psi^{(a)}_0},\dots,\ket{\psi^{(a)}_{p-1}}; the case a=0a = 0 is the Fourier basis.
DerivationWhy these bases are mutually unbiased
  1. ⟨ψb(a)∣ψb′(a′)⟩=1p∑j=0p−1ω(a′−a)j2+(b′−b)j\braket{\psi^{(a)}_b|\psi^{(a')}_{b'}} = \frac1p\sum_{j=0}^{p-1}\omega^{(a'-a)j^2 + (b'-b)j}

    Compute the overlap.

  2. Same aa, different bb: a full sum of pp-th roots of unity, which is 00. So each aa gives an orthonormal basis.

  3. ∣∑j=0p−1ωcj2+ej∣=p(c≢0)  ⟹  ∣⟨ψb(a)∣ψb′(a′)⟩∣2=1p\Big|\sum_{j=0}^{p-1}\omega^{cj^2 + ej}\Big| = \sqrt p \quad (c\not\equiv 0) \;\Longrightarrow\; \abs{\braket{\psi^{(a)}_b|\psi^{(a')}_{b'}}}^2 = \frac1p

    Different aa: complete the square, which is possible because 2c2c is invertible modulo an odd prime. The sum becomes a phase times a quadratic Gauss sum, whose modulus is p\sqrt p.

  4. Every ∣ψb(a)⟩\ket{\psi^{(a)}_b} has entries of modulus 1/p1/\sqrt p, so it is also unbiased to the computational basis. That makes p+1p + 1 MUBs: a complete set.

For prime powers d=pnd = p^n, replace Zp\Z_p by the finite field with pnp^n elements (Wootters & Fields 1989). For nn qubits there is an elegant stabilizer construction: partition the 4n−14^n-1 non-identity Pauli operators into 2n+12^n+1 classes of 2n−12^n-1 mutually commuting operators. The common eigenbases of the classes are mutually unbiased (Bandyopadhyay, Boykin, Roychowdhury & Vatan 2002).

ClassCommuting PaulisCommon eigenbasis
1ZI, IZ, ZZZI,\ IZ,\ ZZComputational (product)
2XI, IX, XXXI,\ IX,\ XX∣±⟩∣±⟩\ket{\pm}\ket{\pm} (product)
3YI, IY, YYYI,\ IY,\ YY∣±i⟩∣±i⟩\ket{\pm i}\ket{\pm i} (product)
4XZ, ZY, YXXZ,\ ZY,\ YXEntangled
5YZ, ZX, XYYZ,\ ZX,\ XYEntangled
A complete set of five MUBs for two qubits, writing XZXZ for X⊗ZX\otimes Z. Each of the (22+1)(22−1)=15(2^2+1)(2^2-1) = 15 non-identity Paulis appears exactly once. Classes 4 and 5 contain no single-qubit Pauli, so their eigenbases are entangled. Each product class uses up one single-qubit Pauli on each qubit, so a Pauli partition contains at most three product bases.

Tomography and 2-designs

DerivationReconstructing a state from a complete set of MUBs
  1. ρ−1dI=∑k=1d+1∑j=1dTr⁡(Qkj(ρ−1dI)) Qkj,Qkj=∣ejk⟩ ⁣⟨ejk∣−1dI\rho - \tfrac1d\id = \sum_{k=1}^{d+1}\sum_{j=1}^{d}\Tr\Big(Q_{kj}\big(\rho - \tfrac1d\id\big)\Big)\,Q_{kj}, \qquad Q_{kj} = \dyad{e^k_j} - \tfrac1d\id

    Within each basis the QQ's form a Parseval frame for their subspace (their Gram matrix I−J/d\id - J/d is a projector), and the d+1d+1 mutually orthogonal subspaces fill all of Td\mathfrak T_d. So this expansion is exact.

  2. ρ=∑k=1d+1∑j=1dpkj ∣ejk⟩ ⁣⟨ejk∣−I,pkj=⟨ejk∣ρ∣ejk⟩\rho = \sum_{k=1}^{d+1}\sum_{j=1}^{d} p_{kj}\,\dyad{e^k_j} - \id, \qquad p_{kj} = \bra{e^k_j}\rho\ket{e^k_j}

    Since Tr⁡(Qkj(ρ−I/d))=pkj−1/d\Tr\big(Q_{kj}(\rho - \id/d)\big) = p_{kj} - 1/d, collecting terms gives a linear inversion formula: measured probabilities in, density matrix out.

  3. ∑k,jpkj2=1+Tr⁡ρ2\sum_{k,j} p_{kj}^2 = 1 + \Tr\rho^2

    Take the Hilbert–Schmidt norm of the same expansion: ∥ρ−I/d∥22=Tr⁡ρ2−1d=∑k,j(pkj−1d)2\norm{\rho - \id/d}_2^2 = \Tr\rho^2 - \tfrac1d = \sum_{k,j}\big(p_{kj}-\tfrac1d\big)^2.

  4. For a qubit, ∣±k⟩ ⁣⟨±k∣=12(I±σk)\dyad{\pm_k} = \tfrac12(\id\pm\sigma_k) turns the formula into ρ=12(I+r⃗⋅σ⃗)\rho = \tfrac12(\id + \vec r\cdot\vec\sigma) with rk=pk,+−pk,−r_k = p_{k,+}-p_{k,-}, and the identity reads ∑k12(1+rk2)=12(3+∣r⃗∣2)=1+Tr⁡ρ2\sum_k\tfrac12(1+r_k^2) = \tfrac12(3+\abs{\vec r}^2) = 1 + \Tr\rho^2.

Check your understanding

A qubit gives pZ,0=0.9p_{Z,0} = 0.9, pX,+=0.5p_{X,+} = 0.5 and pY,+i=0.5p_{Y,+i} = 0.5. Using the identity above, what is its purity Tr⁡ρ2\Tr\rho^2?

  1. 0.640.64
  2. 0.820.82
  3. 0.90.9
  4. 11
Show the answer

B. 0.820.82

∑k,jpkj2=(0.81+0.01)+(0.25+0.25)+(0.25+0.25)=1.82\sum_{k,j}p_{kj}^2 = (0.81 + 0.01) + (0.25+0.25) + (0.25+0.25) = 1.82, so Tr⁡ρ2=0.82\Tr\rho^2 = 0.82. Check: r⃗=(0,0,0.8)\vec r = (0, 0, 0.8) and 12(1+0.64)=0.82\tfrac12(1 + 0.64) = 0.82.

Wootters and Fields showed that, among measurements in d+1d+1 orthonormal bases, mutually unbiased ones minimize the statistical error of this reconstruction in a natural averaged sense. The identity above is the fingerprint of a deeper fact: the d(d+1)d(d+1) vectors of a complete set form a complex projective 2-design, so averaging ∣e⟩ ⁣⟨e∣⊗2\dyad{e}^{\otimes 2} over them reproduces the uniform (Haar) average. Applying Jensen's inequality to −log⁡-\log of the identity also gives an entropic uncertainty relation for complete sets: for pure states, ∑kH(Bk)≥(d+1)log⁡2d+12\sum_k H(B_k) \ge (d+1)\log_2\tfrac{d+1}{2}.

Open problem: dimension six

Tensor products of complete sets show that Cd\C^d with d=p1n1⋯prnrd = p_1^{n_1}\cdots p_r^{n_r} contains at least min⁡ipini+1\min_i p_i^{n_i} + 1 MUBs, so every dimension has at least 3. Whether more exist when dd is not a prime power is unknown, even for d=6d=6, where only three are known. Extensive analytical and numerical searches suggest that no fourth exists, but there is no proof.

Dimension ddGuaranteed by tensor productsComplete set (d+1d+1 bases) known?
2, 3, 4, 5, 7, 8, 9d+1d+1Yes: prime powers
63Open; numerical evidence suggests not even a fourth basis exists
103Open
124Open

Key takeaways

  • Bases are mutually unbiased if ∣⟨ej∣fk⟩∣2=1/d\abs{\braket{e_j|f_k}}^2 = 1/d: a vector of one basis gives uniformly random outcomes in the other.
  • At most d+1d+1 MUBs exist, by dimension counting in the space of traceless Hermitian operators. Complete sets exist in every prime-power dimension (Gauss sums, finite fields, Pauli partitions).
  • A complete set gives exact linear tomography, ρ=∑k,jpkj∣ejk⟩ ⁣⟨ejk∣−I\rho = \sum_{k,j}p_{kj}\dyad{e^k_j} - \id, and forms a 2-design: ∑k,jpkj2=1+Tr⁡ρ2\sum_{k,j}p_{kj}^2 = 1 + \Tr\rho^2.
  • In other dimensions only min⁡ipini+1\min_i p_i^{n_i}+1 MUBs are guaranteed, and whether C6\C^6 has more than 3 is open.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What is the maximum number of mutually unbiased bases in C5\C^5?

  1. 44
  2. 55
  3. 66
  4. 2525
Show the answer

C. 66

The bound is d+1=6d+1 = 6, and since 5 is prime the Gauss-sum construction achieves it.

Question 2

Which pair of qubit bases is mutually unbiased?

  1. The ZZ basis and the YY basis
  2. The ZZ basis and the eigenbasis of the Hadamard gate
  3. The XX basis and the basis {∣−⟩,∣+⟩}\{\ket-,\ket+\}
  4. The ZZ basis and the eigenbasis of (Z+Y)/2(Z + Y)/\sqrt2
Show the answer

A. The ZZ basis and the YY basis

Mutually unbiased qubit bases correspond to perpendicular Bloch axes, and z^⊥y^\hat z \perp \hat y.

Question 3

In the proof of the d+1d+1 bound, what does mutual unbiasedness turn into?

  1. Linear independence of the basis vectors
  2. Commutation of the projectors
  3. Equality of the traces of the projectors
  4. Hilbert–Schmidt orthogonality of the traceless parts ∣e⟩ ⁣⟨e∣−I/d\dyad{e}-\id/d and ∣f⟩ ⁣⟨f∣−I/d\dyad{f}-\id/d
Show the answer

D. Hilbert–Schmidt orthogonality of the traceless parts ∣e⟩ ⁣⟨e∣−I/d\dyad{e}-\id/d and ∣f⟩ ⁣⟨f∣−I/d\dyad{f}-\id/d

Tr⁡((∣e⟩ ⁣⟨e∣−I/d)(∣f⟩ ⁣⟨f∣−I/d))=∣⟨e∣f⟩∣2−1/d\Tr\big((\dyad e-\id/d)(\dyad f - \id/d)\big) = \abs{\braket{e|f}}^2 - 1/d, which vanishes exactly for unbiased pairs. Each basis then occupies its own (d−1)(d-1)-dimensional slice of a (d2−1)(d^2-1)-dimensional space.

Question 4

What is known about mutually unbiased bases in C6\C^6?

  1. A complete set of 7 has been constructed
  2. Three are known; whether a fourth exists is open, and numerical evidence suggests it does not
  3. It has been proven that exactly 3 exist
  4. None exist, because 6 is not a prime power
Show the answer

B. Three are known; whether a fourth exists is open, and numerical evidence suggests it does not

The tensor-product construction gives min⁡(2,3)+1=3\min(2,3) + 1 = 3. Extensive searches have failed to find a fourth, but there is no proof.

Further reading

  • I. D. Ivanović, "Geometrical description of quantal state determination", Journal of Physics A 14 (1981).
  • W. K. Wootters & B. D. Fields, "Optimal state-determination by mutually unbiased measurements", Annals of Physics 191 (1989).
  • S. Bandyopadhyay, P. O. Boykin, V. Roychowdhury & F. Vatan, "A new proof for the existence of mutually unbiased bases", Algorithmica 34 (2002).
  • T. Durt, B.-G. Englert, I. Bengtsson & K. Życzkowski, "On mutually unbiased bases", International Journal of Quantum Information 8 (2010).