Maybe we could add in the first paragraph that quantum computers are by their very nature probabilistic devices and only probabilistic algorithms can be implemented on them. Also, quantum computers can be simulated by Turing machines and are therefore no attack to the Church-Turing[?] thesis. --AxelBoldt
In the complexity section, it says that BQP is the class of problems that can be solved by quantum computers. These however are only the problems that can be solved by quantum computers in polynomial time. Maybe you could say "the problems that can be solved by quantum computers in reasonable time" or "that can be realistically solved by quantum computers".
Then it says that quantum computers probably cannot solve all NP-complete problems. There are two problems with this statement: strictly speaking, a quantum computer only works probabilistically and cannot "solve" any NP-complete problem (or any other decision problem for that matter) in the same sense a Turing machine solves them, with a deterministic and correct Yes/No answer. Furthermore, if we allow probabilistic solutions, then quantum computers can of course solve all NP-complete problems, just like any Turing machine can; it may just take a lot of time to do so... --AxelBoldt
Also, it might be useful to mention "reversibility", the haddamard(sp?) transformation and the various types of quantum logic gates (CNOT, etc...). I'm not an expert, so I'll defer to someone who knows about this stuff -- Matt Stoker
What does it mean to have a "quantum computer with nonlinear operators"? --Robert Merkel
I hope that's clearer now. --LC
How the heck do you implement a nonlinear operation on qubits? Evolution always proceeds by unitary - therefore linear - operations. -- CYD
I agree, that seems to be a consequence of Schrodinger's equation, which is pretty basic to QM. --AxelBoldt
I agree. The papers proving the result never said it could be done. But it's an interesting result. It hasn't been ruled out that a large linear system could act like a small nonlinear system, and give the desired result. The Shi paper refers to the nonlinearity of the Gross-Pitaevskii equations, but I'm not familiar with them. I would assume the Shi paper is flawed, since it wasn't accepted anywhere, but I'm not aware of any proofs that this sort of thing is inherently impossible. --LC
Oh. I just checked the site, and the Shi paper has now been accepted in a journal. It hadn't yet been accepted when I first wrote the article. I'll remove the "not peer reviewed" note. Is anyone here familiar with the "Internation Journal of Modern Physics"? Is it generally respectable? --LC
I don't think this characterization of many worlds is correct. The different universes don't come with complex numbers attached. Instead, the more likely states are exhibited in more universes. The goal of the matrix manipulations is to bring essentially all universes into the same state. Once you measure the state, the universes stop to communicate and truly split. --AxelBoldt
Good point. I've reworded it. --LC
"The square of (a+ib) is (a^2+b^2)."
Actually the square of (a+ib) would be (a^2-b^2) + i(2ab).
Probably you mean the norm or the mod or something like that? (it's been a while since i used complex numbers, not sure of the name any more).
In quantum mechanics, (a+bi) is called the amplitude, and (a2+b2) is called the squared amplitude, even though the latter equals |a+bi|2 rather than the (a+bi)2 that the name might suggest. I suppose the terminology is counterintuitive. I'll reword the article to make it clearer. --LC
I've removed the following contribution from User:Harry Potter:
Quantum computation doesn't involve time travel in any description I've seen. -- Oliver P. 00:01 9 Jun 2003 (UTC)