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."
RE[8]: Niche product?
by GeorgesBraque on Sun 23rd Jan 2011 22:53 UTC in reply to "RE[7]: Niche product?"

Member since:
2005-07-07

But by proving that NP=P is the only way you can substantiate claims that an NP problem can be solved in P time using Quantum computers. Which was the gist of the discussion we've been having.

Quantum computer may help make part of an NP computation deterministic, but that does not mean that NP problems become deterministic in the least.

P time is not the same as the class P.

P time means solvable in polynomial time.

The class P is the set of problems solvable in polynomial time on a deterministic machine. The class NP is the set of problems solvable in polynomial time on a non-deterministic machine.

NP problems are often O(N!) or O(N^N) or worse on deterministic machines. However, they most likely are solvable in P time on quantum computing machines. This does NOT mean that P=NP because quantum computing machines are NOT deterministic.

RE[9]: Niche product?
by magni on Tue 25th Jan 2011 04:47 in reply to "RE[8]: Niche product?"
Member since:
2011-01-25

NP problems are often O(N!) or O(N^N) or worse on deterministic machines. However, they most likely are solvable in P time on quantum computing machines. This does NOT mean that P=NP because quantum computing machines are NOT deterministic.

This is a common misunderstanding about the power of quantum computers.

When you talk about problems solvable in P time on quantum computers, I guess you mean the complexity class BQP. However, today the question of weather BQP=NP is as open as the P=NP question.

Or to quote Scott Aaronsson "Quantum computers are not known to be able to solve NP-complete problems in polynomial time."