2021/12/03 by Priyanga Ganesan, Ganesan, Priyanga · 3 citations
Computer Science · Mathematics · #FOS: Mathematics #FOS: Physical sciences #Operator Algebras (math.OA) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2112.01726
openalex publication_date 2021/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quantum graphs are an operator space generalization of classical graphs that have emerged in different branches of mathematics including operator theory, non-commutative topology and quantum information theory. In this paper, we obtain lower bounds for the classical and quantum chromatic number of a quantum graph using eigenvalues of the quantum adjacency matrix. In particular, we prove a quantum generalization of Hoffman's bound and introduce quantum analogues for the edge number, Laplacian and signless Laplacian. We generalize all the spectral bounds given by Elphick and Wocjan (2019) to the quantum graph setting and demonstrate the tightness of these bounds in the case of complete quantum graphs. Our results are achieved using techniques from linear algebra and a combinatorial definition of quantum graph coloring, which is obtained from the winning strategies of a quantum-to-classical nonlocal graph coloring game, given by M. Brannan, P. Ganesan and S. Harris (2020).