[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
State Hash
Georgi Guninski <[email protected]> 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