Graph State Optimization with Integer Linear Programs

Graph states are a powerful class of entangled states that find use in the field of quantum information and quantum computation (e.g. quantum repeaters, measurement-based quantum computing, error correction). Local Clifford (LC) operations mapping between graph states can be interpreted as sequences of local complementations on their corresponding graphs. These local complementations can alter the number of edges in a graph. This is important because the number of edges of a graph is related to the cost of constructing the associated graph state through entangling gates. We investigate the problem of finding a graph state with the minimum number of edges (and thus cost) in the LC-orbit of a given graph; we call this a minimum edge representative (MER). To do this we leverage Bouchet's formulation of LC equivalence in terms of binary linear algebra to find MERs by encoding the associated minimization into an integer linear program (ILP). We also propose a simulated annealing (SA) approach based on a graph metric called the clustering coefficient. We combine the two algorithms to find MERs for bounded-degree graphs with up to 17 vertices and for Erdos-Renyi graphs with 13 vertices. Our method can also be used to find MERs when the edges have weights attached to them, and for solving the vertex-minor problem.