1
$\begingroup$

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!

enter image description here

$\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$
    – jecado
    Sep 17 '21 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$ Sep 17 '21 at 19:13
1
$\begingroup$

First, you need to get familiar with the notion of classical complexity and big-O notation. For this, I recommend:

After getting a good grasp about classical complexity theory, you can start diving into quantum complexity theory. I recommend the following texts:

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the excellent resources ! $\endgroup$ Sep 21 '21 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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