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

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

See the handbook [40] for tables of various designs.

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 bosonic modes [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, “Free Quantum Codes from Twisted Unitary \(t\)-groups”, (2024) arXiv:2402.01638
[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

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.