![](https://secure.gravatar.com/avatar/635e272382797fde6f1730cf108bb0b0.jpg?s=120&d=mm&r=g)
8 Oct
2014
8 Oct
'14
3:48 p.m.
Georgi Guninski <guninski@guninski.com> wrote:
second, it is not known even if P ≠ NP, can a sufficiently powerful quantum computer solve SAT efficiently? -- if the answer is ``yes'' djb & co fail.
And yet a quantum computer efficiently solving SAT would be substantially more surprising than P=NP! Quantum computation is not magic; the limits of quantum mechanics already imply relatively strong lower bounds for quantum hash collision search. -=rsw