Graph Theory in Quantum Physics

Title of the Talk: Graph Theory in Quantum Physics
Speaker: Dr. L. Sunil Chandran
Host Faculty: Dr.Rogers Mathew
Date: March 18, 2025
Time: 12:00 to 13:00 pm

Abstract: In 2018, Krenn reported that certain problems related to the perfect matchings and colourings of graphs emerge out of studying constructability of general quantum states using modern photonic technologies. He realized that if we can prove that the weighted matching index of a graph, a parameter defined in terms of perfect matchings and colourings of the graph is at most 2, that could lead to exciting insights on the potential of resources of quantum inference. Motivated by this, he conjectured that the weighted matching index of any graph is at most 2. The first result on this conjecture was by Bogdanov, who proved that the (unweighted) matching index is at most 2, thus classifying graphs non-isomorphic to K_4 into Type 0, Type 1 and Type 2. By definition, the weighted matching index of Type 0 graphs is 0. We give a structural characterization for Type 2 graphs, using which we settle Krenn’s conjecture for Type 2 graphs.

We also present several other results regarding Krenn’s conjecture: (1) Krenn’s conjecture is true for multi-graphs whose underlying simple graph is of maximum degree at most 3. Also we show that Krenn’s conjecture is true when the underlying simple graph has vertex connectivity at most 2. We also show some non-constructability results when the experiment graph is assumed to be simple.

Bio of the speakerphd:

Dr. L. Sunil Chandran is a professor in the Department of Computer Science and Automation in Indian Institute of Science, Bangalore. He received his Ph.D from Indian Institute of Science, Bangalore and was a post doctoral fellow in Max-Planck Institute for Informatik, Saarbruecken, Germany. His area of research is graph theory, combinatorics and graph algorithms. He is fellow of Indian National Science Academy (INSA) and Indian National Academy of Engineering (INAE).