Georgia Institute of Technology College of Sciences

Quantum computing is concerned with harnessing the peculiar properties of quantum mechanics, in order to perform information-processing tasks beyond the capabilities of classical computers. Graph states are a family of quantum states, the resources for quantum computers. Graph states exhibit complex forms of quantum entanglement, implying for example that a quantum computer based on graph states is as powerful as any other quantum computer. But, unlike general quantum states, graph states are very easy to describe thanks to their one-to-one correspondence with mathematical graphs. This correspondence implies that many tools from graph theory can be applied to problems in quantum computing.

This talk aims to provide a gentle introduction to graph states, directed toward graph theorists. I will discuss two main applications of graph states, quantum networks and measurement-based quantum computing, and relate these applications to well-known graph-theoretical concepts, in particular vertex-minors. Finally, I will discuss the problem of classifying graph states, and the recent progress achieved through the development of new graph-theoretical tools.