Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits

DOI10.1016/J.JCSS.2016.12.002MaRDI QIDQ2396823zbMATHOpenAlexFDO

Authors Jacob M. Turner

Publication date 26 May 2017

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

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

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)

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.

Recommendations

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

Cites work

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

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)