Tensors masquerading as matchgates: Relaxing planarity restrictions on Pfaffian circuits

Holographic algorithms, alternatively known as Pfaffian circuits, have received much attention for giving polynomial-time algorithms to a subset of problems in #P. Much work has been done determining the power of this machinery. One intriguing aspect is that these circuits must be planar. We investigate relaxations of this planarity condition. We show that an approach using orbit closures does not work, but give a different technique that allows one SWAP gate to be used in a Pfaffian circuit given suitable bases and restricted types of graphs. This is done by exploiting the fact that Pfaffian gates lie in a hyperplane.