Design 

Also known as Cubature, Averaging set.

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 [79] (the sphere or the real, complex, quaternionic, or octonionic projective spaces [10]). Complex projective designs are designs on the space of all quantum states [1113].

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 [1821], Grassmanian designs [22,23], and (exact) quadrature/cubature formulas for integration over the reals [2427]. 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

Your contribution is welcome!

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

edit on this site

Zoo Code ID: t-designs

Cite as:
“Design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/t-designs
BibTeX:
@incollection{eczoo_t-designs, title={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:

“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/properties/block/universally_optimal/t-designs.yml.