I wrote about this below -- the speedup comes from interference among amplitudes (the complex numbers that replace probabilities in quantum mechanics). The goal, with every quantum algorithm, is to choreograph a pattern of interference wherein the contributions to the amplitude of each wrong answer cancel each other out, whereas the contributions to the amplitude of the right answer reinforce each other. This is a really weird hammer Nature gave us -- one that I doubt any sci-fi writer would've had the imagination to invent -- and it wasn't obvious a priori that it would be good for anything, other than simulating quantum mechanics itself.