Scott Aaronson’s Quantum Computing Since Democritus is a clear, entertaining explanation of computational complexity theory as applied to both classical and quantum computers. I thoroughly enjoyed the book, and have recommended it to a number of friends.

https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...