Talk:Quantum computing
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