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."
Permalink for comment 459465
To read all comments associated with this story, please click here.
RE[4]: Niche product?
by GeorgesBraque on Sun 23rd Jan 2011 20:39 UTC 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