Lipton wrote a pretty decent and short intro to QC that builds the theory a little differently from usual. It is aimed more towards Mathematicians and Computer Scientists than Physicists, I believe, but I think it is pretty understandable in general.

I think Sipser is probably the best introduction to Computation if you do not have a background in Computability and Complexity. Arora and Barak's text has a much larger breadth and is much more detailed as far as Complexity goes. It is the more appropriate of the two if you are just interested in Computational Complexity.