Trying to learn about how to derive (& intuition) the complexity for a given algorithm as shown below. If there is any good reference or starting point that anyone can suggest that will be highly appreciated!
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Could you clarify the scope of your question? For example, are you asking about the concept of algorithmic complexity and big-O notation, or are you are asking about the details of each individual algorithm? $\endgroup$– jecadoCommented Sep 17, 2021 at 19:02
-
$\begingroup$ If you're just looking for general advice on approaching Quantum Complexity; first obviously tackle some Classical Complexity. Then get comfortable with Grover Searches, Quantum Counting, Amplitude Amplification, Quantum Walks, etc. And from there you can approach any specific algorithm whose complexity is almost always analyzed in the paper the algorithm is introduced in. For actual analysis of upper/lower bounds The Adversarial Method and The Polynomial Method are often used. $\endgroup$– Bertrand Einstein IVCommented Sep 17, 2021 at 19:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
First, you need to get familiar with the notion of classical complexity and big-O notation. For this, I recommend:
- MIT 16.070 Big O notation lecture notes
- Computational Complexity: A Modern Approach
- The Complexity Zoo and links in the See Also section.
After getting a good grasp about classical complexity theory, you can start diving into quantum complexity theory. I recommend the following texts:
- Quantum Computational Complexity
- MIT 6.845 lecture notes. You may be tempted to skip the first few lectures from here, but I think all of them are worth reading to have a solid understanding of the fundamentals you'll need later on.
- Quantum Computing Since Democritus notes. There is also a book version, but that's not free. These notes may be a bit more informal, but very worth reading.
-
1$\begingroup$ Thank you for the excellent resources ! $\endgroup$ Commented Sep 21, 2021 at 14:22