We have gotten to the point where we can consider quantum computing. First we need to go over the mathematical physics we need. On the one hand, the math we need is mostly just ordinary linear algebra -- although it's most generally carried out in an infinite-dimensional space called Hilbert Space -- and we will need only a small part of the mathematical machinery. On the other hand, problems of measurement and interpretation are still hotly debated by physicists.
After covering what we need, my strategy is to start with what is
usually considered the simplest example of something that can be
done more efficiently with a quantum mechanical model than with
a classical Turing Machine. It's in the very influential:
[DJ92] D. Deutsch and R. Jozsa,
"Rapid solution of problems by quantum computation",
Proc. R. Soc. Lond. A, 439:553-558, 1992,
This paper is rather dense and compact, but nevertheless
includes some issues of complexity that are sloughed over
in second-hand treatments.