News for hackers. Stuff that matters.
Re:I'm Scott Aaronson, quantum computing/computational compl... by selimthegrim on Friday June 29, 2018 @01:36PM (#17426079)
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.

Re:I'm Scott Aaronson, quantum computing/computational compl... by ScottAaronson on Saturday June 30, 2018 @04:37PM (#17432634)
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.

Re:I'm Scott Aaronson, quantum computing/computational compl... by ScottAaronson on Sunday July 01, 2018 @08:20AM (#17435303)
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.
Re:I'm Scott Aaronson, quantum computing/computational compl... by selimthegrim on Sunday July 01, 2018 @07:14PM (#17438242)
Thanks, Scott! I thought you’d missed this. Maybe we’ll get to have you give a colloquium here at Tulane someday soon!
Re:I'm Scott Aaronson, quantum computing/computational compl... by quantum_dog on Sunday July 01, 2018 @05:21PM (#17437675)
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.

Re:I'm Scott Aaronson, quantum computing/computational compl... by ScottAaronson on Monday July 09, 2018 @03:02PM (#17492580)
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.