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 459465
To view parent comment, click here.
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

RE[5]: Niche product?
by tylerdurden on Sun 23rd Jan 2011 21:14 in reply to "RE[4]: Niche product?"
tylerdurden Member since:
2009-03-17

It may take O(1) (not really but I will play along) to "solve" a single problem instance after it has been mapped, but you still need to MAP the problem to the quantum solver for each instance. And the mapping process/problem is definitively not O(1), or even P for that matter, in terms of complexity. There are 3-sat solvers for example which compute solutions in P time, as long as the mapping process is ignored.

Which is why I said that the speed of the computer is irrelevant when trying to prove that P=NP.

Edited 2011-01-23 21:15 UTC

Reply Parent Score: 2

RE[6]: Niche product?
by GeorgesBraque on Sun 23rd Jan 2011 22:15 in reply to "RE[5]: Niche product?"
GeorgesBraque Member since:
2005-07-07

It may take O(1) (not really but I will play along) to "solve" a single problem instance after it has been mapped, but you still need to MAP the problem to the quantum solver for each instance. And the mapping process/problem is definitively not O(1), or even P for that matter, in terms of complexity. There are 3-sat solvers for example which compute solutions in P time, as long as the mapping process is ignored.

Which is why I said that the speed of the computer is irrelevant when trying to prove that P=NP.


I think that quantum computing cannot ever apply to proving P=NP or P!=NP because complexity theory is predicated on running programs on deterministic machines. Quantum machines would be non-deterministic.

Also, just for fun, check this out (if you haven't already):

http://science.slashdot.org/story/11/01/21/2047229/Eulers-Partition...

Reply Parent Score: 1