## 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\).

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) [1]. Designs on the full space of binary string (Hamming space) are called orthogonal arrays.

More generally, designs exist when \(X\) is \(q\)-ary Hamming space (where they are called orthogonal arrays), ordered Hamming space [2,3], \(q\)-Johnson space [4,5] (where they are called subspace designs), a sphere [6] (where they are called spherical designs), or a compact connected two-point homogeneous space [7–9] (the sphere or the real, complex, quaternionic, or octonionic projective spaces [10]). Complex projective designs are designs on the space of all quantum states [11–13].

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

Other notable designs include torus designs [16,17], simplex designs [18–21], Grassmanian designs [22,23], and (exact) quadrature/cubature formulas for integration over the reals [24–27]. Existence has been proven for combinatorial designs [28], subspace designs [29,30], as well as designs on continuous topological spaces [31].

## 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) [1,8,32][7; Exam. 1]; see also Ref. [33].
- Subspace design — Subspace designs are designs on a space of fixed-weight \(q\)-ary strings (a.k.a. \(q\)-Johnson association scheme) [32].
- 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 [34] that is a unitary two-design [35].
- Bosonic code — The notion of quantum state designs has been extended to bosonic modes [36].
- 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.
- Qubit stabilizer code — Stabilizer states on \(n\) qubits form complex projective 3-designs [37], while the Clifford group is a unitary 3-design [38,39].
- Modular-qudit stabilizer code — Stabilizer states on \(n\) prime-dimensional qubits form complex projective 2-designs [37], while the prime-qudit Clifford group is a unitary 2-design [40].
- Twisted \(1\)-group code — Twisted unitary \(t\)-group generalize the idea of unitary \(t\)-groups, which are subgroups of the unitary group that form unitary \(t\)-designs.

## References

- [1]
- Delsarte, Philippe. "An algebraic approach to the association schemes of coding theory." Philips Res. Rep. Suppl. 10 (1973): vi+-97.
- [2]
- 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
- [3]
- A. Barg and P. Purkayastha, “Bounds on ordered codes and orthogonal arrays”, (2009) arXiv:cs/0702033
- [4]
- 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.
- [5]
- 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
- [6]
- P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI
- [7]
- P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
- [8]
- 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.
- [9]
- H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
- [10]
- H.-C. Wang, “Two-Point Homogeneous Spaces”, The Annals of Mathematics 55, 177 (1952) DOI
- [11]
- J. M. Renes et al., “Symmetric informationally complete quantum measurements”, Journal of Mathematical Physics 45, 2171 (2004) arXiv:quant-ph/0310075 DOI
- [12]
- A. Ambainis and J. Emerson, “Quantum t-designs: t-wise independence in the quantum world”, (2007) arXiv:quant-ph/0701126
- [13]
- I. Bengtsson and K. Życzkowski, Geometry of Quantum States (Cambridge University Press, 2017) DOI
- [14]
- 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
- [15]
- W. T. Gowers, “An Almost m-wise Independent Random Permutation of the Cube”, Combinatorics, Probability and Computing 5, 119 (1996) DOI
- [16]
- G. Kuperberg, “Numerical cubature from Archimedes’ hat-box theorem”, (2004) arXiv:math/0405366
- [17]
- J. T. Iosue et al., “Projective toric designs, difference sets, and quantum state designs”, (2023) arXiv:2311.13479
- [18]
- 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
- [19]
- P. C. Hammer and A. H. Stroud, “Numerical Integration Over Simplexes”, Mathematical Tables and Other Aids to Computation 10, 137 (1956) DOI
- [20]
- M. S. BALADRAM, “On Explicit Construction of Simplex <i>t</i>-designs”, Interdisciplinary Information Sciences 24, 181 (2018) DOI
- [21]
- W. F. Guthrie, “NIST/SEMATECH e-Handbook of Statistical Methods (NIST Handbook 151)”, (2020) DOI
- [22]
- C. Bachoc, E. Bannai, and R. Coulangeon, “Codes and designs in Grassmannian spaces”, Discrete Mathematics 277, 15 (2004) DOI
- [23]
- C. Bachoc, “Designs, groups and lattices”, (2007) arXiv:0712.1939
- [24]
- R. Cools, “Constructing cubature formulae: the science behind the art”, Acta Numerica 6, 1 (1997) DOI
- [25]
- F. Stenger, “Approximate Calculation of Multiple Integrals (A. H. Stroud)”, SIAM Review 15, 234 (1973) DOI
- [26]
- R. Cools, “An encyclopaedia of cubature formulas”, Journal of Complexity 19, 445 (2003) DOI
- [27]
- F. W. J. Olver et al., “Digital Library of Mathematical Functions”, (2019) DOI
- [28]
- L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
- [29]
- 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
- [30]
- P. Keevash, A. Sah, and M. Sawhney, “The existence of subspace designs”, (2023) arXiv:2212.00870
- [31]
- P. D. Seymour and T. Zaslavsky, “Averaging sets: A generalization of mean values and spherical designs”, Advances in Mathematics 52, 213 (1984) DOI
- [32]
- Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
- [33]
- G. Kuperberg, S. Lovett, and R. Peled, “Probabilistic existence of regular combinatorial structures”, (2017) arXiv:1302.4295
- [34]
- 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
- [35]
- T. Can et al., “Kerdock Codes Determine Unitary 2-Designs”, IEEE Transactions on Information Theory 66, 6104 (2020) arXiv:1904.07842 DOI
- [36]
- J. T. Iosue et al., “Continuous-Variable Quantum State Designs: Theory and Applications”, Physical Review X 14, (2024) arXiv:2211.05127 DOI
- [37]
- R. Kueng and D. Gross, “Qubit stabilizer states are complex projective 3-designs”, (2015) arXiv:1510.02767
- [38]
- H. Zhu, “Multiqubit Clifford groups are unitary 3-designs”, Physical Review A 96, (2017) arXiv:1510.02619 DOI
- [39]
- Z. Webb, “The Clifford group forms a unitary 3-design”, (2016) arXiv:1510.02769
- [40]
- M. A. Graydon, J. Skanes-Norman, and J. J. Wallman, “Clifford groups are not always 2-designs”, (2021) arXiv:2108.04200

## Page edit log

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

## Cite as:

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