Quantum isomorphism, which is originated from solving problems in physics, has now become a crucial concept in graph theory for analyzing the structure of two graphs. It is of great importance to determine whether any given pair of graphs is quantum isomorphic, as well as to identify cases where two graphs are not isomorphic but exhibit quantum isomorphism. Furthermore, it has been observed that graphs are quantum isomorphic only when they contain at least 16 vertices. Thus, the primary objective of this thesis is to address the quantum isomorphism of specific problems and graphs with 16 vertices that are classified based on their girth.

The main tool we use in the thesis are two notions called scaffolds and pattern reduction. The former notion is closely associated with counting graph homomorphisms that are relevant to quantum isomorphism, while the latter represents a novel process outlined in this thesis, aiming at simplifying the research procedure. Based on our investigations, we have obtained several results. Firstly, the strongly regular graphs(SRG), specifically the H(2, 4) and the Shrikhande graph, are not quantum isomorphic, and neither are the T(8) and the three Chang graphs. Moreover, when considering two graphs with 16 vertices and respective girths g_1 and g_2, we establish that they are not quantum isomorphic if any of the following conditions hold: (a) both g_1 = g_2 ≥ 9 or ∞; (b) g_1 = g_2 = 8 and both of the graphs are planar or nonplanar. Importantly, through our methods, we are able to generalize part of the results to encompass all graphs. We have concluded that two graphs are not quantum isomorphic under the following conditions: (a) g_1 ≠ g_2 and g = min{g_1, g_2} is odd, or (b) both two graphs are planar, regardless of the number of vertices.

Albert Atserias, Laura Mančinska, David E Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289–328, 2019.
Norman Biggs, Norman Linstead Biggs, and Biggs Norman. Algebraic graph theory. Number 67. Cambridge University Press, 1993.
Andries E Brouwer and Willem H Haemers. Distance-regular graphs. Springer, 2012.
Andries E Brouwer, AM Cohen, and A Neumaier. Distance-regular graphs, Springer-Verlag, Berlin etc. 1989.
Ada Chan and William J Martin. Quantum isomorphism of graphs from association schemes. arXiv preprint arXiv:2209.04581, 2022.
Yoshimi Egawa. Characterization of H(n, q) by the parameters. Journal of Combinatorial Theory, Series A, 31(2):108–125, 1981.
Chris Godsil and Gordon F Royle. Algebraic graph theory, volume 207. Springer Science & Business Media, 2001.
Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta Mathematicae, 15(1):271–283, 1930.
Xiaoye Liang, Ying-Ying Tan, Hajime Tanaka, and Tao Wang. A duality of scaffolds for translation association schemes. Linear Algebra and its Applications, 638:110–124, 2022.
Laura Mančinska and David E Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661–672. IEEE, 2020.
William J Martin. Scaffolds: a graph-theoretic tool for tensor computations related to Bose-Mesner algebras. Linear Algebra and its Applications, 619:50–106, 2021.
Ion Nechita, Simon Schmidt, and Moritz Weber. Sinkhorn algorithm for quantum permutation groups. Experimental Mathematics, pages 1–13, 2021.
Simon Schmidt. Quantum automorphism groups of finite graphs. 2020.
Simon Schmidt. On the quantum symmetry of distance-transitive graphs. Advances in Mathematics, 368:107150, 2020.
W. A. Stein et al. Sage Mathematics Software (Version 9.3). The Sage Group, 2021. http://www.sagemath.org.
Paul Terwilliger. A characterization of P-and Q-polynomial association schemes. Journal of Combinatorial Theory, Series A, 45(1):8–26, 1987.
Stanisław L Woronowicz. Compact matrix pseudogroups. Communications in Mathematical Physics, 111:613–665, 1987.
Stanisław L Woronowicz. A remark on compact matrix quantum groups. Letters in Mathematical Physics, 21(1):35–39, 1991.