Holographic algorithms without matchgates

DOI10.1016/j.laa.2012.01.010zbMath1257.05007arXiv0904.0471OpenAlexW2962703159MaRDI QIDQ1931767

Jason Morton, Serguei Norine, Joseph M. Landsberg

Publication date: 16 January 2013

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

spinorsPfaffianholographic algorithmsmatchgates

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Nonnumerical algorithms (68W05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Special matrices (15B99)

Related Items

On blockwise symmetric matchgate signatures and higher domain \#CSP ⋮ Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain ⋮ Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits ⋮ Counting degree-constrained subgraphs and orientations ⋮ \(P\) versus \(NP\) and geometry ⋮ A finite-tame-wild trichotomy theorem for tensor diagrams ⋮ Polynomial-time solvable \(\#\)CSP problems via algebraic models and Pfaffian circuits ⋮ Generalized counting constraint satisfaction problems with determinantal circuits ⋮ Computing the Tutte polynomial of lattice path matroids using determinantal circuits ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Basis collapse in holographic algorithms
• Pfaffian graphs, \(T\)-joins and crossing numbers
• NP is as easy as detecting unique solutions
• Applications of minor-summation formula. II: Pfaffians and Schur polynomials
• Nonintersecting paths, pfaffians, and plane partitions
• Expressiveness of matchgates.
• A combinatorial Laplacian with vertex weights
• Holographic algorithms by Fibonacci gates
• Valiant's holant theorem and matchgate tensors
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Holographic Algorithms
• On Symmetric Signatures in Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• On the computational complexity of the Jones and Tutte polynomials
• Quantum computers that can be simulated classically in polynomial time
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms: The Power of Dimensionality Resolved
• Automata, Languages and Programming
• Theory and Applications of Models of Computation