Linked by Hadrien Grasland on Sun 23rd Jan 2011 17:30 UTC, submitted by fran
Hardware, Embedded Systems "Scientists from Oxford University have made a significant step towards an ultrafast quantum computer by successfully generating 10 billion bits of quantum entanglement in silicon for the first time -- entanglement is the key ingredient that promises to make quantum computers far more powerful than conventional computing devices."
Thread beginning with comment 459447
To view parent comment, click here.
To read all comments associated with this story, please click here.
RE[2]: Niche product?
by GeorgesBraque on Sun 23rd Jan 2011 18:15 UTC in reply to "RE: Niche product?"
GeorgesBraque
Member since:
2005-07-07

A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*.


In this way, quantum computing (which is a completely different computing paradigm) would allow NP problems to be solved in P time on a quantum computing device. In order to confuse symbolic logicians everywhere, I propose P time on a quantum computing machine be cannonicly called QP (or maybe C3PO).

Reply Parent Score: 1

RE[3]: Niche product?
by tylerdurden on Sun 23rd Jan 2011 19:05 in reply to "RE[2]: Niche product?"
tylerdurden Member since:
2009-03-17

Not really.

The proof of P=NP does not depend on the speed or parallelism of the computer. Today, you can solve some NP problems very fast, esp. using FPGAs, with careful mapping. It is the "careful mapping" part which is also pertinent to quantum computers, and which makes the proof still elusive.

Reply Parent Score: 3

RE[4]: Niche product?
by GeorgesBraque on Sun 23rd Jan 2011 20:39 in reply to "RE[3]: Niche product?"
GeorgesBraque Member since:
2005-07-07

Not really.

The proof of P=NP does not depend on the speed or parallelism of the computer. Today, you can solve some NP problems very fast, esp. using FPGAs, with careful mapping. It is the "careful mapping" part which is also pertinent to quantum computers, and which makes the proof still elusive.


It's not a matter of speed, but of complexity. If it is always O(1) to look at all branches of a solution path simultaneously (as it is in theory with a quantum computing device), then NP problems can be solved in P time on a quantum computing device. In essence, quantum computing simulates non-determinacy in that instead of an oracle function revealing the correct path, all paths are considered simultaneously (without increasing the complexity).

Reply Parent Score: 1