## A Quantum Hammersley–Clifford Theorem

I’m at this workshop:

Sydney Quantum Information Theory Workshop: Coogee 2012, 30 January – 2 February 2012, Coogee Bay Hotel, Coogee, Sydney, organized by Stephen Bartlett, Gavin Brennen, Andrew Doherty and Tom Stace.

Right now David Poulin is speaking about a quantum version of the Hammersley–Clifford theorem, which is a theorem about Markov networks. Let me quickly say a bit about what he proved! This will be a bit rough, since I’m doing it live…

The mutual information between two random variables is

$I(A:B) = S(A) + S(B) - S(A,B)$

The conditional mutual information between three random variables $C$ is

$I(A:B|C) = \sum_c p(C=c) I(A:B|C=c)$

It’s the average amount of information about $B$ learned by measuring $A$ when you already knew $C.$

All this works for both classical (Shannon) and quantum (von Neumann) entropy. So, when we say ‘random variable’ above, we
could mean it in the traditional classical sense or in the quantum sense.

If $I(A:B|C) = 0$ then $A, C, B$ has the following Markov property: if you know $C,$ learning $A$ tells you nothing new about $B.$ In condensed matter physics, say a spin system, we get (quantum) random variables from measuring what’s going on in regions, and we have short range entanglement if $I(A:B|C) = 0$ when $C$ corresponds to some sufficiently thick region separating the regions $A$ and $B.$ We’ll get this in any Gibbs state of a spin chain with a local Hamiltonian.

A Markov network is a graph with random variables at vertices (and thus subsets of vertices) such that $I(A:B|C) = 0$ whenever $C$ is a subset of vertices that completely ‘shields’ the subset $A$ from the subset $B$: any path from $A$ to $B$ goes through a vertex in a $C.$

The Hammersley–Clifford theorem says that in the classical case we can get any Markov network from the Gibbs state

$\exp(-\beta H)$

of a local Hamiltonian $H,$ and vice versa. Here a Hamiltonian is local if it is a sum of terms, one depending on the degrees of freedom in each clique in the graph:

$H = \sum_{C \in \mathrm{cliques}} h_C$

Hayden, Jozsa, Petz and Winter gave a quantum generalization of one direction of this result to graphs that are just ‘chains’, like this:

o—o—o—o—o—o—o—o—o—o—o—o

Namely: for such graphs, any quantum Markov network is the Gibbs state of some local Hamiltonian. Now Poulin has shown the same for all graphs. But the converse is, in general, false. If the different terms $h_C$ in a local Hamiltonian all commute, its Gibbs state will have the Markov property. But otherwise, it may not.

For some related material, see:

• David Poulin, Quantum graphical models and belief propagation.

### One Response to A Quantum Hammersley–Clifford Theorem

1. Ah, I grew up just up the hill. :-)