On 28/05/11 03:37, James A. Donald wrote:
What can be said is that the class of problems soluble by a quantum computer
is larger than the class of problems soluble by a classical computer.
On 2011-05-29 9:01 AM, David-Sarah Hopwood wrote:
No, it can't:
- for idealized quantum and classical computers (with unbounded memory
running for unbounded time), those classes are identical.
- for quantum and classical computers that can be practically built at any
point in time, and with a limit on the time to find a solution, it
certainly isn't clear that the class of problems soluble by quantum
computers will be larger (ever). That depends on how big and fast you
can make quantum computers and classical computers.
What can be said is that the class of problems soluble by a quantum
computer with a polynomially large number of components in polynomial
time is larger than the class of problems soluble by a classical
computer with a polynomially large number of components in polynomial time.
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
