Good introductory material on quantum computational complexity classes

Question

I wish to learn more about computational complexity classes in the context of quantum computing.

The medium is not so important; it could be a book, online lecture notes or the like. What matters the most are the contents.

The material should cover the basics of quantum computational complexity classes and discuss the similarities, differences and relationships between them and perhaps also with classical computational complexity classes.

I would prefer a rigorous treatment over an intuitive one. The author's style doesn't matter.

As for prerequisites, I know next to nothing about the topic, so maybe more self-contained material would be better. That being said, I probably would not read a 1000 page book unless it was phenomenally good, anything in the range of 1-500 pages might work.

As for availability, I would of course prefer material that is not behind a paywall of some sort and can be found online, but this is not a strict requirement.

What do you recommend?

Answer 1

I think John Watrous' survey is a great place to start (Professor Watrous recommended it to me a long long time ago and I have been hooked ever since!):

J. Watrous. Quantum computational complexity. Encyclopedia of Complexity and System Science, Springer, 2009. arXiv:0804.3401 [quant-ph]

To the best of my knowledge, it has the highest complexity classes to page ratio.

I also really like Scott Aaronson's 2016 Barbados Lecture Notes:

S. Aaronson (with A. Bouland and L. Schaeffer). The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. ECCC TR16-109

Answer 2

I can recommend the Lecture notes of Ronald de Wolf, used for a semester course taught by him on Quantum Computing in the context of the Dutch Mastermath program.

Chapter 13 "Quantum Complexity Theory", covers the 'classical' complexity classes briefly, but gives enough background to talk about the 'quantum' complexity classes and compare them with the classical. It doesn't cover everything, but refers to other material for further reading.

Chapter 16 "Quantum Communication Complexity" is also relevant and is more technical, mainly since to the theory of communication complexity has interesting applications within quantum computation.