[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.

[selimthegrim]

Thanks, Scott! I thought you’d missed this. Maybe we’ll get to have you give a colloquium here at Tulane someday soon!