  We show it is possible to obtain quantum pseudorandomness and
pseudoentanglement from random subset states -- i.e. quantum states which are
equal superpositions over (pseudo)random subsets of strings. This answers an
open question of Aaronson et al. [arXiv:2211.00747], who devised a similar
construction augmented by pseudorandom phases. Our result follows from a direct
calculation of the trace distance between $t$ copies of random subset states
and the Haar measure, via the representation theory of the symmetric group. We
show that the trace distance is negligibly small, as long as the subsets are of
an appropriate size which is neither too big nor too small. In particular, we
analyze the action of basis permutations on the symmetric subspace, and show
that the largest component is described by the Johnson scheme: the
double-cosets of the symmetric group $\mathbb{S}_N$ by the subgroup
$\mathbb{S}_t \times \mathbb{S}_{N-t}$. The Gelfand pair property of this
setting implies that the matrix eigenbasis coincides with the symmetric group
irreducible blocks, with the largest eigenblock asymptotically approaching the
Haar average. An immediate corollary of our result is that quantum pseudorandom
and pseudoentangled state ensembles do not require relative phases.
