We clarify the mathematical structure underlying unitary $t$-designs. These are sets of unitary matrices, evenly distributed in the sense that the average of any $t$-th order polynomial over the design equals the average over the entire unitary group. We present a simple necessary and sufficient criterion for deciding if a set of matrices constitutes a design. Lower bounds for the number of elements of 2-designs are derived. We show how to turn mutually unbiased bases into approximate 2-designs whose cardinality is optimal in leading order. Designs of higher order are discussed and an example of a unitary 5-design is presented. We comment on the relation between unitary and spherical designs and outline methods for finding designs numerically or by searching character tables of finite groups. Further, we sketch connections to problems in linear optics and questions regarding typical entanglement.

Author comments: 15 pages, one figure. Minor revisions to mirror version to appear in J. Math. PhysJournal ref: J. Math. Phys. 48, 052104 (2007)

Doi: 10.1063/1.2716992

http://arxiv.org/abs/quant-ph/0611002

http://arxiv.org/pdf/quant-ph/0611002.pdf

The following observation resolves in the affirmative a decade-old open conjecture from this paper, except for $d=3$.

The Conjecture asks if any unitary 2-design must have cardinality at least $d^4 - d^2$, a value which is achievable by a Clifford group. This is true for any group unitary 2-design as follows. The cardinality of the group design has to be divisible by $d$, because a 2-design is also a 1-design, hence an irrep, and the order of the irrep has to divide the order of the group. Also $d(d\pm1)/2$ must divide the cardinality because the symmetric and antisymmetric reps must also be irreps to be a 2-design (by Theorem 6). The lcm $L$ of those must also be a divisor and is $d^3-d$ if $d$ is even and $\frac{d^3-d}{4}$ if $d$ is odd. The existing lower bound (Theorem 5) of $d^4-2d^2+2$ can be strengthened to the next greatest integer divisible by $L$, or equivalently, the least integer $k$ for which

$$ kL \ge d^4-2d^2+2. \qquad (1) $$

For the even case, it is easy to check that $k=d-1$ never yields solutions to (1), but $k=d$ is always a solution and yields the required bound. For the odd case, $k=4d-1$ only yields a solution to (1) for $d=3$ and $k=4d$ is always a solution and gives the desired bound. QED.

Although this resolves the conjecture for group 2-designs in dimensions $d\not=3$, it leaves open the possibility of exact 2-designs without any group symmetry that might have a slightly smaller cardinality.

Edited Dec 18 2017 20:54 UTC by Steve Flammia

Neat!

whoa, awesome! But why do you get that $d^3-d$ must be a divisor instead of $(d^3-d)/2$?

It splits into even and odd cases, actually. I was originally sloppy about the distinction between integer and polynomial division, but it's fixed now. There is a little room left in the case $d=3$ now though, but it's still proven in every other dimension.

Nice observation, Steve! :-)