I’ve read a little bit about quantum computing, but I don’t know a whole lot about the current theoretical state of the art. From a simplistic description, quantum computers sound a whole lot like nondeterministic Turing machines (at least to me). Stuff I’ve read from a couple of years ago said that it was still an open problem, but that’s all I know. Does anybody know of any theorems about where quantum computers fit into the whole P/NP/etc. picture? I know of Schorr’s algorithm for factoring numbers in polynomial time, so it seems like quantum computers might be “better” than deterministic Turing machines (well, assuming P!=NP, which I guess is dangerous). But am I not correct in thinking that a nondeterministic Turing machine would be able to factor in O(1) time?
Let me begin by saying, “um, well…”
Fact is, I don’t have a clue about your OP, but in the interest of keeping this question on the front page, I’ll point you to some recent news which I also do not understand.
http://arstechnica.com/archive/2000/0800.html slide down a little way and you will find a link-laden sketch on QC under the heading “Quantum Computing Advances.” Ars Technica is a fine site, and well worth looking over even if this doesn’t help.
I’m not sure I follow your question; I’ve never heard that quantum computing would be “non-deterministic”. As I understand it, the point of quantum computing is that by using qbits, you can apply a computing operation to all possible values of those qbits simultaneously.
Don’t you lose determinism as soon as you enter the world of quantum physics? Isn’t the whole basis of determinism the idea of A always leading to B, whereas the whole basis of quantum physics is that A will probably lead to B?
Isn’t the whole power of qbits their simultaneity? Determinism will allow discrete items to be simultaneous, but how can determinism allow a single qbit to exist in several states at the same time?
Except I’m not sure that “deterministic” means the same thing for a Turing machine (read: Normal computer) as it does for physical systems. I don’t know the answer, either (not nearly enough CS classes under my belt), but now you’ve got me wondering, too.
A non-deterministic Turing machine always makes the “right” decision at each decision point, rather than having to iterate through each possible case. The term you see often is “NP-complete” which essentially means that the algorithm can be solved in polynomial time by a non-deterministic Turing Machine. Until the advent of QM, the non-deterministic TM was a theoretical device used to distinguish between problems that are incomputable (such as the halting problem, which cannot be solved even by a non-deterministic TM) and those that were merely difficult (such as the travelling salesman problem).
To elaborate a bit, “polynomial time” means that T = S[sup]k[/sup], where T is the time to solve the problem, S is the size of the problem (such as the number of digits in two numbers to be multiplied) and k is a constant. For other problems (such as the travelling salesman problem), the time to solve the problem grows faster in relationship to its size, e.g. T = k[sup]S[/sup] or T = S!.
It is also interesting to note that all (or at least a large majority) of NP-complete problems are equivalent, including the factorization problem underlying modern encryption techniques. If you could develop a means to solve one, you would solve them all.
The apparently infinte nature of virtual quantum interactions might permit such “non-deterministic” magic; regardless of the size of the specific problem, all cases at a decision point could be evaluated simultaneously.
Joe:
I think I actually understood that! THanks for a great explanation.
Chronos is correct, there is a technical complexity-theory definition of nondeterministic. A nondeterministic Turing machine is kind of hard to describe. Basically, if, in running an algorithm, the machine has to make a choice among many different things and only one of those things is correct, a NDTM can magically always make the correct choice first. So a factoring algorithm for a NDTM is basically just “guess the factors.” A better explanation can be found at http://www.cs.columbia.edu/~thanasis/complexity/TM2.txt
It seems like a nondeterministic Turing machine should be able to do a lot of computations faster than a regular TM, but amazingly nobody has yet been able to prove that this is the case (this is the whole P=NP thing).
Slight mistake in Joe Malik’s post: He seems to be confusing NP with NP-complete. A problem that can be solved in polynomial time by a normal Turing machine is in P. One where the answer can be verified in polynomial time (or alternately, solved by a non-deterministic machine) is in NP, making P a subset of NP. A problem is NP-complete if all other NP problems can, in polynomial time, be converted to a form of that problem. If there exists any problem which is in NP but not in P (widely believed to be true), then all NP-complete problems are not in P. All NP-complete problems are, by definition, equivalent, but not necessarily all “difficult” problems. Interestingly, it turns out that determining whether a given Minesweeper position is consistent is an NP-complere problem, according to my latest Scientific American
So does anyone know if this makes quantum computers nondeterministic, or are they just really nifty deterministic devices?
Minesweeper is NP-complete!? Crap, convert some traveling salesman problems to that and let me at 'em.
My mind’s ability to deal Quantum Physics effectvly was lost several hundred beers, joints, drop and snorts ago. But As I recall quantum computing is not exactly Deterministic, and not Nondeterministic (basically what Keeve said). Rather than The classical Non-deterministic machine that chooses correctly at each point, a quantum computer changes the nature of determining so that it chooses every possible choice at the same time. Then magic happens(this may be where my mind is failing) and out of all the possible answers it “displays” the correct one. Since Non-deterministic is a stringent qualification, I would call it nifty determinisism, since it is using determinism, just in a way that classical physics doesn’t expect
You are correct, Chronos. That’s what I get for posting from work and not waiting until I get home to check my references!