At first, the results claimed here seem to clash with the fact that we know, for instance, that it is NP-hard to 5-color a graph which is promised to be 3-colorable [1]. Of course, the devil is in the details - on page 11, where they describe the "LOCAL" computation model they work in, they explain:
"In each round the processors may perform unbounded computations on their respective local state variables and subsequently exchange of messages of arbitrary size along the links given by the underlying input graph."
Given this setup, it should be possible to solve any problem in O(n) rounds, and indeed they point this out in the introduction:
"If the chromatic number of G is χ, in this setting it is trivial to find a χ-coloring in T = O(n) rounds, as in O(n) rounds all nodes can learn the full topology of their own connected component and they can locally find an optimal coloring by brute force without any further communication."
While this paper is very interesting from a theoretical perspective, it is saying more about the LOCAL model of distributed computing than it is about quantum computing. Nobody should come away from this with the conclusion that we have somehow proved that quantum algorithms are useless for real-world problems.
The assumption that output distributions don't violate the no-signaling from the future principle may be a useful abstraction, but it seems a little too neat for real-world quantum interactions. It's a model, not physical reality. Also, the necessity of knowing specific graph parameters in advance could limit the usability of these algorithms in unpredictable distributed systems.
It is not known if there is there any graph problem that someone cares about for which there exist algorithm with distributed quantum advantage?
For many graph problems it's possible show to show that there is no quantum advantage by by defining a model so that it can do anything except violating causality.
This paper shows that approximate graph coloring has not quantum advantage.
The other side of Shor's algorithm is that you can use it to solve discrete logarithm (which additionally breaks elliptic curve crypto; factoring breaks RSA).
I don't agree that Grover's algorithm is as fundamental in breaking encryption, since it "only" yields a quadratic speed-up. You'd have similar effective security as in the pre-quantum world by doubling the key length; you could do this by, say, switching to AES-256 instead of AES-128. Meanwhile, switching from RSA-2048 to RSA-4096 only helps if it means the problem size now exceeds the size of the biggest quantum computers.
I think there is promise with tons of optimization problems (machine learning, approximating differential equations). I hope these would be significantly faster in practice.
It would be cool if we had quantum accelerated game physics engines. Super realistic games that are fast.
Simulations could scale better, so we could make them a lot more useful.
Unless you are simulating quantum effects, these sorts of simulations are unlikely to be faster on a quantum computer. Also, attempts at using the Ising model for general-purpose optimization have found themselves somewhat limited in application.
For people doing drug discovery and quantum physics/chemistry research, they will see an exponential speedup from quantum computing, but I think you're overstating how applicable this technology is.
I suspect the point is that all NP-hard problems are equivalent to each other, often one can be transform one NP-hard problem to another. This shows that quantum will not save us. This is bad but also good for encryption. NP remains an important topic post-quantum that cannot be hand-waved away.
"In each round the processors may perform unbounded computations on their respective local state variables and subsequently exchange of messages of arbitrary size along the links given by the underlying input graph."
Given this setup, it should be possible to solve any problem in O(n) rounds, and indeed they point this out in the introduction:
"If the chromatic number of G is χ, in this setting it is trivial to find a χ-coloring in T = O(n) rounds, as in O(n) rounds all nodes can learn the full topology of their own connected component and they can locally find an optimal coloring by brute force without any further communication."
While this paper is very interesting from a theoretical perspective, it is saying more about the LOCAL model of distributed computing than it is about quantum computing. Nobody should come away from this with the conclusion that we have somehow proved that quantum algorithms are useless for real-world problems.
[1] https://arxiv.org/abs/1811.00970