13
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Generally speaking, soliciting recommendations for a class or other materials isn't considered on topic for a Stack Exchange site; but that issue aside, the topic of your post isn't really about the subject of "quantum computing". Teaching the concepts of computational complexity is a better fit for our Computer Science site. $\endgroup$
    – Robert Cartaino
    Commented Apr 11, 2018 at 19:41
  • $\begingroup$ @RobertCartaino Thanks for the feedback, let me try to address your points. I was requesting material for self-study, and afaik resource requests are allowed within parameters. I will try my best to modify the question to be on topic. $\endgroup$
    – Kiro
    Commented Apr 12, 2018 at 7:39
  • 1
    $\begingroup$ @MEE Except you glossed over the crux of this being off topic — teaching the rudiments of computational complexity is merely coincidental to the expertise of quantum computing. I call this "the favorite soft drink of programmers" problem. It's a computer science issue where adding "in the context of quantum computing" doesn't make it any moreso on topic here in this instance. No matter; the user doesn't have a question about this subject, and they simply want to go elsewhere to find that information. Whatever you decide. $\endgroup$
    – Robert Cartaino
    Commented Apr 12, 2018 at 15:06
  • $\begingroup$ @RobertCartaino ok, I understand your point now, I misunderstood the closure reason. Therefore I would like to retract my reopen vote now but because this is not possible I voted to close this question. $\endgroup$
    – User that hates AI
    Commented Apr 12, 2018 at 15:10
  • 2
    $\begingroup$ @RobertCartaino "the rudiments of computational complexity is merely coincidental to the expertise of quantum computing" I agree that the 'rudiments' are coincidal, but I think that the question as currently asked is on-topic enough that I can refer to lecture notes on quantum computing as an answer. I agree that the previous version would indeed by a case of "the favorite soft drink of programmers", but I think that has been resolved by now. $\endgroup$
    – Discrete lizard
    Commented Apr 12, 2018 at 17:05

2 Answers 2

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.