I'm currently studying various quantum supremacy protocols and i'm struggling to have a clear and well defined view on the rôle of approximating the Haar-measure (through k-designs ...) and the hardness argument of quantum random sampling.
To give a bit of context :
Let $\{U\}$ be a set of unitaries (can be circuits,evolution operator ...). The protocol of quantum random sampling consist of randomly drawing U from the set (directly of indirectly, the set can actually be defined by a randomly parametrised circuit or randomly valued hamiltonian), and sampling the ouput state. Obviously from this point it's far from finished, one need to realise some statistical test on the output bitstrings (LXEB ...) but it's not the topic of discussion (or at least from my point of view).
The hardness of such task lies in the fact that the underlying probability distribution of the samples coming from an instance $U$ can be hard to compute.
What i've manage to understand :
From a intuitive "cryptographic" point of view : Randomly selecting unitaries/circuits allows to "hide" each instances to the "classical attacker" (who desperately wants to simulate/sample it efficiently) until the last moment, hence forcing him to be ready for each unitaries. Said differently, it forces him to compute everything without being able to take advantage of a specificity of a fixed unitary. The actual formal explanation of this lies in the $\textit{hiding property}$ of random sampling protocols see https://arxiv.org/pdf/1803.04402.pdf.
If the device is able to realise universal quantum computations, then hardness can be found in the fact that output probabilities of some instances $U$ can encode hard function s.a. the partition function of certain Ising model partition function (as in the initial Google argument). In this case how approximation of the Haar-measure with some $\epsilon$-approximate $k$-design $\{U\}^k_\epsilon$, assure us to have hard instances.
More generally, how can the link be made between a specific measure on some unitary space and the presence (up to some probability related to the measure) of hard instances.
Any relevant references are welcome.
