Tensors masquerading as matchgates: Relaxing planarity restrictions on Pfaffian circuits

作者：

Highlights：

• We extend the set of tensor network with polynomial time evaluations.

• We show that, only one of the strategies can be used in non-planar tensor networks.

• We show that this strategy does not extend to circuits with two or more crossings.

摘要

•We extend the set of tensor network with polynomial time evaluations.•We show that, only one of the strategies can be used in non-planar tensor networks.•We show that this strategy does not extend to circuits with two or more crossings.

论文关键词：Counting complexity,Tensor network,Holographic algorithms,Holant problems

论文评审过程：Received 6 October 2015, Revised 14 November 2016, Accepted 16 December 2016, Available online 28 December 2016, Version of Record 27 February 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.12.002