"Although RSA factorization is considered to be an NP- hard problem if keys that fulfil the above conditions are used..."
Isn't this incorrect? The implication would be that quantum computers could solve NP-Complete problems in polynomial time.
Isn't this incorrect? The implication would be that quantum computers could solve NP-Complete problems in polynomial time.
Wikipedia has it first on their "list of problems that might be NP-intermediate", i.e. problems that are in NP but not in P or NP-hard. [0]
A quantum computer is not a Turing machine. Yes, it can solve things in polynomial time that a Turing machine cannot do. But that doesn't mean that given problem is/isn't NP hard.
That's all I'm saying... they're implying that you could reduce, say, 3SAT to factoring, which would be very very surprising.
("BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.")