I have been thinking about ways to construct interesting adiabatic algorithms for tasks other than optimization. One of the areas I have been looking is in quantum simulation and in particular in calculating energy eigenvalues & eigenvectors of quantum systems.
Here is a question I was looking at earlier today that I don’t know the answer to, maybe you can help. Here is my question.
Assume you are given two Hermitian matrices and . What are the resource costs for determining if all the eigenvalues of and are the same, ie. they both have the same spectrum? Note that we don’t need to know what the eigenvalues actually are, just whether the two matrices have the same eigenvalues. One way to do it is to (a) diagonalize and , (b) sort each list of eigenvalues, and (c) compare them one by one. This is exponential in . I’m sure there must be a much better way to do this. Anyone have any helpful hints?
Here is a thought. If there exists an invertible matrix such that then and have the same eigenvalues. I think the phrase commonly used for these are similar matrices. So given two matrices is there an efficient way to check whether such a exists?