>http://www.ph.unimelb.edu.au/~schmuel/comp/node11.html
>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 author is guessing, nothing wrong with that but I think he should make it
clear that's what he's doing, he can't even know that's true for the old
fashioned computers we have today. For all we know it's possible to easily
solve NP-complete problems on a single processor conventional computer if you
have the right algorithm; personally I doubt it, but its never been proved to
be impossible. There is an enormous amount of stuff in this area we know
nothing about, we have found some problems that we can prove are at least as
difficult to solve as any NP problem, and we call these NP complete,
but maybe all NP problems are NP-complete, then again maybe not.
An NP problem is a problem that can be solved in polynomial time on a
nondeterministic Turing machine, a Turing machine that can make a lucky guess.
For example, there probably is not an algorithm that can factor a large number
in polynomial time, but if I was to guess what the factors were, we know for
sure that there is an algorithm to check if I was right or not and do it
polynomial time, so factoring is an NP problem. It is not known if factoring
is an NP-complete problem or not. One of the greatest unsolved problems in
Mathematics is, does P = NP, is there an algorithm that can solve NP problems
in polynomial time? Most are confident that P is NOT equal to NP, but its
never been proven and if they're wrong then we wouldn't need Quantum
Computers, regular ones would do.
>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 Shor's factoring algorithm, wrong answers interfere destructively and
correct answers interfere constructively.
>http://aerodec.anu.edu.au/~qc/open.question.html
>The real future of quantum computers occurs if a general
>computer can be built. [...] 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.
Even if a Quantum Computer can never do anything except act as one of
Seth Lloyd's Universal Quantum Simulators (see August 23 1996 Science) that
alone would be more than enough to change the world thank you very much.
John K Clark johnkc@well.com
-----BEGIN PGP SIGNATURE-----
Version: 2.6.i
iQCzAgUBMsdX2H03wfSpid95AQGCOwTva5AFL2UIbxhXYpwN2Zi4Se5lAwWH6T/5
Q8SL+SlCgOIS8gWXz3lkDmRy3l7TLDS111Df+g+B8Sql5brXH/fcdaT7HA5bs3Ja
eGG+WhQjCgKa8hVe0IKo7SKWebPozPnZ35pSiFneq/RsqL6zKWie3Pj4yq1/JpQG
dJVaeNUUYeNTkk03+4t5maxqvj5DYJ6u9YGI7GyGqxUdcprsp6A=
=nwFG
-----END PGP SIGNATURE-----