A New Graph Polynomial and Generalized Tutte–Grothendieck Invariant from Quantum Circuits

A new polynomial associated to graphs G is defined and studied. The main theorems represent as a quasi-specialization of the rank-generating polynomial of Oxley and Whittle, J Comb Theory Ser B 59:210–244, 1993,[10] and show that is likewise a generalized Tutte–Grothendieck invariant. The value gives the amplitude of acceptance for a class of quantum circuits with associated graphs G. This class, called stabilizer circuits or Clifford circuits, has long been known to have deterministic polynomial time simulation, so is polynomial time computable, given G as input. The specialization has, which (along with its complex conjugate) is the only choice that invalidates formulas in a theorem by Noble, Comb. Probab. Comput 15:449–461, 2006,[9] classifying hard and easy real points of, so the complexity of other points is open. We reduce the base cases for by adjoining multiple kinds of isolated nodes and draw possible further implications of the connections between matroid theory and quantum computing developed by this work.