From: Stirling Westrup (sti@cam.org)
Date: Sat Mar 25 2000 - 07:13:30 MST
Robert J. Bradbury wrote:
> It is unclear (to me) at this time whether quantum computers have any uses
> other than for producing rapid solutions for a limited set of problems. I
> know of nothing that has equated a quantum computer to a turing machine,
> which if I recall can compute anything that is computable. [Someone correct
> me if this is wrong.]
Quantum computers can be described by Quantum Turing Machines which are an
extension of Probabalistic Turing Machines, which are themselves an
extension of Universal Turing Machines. Any one of these machines can be
used to simulate any other, albeit at a potentially exponential slowdown.
There are results that show that there are problems such that the slowest
quantum computer can solve them faster than the fastest classical
computer, but this is essentially just a proof that for any K, there is a
value X such that e^X is greater than XK. The reason that you haven't seen
many papers about this is that they predate the web, but lately a few of
the foundational papers have been put on line. Check out:
Richard P. Feynman, "Simulating Physics with Computers",
International Journal of Theoretical Physics,
Vol. 21, Nos. 6/7, 1982, pp. 467-488
---
Feynman's seminal paper in which he argues that quantum physics cannot be
modeled efficiently on classical computers, and that quantum computers
will do a better job in this respect. As far as I know, this is the first
ever mention of quantum computers.
<No URL known>
David Deutsch, "Quantum Theory, the Church-Turing Principle, and the
Universal Quantum Computer",
Proceedings of the Royal Society of London, Vol. A400, 1985, pp. 97-117
---
The first description and discussion of the Quantum Turing Machine, and reformulation
of the Church-Turing thesis. Quantum parallelism is discussed too.
<http://www.qubit.org/resource/deutsch85.pdf>
> Nano-assembly can build anything that can be assembled (a different problem
> from computed). The current problem with quantum computers is that you
> need a bench full of equipment to get a couple of qubits. Nanoassembly
> might shrink this somewhat but how much remains very unclear.
There has been some good work done recently in Solid-State quantum gates,
which seem to indicate that qubits will be able to be made on a scale
similar to that for wafer fabrication. There are huge technological
hurdles to be overcome first, but these result are promising:
<http://www.techweb.com/wire/story/TWB19990706S0023>
--
Stirling Westrup | Use of the Internet by this poster
sti@cam.org | is not to be construed as a tacit
| endorsement of Western Technological
| Civilization or its appurtenances.
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:27:38 MST