Graph state invariants and the graph isomorphism problem
thesisposted on 2020-07-29, 09:45 authored by Patrick Mills
The application of equal-angle Wigner functions (EAWF) of graph states to the graph isomorphism problem has been investigated. The method has promise as the EAWF is inherently permutation invariant and has previously been used to efficiently identify quantum states. Other quantum approaches to the problem have mainly used quantum walks or adiabatic methods and have not been based upon graph states, leaving a gap which this work makes steps to fill. The EAWFs of graph states were numerically calculated and nonisomorphic graphs were found which shared EAWFs. The reason for this degeneracy was investigated resulting in the development of a family of new graph invariants, members of which may be complete. The practicality of applying these invariants is analysed, but no polynomially efficient implementation has been found due to the difficulties associated with obtaining adequate statistics for large systems of qubits. The significance of the work is the discovery of a family of graph invariants which may offer new insight on the graph isomorphism problem.