Computing the Tutte polynomial of lattice path matroids using determinantal circuits

DOI10.1016/J.TCS.2015.07.042MaRDI QIDQ496045zbMATH OpenOpenAlexFDO

Authors Jason Morton, Jacob M. Turner

Publication date 16 September 2015

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

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

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)

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.

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

Cites work

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

Cited in

(7)

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

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)