Kirchhoff's Matrix‐Tree Theorem Revisited: Counting Spanning Trees with the Quantum Relative Entropy
Vittorio Giovannetti, Simone Severini · 2013
By reinterpreting the Kirchhoff's matrix-tree theorem in the context of quantum information theory, the authors provide an exact formula to count spanning trees based on the notion of quantum relative entropy. This function is the quantum mechanical analog of the relative entropy. The authors show that the number of spanning trees is proportional to the distinguishability/distance between a certain density matrix associated with the graph in context and the maximally mixed state, that is, the state with maximum von Neumann entropy, or, equivalently, maximum amount of classical uncertainty. The chapter contains the mathematical setup and the main result. It offers a discussion on the lower and upper bounds on t(G) by exploiting known facts about the quantum relative entropy. The authors show particular attention to a plausible operational meaning for the number of spanning trees, when considering class of quantum states.