A Problem That Only Quantum Computers Will Ever Be Able to Solve

> Here’s the problem. Imagine you have two random number generators, each producing a sequence of digits. The question for your computer is this: Are the two sequences completely independent from each other, or are they related in a hidden way (where one sequence is the “Fourier transform” of the other)?

and then

> The new paper by Raz and Tal proves that a quantum computer needs far fewer hints than a classical computer to solve the forrelation problem. In fact, a quantum computer needs just one hint, while even with unlimited hints, there’s no algorithm in PH that can solve the problem.

At the risk of someone winning buzzword bingo, this feels very AGI-esque. It seems to me that right now, our best classification algorithms are very bad at extrapolating related patterns on sequences that are related, but that the classifier has never seen. Or, more clearly, it is bad at correlating pattern unless the success heuristic has been tuned to look for it. If we have proved that classical computers cannot escape their heuristic, but quantum computers could (i.e. "dear computer, find related patterns, ready, go"), that seems like a very compelling reason to dump money into quantum computers.

Anyone more knowledgeable care to temper my excitement?

Dupe: https://news.ycombinator.com/item?id=17368493

I'll copy the first comment by fyi1183

> This is basically the TCS version of a clickbait headline. It's a separation of BQP and PH by an oracle. Certainly a nice result, but to put it into context, we also have a separation of P and NP by an oracle. Yet, we are very far away from actually proving that P and NP are distinct.