Quantum Computing since Democritus in high school reading list is very heavy. I have had Theory of Computation class in college and I can't read 20 pages of that book.
(I didn't do this myself with QCD, but I very nearly did it with SICP in middle school.)
I didn't understand much of algorithms or quantum computing when I first read the lecture notes the book is sourced from [1]. Was still worth it.
Now I'm about half-way through Godel, Esher, Bach, and I have to say that GEB and QCSD feel similar, with an overlap not only in theme but also in genre and style.
It might be a bit overkill, but if you go over the main chapters of Arora and Barak you should have more than enough background in complexity theory for your purposes.