The claims in this paper are wrong. An epsilon-randomizing map requires >=(1-eps)*d unitaries to work even for a single input, since anything within trace distance epsilon of the maximally mixed state has to have rank at least (1-eps)*d.

Good point.

Even NPT n-undistillable states exist, so that's a big obstacle to anything like this.

It is not clear how the v_k vectors can be chosen in a way that guarantees they all have the desired angles with one another.

This can be done in time O(N polylog(N)) using the techniques of quant-ph/0407082 or, for qudits, using quant-ph/0601001.

The title is amazing!

This simplifies and strengthens the state-randomization result of quant-ph/0307104 (and quant-ph/0307100).

The original idea is that if you act on any pure state with a bunch of random unitaries you get a state where all its eigenvalues are within epsilon/d of 1/d. This is proved by taking an epsilon-net over all pure states and showing with the union bound that w.h.p. this holds for all states in the epsilon net.

The original paper actually took an epsilon/d net, figuring that when you move out of the net by delta, the largest eigenvalue could increase by as much as delta. The new paper shows than an epsilon-net is sufficient. This is done with a sort of bootstrapping argument. It's simple mathematically, but hard to concisely explain in words. If I were to try, I'd say that if the map is known to be weakly randomizing everywhere, then moving out of the net by delta won't hurt you by as much as delta. This in turn improves our estimates of how well the map randomizes, and we can iterate this to get a much better bound.