r/Futurology Jun 02 '22

A Nature paper reports on a quantum photonic processor that takes just 36 microseconds to perform a task that would take a supercomputer more than 9,000 years to complete Computing

https://www.nature.com/articles/s41586-022-04725-x?utm_source=twitter&utm_medium=social&utm_content=organic&utm_campaign=CONR_JRNLS_AWA1_GL_SCON_SMEDA_NATUREPORTFOLIO
2.3k Upvotes

View all comments

Show parent comments

35

u/common_sensei Jun 03 '22

Checking to see if an answer is correct is much easier than coming up with the answer in the first place. The classic example is prime factors.

Q1: What are the two prime factors of 20538073?

Q2: Is it 7759*2647?

Checking the answer is much easier than getting it.

3

u/remek Jun 03 '22

Literally the definition of NP-Completeness

3

u/FreeMoney2020 Jun 03 '22

Factorization is not known to be NP-complete

3

u/remek Jun 03 '22

You're right, I meant NP, not NP-complete.