[Jump to code hierarchy]

\(t\)-design

Alternative names: Quadrature, Cubature, Averaging set.
Root code for the Classical Domain
Codes for communication over classical channels

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}\textnormal{d}xp(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 weighted designs are exact Gaussian quadrature or cubature formulas for integration over the reals [1–5], \(X = \mathbb{R}^n\) (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) [6], which includes Steiner systems as a special case. Other designs exist when \(X\) is \(q\)-ary Hamming space (where they are called orthogonal arrays), ordered Hamming space [7,8], \(q\)-Johnson space [9,10] (where they are called subspace designs), or a sphere [11] (where they are called spherical designs).

Complex projective designs are designs on complex projective space, i.e., the space of all quantum states [12–14]. A limit of infinite dimensions yields rigged designs or, more colloquially, continuous-variable (CV) designs [15], which can be used as operator-valued measures for the space of bosonic quantum states (i.e., Schwartz space over the reals).

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

Other notable designs not included below include torus designs [21,22], simplex designs [23–26], quantum-channel designs [27], and designs on vertex operator algebras (a.k.a. conformal designs) [28]. Existence has been proven for combinatorial designs [29–33], subspace designs [34,35], as well as designs on continuous topological spaces [36–39].

Notes

See books [1,40] for tables of various designs.

Cousins

  • Error-correcting code (ECC)— ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [41,42].
  • Two-point homogeneous-space code— Designs exist on compact connected two-point homogeneous spaces [41,43,44]. ECCs and \(t\)-designs on two-point homogeneous spaces are intimately related via association schemes [41,42].
  • Barnes-Wall (BW) lattice— BW lattices support Grassmannian 6-designs [45].
  • Complex projective space code— Quantum states in an \(N\)-dimensional Hilbert space are parameterized by points in the complex projective space \(\mathbb{C}P^N\). As such, complex projective designs are designs on the space of all quantum states [12–14]. Symmetric informationally complete quantum measurements (SIC-POVMs) [12,46] and mutually unbiased bases (MUBs) [47–52] are important examples of such designs.
  • Grassmannian code— Designs have been formulated on Grassmannians [39,45,53–55].
  • Poset code— Designs exist on ordered Hamming space [7,8].
  • Polygon code— The \(q/2\) sets of antipodal pairs of a \(q\)-gon form a tight design on the projective plane [44].
  • Witting polytope code— Antipodal pairs of points of the Witting polytope code form a 3-design in \(\mathbb{R}P^7\) [56].
  • 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 [57,58].
  • Number-phase code— Pegg-Barnett phase states undergoing Kerr evolution, together with Fock states, form a rigged 2-design for a single mode [15].
  • Bosonic code— Gaussian states, under a particular measure, do not form rigged two-designs [59].
  • Gottesman-Kitaev-Preskill (GKP) code— GKP states on \(n\) modes and their displaced versions for all possible lattices form a rigged 2-design for all \(n\) [60].
  • Cluster-state code— Kerdock codes correspond to cluster states, and the corresponding Clifford-group automorphisms of this set form a particular group [61] that is a unitary 2-design on \(U(2^n)\) [62]. As such, cluster states form complex projective 2-designs on \(\mathbb{C}P^{2^n}\). These are useful in matrix-vector multiplication [63].
  • Qubit stabilizer code— Stabilizer states on \(n\) qubits form 3-designs on complex projective spaces \(\mathbb{C}P^{2^n}\) [64], while the Clifford group is a unitary 3-design on \(U(2^n)\) [65,66]. The \([[2m,2m-2,2]]\) code for \(2m\) being a multiple of four obstructs the Clifford group from being a 4-design [67].
  • Modular-qudit stabilizer code— Stabilizer states on \(n\) prime-dimensional qubits form 2-designs on complex projective spaces \(\mathbb{C}P^{p^n}\) [64], while the prime-qudit Clifford group is a unitary 2-design on \(U(p^n)\) [68].
  • Galois-qudit stabilizer code— Stabilizer states on \(n\) Galois qubits form 2-designs on complex projective spaces \(\mathbb{C}P^{p^{mn}}\) [69].

Member of code lists

Primary Hierarchy

Classical Domain
\(t\)-design
Children
Unitary \(t\)-design
Unitary \(t\)-designs are designs on the unitary group \(U(N)\).
Subspace design
Subspace designs are designs on the finite-field Grassmannian (a.k.a. \(q\)-Johnson space or \(q\)-Johnson association scheme) [70][71; Sec. 8.6].
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)Perfect binary MDS GRS
Orthogonal arrays are designs on Hamming space \(\mathbb{F}_q^n\) (a.k.a. the Hamming association scheme) [6,43,70][41; Exam. 1]; see also Ref. [72].
Spherical design
Spherical designs are designs on real or complex spheres.

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, A. B. Olde Daalhuis, D. W. Lozier, B. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, “Digital Library of Mathematical Functions”, (2019) DOI
[5]
E. Bannai, E. Bannai, M. Hirao, and M. Sawa, “Cubature formulas in numerical analysis and Euclidean tight designs”, European Journal of Combinatorics 31, 423 (2010) DOI
[6]
Delsarte, Philippe. “An algebraic approach to the association schemes of coding theory.” Philips Res. Rep. Suppl. 10 (1973): vi+-97.
[7]
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
[8]
A. Barg and P. Purkayastha, “Bounds on ordered codes and orthogonal arrays”, (2009) arXiv:cs/0702033
[9]
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.
[10]
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 843 (2013) DOI
[11]
P. Delsarte, J. M. Goethals, and J. J. Seidel, “Spherical codes and designs”, Geometriae Dedicata 6, 363 (1977) DOI
[12]
J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves, “Symmetric informationally complete quantum measurements”, Journal of Mathematical Physics 45, 2171 (2004) arXiv:quant-ph/0310075 DOI
[13]
A. Ambainis and J. Emerson, “Quantum t-designs: t-wise independence in the quantum world”, (2007) arXiv:quant-ph/0701126
[14]
I. Bengtsson and K. Życzkowski, Geometry of Quantum States (Cambridge University Press, 2017) DOI
[15]
J. T. Iosue, K. Sharma, M. J. Gullans, and V. V. Albert, “Continuous-Variable Quantum State Designs: Theory and Applications”, Physical Review X 14, (2024) arXiv:2211.05127 DOI
[16]
C. Dankert, “Efficient Simulation of Random Quantum States and Operators”, (2005) arXiv:quant-ph/0512217
[17]
C. Dankert, R. Cleve, J. Emerson, and E. Livine, “Exact and approximate unitary 2-designs and their application to fidelity estimation”, Physical Review A 80, (2009) arXiv:quant-ph/0606161 DOI
[18]
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
[19]
T. Schuster, J. Haferkamp, and H.-Y. Huang, “Random unitaries in extremely low depth”, (2025) arXiv:2407.07754
[20]
W. T. Gowers, “An Almost m-wise Independent Random Permutation of the Cube”, Combinatorics, Probability and Computing 5, 119 (1996) DOI
[21]
G. Kuperberg, “Numerical cubature from Archimedes’ hat-box theorem”, (2004) arXiv:math/0405366
[22]
J. T. Iosue, T. C. Mooney, A. Ehrenberg, and A. V. Gorshkov, “Projective toric designs, quantum state designs, and mutually unbiased bases”, Quantum 8, 1546 (2024) arXiv:2311.13479 DOI
[23]
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
[24]
P. C. Hammer and A. H. Stroud, “Numerical Integration Over Simplexes”, Mathematical Tables and Other Aids to Computation 10, 137 (1956) DOI
[25]
M. S. BALADRAM, “On Explicit Construction of Simplex <i>t</i>-designs”, Interdisciplinary Information Sciences 24, 181 (2018) DOI
[26]
W. F. Guthrie, “NIST/SEMATECH e-Handbook of Statistical Methods (NIST Handbook 151)”, (2020) DOI
[27]
J. Czartowski and K. Życzkowski, “Quantum Pushforward Designs”, (2025) arXiv:2412.09672
[28]
G. Hoehn, “Conformal Designs based on Vertex Operator Algebras”, (2007) arXiv:math/0701626
[29]
P. Keevash, “The existence of designs”, (2024) arXiv:1401.3665
[30]
L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
[31]
S. Glock, D. Kühn, A. Lo, and D. Osthus, “The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\)”, (2020) arXiv:1611.06827
[32]
P. Keevash, “The existence of designs II”, (2018) arXiv:1802.05900
[33]
P. Keevash, “A short proof of the existence of designs”, (2024) arXiv:2411.18291
[34]
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
[35]
P. Keevash, A. Sah, and M. Sawhney, “The existence of subspace designs”, (2023) arXiv:2212.00870
[36]
P. D. Seymour and T. Zaslavsky, “Averaging sets: A generalization of mean values and spherical designs”, Advances in Mathematics 52, 213 (1984) DOI
[37]
I. Z. Pesenson and D. Geller, “Cubature formulas and discrete fourier transform on compact manifolds”, (2011) arXiv:1111.5900
[38]
D. M. Kane, “Small Designs for Path Connected Spaces and Path Connected Homogeneous Spaces”, (2012) arXiv:1112.4900
[39]
U. Etayo, J. Marzo, and J. Ortega-Cerdà, “Asymptotically optimal designs on compact algebraic manifolds”, Monatshefte für Mathematik 186, 235 (2018) arXiv:1612.06729 DOI
[40]
C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
[41]
P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
[42]
R. A. Bailey, Association Schemes (Cambridge University Press, 2004) DOI
[43]
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.
[44]
H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
[45]
C. Bachoc, “Designs, groups and lattices”, (2007) arXiv:0712.1939
[46]
Zauner, G. (1999). Grundzüge einer nichtkommutativen Designtheorie. Ph. D. dissertation, PhD thesis.
[47]
A. Klappenecker and M. Roetteler, “Constructions of Mutually Unbiased Bases”, (2003) arXiv:quant-ph/0309120
[48]
A. Klappenecker and M. Roetteler, “Mutually Unbiased Bases are Complex Projective 2-Designs”, (2005) arXiv:quant-ph/0502031
[49]
A. J. Scott, “Optimizing quantum process tomography with unitary2-designs”, Journal of Physics A: Mathematical and Theoretical 41, 055308 (2008) arXiv:0711.1017 DOI
[50]
T. DURT, B.-G. ENGLERT, I. BENGTSSON, and K. ŻYCZKOWSKI, “ON MUTUALLY UNBIASED BASES”, International Journal of Quantum Information 08, 535 (2010) arXiv:1004.3348 DOI
[51]
H. Zhu, “Mutually unbiased bases as minimal Clifford covariant 2-designs”, Physical Review A 91, (2015) arXiv:1505.01123 DOI
[52]
D. McNulty and S. Weigert, “Mutually Unbiased Bases in Composite Dimensions – A Review”, (2024) arXiv:2410.23997
[53]
C. Bachoc, R. Coulangeon, and G. Nebe, “Designs in Grassmannian Spaces and Lattices”, Journal of Algebraic Combinatorics 16, 5 (2002) DOI
[54]
C. Bachoc, E. Bannai, and R. Coulangeon, “Codes and designs in Grassmannian spaces”, Discrete Mathematics 277, 15 (2004) DOI
[55]
A. Breger, M. Ehler, M. Gräf, and T. Peter, “Cubatures on Grassmannians: Moments, Dimension Reduction, and Related Topics”, Applied and Numerical Harmonic Analysis 235 (2017) arXiv:1705.02978 DOI
[56]
H. Cohn and A. Kumar, “Universally optimal distribution of points on spheres”, Journal of the American Mathematical Society 20, 99 (2006) arXiv:math/0607446 DOI
[57]
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
[58]
F. Lacerda, J. M. Renes, and V. B. Scholz, “Coherent state constellations for Bosonic Gaussian channels”, 2016 IEEE International Symposium on Information Theory (ISIT) 2499 (2016) DOI
[59]
R. Blume-Kohout and P. S. Turner, “The Curious Nonexistence of Gaussian 2-Designs”, Communications in Mathematical Physics 326, 755 (2014) arXiv:1110.1042 DOI
[60]
J. Conrad, J. T. Iosue, A. G. Burchards, and V. V. Albert, “Continuous-variable designs and design-based shadow tomography from random lattices”, (2025) arXiv:2412.17909
[61]
A. Calderbank, P. Cameron, W. Kantor, and J. Seidel, “Z\({}_{\text{4}}\) -Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets”, Proceedings of the London Mathematical Society 75, 436 (1997) DOI
[62]
T. Can, N. Rengaswamy, R. Calderbank, and H. D. Pfister, “Kerdock Codes Determine Unitary 2-Designs”, IEEE Transactions on Information Theory 66, 6104 (2020) arXiv:1904.07842 DOI
[63]
T. Fuchs, D. Gross, F. Krahmer, R. Kueng, and D. G. Mixon, “Sketching with Kerdock’s crayons: Fast sparsifying transforms for arbitrary linear maps”, (2021) arXiv:2105.05879
[64]
R. Kueng and D. Gross, “Qubit stabilizer states are complex projective 3-designs”, (2015) arXiv:1510.02767
[65]
H. Zhu, “Multiqubit Clifford groups are unitary 3-designs”, Physical Review A 96, (2017) arXiv:1510.02619 DOI
[66]
Z. Webb, “The Clifford group forms a unitary 3-design”, (2016) arXiv:1510.02769
[67]
H. Zhu, R. Kueng, M. Grassl, and D. Gross, “The Clifford group fails gracefully to be a unitary 4-design”, (2016) arXiv:1609.08172
[68]
M. A. Graydon, J. Skanes-Norman, and J. J. Wallman, “Clifford groups are not always 2-designs”, (2021) arXiv:2108.04200
[69]
H. F. Chau, “Unconditionally Secure Key Distribution in Higher Dimensions by Depolarization”, IEEE Transactions on Information Theory 51, 1451 (2005) arXiv:quant-ph/0405016 DOI
[70]
Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
[71]
T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Harmonic Analysis on Finite Groups (Cambridge University Press, 2008) DOI
[72]
G. Kuperberg, S. Lovett, and R. Peled, “Probabilistic existence of regular combinatorial structures”, (2017) arXiv:1302.4295
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: t-designs

Cite as:
“\(t\)-design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/t-designs
BibTeX:
@incollection{eczoo_t-designs, title={\(t\)-design}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/t-designs} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/t-designs

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/t-designs.yml.