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
