How does quantum computing fit into that basic understanding?
It's completely different. I'll get some references together and post them, but you can find a great reference to it if you look for the course notes on the quantum computing course at the Caltech Physics department.
Parallelism reduces the problem by a linear factor only, and is useless (well, not very useful) for attacking truly complex problems. When we talk about computational complexity, we can talk about a problem being a polynomial-time problem -- as the number of inputs increases, the function of the time it takes is a polynomial function. In p-time functions, the coefficients are essentially ignored because they don't change the complexity. A problem that runs in n^2 time and a problem that runs in 1000n^2 time are essentially equally complex, because the exponent overwhelms the coefficient. And the point is, parallelism affects the coefficient, not the exponent. Or to put it another way, if you have 1,000 CPUs working in parallel on a problem that would take a trillion years to finish, you've now reduced it to only a billion years. Remember, for exponential problems, it doesn't take much input at all to make the problem completely impractical to solve.
Quantum computation uses fundamentally different algorithms, oftentimes with algorithmic complexity that are orders of magnitude different. If you can take an exponential problem (i.e., one that runs in n! time) and reduce it to a polynomial time, you've really done something -- and done far more than you could do through parallelism.
