Computing the Tutte Polynomial of Lattice Path Matroids Using Determinantal Circuits
arXiv:1312.3537 · doi:10.1016/j.tcs.2015.07.042
Abstract
We give a quantum-inspired algorithm computing the Tutte polynomial of a lattice path matroid, where is the size of the ground set of the matroid. Furthermore, this can be improved to 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 , 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.
References in corpus (15)
- The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
- Novel schemes for measurement-based quantum computation
- Matchgates and classical simulation of quantum circuits
- Lattice path matroids: enumerative aspects and Tutte polynomials
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Lattice Path Matroids: Structural Properties
- Categorical Tensor Network States
- Atemporal diagrams for quantum circuits
- Channel kets, entangled states, and the location of quantum information
- The Jones polynomial: quantum algorithms and applications in quantum complexity theory
- Multi-Path Matroids
- Tensor Network Methods for Invariant Theory
- Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Pfaffian Circuits
Cited by in corpus (5)
- Generalized Counting Constraint Satisfaction Problems With Determinantal Circuits
- Delta-matroids as subsystems of sequences of Higgs lifts
- Facial structures of lattice path matroid polytopes
- The Young matroid: A multiset extension of the Catalan matroid to arbitrary Young diagrams
- On lattice path matroid polytopes: integer points and Ehrhart polynomial