Abstract
We give a strongly explicit construction of ๐-approximate ๐-designs for the orthogonal group O(๐) and the unitary group U(๐), for ๐ = 2โฟ. Our designs are of cardinality poly(๐แต/๐) (equivalently, they have seed length ๐(๐๐ + log(1/๐))); up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.
Joint work with Pedro Paredes (Princeton) and Rocco Servedio (Columbia).