Viewing a single comment thread. View all comments

suvlub t1_j2hpza8 wrote

>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.

54

hbrthree t1_j2hviol wrote

So previous poster is full of shit lol?

12

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.

25

Oatz3 t1_j2hwcc7 wrote

Yes, quantum still can't solve traveling salesmen

8

AunKnorrie t1_j2huhwx wrote

Ah, You must have had professional training in the field ;)

4

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.

11

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.

3

coolthesejets t1_j2i3e3w wrote

Would you say the existence of Shors means prime factorization is definitely not in np complete?

4

suvlub t1_j2ibswe wrote

It's a strong indication, but we still don't have a proof that P != NP, so no, not definitely.

4

AideNo621 t1_j2ih99i wrote

Thanks for the correction. I was only reproducing what I read about the topic.

3

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?

1

suvlub t1_j2j4qhu wrote

Sorry, I was sloppy. "Solve in polynomial time" is what I meant.

1