Tim Gowers this morning recommended Scott Aaronson’s notes for a lecture course ‘Quantum computing since Democritus.’ I’m half way through, and the notes are a great read and highly illuminating. So I add my recommendation, if you want to get to know more about computational complexity and about quantum mysteries too. (Aaronson also has a fun blog.)