I am reading Nielsen and Chuang's "Quantum Computation and Quantum Information". One important concept about algorithms is how the number of operations scales with the length of the input. I realized I might not be getting what they actually mean by this in Exercise 5.17:

enter image description here

Part (1) is OK. In part (2) I think there is a typo. According to the answer to this question, it should read "$y=\log_2 N$" rather than just "$\log_2 N$". Then, what I understand the algorithm is doing in that step is computing $x=\log_2N/b$ for each $b \leq L$. These are $O(L)$ operations rather than $O(L^2)$ as it claims. Where are the other $O(L)$ operations?

I have thought perhaps these numbers don't agree because you have to take into account the number of operations required for elementary mathematical operations (see e.g. here), and computing $2^x$ takes more than one operation. But if I take into account the complexity of $2^x$, then I should also take into account the complexity of division in $x = \log_2 N/b$. Moreover, I don't think they are referring to this, because I have read all the chapters until here and I don't remember that they have explained this.

  • 1
    $\begingroup$ The complexity class O(L^2) includes O(L) as a subset. If you're using L operations, that's still in O(L^2) it just also happens to be in O(L). $\endgroup$ Commented Apr 3, 2020 at 18:31
  • $\begingroup$ @CraigGidney yes, of course, but do you think that's what they mean by "at most $O(L^2)$ operations"? Why would they write $O(L^2)$ when you can write $O(L)$? $\endgroup$
    – MBolin
    Commented Apr 3, 2020 at 18:35
  • $\begingroup$ In order to make the exercise easier. $\endgroup$ Commented Apr 3, 2020 at 22:59


Your Answer

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