Long overdue update 2/14/2007: The quantum computing result described below remains unproven (though not disproven). It is true that homogeneous mean field spin models (i.e., ones where every spin is coupled to every other and every coupling has the same strength) are characterized at criticality by an entanglement entropy that increases only logarithmically with the number of spins [see, for example, this article by Latorre, et al.] It is also true that systems whose entanglement entropy is O(log N) should be efficiently simulable classically [the seminal paper is this one by Vidal]. However, it remains unclear whether inhomogeneous mean-field models (i.e., ones where every spin is connected to every other, and the coupling strengths have some nonzero mean, but they are not all the same) also have logarithmic entanglement entropy scaling.  Most pertinently, the method described below can’t resolve the issue. That is, showing that the ground state energy of an inhomogeneous mean-field model can be given exactly in the thermodynamic limit by a separable Ansatz does not mean that the model’s true ground state is separable. Silly me. 😦 On the bright side, the calculation about the probability a pair of people in a room with N people share a birthday is definitely correct. 🙂

This whiteboard reflects the two things about which I was thinking today.

whiteboard2.jpg

[Click the picture for a full-size 1600 x 1200 JPEG.]

[The left hand side] Writing up a talk I gave at the Quantum Computation and Many-Body Systems (QCMBS) conference in Key West, FL in early February. (The conference website can be found here. The conference program page has downloadable PDFs of the presentations that were given. Mine is here.) What you see on the board is a formal power series expansion of the Gibbs free energy of a general, pairwise coupled quantum spin system around the noninteracting case. The notable aspects are that if there’s C nonzero couplings in the system, then at every order in the expansion there’s just C nonzero terms and they are such that you can say the magnitude of the nth order correction scales as CJn, where J is the typical coupling constant. For systems where, as the number of spins N goes to infinity,

(1) every spin is still connected to a finite fraction of all the other spins and
(2) the ratio of the mean coupling between any 2 spins to the standard deviation of the coupling between any 2 spins does not vanish,

J must be of order 1/N so as to have a finite free energy per spin. In such a case, only the first 2 terms in the expansion are extensive, and thus spin-spin correlations (be they classical or quantum) do not matter for the Gibbs free energy per spin at any temperature (and thus the Helmholtz free energy per spin at any temperature and thus the ground state energy per spin at zero temperature). This asymptotic lack of quantum entanglement in the ground state implies that a wide class of adiabatic quantum algorithms cannot provide any speedup over classical algorithms for NP-complete graph theory problems on graphs where each vertex is connected to a finite fraction of all the others.

[The right hand side] Recalling, after being embarassingly confused with two of my friends, how to do that old problem “In a room with N people, what’s the probability that at least 2 of them have the same birthday?”, and thus explain why there’s a large chance even in a room of, say, 30 people (much larger than the woefully naive estimate of 30/365).

Advertisements