From: Mitchell Porter (mitch@thehub.com.au)
Date: Sun Dec 29 1996 - 19:57:43 MST
[Eliezer Yudkowsky on the uses of quantum computers]
> Think genetic programming. Current "populations" are in the 10^3-10^6
> range. With a 64-qubit QC, you could have a population of sixteen
> billion billion. Heck, with a 64-qubit QC, you could probably string
> instructions together completely at random and wind up with the most
> powerful solution immediately. Who needs evolutionary computation?
I thought along similar lines; I thought quantum parallelism would make
constraint satisfaction problems (e.g. "find a path that passes through
every vertex of this graph without intersecting itself") easy:
Just put the quantum computer into a superposition that covers every
element of the search space, and filter the superposition by asking some
yes/no question about all its elements at once.
Then I saw this thread and asked myself, "How would this actually work?",
and decided to look for expert opinion:
http://www.ph.unimelb.edu.au/~schmuel/comp/node11.html
[...] This requirement appears to be a general one: Quantum parallelism
will only yield an exponential speedup in problems whose structure avoids
the need to try exponentially many solutions. Thus, a brute force approach
to some of the hardest computational questions, known as NP-complete
problems, will not succeed with the aid of quantum parallelism. [...]
The point is that there is only a limited set of measurements you can
perform on a real quantum system. The question you ask at the "read-out"
step (e.g. "does the fitness measure exceed this cutoff?") must be
practically computable, you have to be able to get at that information.
In the case of Shor's quantum factoring algorithm, there's a specific
trick which makes it possible to find factors (see
http://www.ph.unimelb.edu.au/~schmuel/comp/node14.html). But no one
seems to know yet just what class of problems allows a speedup:
http://aerodec.anu.edu.au/~qc/open.question.html
The real future of quantum computers occurs if a general computer can be
built. This is what allowed classical computers to take off, since you no
longer needed to build a "one-task" computer (typically an analog computer).
If a general quantum computer (one that can be programmed, in some sense,
to solve many different problems on the once computer) can be constructed,
they are set to change the way computation is thought about. If not, then
basically we are stuck with building computers that can only solve a very
limited group of problems (be it very quickly), restricting their
usefullness.
One more URL: http://rosebay.matra.com.au/~gregb/q-gol//index.html
Q-gol - a high-level programming language for quantum computers!
But still buggy, it seems. Elsewhere in his web (see the "summary" page),
this guy says he's defined a whole set of generalizations of ordinary
computation (of which quantum computation is just one), including one
appropriate for time-travelling computation (in which you might have
access to information from the future).
Damien Broderick added:
> If you crossed a quantum computer with Borges's Library of Babel, it struck
> me a while back, might you destructively interfere all the `wrong'
> descriptions of physics, being left with a single Book of True Everything
> (Abridged)? I love the idea that you could turn on the infinite monkey
> machine and get out Ed Witten Mark Aleph Null.
The problem here (apart from general problems of implementation mentioned
above): what do you use as your filtering criterion, to screen out the
wrong descriptions?
-mitch
http://www.thehub.com.au/~mitch/q-comp.html
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:35:56 MST