Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits

DOI10.1016/j.jcss.2016.12.002zbMath1370.68143arXiv1510.01541OpenAlexW2271519933MaRDI QIDQ2396823

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)

Related Items (1)

A finite-tame-wild trichotomy theorem for tensor diagrams

Cites Work

• Unnamed Item
• On spinor varieties and their secants
• Instability in invariant theory
• The complexity of tensor calculus
• Nonintersecting paths, pfaffians, and plane partitions
• Expressiveness of matchgates.
• Holographic algorithms without matchgates
• 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
• Matchgates and classical simulation of quantum circuits
• A complete set of covariants of the four qubit system
• Complexity of counting CSP with complex weights
• A complete dichotomy rises from the capture of vanishing signatures
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

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