Explicit orthogonal and unitary designs

2023/10/20 by O'Donnell, Ryan, Servedio, Rocco A., Paredes, Pedro · 2 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2310.13597

Abstract

We give a strongly explicit construction of ε-approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for N=2ⁿ. Our designs are of cardinality poly(N^k/ε) (equivalently, they have seed length O(nk + log(1/ε))); up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

Cited by

• Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms
• Will it glue? On short-depth designs beyond the unitary group

Related

• Explicit construction of exact unitary designs
• Generalized group designs: overcoming the 4-design-barrier and constructing novel unitary 2-designs in arbitrary dimensions
• Signed group orthogonal designs and their applications
• Universal p-ary designs
• On certain classes of rectangular designs