\(t\)-design 

Also known as Quadrature, 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}\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 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–22] are important examples of such designs.

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

Other notable designs include torus designs [27,28], simplex designs [29–32], Grassmanian designs [33–35], quantum-channel designs [36], and designs on vertex operator algebras (a.k.a. conformal designs) [37]. Existence has been proven for combinatorial designs [38–42], subspace designs [43,44], as well as designs on continuous topological spaces [45–47].

Notes

See books [1,48] 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,49][11; Exam. 1]; see also Ref. [50].
  • Subspace design — Subspace designs are designs on a space of fixed-weight \(q\)-ary strings (a.k.a. \(q\)-Johnson association scheme) [49].
  • 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 [51] that is a unitary 2-design [52]. As such, cluster states form complex projective 2-designs. These are useful in matrix-vector multiplication [53].
  • 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 [54,55].
  • Bosonic code — The notion of quantum state designs has been extended to states of a bosonic mode [56].
  • 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 [57].
  • Qubit stabilizer code — Stabilizer states on \(n\) qubits form complex projective 3-designs [58], while the Clifford group is a unitary 3-design [59,60].
  • Kitaev surface code — Unitary \(t\)-designs can be generated via coherent errors, syndrome extraction, and correction [61].
  • Modular-qudit stabilizer code — Stabilizer states on \(n\) prime-dimensional qubits form complex projective 2-designs [58], while the prime-qudit Clifford group is a unitary 2-design [62].
  • Twisted \(1\)-group code — Twisted unitary \(t\)-groups [63] generalize the idea of unitary \(t\)-groups [64,65], 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, 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]
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, 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
[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]
A. Klappenecker and M. Roetteler, “Constructions of Mutually Unbiased Bases”, (2003) arXiv:quant-ph/0309120
[19]
A. Klappenecker and M. Roetteler, “Mutually Unbiased Bases are Complex Projective 2-Designs”, (2005) arXiv:quant-ph/0502031
[20]
A. J. Scott, “Optimizing quantum process tomography with unitary2-designs”, Journal of Physics A: Mathematical and Theoretical 41, 055308 (2008) arXiv:0711.1017 DOI
[21]
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
[22]
H. Zhu, “Mutually unbiased bases as minimal Clifford covariant 2-designs”, Physical Review A 91, (2015) arXiv:1505.01123 DOI
[23]
C. Dankert, “Efficient Simulation of Random Quantum States and Operators”, (2005) arXiv:quant-ph/0512217
[24]
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
[25]
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
[26]
W. T. Gowers, “An Almost m-wise Independent Random Permutation of the Cube”, Combinatorics, Probability and Computing 5, 119 (1996) DOI
[27]
G. Kuperberg, “Numerical cubature from Archimedes’ hat-box theorem”, (2004) arXiv:math/0405366
[28]
J. T. Iosue, T. C. Mooney, A. Ehrenberg, and A. V. Gorshkov, “Projective toric designs, quantum state designs, and mutually unbiased bases”, (2024) arXiv:2311.13479
[29]
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
[30]
P. C. Hammer and A. H. Stroud, “Numerical Integration Over Simplexes”, Mathematical Tables and Other Aids to Computation 10, 137 (1956) DOI
[31]
M. S. BALADRAM, “On Explicit Construction of Simplex <i>t</i>-designs”, Interdisciplinary Information Sciences 24, 181 (2018) DOI
[32]
W. F. Guthrie, “NIST/SEMATECH e-Handbook of Statistical Methods (NIST Handbook 151)”, (2020) DOI
[33]
C. Bachoc, E. Bannai, and R. Coulangeon, “Codes and designs in Grassmannian spaces”, Discrete Mathematics 277, 15 (2004) DOI
[34]
C. Bachoc, “Designs, groups and lattices”, (2007) arXiv:0712.1939
[35]
A. Breger, M. Ehler, M. Gräf, and T. Peter, “Cubatures on Grassmannians: Moments, Dimension Reduction, and Related Topics”, Compressed Sensing and its Applications 235 (2017) arXiv:1705.02978 DOI
[36]
J. Czartowski and K. Życzkowski, “Quantum Pushforward Designs”, (2024) arXiv:2412.09672
[37]
G. Hoehn, “Conformal Designs based on Vertex Operator Algebras”, (2007) arXiv:math/0701626
[38]
P. Keevash, “The existence of designs”, (2024) arXiv:1401.3665
[39]
L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
[40]
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
[41]
P. Keevash, “The existence of designs II”, (2018) arXiv:1802.05900
[42]
P. Keevash, “A short proof of the existence of designs”, (2024) arXiv:2411.18291
[43]
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
[44]
P. Keevash, A. Sah, and M. Sawhney, “The existence of subspace designs”, (2023) arXiv:2212.00870
[45]
P. D. Seymour and T. Zaslavsky, “Averaging sets: A generalization of mean values and spherical designs”, Advances in Mathematics 52, 213 (1984) DOI
[46]
I. Z. Pesenson and D. Geller, “Cubature formulas and discrete fourier transform on compact manifolds”, (2011) arXiv:1111.5900
[47]
D. M. Kane, “Small Designs for Path Connected Spaces and Path Connected Homogeneous Spaces”, (2012) arXiv:1112.4900
[48]
C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
[49]
Ph. Delsarte, “Hahn Polynomials, Discrete Harmonics, andt-Designs”, SIAM Journal on Applied Mathematics 34, 157 (1978) DOI
[50]
G. Kuperberg, S. Lovett, and R. Peled, “Probabilistic existence of regular combinatorial structures”, (2017) arXiv:1302.4295
[51]
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
[52]
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
[53]
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
[54]
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
[55]
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
[56]
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
[57]
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
[58]
R. Kueng and D. Gross, “Qubit stabilizer states are complex projective 3-designs”, (2015) arXiv:1510.02767
[59]
H. Zhu, “Multiqubit Clifford groups are unitary 3-designs”, Physical Review A 96, (2017) arXiv:1510.02619 DOI
[60]
Z. Webb, “The Clifford group forms a unitary 3-design”, (2016) arXiv:1510.02769
[61]
Z. Cheng, E. Huang, V. Khemani, M. J. Gullans, and M. Ippoliti, “Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements”, (2024) arXiv:2412.04414
[62]
M. A. Graydon, J. Skanes-Norman, and J. J. Wallman, “Clifford groups are not always 2-designs”, (2021) arXiv:2108.04200
[63]
E. Kubischta and I. Teixeira, “Quantum Codes from Twisted Unitary t -Groups”, Physical Review Letters 133, (2024) arXiv:2402.01638 DOI
[64]
R. M. Guralnick and P. H. Tiep, “Decompositions of Small Tensor Powers and Larsen’s Conjecture”, (2005) arXiv:math/0502080
[65]
E. Bannai, G. Navarro, N. Rizo, and P. H. Tiep, “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:
“\(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/properties/block/universally_optimal/t-designs.yml.