/sci/ - Science & Math

>>6323888
Nearly all conventional encryption schemes are useless against a quantum computer, because quantum computers can factor prime numbers in polynomial time.

Well, gate-based ones anyway. I dunno if D-Wave's thing could do that.

>>6324242
D-Wave's architecture only works for traveling salesman problems for now.

>>6324242
>Nearly all conventional encryption schemes are useless against a quantum computer, because quantum computers can factor prime numbers in polynomial time.

CS majors and other retards belong on >>>/g/ayfish

so are classical computer going to be obsolete in the near future?

>>6324668
Nope they still do the job for the most part, I’m guessing the future set-up will be a mix of quantum computers & server farms in conjunction with cloud with classical pc's on the users end.

>>6324242
> factoring primes
Did popsci articles tell you that?

On the other hand, factoring large integers doesn't help much against AES, as an example. I do think symmetric-key crypto will be more popular.

Also, what the fuck is with all the CS hate on this boards? Surely, most CS schools suck ass, but then again, I've met more than a handful of CS majors who are smarter and better mathematicians than math majors (when facing previously unseen problems).

>>6324670
are there tasks, which will be inheritely performed better by classical computers or is it more a thing of quantum computers eing too expensive for a while

>>6324677
All undergrad CS schools suck ass. Standford for the longest time refused to even offer a CS major because there's next to nothing you can even teach them in undergrad. You should major in something else and comeback to study it in graduate school or just learn about it in your free time.

The best programs for CS are always some sort of misnamed CE/CSE/ECE hybrid programs

>>6324314
Go fuck yourself.

I'm led to believe that public/private key encryption doesn't work against quantum computers, since they can perform prime factorization much mcuh faster than conventional computers. However, I don't believe they can crack hashes any faster.

Do quantum computers even exist and run already?
I thought they were still pre-operation stage
Are we just talking about 'when they do work'

I need to read the news about these, any good articles to catch up on?

>>6325143

>>6325270
gr8 b8 m8; i r8 it 8/8

Qubits can store and calculate way more data than normal binary transistors so any function which is algorithmically computable can be run much faster on a quantum computer.

>>6325270
Kill yourself

>>6325326
>>6325426

He got you guys. you folks need to learn how to deal with trolls. present him with the board rules, specifically Global Rules #3: http://www.4chan.org/rules#global and then take appropriate steps (you know what to do). That's how you deal with trolls. by replying to him, you're just encouraging that behavior.

>>6325433
Why do you call him a troll? When did this bullshit meme start? When did people start to abuse the word "troll" denote posters they disagree with? Not every opinion is a "troll".

Quantum computers are basically (provingly) good/better at three things: a) factoring numbers, b) computing discrete logarithms, c) sorting stuff (a/b are Shor's algorithms, c is Grovers algorithm).

a) and b) will break most asymmetric crypto schemes which are currently very widely used (RSA, ElGamal..). This will not break every crypto scheme per se, since symmetric schemes such as AES or Twofish or whatever are not relying on facting primes or discrete logarithms. However, communication about the keys for symmetric schemes are usually done using asymmetric schemes and those will be broken. There are quite a lot of researchers working on quantum-"proof" schemes, though (at least until someone invents a quantum-algorithm which makes the hard-to-compute-problem which is the basis of the respective scheme easy to compute..).

>>6325377
>qubits can store and calculate way more data

this isnt why they are faster.

>>6325441

Sup troll. I see you're pissed.

You seem to be spamming this board. Examples:

>>6325270
>>6325412

These are not opinions. This is trolling spam.

>>6325441
His opinion is so extreme and so ridiculous that it's obviously not genuine, and only there to provoke people to anger.

>>6325446

Quantum computers aren't better at sorting, but rather at searching,

>>6325474
I am not that poster and I still don't see why you call him/her a "troll". If you disagree with the posts, you should post actual criticism. Yelling "troll" just makes you another shitposter.

>>6325475
How is it "extreme" or "ridiculous"? I have my reasons to share the same opinion and I see nothing wrong with it.

>>6325489
>>6325270
>>6325441
>>6324314
samefag

>>6325491
Your samefag detector must be broken.

>>6325377
>so any function which is algorithmically computable can be run much faster on a quantum computer.

Nope, there are certain problems (can't think of any from the top of my head) where it is proven that quantum computation model does not provide any asymptotic speed up.

>>6325591
BQP is low in PP

>>6325599
But BQP is not even every problem as the post is stating.

>>6325622
But it's every problem that's efficiently solvable on a quantum computer.

>>6325446
As far as I know lattice reduction problems are NP-hard even for quantum computers and there are already encryption schemes based on lattices that have been implemented (like NTRU though I'm not sure this one in particular is hard for quantum algorithms). It's rather that they are not really used since the key is usually a huge matrix which is not practical for storage.

>>6325665
Yes, efficiently. But the original message was that ANY algorithmycally computable (not only efficiently) function can be computed much faster on a quantum computer which is not the case.

On quantum computers P=NP.