Franklin Wayne Poley <culturex@vcn.bc.ca> Wrote:
> Could you please explain "more than polynomial time" and
> "superposition" for us laymen?
I'll give the readers digest condensed version. Let's say X is a problem a
computer can solve, now let's increase the number of variables in the problem,
can the computer still solve it before the sun burns out? If the time to solve the
problem only increases as X^n where n is any integer then we say problem is in
polynomial time and solvable; but if the time to solve the problem increases as
n^X it's exponential and not solvable with a normal computer because just a small
increase in the number of variables yields a huge increase in the time to solve it.
The reason people get excited about Quantum Computers is that when a conventional
64 bit single processor computer performs an operation, it does it on one 64 bit number
at a time. When a 64 bit (actually a 64 qubit) single processor Quantum Computer
performs an operation the numbers are in superposition so it operates on all 64 bit numbers
at the same time, all 2^64 of them, more than a billion billion, and any increase in the number
of qubits the computer can handle will increase its already astronomical power exponentially.
John K Clark jonkc@att.net
This archive was generated by hypermail 2b29 : Mon Oct 02 2000 - 17:35:48 MDT