Graphs in quantum information theory

I will discuss some of the relationships between quantum information and graph theory that have been developed over the past few years. There are two main points of contact between these seemingly disparate fields. One of these is to consider a graph as a collection of vertices in either real or configuration space, connected by edges. A major effort in this case is to construct quantum algorithms that can efficiently determine properties of the graph, and I will describe in detail one such approach which is based on quantum walks. The other point of contact is to consider each vertex as a qudit, with edges representing an entangling operation. In this picture, each graph is uniquely associated with a highly entangled quantum state known as a graph state or stabilizer state. I will discuss the relationship between stabilizers and the theory of quantum error correction. I will also show that certain graph states, known as cluster states, are a resource for universal quantum computation based only on measurements.