[ScottAaronson]

My favorite part of my sabbatical in Tel Aviv was having some actual time to do research. My second-favorite part was the hummus.

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.

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

[quantum_dog]

Hi Scott,

Have you seen https://arxiv.org/abs/1806.09729?

I would call that quantum deep learning, or more accurately, foundations of quantum deep learning.

[ScottAaronson]

No, I hadn't seen that paper; thanks! I don't want to comment on it without having studied it, except to mention that it doesn't make any reference to Forrelation.