# Evenly distributed unitaries: on the structure of unitary designs

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.
Submitted 31 Oct 2006 to Quantum Physics [quant-ph]
Published 2 Nov 2006
Updated 13 May 2007
Author comments: 15 pages, one figure. Minor revisions to mirror version to appear in J. Math. Phys
Journal 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

Steve Flammia Dec 17 2017 20:25 UTC (12 points)

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.

Blake Stacey in reply to Steve Flammia Dec 17 2017 21:43 UTC

Neat!

Aram Harrow in reply to Steve Flammia Dec 18 2017 19:30 UTC

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

Steve Flammia in reply to Aram Harrow Dec 18 2017 20:59 UTC (1 points)

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.

David Gross Dec 17 2017 20:28 UTC

Nice observation, Steve! :-)