Re: OT: Quantum Computing -- NOT

From: Ken Clements (
Date: Sun Aug 13 2000 - 13:48:50 MDT

Thanks, John. I recomend the book The_Feynman_Processor for the general public.


John Clark wrote:

> Franklin Wayne Poley <> 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

This archive was generated by hypermail 2b29 : Mon Oct 02 2000 - 17:35:48 MDT