suvlub t1_j2hpza8 wrote
Reply to comment by AideNo621 in can someone explain the difference between quantum computing and classic computing in simpler words? how can quantum computing benefit us from a consumer perspective? by village_aapiser
>An example of a task that is very tedious for a normal computer but easy for a quantum computer is so called "traveling salesman problem".
Not true. Travelling salesman is an NP-complete problem, quantum computers can't solve those any better than classical computers. See this diagram. P is what traditional computers are good at, BQP is quantum computers.
An example of a problem that quantum computers can solve (and classical probably can't) is prime factorization.
hbrthree t1_j2hviol wrote
So previous poster is full of shit lol?
suvlub t1_j2hwusy wrote
They were largely right until the example. To be fair, this is a common mistake, for sake of simplicity, or out of laziness, P and NP-complete problems are often explained as two opposite categories without mentioning all the other ones, so when people then hear that quantum computers can (easily) solve problems outside of P, they jump to the conclusion that they can solve NP-complete problems.
Oatz3 t1_j2hwcc7 wrote
Yes, quantum still can't solve traveling salesmen
AunKnorrie t1_j2huhwx wrote
Ah, You must have had professional training in the field ;)
suvlub t1_j2hwyfk wrote
Am programmer with masters in software engineering. Quantum computing is just something I'm vaguely interested in. I'd like to learn more about it, but shit's mind-boggling.
AunKnorrie t1_j2ilrrj wrote
Perhaps I should read up myself. I have an engineering degree in IT, so I had to read about Church’ thesis. Quantum is something new to me though.
PepperMill_NA t1_j2hy886 wrote
With that comes facility at cracking encryption keys
coolthesejets t1_j2i3e3w wrote
Would you say the existence of Shors means prime factorization is definitely not in np complete?
suvlub t1_j2ibswe wrote
It's a strong indication, but we still don't have a proof that P != NP, so no, not definitely.
coolthesejets t1_j2iyep1 wrote
Oh right! Interesting thank-you.
AideNo621 t1_j2ih99i wrote
Thanks for the correction. I was only reproducing what I read about the topic.
Yamidamian t1_j2j39b2 wrote
How is prime factorization ‘unsolvable’ on a classic computer? It seems like something any programmer could pound out a simple program to do pretty easily.
It would be slow as heck for really big values, due to recursion involved, but it would eventually give a solution.
Is there some kind of math definition of ‘solved’ that I’m unfamiliar with?
suvlub t1_j2j4qhu wrote
Sorry, I was sloppy. "Solve in polynomial time" is what I meant.
Viewing a single comment thread. View all comments