## Description

A code whose codewords are uniformly distributed in a way that is useful for determining averages of polynomials over the code's underlying space \(X\). In that way, the codewords form an approximation of the space. A code is a design on \(X\) of strength \(t\), i.e., a \(t\)-design on \(X\), if the average of any polynomial of degree up to \(t\) over its codewords is equal to the uniform average over all of \(X\).

As such, a design can be used to determine the average of degree-\(\leq t\) polynomials \(p\) over \(X\), \begin{align} \int_{X}dxp(x)={\textstyle \frac{1}{|D|}}\sum_{x\in D}p(x)~, \tag*{(1)}\end{align} where the integral is over \(X\) (given some measure \(d x\)), while the sum is over the design \(D\subset X\). A weighted design is a design for which each term \(p(x)\) in the above sum must be multiplied by a weight \(w(x)\) in order to be equal to the left-hand side. The most well-known examples of weighed designs are exact Gaussian quadrature or cubature formulas for integration over the reals [1–4], \(X = \mathbb{R}^D\) (with appropriate measure); these tend to be weighted designs.

Fixed-weight codewords of a binary code can form a design on \(X\) being a Johnson space \(J^n_w\), i.e., the space of length-\(n\) binary strings of weight \(w\). Such a design is called a combinatorial design (a.k.a. block design or covering design) [5], which includes Steiner systems as a special case. Designs on the full space of binary strings (Hamming space) are called orthogonal arrays.

More generally, designs exist when \(X\) is \(q\)-ary Hamming space, ordered Hamming space [6,7], \(q\)-Johnson space [8,9] (where they are called subspace designs), a sphere [10] (where they are called spherical designs), or a compact connected two-point homogeneous space [11–13] (the sphere or the real, complex, quaternionic, or octonionic projective spaces [14]).

Complex projective designs are designs on the space of all quantum states [15–17]. Symmetric informationally complete quantum measurements (SIC-POVMs) [15] and mutually unbiased bases (MUBs) [18,19] are important examples of such designs.

Designs also exist on groups. Designs on the unitary (projective unitary) group are called strong unitary (unitary) designs [20–22], while \(t\)-designs on the permutation group are called permutation \(t\)-designs [23] (a.k.a. \(t\)-wise independent permutations).

Other notable designs include torus designs [24,25], simplex designs [26–29], Grassmanian designs [30–32], and designs on vertex operator algebras (a.k.a. conformal designs) [33]. Existence has been proven for combinatorial designs [34], subspace designs [35,36], as well as designs on continuous topological spaces [37–39].

## Notes

## Parent

## Children

- Sharp configuration — Sharp configurations attain a universal bound expressed in terms of the minimal distance, the number of distances between codewords, and the strength of the design formed by the codewords.
- Orthogonal array (OA) — Orthogonal arrays are designs on Hamming space \(GF(q)^n\) (a.k.a. the Hamming association scheme) [5,12,41][11; Exam. 1]; see also Ref. [42].
- Subspace design — Subspace designs are designs on a space of fixed-weight \(q\)-ary strings (a.k.a. \(q\)-Johnson association scheme) [41].
- Spherical design — Spherical designs are designs on real or complex spheres.

## Cousins

- Kerdock code — Kerdock codes correspond to cluster states, and the corresponding Clifford-group automorphisms of this set form a particular group [43] that is a unitary two-design [44]. As such, cluster states form complex projective two-designs. These are useful in matrix-vector multiplication [45].
- Coherent-state constellation code — Coherent-state constellation codes consisting of points from a Gaussian quadrature rule can be concatenated with quantum polar codes to achieve the Gaussian coherent information of the thermal noise channel [46,47].
- Bosonic code — The notion of quantum state designs has been extended to states of a bosonic mode [48].
- Haar-random qubit code — Approximating the random projections through \(t\)-designs is necessary in order to make the protocol practical. Replacing with random Clifford gates is especially convenient since the Clifford group forms a unitary 2-design and produces stabilizer codes.
- Local Haar-random circuit qubit code — Local Haar-random circuits of polynomial depth form approximate unitary designs [49].
- Qubit stabilizer code — Stabilizer states on \(n\) qubits form complex projective 3-designs [50], while the Clifford group is a unitary 3-design [51,52].
- Modular-qudit stabilizer code — Stabilizer states on \(n\) prime-dimensional qubits form complex projective 2-designs [50], while the prime-qudit Clifford group is a unitary 2-design [53].
- Twisted \(1\)-group code — Twisted unitary \(t\)-groups [54] generalize the idea of unitary \(t\)-groups [55,56], which are subgroups of the unitary group that form unitary \(t\)-designs.

## References

- [1]
- Stroud, Arthur H. Approximate calculation of multiple integrals. Prentice Hall, 1971.
- [2]
- R. Cools, “Constructing cubature formulae: the science behind the art”, Acta Numerica 6, 1 (1997) DOI
- [3]
- R. Cools, “An encyclopaedia of cubature formulas”, Journal of Complexity 19, 445 (2003) DOI
- [4]
- F. W. J. Olver et al., “Digital Library of Mathematical Functions”, (2019) DOI
- [5]
- Delsarte, Philippe. "An algebraic approach to the association schemes of coding theory." Philips Res. Rep. Suppl. 10 (1973): vi+-97.
- [6]
- W. J. Martin and D. R. Stinson, “Association Schemes for Ordered Orthogonal Arrays and (T, M, S)-Nets”, Canadian Journal of Mathematics 51, 326 (1999) DOI
- [7]
- A. Barg and P. Purkayastha, “Bounds on ordered codes and orthogonal arrays”, (2009) arXiv:cs/0702033
- [8]
- Cameron, Peter J. "Generalisation of Fisher’s inequality to fields with more than one element." Combinatorics, London Math. Soc. Lecture Note Ser 13 (1973): 9-13.
- [9]
- V. Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound”, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (2013) DOI
- [10]
- P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI
- [11]
- P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
- [12]
- V. I. Levenshtein, “Universal bounds for codes and designs,” in Handbook of Coding Theory 1, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp.499-648.
- [13]
- H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
- [14]
- H.-C. Wang, “Two-Point Homogeneous Spaces”, The Annals of Mathematics 55, 177 (1952) DOI
- [15]
- J. M. Renes et al., “Symmetric informationally complete quantum measurements”, Journal of Mathematical Physics 45, 2171 (2004) arXiv:quant-ph/0310075 DOI
- [16]
- A. Ambainis and J. Emerson, “Quantum t-designs: t-wise independence in the quantum world”, (2007) arXiv:quant-ph/0701126
- [17]
- I. Bengtsson and K. Życzkowski, Geometry of Quantum States (Cambridge University Press, 2017) DOI
- [18]
- T. DURT et al., “ON MUTUALLY UNBIASED BASES”, International Journal of Quantum Information 08, 535 (2010) arXiv:1004.3348 DOI
- [19]
- H. Zhu, “Mutually unbiased bases as minimal Clifford covariant 2-designs”, Physical Review A 91, (2015) arXiv:1505.01123 DOI
- [20]
- C. Dankert, “Efficient Simulation of Random Quantum States and Operators”, (2005) arXiv:quant-ph/0512217
- [21]
- C. Dankert et al., “Exact and approximate unitary 2-designs and their application to fidelity estimation”, Physical Review A 80, (2009) arXiv:quant-ph/0606161 DOI
- [22]
- D. Gross, K. Audenaert, and J. Eisert, “Evenly distributed unitaries: On the structure of unitary designs”, Journal of Mathematical Physics 48, (2007) arXiv:quant-ph/0611002 DOI
- [23]
- W. T. Gowers, “An Almost m-wise Independent Random Permutation of the Cube”, Combinatorics, Probability and Computing 5, 119 (1996) DOI
- [24]
- G. Kuperberg, “Numerical cubature from Archimedes’ hat-box theorem”, (2004) arXiv:math/0405366
- [25]
- J. T. Iosue et al., “Projective toric designs, difference sets, and quantum state designs”, (2023) arXiv:2311.13479
- [26]
- P. C. Hammer, O. J. Marlowe, and A. H. Stroud, “Numerical Integration Over Simplexes and Cones”, Mathematical Tables and Other Aids to Computation 10, 130 (1956) DOI
- [27]
- P. C. Hammer and A. H. Stroud, “Numerical Integration Over Simplexes”, Mathematical Tables and Other Aids to Computation 10, 137 (1956) DOI
- [28]
- M. S. BALADRAM, “On Explicit Construction of Simplex <i>t</i>-designs”, Interdisciplinary Information Sciences 24, 181 (2018) DOI
- [29]
- W. F. Guthrie, “NIST/SEMATECH e-Handbook of Statistical Methods (NIST Handbook 151)”, (2020) DOI
- [30]
- C. Bachoc, E. Bannai, and R. Coulangeon, “Codes and designs in Grassmannian spaces”, Discrete Mathematics 277, 15 (2004) DOI
- [31]
- C. Bachoc, “Designs, groups and lattices”, (2007) arXiv:0712.1939
- [32]
- A. Breger et al., “Cubatures on Grassmannians: Moments, Dimension Reduction, and Related Topics”, Compressed Sensing and its Applications 235 (2017) arXiv:1705.02978 DOI
- [33]
- G. Hoehn, “Conformal Designs based on Vertex Operator Algebras”, (2007) arXiv:math/0701626
- [34]
- L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
- [35]
- A. Fazeli, S. Lovett, and A. Vardy, “Nontrivial t-designs over finite fields exist for all t”, Journal of Combinatorial Theory, Series A 127, 149 (2014) DOI
- [36]
- P. Keevash, A. Sah, and M. Sawhney, “The existence of subspace designs”, (2023) arXiv:2212.00870
- [37]
- P. D. Seymour and T. Zaslavsky, “Averaging sets: A generalization of mean values and spherical designs”, Advances in Mathematics 52, 213 (1984) DOI
- [38]
- I. Z. Pesenson and D. Geller, “Cubature formulas and discrete fourier transform on compact manifolds”, (2011) arXiv:1111.5900
- [39]
- D. M. Kane, “Small Designs for Path Connected Spaces and Path Connected Homogeneous Spaces”, (2012) arXiv:1112.4900
- [40]
- C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
- [41]
- Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
- [42]
- G. Kuperberg, S. Lovett, and R. Peled, “Probabilistic existence of regular combinatorial structures”, (2017) arXiv:1302.4295
- [43]
- A. Calderbank et al., “Z\({}_{\text{4}}\) -Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets”, Proceedings of the London Mathematical Society 75, 436 (1997) DOI
- [44]
- T. Can et al., “Kerdock Codes Determine Unitary 2-Designs”, IEEE Transactions on Information Theory 66, 6104 (2020) arXiv:1904.07842 DOI
- [45]
- T. Fuchs et al., “Sketching with Kerdock’s crayons: Fast sparsifying transforms for arbitrary linear maps”, (2021) arXiv:2105.05879
- [46]
- F. Lacerda, J. M. Renes, and V. B. Scholz, “Coherent-state constellations and polar codes for thermal Gaussian channels”, Physical Review A 95, (2017) arXiv:1603.05970 DOI
- [47]
- F. Lacerda, J. M. Renes, and V. B. Scholz, “Coherent state constellations for Bosonic Gaussian channels”, 2016 IEEE International Symposium on Information Theory (ISIT) (2016) DOI
- [48]
- J. T. Iosue et al., “Continuous-Variable Quantum State Designs: Theory and Applications”, Physical Review X 14, (2024) arXiv:2211.05127 DOI
- [49]
- F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, “Local Random Quantum Circuits are Approximate Polynomial-Designs”, Communications in Mathematical Physics 346, 397 (2016) arXiv:1208.0692 DOI
- [50]
- R. Kueng and D. Gross, “Qubit stabilizer states are complex projective 3-designs”, (2015) arXiv:1510.02767
- [51]
- H. Zhu, “Multiqubit Clifford groups are unitary 3-designs”, Physical Review A 96, (2017) arXiv:1510.02619 DOI
- [52]
- Z. Webb, “The Clifford group forms a unitary 3-design”, (2016) arXiv:1510.02769
- [53]
- M. A. Graydon, J. Skanes-Norman, and J. J. Wallman, “Clifford groups are not always 2-designs”, (2021) arXiv:2108.04200
- [54]
- E. Kubischta and I. Teixeira, “Quantum Codes from Twisted Unitary t -Groups”, Physical Review Letters 133, (2024) arXiv:2402.01638 DOI
- [55]
- R. M. Guralnick and P. H. Tiep, “Decompositions of Small Tensor Powers and Larsen’s Conjecture”, (2005) arXiv:math/0502080
- [56]
- E. Bannai et al., “Unitary t-groups”, (2018) arXiv:1810.02507

## Page edit log

- Victor V. Albert (2024-06-19) — most recent
- Greg Kuperberg (2024-06-19)
- Alexander Barg (2024-06-19)

## Cite as:

“\(t\)-design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/t-designs