Re: Classical and Quantum Computers

Alfredo Pereira Jr wrote
>  Nielsen and Chuang wrote (p. 6-7) that Shor's
> demonstration of two problems - finding prime factors of
> an integer and the 'discrete logarithm' one - "attracted
> widespread interest because these two problems were
> and still are widely believed to have no efficient solution
> on a classical computer. Shor's results are a powerful
> indication that quantum computers are more powerful
> than Turing machines".
> They write the same in p. 216, that some problems are
> "infeasible" or "intractable" in classical computers,
> but not in quantum computers.
> You can say it is only a matter of speed, but if you
> need infinite time to execute a function in a classical
> computer, for practical purposes they don't execute it...

Nielsen and Chuang is the textbook
M. A. Nielsen, and I. L. Chuang, ``Quantum computation and
quantum information'' Cambridge (2000).

William Seager correctly replied
> Neither example: finding prime factors and the discrete
> logarithm problem, require infinite time on a classical
> computer to solve (merely exponentially increasing time
> with size of input).

Seager went on
> I'd be interested in examples of problems we *know* can be
> solved in finite time with quantum computers but require
> infinite time on a classical computer (I've heard rumours of
> such, presumably involving a superposition of an infinite
> number of states but know of no such examples).

Jeff Medina asked
> Do you know of any specific problems that require
> infinite time on a classical computer and finite on a
> quantum? The problem with classical computers is that
> they require exponentially increasing amounts of
> finite time to solve NP problems, not that they need
> *infinite* time. I believe there's an important
> distinction there.

A paper which introduces such a problem but which does invoke
an infinite superposition in an infinite dimensional Hilbert space
is discussed by C.S. Calude and B. Pavlov, in ``Coins, Quantum
Measurements, and Turing's Barrier'' quant-ph/0112087

available from abstract at

http://arXiv.org/abs/quant-ph/0112087

``Ordinary'' finite quantum computers use only finite
dimensional Hilbert spaces.  If they could be build, then they
would be exponentially more efficient than classical
computers, but would be simulable by classical Turing
machines.

There are two distinct issues of practicality here.

No forseeable conventional classical computer can factorize
arbitrary 100 digit numbers, but that doesn't mean that I can't
give you a simple classical algorithm that solves the problem
in theory:

(take the number, generate primes up to its square root, do trial
divisions until you've finished.)

This algorithm uses something like root N steps, where N is the
100 digit number, so it is impractical.

In theory, using Shor's algorithm, a finite quantum computer
could factorize the number in something like  log N = 100 steps.

(Actually, it is a power of log N rather than log N, but this  is
not important.)

The practical problem with quantum computers is to build the
things.  The fact that the state of the art allows us to factorize
15 shows how difficult this is.

Building Calude and Pavlov's infinite ``quantum computer'' would
be all the more difficult.  In fact, I hardly think it worth
considering unless we can get a lot further down the road
towards useful finite quantum computers.

The Church-Turing thesis says that all computation and
information-processing can be performed by finite replicable
stable systems.  This is a wonderful idea and it pulls ideas
of computation and mathematics and intelligence out of the
realm of magic and into the realm of engineering.

The present understanding of finite quantum computation is
also out of the realm of magic.  That is why, if you suppose
that brains use such computation,  you need to answer detailed
questions about what the computation is computing, what
processes are involved in it, and how those processes could have
evolved.

Two interesting papers on the subject which are relevant to
the present discussion are:

``Quantum Computation'' by Dorit Aharonov, quant-ph/9812037
available from

http://arXiv.org/abs/quant-ph/9812037

This is a reasonably self-contained long review.

``Quantum computing: a view from the enemy camp'' by
M.I. Dyakonov,  cond-mat/0110326, available from

http://arXiv.org/abs/cond-mat/0110326

Dyakonov argues that no working (finite) useful large-scale
quantum computer will be built in the forseeable future.  I think
that many of Dyakonov's arguments are plausible, and I think
that they apply a fortiori to the difficulties of evolving useful
biological quantum computation.



Matthew Donald ([EMAIL PROTECTED])
web site:
http://www.poco.phy.cam.ac.uk/~mjd1014
``a many-minds interpretation of quantum theory''

 ***************************************************