Source-linked AI summary
Unitary designs and codes
Aidan Roy, A. J. Scott
TL;DR
Quantum information problems have motivated unitary designs, but the paper addresses the general problem of bounding their size and that of related unitary codes. Using irreducible representations, it derives design lower bounds and code upper bounds, with design size at least D(d, ⌈t/2⌉, ⌊t/2⌋).
Problem
The paper studies how large unitary t-designs and related unitary codes must be, for general d and t.
Source: §1 · p. 2Method
Results
Takeaways & Limitations
The bounds can be strengthened when the inner-product values in a design or code are specified.
Source: §1 · p. 3, §5 · p. 13Tight t-designs appear rare: numerical searches have found none for t > 1.
Source: §5 · p. 17
Abstract
from arXiv · showhide
A unitary design is a collection of unitary matrices that approximate the entire unitary group, much like a spherical design approximates the entire unit sphere. In this paper, we use irreducible representations of the unitary group to find a general lower bound on the size of a unitary t-design in U(d), for any d and t. We also introduce the notion of a unitary code - a subset of U(d) in which the trace inner product of any pair of matrices is restricted to only a small number of distinct values - and give an upper bound for the size of a code of degree s in U(d) for any d and s. These bounds can be strengthened when the particular inner product values that occur in the code or design are known. Finally, we describe some constructions of designs: we give an upper bound on the size of the smallest weighted unitary t-design in U(d), and we catalogue some t-designs that arise from finite groups.
1 Introduction
Motivated by quantum information, the paper studies unitary t-designs and their dual notion, unitary codes. It develops representation-based bounds and criteria for designs, then outlines refinements and constructions.
1 Introduction
- A unitary t-design is a unitary-group analogue of a spherical design, motivated by problems in quantum information theory.Among applications in quantum information, 2-designs are described as especially interesting.Source: §1 · pp. 2–3
- Irreducible representations yield a lower bound on unitary t-design size and an upper bound on unitary code size.The paper identifies a duality between designs and codes whose members have few distinct pairwise inner-product values.Source: §1 · p. 2
- For a unitary t-design, equality in the stated characterization holds if and only if the set is a t-design.The passage presents this as a second characterization that is easier to compute; its displayed expression is not included here.Source: §1 · pp. 2–3
- The paper also outlines relative bounds for specified distances, a size bound for weighted designs, and constructions from finite groups.The relative bounds apply when the inner-product values in a design or code are specified.Source: §1 · p. 3
2 Unitary Representations
This section develops the representation-theoretic tools used later to bound designs and codes. It describes how unitary-group representations are indexed and how dimensions of their matrix spans can be evaluated.
2 Unitary Representations
- Every finite-dimensional representation of U(d) extends uniquely to an algebraic representation of GL(d, C).This allows results stated for GL(d, C) representations to apply to U(d).Source: §2 · p. 4
- Irreducible representations of U(d) are indexed by nonincreasing integer sequences of length d, with dimensions given by Weyl’s character formula.The standard representation corresponds to (1, 0, . . . , 0).Source: §2 · p. 4
- The section gives a closed form for the dimension of the space spanned by matrices U^⊗r ⊗ (U*)^⊗s, expressed through Hom(U(d), r, s).The dimension can be bounded asymptotically by O(d^2(r+s)) for fixed r and s, or O((rs)d^2−1) for fixed d.Source: §2 · pp. 6–7
3 Absolute bounds
The section establishes absolute bounds whose inputs are design strength or code degree, rather than the specific distances in a set. It also gives asymptotic consequences for design size.
3 Absolute bounds
- The design and code bounds are absolute because they depend on design strength or code degree, not on the distances that occur.The paper distinguishes these from relative bounds that use specified distances.Source: §3 · pp. 7–8
- |X| ≥ D(d, ⌈t/2⌉, ⌊t/2⌋) for every unitary t-design X.The proof uses an orthonormal basis for Hom(⌈t/2⌉, ⌊t/2⌋) to obtain the lower bound.Source: §3 · p. 8
- For fixed t, the design-size lower bound implies Ω(d^2t); for fixed d, it implies Ω(td^2−1).Constructions meeting the latter asymptotic lower bound are known for U(2).Source: §3 · p. 9
- A unitary code of degree s, whose distinct pairs have only s possible squared trace inner products, satisfies |X| ≤ D(d, s, s).If some pair is orthogonal, the section gives a further conditional bound.Source: §3 · p. 9
4 Zonal orthogonal polynomials
The section introduces zonal orthogonal polynomials as tools for characterizing unitary designs. These functions depend on the spectrum of U* M, and their span provides a criterion for design membership.
4 Zonal orthogonal polynomials
- Zonal orthogonal polynomials depend only on the eigenvalues of U* M and are orthogonal for distinct representation indices.Their “zone” is the spectrum of the matrix product.Source: §4 · pp. 9–10
- A finite set X is a t-design exactly when its averages of the specified nontrivial zonal polynomials vanish.The criterion follows because these polynomials span the relevant space of functions and are orthogonal to the constant component.Source: §4 · pp. 10–11
- The zonal polynomials can be written as symmetric polynomials in the eigenvalues of Λ = U* M.Table 1 lists the first few characters and zonal orthogonal polynomials for sufficiently large d.Source: §4 · p. 11, Table 1 · p. 12
5 Relative bounds
Relative bounds sharpen unitary-code bounds by using the particular trace-inner-product values present. For designs, coefficient-sign conditions yield bounds with equality criteria that characterize designs and restricted inner-product patterns.
5 Relative bounds
- Relative code bounds use the inner-product values that occur, unlike the absolute bound, which depends only on the number of distinct values.Their proof uses zonal orthogonal polynomials and, in spirit, linear programming.Source: §5 · p. 13
- For a unitary 1-distance set with |tr(U* M)|^2 = α < 1, the bound is |X| ≤ (d^2−α)/(1−α), with equality exactly for an equiangular 1-design.Source: §5 · p. 14
- For unitary 2-distance sets, equality in the stated bound holds exactly when X is a 2-design; mutually unbiased unitary operator bases have inner-product values {0, 1}.Source: §5 · p. 15
- For a t-design, Theorem 16 applies when a symmetric F is nonnegative off the diagonal and its expansion coefficients are nonpositive above degree t.When the relevant low-degree coefficients are positive, equality in equation (4) holds exactly for a t-design.Source: §5 · pp. 13, 16
- For a unitary 1-design with |tr(U* M)|^2 ≥ α and α < 1, equality in the stated bound requires every pair to have squared trace inner product α.Source: §5 · p. 16
- For 2-designs, bounds apply when pairwise squared trace inner products lie outside (α, β); equality requires values in {α, β}, or {0, β} in the zero-threshold case.The parameters satisfy α < β, α + β ≤ 4, and α + β < αβ + 2.Source: §5 · pp. 16–17
- Minimal-size designs have an annihilator that vanishes on distinct pairs, while tight designs have rigid structure; numerical searches found no tight t-designs for t > 1.Tight 1-designs have size d^2 and orthogonal matrices; tight 2-designs have size d^4−2d^2+2, and tight 3-designs have size d^2(d^4−3d^2+6)/2.Source: §5 · p. 17
6 Weighted designs
The section bounds the size of weighted unitary designs from below and constructs weighted designs with a general upper bound, improved by one using connectedness of U(d). It also explains why weighted designs are useful and how a convex-hull argument yields the construction.
6 Weighted designs
- Every weighted t-design has |X| ≥ D(d, ⌈t/2⌉, ⌊t/2⌋), with equality only for an unweighted t-design.The lower bound and equality condition are stated for weighted designs.Source: §6 · p. 18
- Weighted designs are described as easier to find and just as useful as unweighted designs for many applications of classical design theory or spherical designs.Source: §6 · p. 18
- For any t and d, a weighted unitary t-design exists with |X| ≤ D(d,t,t).The construction uses positive weights that sum to one.Source: §6 · p. 18
- The existence proof places the zero function in a convex hull, then applies Carathéodory’s theorem to select a finite weighted design.The resulting set has cardinality at most D(d,t,t).Source: §6 · p. 19
- |X| ≤ D(d,t,t) − 1 for every t and d, improving the weighted-design existence bound because U(d) is connected.The initial bound is |X| ≤ D(d,t,t).Source: §6 · pp. 18–19
7 Constructions
The section describes character-based tests and finite-group constructions of unitary designs. It gives Clifford-design size formulas, catalogs known group designs against a lower bound, and notes that finding 2-design families of size O(d^4) in arbitrarily large dimensions remains open.
7 Constructions
- Unitary t-designs exist for every t and d, and the preceding section bounds the smallest weighted design size by O(d^4t).For d > 2 and t > 1, all known constructions described here come from groups.Source: §7 · p. 20
- For group designs, verification can use the character criterion and reduces to checking ⟨1, f⟩X = ⟨1, f⟩ for f(U) = |tr(U)|^(2t).In general, a basis for Hom(t,t) must be checked.Source: §7 · p. 20
- A finite-group representation gives a unitary 1-design exactly when it is irreducible; ignoring central phases reduces the design size to |G|/|Z(G)|.The central quotient also defines a design through an irreducible projective unitary representation.Source: §7 · p. 20
- Table 2 catalogs the smallest known group-design sizes for each t and d alongside the Theorem 8 lower bound.The table identifies Clifford designs among its entries.Source: Table 2 · p. 21, §7 · p. 22
- Searching for designs by calculating Schur covering groups is exhaustive in principle but computationally expensive, and found no additional designs beyond those described.Source: §7 · p. 22
- |X| = k d^2(d^2 − 1) for a Clifford 2-design from H = F2n ⋊ H′ when H′ acts transitively on F2n \ {0} and |H′| = k(q^2n − 1).Here d = q^n; the construction uses a projective unitary representation.Source: §7 · p. 22
- The construction H = F2d ⋊ Sp(2,d) gives 2-designs in all prime-power dimensions, but its size exceeds the lower bound by a factor of d asymptotically.Whether 2-design families of size O(d^4) exist in arbitrarily large dimensions is an open problem.Source: §7 · p. 22
- In U(2), a weighted 11-point 2-design exists, while the smallest unweighted 2-design has 12 points; no nontrivial weighted examples are known for d > 2.Source: §7 · p. 22