I am going through S. Gharibian's course on quantum complexity theory (https://groups.uni-paderborn.de/fg-qi/data/QCT_Masterfile.pdf) and encountered the following problem (Ex 6.39, note that here $\lambda_{\text{min}}()$ stands for the smallest eigenvalue):

enter image description here

Does anyone know how to approach this problem? Personally I am not even convinced that the statement is true! Suppose that there are two normal operators $A, B$ with the computational basis as their common eigenbasis, $$A = \begin{pmatrix} 1 & 0 \\ 0 & 10 \end{pmatrix}$$ and $$B = \begin{pmatrix} 10 & 0 \\ 0 & 5 \end{pmatrix}.$$

Clearly, $$A+B = \begin{pmatrix} 11 & 0 \\ 0 & 15 \end{pmatrix}$$ and $$\lambda_{\text{min}}(A+B) = 11,$$ which is different than $\lambda_{\text{min}}(A) + \lambda_{\text{min}}(B) = 1 + 5 = 6$.

What went wrong in my reasoning?

  • 1
    $\begingroup$ Hi and welcome to Quantum Computing SE. Please, do not post screen shots of theorems, codes, etc. Rather use quote environment. Thanks for understanding. $\endgroup$ Feb 5 at 6:57
  • 1
    $\begingroup$ Your reasoning looks sound to me! For the rest of the proof, it would be sufficient to say $\lambda_{\min}(A+B)\geq\lambda_{\min}(A)+\lambda_{\min}(B)$ wouldn't it? And it is true that the bound can be saturated for the commuting case. $\endgroup$
    – DaftWullie
    Feb 5 at 12:21
  • $\begingroup$ @DaftWullie What did you mean by the bound being saturated? And why would two commuting operators guarantee that? Thanks! $\endgroup$
    – user896578
    Feb 6 at 23:34
  • $\begingroup$ All I was saying is that there exist cases where $\lambda_{\min}(A+B)=\lambda_{\min}(A)+\lambda_{\min}(B)$, and these are particularly easy to construct for commuting operators (but I agree that not all commuting operators satisfy this). $\endgroup$
    – DaftWullie
    Feb 8 at 7:42
  • $\begingroup$ @DaftWullie I suppose the only commuting operators that satisfy the equality are those with non-decreasing ordered eigenvalues $\endgroup$
    – user896578
    Feb 12 at 0:58

1 Answer 1


I checked the note you provided and believe there should be a implicit condition for normal operators $A$ and $B$, which seems not to be stated explicitly in the note. If $$\lambda_1\leq\lambda_2\leq...\leq \lambda_n$$ is the eigenvalue for $A$, you should always apply a permutation such that the the diagonalized $A$ is $$ diag\{\lambda_1, \lambda_2... \lambda_n\} $$ and the same for $B$.

In your case, you should define $B=diag\{5, 10\}$ instead.

  • $\begingroup$ Thanks @Yunzhe for your comment. Is the permutation you mentioned a trivial operation that can always be done with poly time for any normal matrices? An example or a reference to where I can read into more would be great thanks! $\endgroup$
    – user896578
    Feb 6 at 23:55
  • $\begingroup$ There are many sorting algorithms that only requires polynomial time complexity (more precisely, $O(n^2)$). As the permutation operations are actually sorting operations, I don't think it will add any overhead in the context of complexity class. $\endgroup$
    – Yunzhe
    Feb 7 at 6:12

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.