[misterrobot]

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

[kamkha]

It's definitely not proven to be correct; we definitely don't know for sure that integer factorization is in NP-hard. If I remember correctly, it's generally suspected that factorization is not NP-complete (and thus outside of NP-hard).

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]

[0] https://en.wikipedia.org/wiki/NP-intermediate

[petrs]

Yes, this is an incorrect statement, sorry. It sneaked there after edits by proofreading service, but that is no excuse for us. Should be just NP. (I'm one of the authors of the paper)

[misterrobot]

Please don't apologize, this is an excellent paper! In retrospect I feel a little bad for nitpicking, honestly -- it's a really fascinating read :)

[dalke]

NP hard is defined with reference to a non-deterministic Turing machine which runs in polynomial time.

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.

[misterrobot]

That's not what I'm saying. I'm saying that if factoring were NP hard, by extension a quantum computer could solve NP complete problems in polynomial time (since every problem in NP is reducible to every NP hard problem, by definition [0]).

That's all I'm saying... they're implying that you could reduce, say, 3SAT to factoring, which would be very very surprising.

[0] https://en.wikipedia.org/wiki/NP-hardness

[dalke]

I do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp... , "The relation between BQP and NP is not known."

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

[rlanday]

Right, it’s not known. Although technically we don’t know for sure if classical computers can solve NP-hard problems in polynomial time either (that’s the P vs. NP problem).

[misterrobot]

Not to mention that being an NP hard problem wouldn't be a strong enough property to ensure the average-case was hard, so I don't think the "considered" saves this from being incorrect...