3 ms·
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 ha
by pitpatagain 2y ago
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.
- qnleigh 2y agoDepends 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.
- gyrovagueGeist 2y agoThey likely mean on any of the current era of NISQ-like devices (https://en.wikipedia.org/wiki/Noisy_intermediate-scale_quantum_era https://en.wikipedia.org/wiki/Noisy_intermediate-scale_quant...) like this one or quantum annealers.
- hammock 2y agoDo we have any proof or evidence that such a problem even exists?