Linked by Hadrien Grasland on Sun 23rd Jan 2011 17:30 UTC, submitted by fran

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

To view parent comment, click here.

To read all comments associated with this story, please click here.

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.

RE[4]: Niche product?

by GeorgesBraque on Sun 23rd Jan 2011 20:39
in reply to "RE[3]: Niche product?"

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

Member since:

2005-07-07

In this way, quantum computing (which is a completely different computing paradigm) would allow

NPproblems to be solved inPtime on a quantum computing device. In order to confuse symbolic logicians everywhere, I proposePtime on a quantum computing machine be cannonicly calledQP(or maybeC3PO).