In making my research open I’ve continually encountered the difficulty of working out what to actually post. My typing speed doesn’t really match the speed at which I write down notes. In order to overcome this I’ve already censored most of the worst mistakes in my handwritten notes: i.e., I’ve spared you all of the crossed-out calculations where I made, eg., a minus-sign error and just written up the corrected notes. But apart from this you are pretty much getting what I’m thinking. There is an exception: I am involved in several projects where my co-authors have, for good reasons, requested I not post on them.
In writing my notes for a wider audience I also attempt to preface each post with some kind of general discussion. This seems to be a useful device, not unlike when using del.icio.us where you are forced to write a description. These little extra tasks seem like a useful mental filing device. Also, I think of the prefaces and tags etc. as a way to enthuse a wider audience to work on the problems I’m working on. (Not entirely clear if this is working yet…)
In this post I’d like to talk about a problem that I’m not really working on, but plan one day to work on if I have an idea. I guess most researchers have these kind of “to do” lists of problems waiting for time/inspiration. I find that these problems take up a lot of mental space (even when I’m not thinking about them directly: eg. “I must remember to think about problem X”) and I’d like to experiment by posting about one of them here in an attempt to clear out this to-do list, so to speak.
The problem/idea I’d like to talk about today is principally motivated by a single figure (Figure 1) in a paper of Cirac and Verstraete.
1. Translation-invariant quantum systems
In this post I’d like to focus on the following setting: imagine we have qubits arranged in a ring. (Everything I’m going to say will also make obvious sense for qutrits in a ring and qudits in a regular lattice etc.) The hilbert space of this system is given by . There is an obvious symmetry of the ring, namely translation , which acts on a quantum basis state , , , via
Before we go any further we need to set up a hamiltonian for our system. Let’s agree on what form we’d like this hamiltonian to have. Firstly, physically, any interaction between qubits is likely to be short-ranged, so let’s agree that the hamiltonian for our system should involve only nearest-neighbour interactions (you’ll be able to easily generalise everything I say here to the next-nearest neighbour setting etc.). Secondly, there is this nice translation-invariance symmetry of the ring, so let’s agree that the hamiltonian should be also translation-invariant. Having agreed on these constraints we end up with a hamiltonian which looks like
where the qubits that acts nontrivially on, i.e. it’s support , are , where we identify . Because the system is translation invariant the actual interaction between qubits and is identical to that between and , etc. Another way of saying this is that
So (2) actually represents a family of hamiltonians indexed by the size of the system and the nature of the interaction between the nearest-neighbouring qubits. Because of the translation-invariance the actual interactions between the qubits are completely specified by which is, in turn, completely specified by a matrix via . Now is hermitian, so is as well. We can write any hermitian matrix as
where are real and
are the Pauli sigma matrices. The coefficient really sets the zero of energy, so we typically set it to . This leaves other parameters. Thus, for each , we have a -dimensional family of translation-invariant hamiltonians.
A note on : we are going to keep finite, but we want everything we say to be independent of . This will facilitate the transition to the thermodynamic limit , which is often the most interesting setting. If you want you can already think of as being infinite. But, in this case, you must understand that every statement we make from now on is only true at the level of physical rigour. (This can all be fixed up by working with quasi-local algebras etc. But let’s ignore this for the moment.)
In a sense, the family (2) captures a lot of 1 condensed-matter physics. Many of the celebrated models studied in 1 condensed matter physics are simply points in this -dimensional space. Examples include the model and the Heisenberg model. There are many obvious counterexamples to this statement and I leave those to you to enumerate. But the point is that (2) is already a nontrivial interesting class in it’s own right.
Obviously it is actually straightforward to generalise everything I’ve said so far to non-translation invariant systems. In this case the manifold of possible nearest-neighbour systems becomes -dimensional. Also, I leave the generalisations to next-nearest neighbour systems, and higher dimensional systems to you.
2. Ground states
The most fundamental quantum state associated with a quantum hamiltonian is its ground state , which achieves the minimum in the following variational problem:
Note that the minimum can always be achieved on a (possibly mixed) translation-invariant quantum state. Given a system of the form (2) it is a challenging problem to work out and . Indeed, for just one point in our -dimensional space, namely the Heisenberg model, the solution — via the Bethe ansatz — is extremely subtle and complicated.
However, there is a vast simplification available: notice that the energy of a (possibly mixed) translation-invariant quantum state for a system of the form (2) is given by
where , i.e., the state of just spins and , and we’ve exploited the translation invariance. This tells us that the energy of a translation-invariant state depends linearly only on the reduced density operator of the first two spins.
So this is meant to be motivation for the following
Definition 1 Let be the convex set of all translation-invariant quantum states, i.e.,
and let be the convex set
Remark 1 The actual proofs of the facts that and are convex is left to you as an exercise.
where and , i.e., is a positive semidefinite operator. Notice that the convex set of all two-qubit density operators is -dimensional. As a subset of the convex set is also -dimensional.
With these observations in hand we have proved our first result (which is widely known, BTW).
Proposition 2 Let be a system of the form (2). Then the ground-state energy for is given by
This proposition provides us with an interesting corollary: suppose we could understand the -dimensional convex set . It is a finite set; we might be able to compute its boundary offline using vast computational resources. This would be a one-time cost. Supposing we could specify , then proposition 2 tells us that we’d have actually calculated the ground-state energy for every single system of the form (2) as the minimisation involved in calculating is a minimisation of a linear function on a convex set, which is easy. Of course, calculating the ground-state energy for every system of the form (2) is exactly the same as calculating , so this really isn’t a big surprise. But what I think is helpful here is that the convex set provides us with a useful construct: proposition 2 tells us that it might be helpful to think about the totality of systems (2) rather than individual systems piecemeal.
Having introduced the convex set , and having motivated its importance in the study of quantum spin systems, I want to actually talk about what it looks like. Because it is a -dimensional space it is rather difficult to plot. One solution to this is to to plot cross-sections of . This is exactly what Cirac and Verstaete do in Figure 1 of their paper; they plot the and components of all two-qubit density operators (as represented via (9)) in .
All of this discussion so far has been literature review: all these results are well-known. I now want to discuss a little further some properties of the convex set and put forward some questions about the properties of .
3.1. Calculating ?
The first question I want to discuss is the problem of calculating . Obviously it is a pretty ugly set: it has curved surfaces and pointy bits. One might well despair at the prospect of providing an equation for its boundary. But I don’t think we should give up hope immediately: there is a precedent for a convex set with similar geometric properties but which admits a rather simple (implicit) parametrisation, namely, the set . The boundary of this set is defined by two equations: . When expressed in terms of the coefficients this tells us that the boundary of is defined as a real algebraic variety, i.e., as the common zero locus of a quadric surface and a cubic surface. This is the kind of answer I’d like: wouldn’t it be wonderful if the boundary could be written as the common zero locus of a collection of simple(ish) polynomials? Ok, so it wouldn’t immediately solve the energy-minimisation problem (2) because we’d have to compute a point on a real algebraic variety (tough problem, but in principle solvable), but it would have a certain elegance.
Here is some partial evidence, if you call it that, for why I think the boundary of could be a real algebraic variety. Let be finite. Now, the extreme points of , as defined above, are precisely these density operators which satisfy, simultaneously, the following equations
Actually, the last equation is really linear equations in disguise: i.e., if we write
then (13) really stands for the following equations
We could easily spend these equations and rewrite the extreme-point conditions in terms of representative coefficients, i.e., write in terms of the variables
where addition is modulo via . Thus an extreme point of is the common zero locus of the equations (11) and (12), when written in terms of . I’ll write out the first such equation, which is already pretty horrible:
An extreme point of is automatically associated with at least one extreme point of (but not vice versa), so it must satisfy equations (11) and (12), when written in terms of . These are quadratic and cubic equations. But there are a vast number of variables. This isn’t quite right: we want the defining equations of an extreme point to involve only the numbers (which are, incidentally, ) specifying it as a point in . This is, in principle, possible to achieve: since an extreme point of is an extreme point of once we’ve specified there can only be one solution to (11) and (12), so all those other variables are not free at all. But this is vile.
I think it would be far more disappointing, but obviously plausible, if the boundary of involved, in the limit , eg., transcendental functions. I’d still call this a partial victory…
3.2. Supposing we’ve worked out the boundary, now what?
Let’s suppose that we’ve (somehow) worked out an equation, no matter how horrible, for the boundary of . What does this buy us?
Suppose that we know we have a point on the boundary of and, further, that it is the reduced density operator of the ground state of some hamiltonian of the form (2). If the ground state is not degenerate then we know that, given , we should be able to reconstruct : suppose not, then there exist two globally different pure states consistent with with the same energy as the ground state of . But has a nondegenerate ground state, hence contradiction.
So knowing is tantamount to knowing ! But this doesn’t help us if we want to get at something like a correlation function between two separated spins. How can we get at this information? Well, here is a proposal: firstly, all two-point correlators between spin and can be calculated from knowing . The trick is to use knowledge of to get at without needing to solve exponentially many simultaneous equations. I would like to think this can be done sequentially with bounded space and computational requirements using semidefinite programming along the lines of the following method.
- Take and (both equal, and known by assumption). Solve the semidefinite program:
where is some hermitian matrix (to be chosen later). Now, even for ground states of gapped hamiltonians there can be many feasible points for the above SDP: it is only the global state which needs to be unique, but there could be many states consistent with any subset of the spins.
- Trace out qubit : this gives us the reduced density operator . Take (known, by assumption) and solve the above SDP to get . Then trace out qubit .
- Repeat until the reduced density operator is obtained. At this point all correlators can be calculated.
So the problem here is in the first step where we need to choose a single point as the “correct” state consistent with and . (This is what the matrix is doing…) I don’t know at the current time what principle could conceivably do this short of working out and then a posteriori choosing the correct extension state at each step…
So this method seems great if we know we have a point on the boundary corresponding to the ground state of a nondegenerate system. But what about systems with degenerate ground states (like critical systems)? I’m not sure: there can now be many solutions to the above SDP at each step…
Another question is to actually prove the exponential decay of correlations for gapped nondegenerate systems from this method (why? Well, another proof would be kind of interesting…) This might be possible because of the sequential nature of the method presented above: somehow there should be a degradation of information as we iterate the method.
3.3. Approximate results
We can approximate from within using trial states, like finitely correlated states/matrix product states: any reduced density operator of a translation-invariant quantum state is a point in . We can approximate from the outside using lower bounds for the ground-state energy: a lower bound provides an overestimate for the minimisation of proposition 2: by varying over all the hamiltonians of the form (2) we can get points outside .
Suppose we approximately have a point on the boundary of : what can we say about correlations, etc.? This is roughly equivalent to asking how robust the method of the previous subsection is to perturbations.
3.4. Non-translation invariant states
The set of of all nearest-neighbour reduced density operators of states of qubits forms a convex set. Extreme points correspond to ground states of nearest-neighbour hamiltonians, just like for translation-invariant systems. Given an extreme point, just like for translation-invariant systems, the SDP method of above ought to provide a method to obtain correlation functions.
Now one related problem, which is probably on a lot of people’s hit list, is the following. Suppose we have some non translation-invariant nearest-neighbour hamiltonian for qubits. Is there a method which obtains an estimate of the ground-state energy of , guaranteed to be correct to some additive constant factor, which uses only polynomial space and time resources (in ). (If “qubits” are replaced by “qutrits” then I think most people would agree that this is probably false, i.e. the problem is probably(?) QMA-complete…) This is equivalent to getting a point in which is within a distance of the boundary (measured using trace norm).
[Update 13/3/2009: fixed incorrect assertion concerning uniqueness of feasible points of semidefinite programs.]
[Update 21/3/2009: fixed missing equation (2).]