Author: Wyrmwood (---.psu.edu)
Date: 04-04-2003 08:34
Several concerns on this article:
1) The travelling salesman problem is usually formulated as NP-hard. This makes the problem essentially unsolvable in polynomial time by any deterministic computer, baring the unlikely discovery that deterministic computers are no less capable than non-determinisitic ones (i.e. P = NP). In particular, there is a common implication that quantum computers are equivalent to nondeterministic ones, last time I checked that is an open problem.
For those who know nothing about these complexity issues, the easiest description of a nondeteterministic computer is one that can make a finite number of guesses, which are guaranteed to be correct. Quantum computers can do this by superimposing all possible options for the guess, but it's unclear if any possible answer can be extracted when the system is measured (and hence reduces to classical bits of information). Most quantum algorithms involved being very clever about how the superpositions are measured.
2) The engineering problems of qubits aside there is still one very important theoretical question, at which point do a collection of quibits act collectively classical, and essentially lose their quantum utility?
3) One of the interesting elements of quantum computers is that ultimately all powerful algorithms end up being probabilistic. In factoring this can be handled by simply trying the answer to see if it works. With code-breaking the effects can be less to one's liking. Quantum computers are necessarilly very sensitive, and fundamentally unreliable. While error checking methods can help, this should feature strongly in any game extrapolations. After all, there is a good reason why people will likely never need a quantum desk top, even if it becomes feasible to do so.
-Wyrmwood
|
|
