A question about matrices

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 2^n x 2^n Hermitian matrices H_1 and H_2. What are the resource costs for determining if all the eigenvalues of H_1 and H_2 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  H_1 and H_2, (b) sort each list of eigenvalues, and (c) compare them one by one. This is exponential in n. 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 P such that H_1 = P^{-1} H_2 P then H_1 and H_2 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 P exists?

11 thoughts on “A question about matrices

  1. What about using the Smith normal form? I’m not sure what the efficiency of this method is, but basically two matrices, A and B, are similar if and only if the characteristic matrices, A-Ix and B-Ix (or Ix-A and Ix-B), have the same Smith normal form. The only hitch is that it assumes you’re working with a principle ideal domain (PID).

  2. I’m not sure how hard it is, but it’s interesting that if you restrict P to being a permutation matrix, it’s exactly the Graph Isomorphism problem, which is very probably a much harder problem.

    @quantummoxie: Nice attention to detail; luckily, it’s pretty likely he’ll be using a principle ideal domain, as that includes R, C, Z, and Z_2.🙂

  3. Neil: Are you sure that if P is a permutation matrix this is graph isomorphism?

    quantummoxie: yes the intent is that these are Hamiltonians (entries are complex).

    • “Neil: Are you sure that if P is a permutation matrix this is graph isomorphism?”

      Looks that way to me. H1 and H2 are matrix representations of your two graphs and P is the vertex relabeling that gets you from one to the other.

  4. Actually, I thought about it a bit more and it might not be graph isomorphism; if it was just one P instead of two, it would definitely be GI on a graph of 2^n nodes, since that’s exactly how one would define GI on a node-weighted, edge-weighted graph.

    A lower bound on the time it’ll take is n(2^n), since even if you have diagonal matrices, you have to decide between (2^n)! orderings of the elements, which takes at least log((2^n)!) decisions, which scales as n(2^n). (Same argument as that sorting n elements takes nlogn time.) If the matrices are dense, a lower bound is 2^2n time, since there are 2^2n elements that affect the eigenvalues.

    These correspond to nlogn and n^2 times for nxn matrices. I think diagonalization takes at least n^3 time for dense nxn matrices; maybe less for sparse, but I don’t know.

  5. Hi Neil, yes… but I wonder if there is a way to know whether two matrices have the same eigenvalues without having to explicitly calculate them. Any scheme where you have to explicitly calculate all of them is a non-starter because of the exponential size of the matrices (say typically 2^1000 x 2^1000 sizes for a moderate quantum system).

  6. Just matrix multiplication alone is exponentially expensive here. I can’t imagine solving this problem in less operations than a single multiplication. Do you have some polynomial time way to evaluate matrix-vector multiplications?

  7. Jordan: No. But you don’t always have to explicitly work out all the elements of a matrix to know something interesting about it. For example the type of matrix we deal with here is just H_1=\sum_{j=1}^N h_j Z_j + \sum_{i,j \in E} J_{ij} Z_i Z_j where Z_j is the jth Pauli matrix. This matrix has an exponential number of matrix elements but I can easily write it down in a compact form. For this problem I wonder if you can somehow answer the question just by looking at the “generators” of the matrix (in the case above the Z_j matrices).

    I should also emphasize that what I’m looking for isn’t a calculation of the spectra, which obviously would be exponential. I’m wondering if there might be an efficient “oracle” that given two matrices can answer the decision problem “Are these two matrices similar?”

  8. Geordie,

    In the Smith normal form method I mentioned above, you don’t actually need to go through the step of calculating the eigenvalues. True, you need the characteristic matrix, which is not too many steps away, but it still saves a bit of calculating (I’m figuring calculating the Smith normal form is about as resource intensive as calculating the Jordan form which you’d have to do to diagonalize).

    Ian

  9. I think the problem is hard, at least the way you’ve phrased it so far. I assume that as per comment 7 that the way you really want to state this is that you have polynomial sized representations of the matrices H1 or H2….

    Let f1 and f2 be two boolean functions which we specify by circuits in CNF form. Its then easy to construct a H1 such that H1=\sum_x f1(x)|x><x| but which has an efficient polynomial description…i.e. we can write H1 as a product of sums of Pauli Z's acting on the relevant variables. Same goes for H2. In this case your problem is the same as the circuit equivalence problem. But circuit equivalence is coNP-complete. So your problem is coNP-hard but it could be harder.

    One way that it might not be so hard and which I think you might also be implicitly needing in a quantum algorithm for this is that H be a sum of a polynomial number of local terms. The H1 and H2 I constructed above does not have this property even though it has an efficient polynomial sized description. [(a+b)^10 is a small description of a term that is a sum of 2^10 terms]. Note that the representation form can have a big different. Testing circuit equivalence of binary decision diagrams is easy, for example.

    So I think you need to define what you allow H1 and H2 to be given as better…

  10. Here’s a good way to build a quantum simulation, with relative quantum eigenfunctions that give joule valued eigenvalues for the energy and force field particles of an atom’s internal energy cloud. The result is an exact picoyoctometric, interactive, 3D, topological atomic video function.

    Recent advancements in quantum science have produced the picoyoctometric, 3D, interactive video atomic model imaging function, in terms of chronons and spacons for exact, quantized, relativistic animation. This format returns clear numerical data for a full spectrum of variables. The atom’s RQT (relative quantum topological) data point imaging function is built by combination of the relativistic Einstein-Lorenz transform functions for time, mass, and energy with the workon quantized electromagnetic wave equations for frequency and wavelength.

    The atom labeled psi (Z) pulsates at the frequency {Nhu=e/h} by cycles of {e=m(c^2)} transformation of nuclear surface mass to forcons with joule values, followed by nuclear force absorption. This radiation process is limited only by spacetime boundaries of {Gravity-Time}, where gravity is the force binding space to psi, forming the GT integral atomic wavefunction. The expression is defined as the series expansion differential of nuclear output rates with quantum symmetry numbers assigned along the progression to give topology to the solutions.

    Next, the correlation function for the manifold of internal heat capacity energy particle 3D functions is extracted by rearranging the total internal momentum function to the photon gain rule and integrating it for GT limits. This produces a series of 26 topological waveparticle functions of the five classes; {+Positron, Workon, Thermon, -Electromagneton, Magnemedon}, each the 3D data image of a type of energy intermedon of the 5/2 kT J internal energy cloud, accounting for all of them.

    Those 26 energy data values intersect the sizes of the fundamental physical constants: h, h-bar, delta, nuclear magneton, beta magneton, k (series). They quantize atomic dynamics by acting as fulcrum particles. The result is the picoyoctometric, 3D, interactive video atomic model data point imaging function, responsive to keyboard input of virtual photon gain events by relativistic, quantized shifts of electron, force, and energy field states and positions.

    Images of the h-bar magnetic energy waveparticle of ~175 picoyoctometers are available online at http://www.symmecon.com with the complete RQT atomic modeling manual titled The Crystalon Door, copyright TXu1-266-788. TCD conforms to the unopposed motion of disclosure in U.S. District (NM) Court of 04/02/2001 titled The Solution to the Equation of Schrodinger.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s