Alexander Klimov wrote:
A problem with this reasoning is that the physical world and the usual digital computers have exponential simulation gap (it is known at least in one direction: to simulate N entangled particles on a digital computer one needs computations exponential in N). This can be considered as a reason to suspect that physical world is non-polynomially faster than the usual computers (probably even to an ^^^^^^^^^^^^^^^^^^^ extent that all NP computations can be simulated). ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
It is a commonly-held myth that quantum computers could solve NP-complete problems, but most experts who have studied the issue believe this is probably not the case. There is no reason to think that quantum computation could solve all NP problems in polynomial time, and in fact, there are good reasons to believe this is likely not the case. (Do note that factoring is not NP-complete.) See, e.g. http://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_com... or for a more nuanced and deep treatment of these issues, http://www.scottaaronson.com/papers/npcomplete.pdf --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE