For a rank $r,d\times d$ density matrix $\rho$, where $d=2^n$, using $O(rdlog^2d)$ measurement settings can reconstruct the density matrix, while I see another description that we need $\Omega(rd\ \mathrm{poly\ log}d)$ meaurement settings.

(1) Do the $O(rdlog^2d)$ and $\Omega(rd\ \mathrm{poly\ log}d)$ have same meaning?

(2) And What is the meaning of "$\mathrm{poly\ log}d$" in the $\Omega(rd\ \mathrm{poly\ log}d)$?

(3) Do the $\Omega$ have the same mean with $O$, and do they mean the complexity of consumed resources?

  • $\begingroup$ each post should contain a single, laser-focus question. You can ask different questions in separate posts. Feel free to edit the question to focus it on a specific point, adding relevant context and your current understanding where needed. See also quantumcomputing.stackexchange.com/help/how-to-ask $\endgroup$
    – glS
    Commented Aug 11, 2022 at 9:45

2 Answers 2


(1) They are not the same thing. The big $O$ defines an asymptotic upper bound or the worst-case behaviour of an algorithm. The big $\Omega$ gives the lower bound. For example, if we want to give the lower bound on the resources requirements then we use the big $\Omega$. The $O(rd \ \log^2d)$ is a very specific description of asymptotic behaviour, i.e., it tells that the scaling goes as log squared. On the other hand, the $\Omega(rd \ \textrm{poly}\log d)$ is a slightly more loose description. It just says that scaling goes as some polynomial in log. This is to say that scaling is polynomial and not exponential. In general, $\textrm{poly}$ could mean any polynomial of an arbitrary degree $n$. It could be constant, linear or quintic. In your particular case, it is reasonable to assume that $\textrm{poly}$ implies a linear polynomial.

(2) $\textrm{poly} \log$ means a polynomial in $\log$. Here is a degree $n$ polynomial in $x$, $p(x) = a_n x^n + \cdots +a_0$. Now, replace $x$ with $\log$ and you get a $\textrm{poly} \log$. Clearly $\log^2 d$ is a degree two polynomial in $\log$.

(3) I think (1) answers this.


The $O()$ notation indicates worst-case running time ("upper bound time complexity").

For example, if we have an unstructured list with $N$ values, then in the worst case it takes $N$ steps to find a specific value in the list and therefore the worst case complexity is $O(N)$ - i.e linear time complexity, for that specific example.

Using simple words - we can be really unlucky such that we will have to go through all the $N$ values of the unstructured list untill we find the desired value.

The $\Omega ()$ notation indicates best-case running time (“lower bound time complexity”).

Looking at the same example of finding a specific value in an unstructured list with $N$ values, the best-case complexity of this operation is $\Omega (1)$ - i.e constant time complexity.

Using simple words - in the best case we can be really lucky and find the unique value we are looking for in 1 try or few tries, doesn't matter how big is $N$. Therefore the best-case complexity is constant for that specific example.

About that question:

(1) Do the O(rdlog2d) and Ω(rd poly logd) have same meaning?

The answer is basically yes, take a look at this explanation for details.

  • $\begingroup$ Thanks for your answer! Can not open the link "this" above. $\endgroup$
    – karry
    Commented Aug 11, 2022 at 11:28
  • $\begingroup$ No problem. The link works for me. $\endgroup$
    – Ohad
    Commented Aug 11, 2022 at 11:39

Your Answer

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

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