Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits

DOI10.1016/J.JCSS.2016.12.002zbMATH Open1370.68143arXiv1510.01541OpenAlexW2271519933MaRDI QIDQ2396823FDOQ2396823

Authors: Jacob M. Turner 

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: Holographic algorithms, alternatively known as Pfaffian circuits, have received a great deal of attention for giving polynomial-time algorithms of $$-hard problems. Much work has been done to determine the extent of what this machinery can do and the expressiveness of these circuits. One aspect of interest is the fact that these circuits must be planar. Work has been done to try and relax the planarity conditions and extend these algorithms further. We show that an approach based on orbit closures does not work, but give a different technique for allowing the SWAP gate to be used in a Pfaffian circuit given a suitable basis and restricted type of graph. This is done by exploiting the fact that the set of Pfaffian (co)gates always lies in a hyperplane. We then give a variety of bases that can be chosen such that the SWAP gate acts like a Pfaffian cogate and discuss how many SWAP gates can be implemented in a Pfaffian circuit.

Full work available at URL: https://arxiv.org/abs/1510.01541

Recommendations

• Holographic algorithms without matchgates
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
• Holographic algorithms beyond matchgates
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms beyond matchgates

zbMATH Keywords

counting complexityHolant problemsholographic algorithmstensor network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Instability in invariant theory
• The Complexity of the Counting Constraint Satisfaction Problem
• Complexity of counting CSP with complex weights
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of tensor calculus
• Nonintersecting paths, pfaffians, and plane partitions
• Matchgates and classical simulation of quantum circuits
• Holographic algorithms without matchgates
• Expressiveness of matchgates.
• Title not available (Why is that?)
• On spinor varieties and their secants
• A complete set of covariants of the four qubit system
• On the history of the shortest path problem

Cited In (3)

• Generalized counting constraint satisfaction problems with determinantal circuits
• Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits
• A finite-tame-wild trichotomy theorem for tensor diagrams

This page was built for publication: Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396823)