Talk:Quantum computer

Great article!

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

---

I've now added both. They're in the complexity theory section, where they seemed to fit the flow best. -LC

---

Yes.

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

---

It should be clearer now. -LC

---

What is this #P-Complete ? --Taw

---

See #P-Complete. -LC

---

How long does it take to factor an n-digit number with n qubits? --Axel

---

Would Quantum Computing break Elliptic Curve Cryptography ? Taw

Apparently so, through a variation on Shor's algorithm. I haven't studied it, though -- CYD

---

Some recent work [1] (http://www.eet.com/story/OEG20010924S0101) indicates that if spaced sufficiently closely, quntum entanglement between quantum dots may be possible, so it's possible that in the future a quantum computer could be implemented using quantum dots.

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

---

The quantum computer in the above example could be thought of as a black box containing 8 complex numbers. Or, it could be thought of as 8 black boxes, each containing 1 complex number, each sitting in a different alternate universe, and all communicating with each other. These two interpretations correspond to the Copenhagen interpretation and many worlds interpretation, respectively, of quantum mechanics. The choice of interpretation has no effect on the math, or on the behavior of the quantum computer. Either way, it's an 8-element vector that is modified by matrix multiplication

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

---

In the "How they work" section it says:

"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 (a²+b²) is called the squared amplitude, even though the latter equals |a+bi|² rather than the (a+bi)² 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 computing can also theoretically produce time anomalies. The ability of the Quantum computer to find the correct answer in a factorisation problem can be seen as running all the possibilities simultaneously. However, only the correct answer produces a positive response which is then sent back through time to become the only calculation which in fact needs to be made.

Quantum computation doesn't involve time travel in any description I've seen. -- Oliver P. 00:01 9 Jun 2003 (UTC)

Agreed. This sounds purely abstract and theoretical to me, but I am no expert on quantum computing by any means. Perhaps Harry Potter can produce a source in the quantum computing literature that lends some support to this idea? -- Wapcaplet 00:10 9 Jun 2003 (UTC)