# Ground state energy for commuting local Hamiltonians

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):

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?

• Hi and welcome to Quantum Computing SE. Please, do not post screen shots of theorems, codes, etc. Rather use quote environment. Thanks for understanding. Feb 5 at 6:57
• 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. Feb 5 at 12:21
• @DaftWullie What did you mean by the bound being saturated? And why would two commuting operators guarantee that? Thanks! Feb 6 at 23:34
• 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). Feb 8 at 7:42
• @DaftWullie I suppose the only commuting operators that satisfy the equality are those with non-decreasing ordered eigenvalues Feb 12 at 0:58

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.
• 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. Feb 7 at 6:12