Transcript Brown

Quantum Hammersley-Clifford Theorem
Winton Brown
CRM-Workshop on quantum information in
Quantum many body physics 2011
Motivations
• The Hammersley-Clifford theorem is a standard representation theorem for
positive classical Markov networks.
• Recently, quantum Markov networks have been of interest in relation to quantum
belief propagation (QBP) and Markov entropy decomposition (MED)
approximation methods.
• Connections to other problems in QIS
Conditional Mutual Information
Mutual Information
I ( A : B)  S ( A)  S ( A | B)
 S ( A)  S ( B)  S ( AB)
Conditional Mutual Information
I ( A : C | B)  S ( A | B)  S ( A | BC )
 S ( AB)  S ( BC )  S ( B)  S ( ABC )
Strong subadditivity
S ( ABC )  S ( B)  S ( AB)  S ( BC )
Markov Condition (classical)
I ( A : C | B)  0

p ABC  p A|B pB pC|B
where
p A| B 
p AB
pB
Markov Networks
Def: A Markov network is probability distribution, ρ, defined on a graph G,
such that for any division of G into regions A, B and C such that B separates
A and C, ρA and ρC are independent conditioned on ρB
A
B
C
For every B separating A and C
I ( A : C | B)  0
Hammersley-Clifford Theorem (classical)
Thm: A positive probability distribution, p, is a Markov Network on a
graph G iff p factorizes over the complete subgraphs (cliques) of G.
p ( x) 

c
( xc )
ccl ( G )
Proof:
Let
H  log( p)
From conditional independence
p  p A|B pB pC|B  H  log( p A|B pB )  I C  I A  log( pC|B )
 tr( HX Y )  0

H
h
ccl (G )
c
for traceless X and Y that do not lie on the same clique

exp( H )  p 
 exp( h )
c
ccl ( G )
Done.
Quantum Hammersley-Clifford Theorem
For quantum states with:
Hayden, et. al.
Commun. Math. Phys., 246(2):359-374, 2004
I ( A : C | B)  0

H B  i H B A  H B C
i
i
such that
  i qi  AB  CB
A
i
Now let
so
 AB  i
C
i
qi  AB A
   AB  BC
i
where
 BC i
qi CB C
i
[ AB ,  BC ]  0
Quantum Hammersley-Clifford Theorem
Now H decomposes just as in the classical case
H  log(  )  log(  AB )  log(  BC )
 tr( HX Y )  0

H
for traceless X and Y that do not lie on the same clique
h
H AB , H BC   0
ccl (G )
c
But, must show terms commute!
to show


ccl (G )
c
[hc , hc ' ]  0
Quantum Hammersley-Clifford Theorem
For each division into regions A and C separated by B:
H A   hc
H  H A  H B  H C  H AB  H BC
c A
H AB 
h
c
c  B  0  c  A 0

There exist terms
K AB  H A  H AB  H B  A
K BC  H C  H BC  H B C
such that
K AB , K BC   0
with
H B A  H BC  H B
K AB  K BC  H
Hammersley-Clifford Theroem (quantum)
If two genuine 2-body operators share support only on B
TAB   X i  Yi
i
S BC   Z i  Wi
tr( X i )  0 etc.
i
Then their commutator must be a genuine 3-body operator on ABC.
[TAB , S BC ]   X i  [Yi , Z j ]  W j
i, j
Since the commutators of each pair of terms in KAB and KBC have different support,
their commutators can not cancel.
Thus,
K AB , K BC   0
implies:
H AB , H BC   0 ; H AB , H BC   0 ; H BC , H B A   0 ; H BC , H B A   0
Two-Vertex Cliques
If G contains only 2-vertex cliques
then a boundary can always be drawn so that
3
[hij , h jk ]
can not be cancelled by any other terms.
2
1
Thus,
implies
H AB , H BC   0
[hij , h jk ]  0
Two-Vertex Cliques
If there is a single-body term then one need only consider the tree
surrounding the vertex.
3
2
The Hammersley-Clifford decomposition has
been proved to hold on trees.
1
Hastings, Poulin 2011
Thus all positive quantum Markov networks with 2-vertex cliques, are factorizable
into commuting operators on the cliques of the graph.
Three-vertex cliques
A1
X
X
X
A1, A2   0
X
Z
A4
Y
X
Z
Y
A2
X
X
X
A3
A A   0
2,
3
A3 , A4   0
A4 , A1   0
Counter-Example
A1
X
X
X
A1  A2 , A3  A4   0
X
Z
A4
Y
X
Z
Y
A2
X
X
X
A3
Cut 1
Counter-Example
Cut 1
A1
X
X
X
A1  A4 , A2  A3   0
X
Z
A4
Y
X
Z
Y
A2
X
X
X
A3
  exp(  ( A1  A2  A3  A4 ))
Yields a positive quantum Markov
network which can
not be factorized into commuting
terms on its cliques!
But factorizability can be recovered by course-graining.
PEPS
Each bond indicates
a completely entangled state
D
w   ii
i 1
Apply a linear map Λ to each site
to obtain the PEPS
If Λ is unitary, then the PEPS is a Markov network.
Under what conditions can the reverse be shown?
PEPS
For a non-degenerate eigenstate of quantum Markov network.
• Markov Properties  Entanglement Area Law
• Hammersy-Cliffors Decomposition
 PEPS representation of fixed bond dimension
Thus:
• For non-degenerate quantum Markov networks with Hammsley-Clifford
decomposition each eigenstate is a PEPS of fixed bond dimension.
• Open Problem: show under what conditions quantum Markov networks
which are pure states have a Hammersley-Clifford decomposition.
PEPS
Non-factorizable pure state quantum Markov network
U1
U2=U1*
 0   00  11   00  11 
Unitary invariants of completely entangled states
U  U *  ii   ii
network graph
Bell pair
i
i
Thus any state of the form
  U1  0
is a quantum Markov network.
Let U1 be sqrt of SWAP, then |ψ> can not be specified by
projectors on the cliques.
Conclusions
• The Hammersley-Clifford Theorem generalizes to quantum Markov network
when restricted to lattices containing only two-vertex cliques.
• Counter examples for positive Markov networks can be constructed for graphs with
three-vertex cliques and for pure states rectangular graphs.
• Whether counterexamples exist that can’t be course-grained into factorizable
networks is an open question.