Hacker News Reader

Because we don't currently know a problem like this that both has a quantum algorithm we can run on this type of device with expected exponential speedup and has a fast classical verification algorithm. That's exactly the author's point/he has been advocating for quite a while the importance of researching such an example that would be better to use.

View on HN

Depends on what you mean by "this type of device." Strictly speaking there are many efficiently verifiable quantum algorithms (including Shor's algorithm, the one that breaks RSA). But if you mean "this particular device," then yes, none are simple enough to run on a processor of this scale.

They likely mean on any of the current era of NISQ-like devices (https://en.wikipedia.org/wiki/Noisy_intermediate-scale_quant...) like this one or quantum annealers.

Do we have any proof or evidence that such a problem even exists?

Reply on news.ycombinator.com