4 ms·
The problem with using a classical computer to solve an NP-hard problem is that as the problem size increases, in the worst case, as far as we know, the running
by anderskaseorg 7y ago
The problem with using a classical computer to solve an NP-hard problem is that as the problem size increases, in the worst case, as far as we know, the running time increases exponentially.
The problem with using a photonic computer to solve an NP-hard problem is that as the problem size increases, the amount of light at the output node drops exponentially. Even under the assumption that you can get rid of all background noise, that means you need to run your detector for longer so as to be able to detect the output photons, and…the running time increases exponentially.
Perhaps there are interesting quantum effects that could be exploited, but the authors specifically note that they aren’t doing that.
So this is a neat engineering project but an almost certainly irrelevant computational project.
- scythe 7y agoFigure 3 does indeed show an exponential time complexity, but the base exponent is much smaller than for a classical computer. That is an asymptotic improvement at least.
- anderskaseorg 7y agoThat figure is extrapolated based on the longest photon path length through the device. It isn't based on real experimental results (the device was demonstrated with n = 4), and it does not take into account the exponential quantity of photons you'd need to pump through the device before getting a measurable result. Fundamentally, there's nothing this device is doing that a classical computer couldn't, so there's no reason the exponential base should be any different under physically realizable conditions.
- yagyu 7y agoAgreed. Moreover, the physical size of the device will grow exponentially with problem size, so manufacturing will be impractical. The device is small only for simple instances of the SSP. But for those instances you could simulate the device in a few lines of code on a classical computer :) In fact, this device is based on earlier work on a biological computer [1] which suffers from the same drawbacks [2]. [1] https://www.pnas.org/content/113/10/2591.short https://www.pnas.org/content/113/10/2591.short (discussed https://news.ycombinator.com/item?id=11186640 https://news.ycombinator.com/item?id=11186640 ) [2] https://www.pnas.org/content/113/23/E3187 https://www.pnas.org/content/113/23/E3187 EDIT: it is _really_ neat engineering though. EDIT2: Old HN link & grammar
- tudorw 7y agoAlmost :) Isn't the history of breakthroughs filled with almost?
- wyattpeak 7y agoI don't know if breakthroughs often start with something being almost certainly irrelevant, but the converse - that something being almost certainly irrelevant tends to lead to a breakthrough - is certainly false. Things which are almost certainly irrelevant tend to end up being irrelevant.
- tudorw 7y agoYou're probably right, although for a single word, it's a powerful one, 'Sir, your certainly going to die tomorrow' Vs 'Sir, you're almost certainly going to die tomorrow'....
- deleted 7y ago[deleted]
- mrfusion 7y agoI wonder if you could use the same principle as quantum radar to mitigate that problem?