1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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$
    – Craig Gidney
    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
    Apr 3, 2020 at 18:35
  • $\begingroup$ In order to make the exercise easier. $\endgroup$
    – Craig Gidney
    Apr 3, 2020 at 22:59

0

Reset to default

Your Answer

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