Hi Scott - What was the best part/most favorite thing about your sabbatical? Can you explain why Forrelation is a guiding light for quantum deep learning these days? As a bonus - it would be nice to see a walkthrough - commentary of the recent oracle separation proof of Tal and Raz and how they used Fourier transforms specifically.
Forrelation is not a “guiding light for quantum deep learning.” I’m not even sure if there’s such a thing as “quantum deep learning” that’s sufficiently well-developed to deserve the name. You can use Forrelation as a separating example for some other quantum learning problems, e.g. k-means clustering, but so far that mostly just shows that you can artifically shoehorn an exponential quantum speedup into those tasks, rather than that the tasks will give us useful quantum speedups in “real life.”
In the Forrelation problem, I conjecture that the only thing that really matters about the Fourier transform is that it’s a unitary matrix all of whose entries have small absolute values. As such, it lets you relate two Boolean functions in a way that a quantum computer can notice, but that’s extremely “global” in nature and doesn’t show up locally. Raz and Tal may have used some additional technical properties of Forrelation in their proof (now that I write that, I’m actually not sure—I’ll need to check!). But if they did, then I conjecture that another proof could avoid the use of those properties.