Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951178 | Journal of Computer and System Sciences | 2017 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jacob Turner,