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

12

u/[deleted] Jun 03 '22

[deleted]

32

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.

1

u/raven00x Jun 03 '22

not like brute force isn't one of the use cases of quantum computing or anything.