Contraction of matchgate tensor networks on non-planar graphs

Details Contraction of matchgate tensor networks on non-planar graphs Contraction of matchgate tensor networks on non-planar graphs

2008-01-18

arxiv.org/abs/0801.2989v1

Contemporary Mathematics, Vol. 482, pp. 179-211 (2009)

Physics

Quantum Physics

32 pages, 7 figures

Scientific paper

A tensor network is a product of tensors associated with vertices of some graph $G$ such that every edge of $G$ represents a summation (contraction) over a matching pair of indexes. It was shown recently by Valiant, Cai, and Choudhary that tensor networks can be efficiently contracted on planar graphs if components of every tensor obey a system of quadratic equations known as matchgate identities. Such tensors are referred to as matchgate tensors. The present paper provides an alternative approach to contraction of matchgate tensor networks that easily extends to non-planar graphs. Specifically, it is shown that a matchgate tensor network on a graph $G$ of genus $g$ with $n$ vertices can be contracted in time $T=poly(n) + 2^{2g} O(m^3)$ where $m$ is the minimum number of edges one has to remove from $G$ in order to make it planar. Our approach makes use of anticommuting (Grassmann) variables and Gaussian integrals.

Affiliated with

Also associated with

No associations

Rating

Contraction of matchgate tensor networks on non-planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Contraction of matchgate tensor networks on non-planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contraction of matchgate tensor networks on non-planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-18559