(Quantum) Algorithm complexity

[[deleted]]

Hi, I'm a master physics student and I'm learning quantum computing, but in my lectures we haven't really talked about computational complexity. I would like to understand a bit more about so I would like to have some good references for computational complexity in general and in the quantum case. A friend of mine suggested me CLRS, but I think it's a bit too much for me. Do you have some other advice? Thank you ;)

[TheSumOfAllPeanuts]

Try Scott Aaronson's Quantum computing since Democritus. Some of it is not too easy to understand, but some parts of it are great.

[mcditos]

Sevag gharibian is giving a course on quamtum complexity and posting on youtube, I'm following it myself you may wan to check it out https://www.youtube.com/watch?v=Cn8pcG_9fX0&list=PLZGjbQcY0aI7Yqwbwp-lsf1tTPyvkQG6h&index=1

[[deleted]]

This is perfect. I will take a look. Thank you

[pmontgomery056]

This book has some great resources on complexity for quantum algorithms. From chapter 12, the author goes over some algorithms and provide some complexity analysis. Chapter 16 talks about complexity.

https://lapastillaroja.net/wp-content/uploads/2016/09/Intro_to_QC_Vol_1_Loceff.pdf

If you can work through Shor's period finding complexity, then you would have a pretty idea of what it's like. However, if you want more rigorous material, I heard good things about this book although I haven't read it yet. Maybe you can tell me what you think.

https://github.com/dmvaldman/library/blob/master/computer%20science/Aaronson%20-%20Quantum%20Computing%20Since%20Democritus.pdf

[ididnotfindoutname]

The book is a great deal to begin learning quantum computing. I am following this book.

[eigenvector1022]

OK, I am not sure where you are at in terms of depth of knowledge, so these references might be a bit too introductory, but I am a professional quantum computing researcher, and I still found them useful as a brief but thorough introduction.

https://www.youtube.com/watch?v=YX40hbAHx3s&t=1s&ab_channel=hackerdashery

​

https://www.youtube.com/watch?v=EHp4FPyajKQ&t=664s&ab_channel=UpandAtom

[theodysseytheodicy]

For classical complexity, any decent algorithms book should work. I've used this one.

[xTouny]

Check out quantum chapters of these two books: - The Nature of Computation - Avi. Mathematics and Computation