Catullus's Journal: A quantum computation FAQ

Here are some answers to frequently asked questions on Slashdot about the field of quantum computation. If you have any more questions, please post them as comments below.

What resources are available for me to learn about quantum computation?

The best resource is the book "Quantum Computation and Quantum Information" by Nielsen and Chuang. There are also several good sets of lecture notes available online. My favourite introduction (for computer scientists) is Abbas Edalat's lecture notes. John Preskill's lecture notes are excellent, but tougher going.

Can quantum computers solve NP-complete problems?

It is not known whether quantum computers can solve NP-complete problems (such as graph colouring or satisfiability) quickly. So far, nobody has come up with a quantum algorithm to solve such problems, and there is some evidence that quantum algorithms cannot solve NP-complete problems. However, proving this would imply that P != NP, which is the most important unsolved problem in theoretical computer science. So don't hold your breath for a proof.

(more to be added later...)