Hacker News Reader

Comment by anderskaseorg | Hacker News Reader

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.

View on HN

Agreed. 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 (discussed https://news.ycombinator.com/item?id=11186640 )

[2] https://www.pnas.org/content/113/23/E3187

EDIT: it is _really_ neat engineering though. EDIT2: Old HN link & grammar

Figure 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.

That 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.

I wonder if you could use the same principle as quantum radar to mitigate that problem?

Almost :) Isn't the history of breakthroughs filled with almost?

I 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.

You'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'....

Reply on news.ycombinator.com