Comment by ScottAaronson

Just as a quick followup: Avishay Tal has confirmed for me that, indeed, their proof still goes through if you replace the Fourier transform by any other unitary matrix with bounded entries.