[HN Gopher] No distributed quantum advantage for approximate gra...
___________________________________________________________________
No distributed quantum advantage for approximate graph coloring
Author : nabla9
Score : 61 points
Date : 2023-12-08 12:35 UTC (10 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| flanfly wrote:
| Good news for cryptographers in case we need an alternative to
| LWE and coding-based PQC.
| da-bacon wrote:
| I'm not sure this implies much about PQC. The model here is
| LOCAL distributed computing which is pretty far from what
| you're concerned about in PQC.
| nabla9 wrote:
| 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.
| jimsimmons wrote:
| n00b question: what are some important problems for which quantum
| computation has shown to have an advantage
| mebassett wrote:
| factoring large integers into primes (shor's algorithm). that
| and grover's search promise to provide ways to crack a lot of
| encryption.
|
| also quantum computing should improve both classical and
| quantum physical simulations.
| vitus wrote:
| 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.
| erikaww wrote:
| 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.
| pclmulqdq wrote:
| 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.
| NooneAtAll3 wrote:
| you aren't the first asking, so someone made a website listing
| stuff
|
| https://quantumalgorithmzoo.org/
| cevi wrote:
| 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 kh, in this setting it is
| trivial to find a kh-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
| m3kw9 wrote:
| Why are they trying to colour graphs with quantum computers? Just
| reading the title
| david_draco wrote:
| 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.
| cochne wrote:
| NP hard problems aren't all equivalent, that's NP complete.
___________________________________________________________________
(page generated 2023-12-08 23:01 UTC)