Computing the Tutte polynomial of lattice path matroids using determinantal circuits

DOI10.1016/J.TCS.2015.07.042zbMATH Open1329.68120arXiv1312.3537OpenAlexW1491410076MaRDI QIDQ496045FDOQ496045

Authors: Jason Morton, Jacob M. Turner 

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We give a quantum-inspired $O(n^4)$ algorithm computing the Tutte polynomial of a lattice path matroid, where $n$ is the size of the ground set of the matroid. Furthermore, this can be improved to $O(n^2)$ arithmetic operations if we evaluate the Tutte polynomial on a given input, fixing the values of the variables. The best existing algorithm, found in 2004, was $O(n^5)$, and the problem has only been known to be polynomial time since 2003. Conceptually, our algorithm embeds the computation in a determinant using a recently demonstrated equivalence of categories useful for counting problems such as those that appear in simulating quantum systems.

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

Recommendations

• Computing the Tutte polynomial of a graph of moderate size
• The exact complexity of the Tutte polynomial
• Tutte polynomials computable in polynomial time
• On the evaluation at \(( - \iota ,\iota )\) of the Tutte polynomial of a binary matroid
• Lattice path matroids: Enumerative aspects and Tutte polynomials

zbMATH Keywords

quantum simulationTutte polynomialcounting complexitymatroidstensor networks

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• A Contribution to the Theory of Chromatic Polynomials
• Chip firing and the Tutte polynomial
• A Tutte polynomial for toric arrangements
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The geometry of tensor calculus. I
• On the \(h\)-vector of a lattice path matroid
• The complexity of partition functions
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• On the computational complexity of the Jones and Tutte polynomials
• A polynomial quantum algorithm for approximating the Jones polynomial
• A spanning tree expansion of the Jones polynomial
• Lattice path matroids: structural properties
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matchgates and classical simulation of quantum circuits
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Holographic algorithms without matchgates
• Generalized counting constraint satisfaction problems with determinantal circuits
• Multi-Path Matroids
• Quantum computers that can be simulated classically in polynomial time
• Expressiveness of matchgates.
• Tensor network methods for invariant theory
• Channel kets, entangled states, and the location of quantum information
• Contraction of matchgate tensor networks on non-planar graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory and Applications of Models of Computation

Cited In (7)

• On lattice path matroid polytopes: integer points and Ehrhart polynomial
• Facial structures of lattice path matroid polytopes
• Generalized counting constraint satisfaction problems with determinantal circuits
• A finite-tame-wild trichotomy theorem for tensor diagrams
• Delta-matroids as subsystems of sequences of Higgs lifts
• Lattice path matroids and quotients
• A Tutte polynomial inequality for lattice path matroids

This page was built for publication: Computing the Tutte polynomial of lattice path matroids using determinantal circuits

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