**Complexity of graph state preparation** - Mehdi Mhalla

The talk will analyse the complexity of preparation of some quantum states called graph states. We investigate the evolution of the minimal degree of a graph by a combinatorial operation introduced by Bouchet called local complementation, and characterize this minimal degree using local properties and using a game introduced by Sutner called sigma-game. Then we present a graph contraction-based algorithm that benefits of ancillary qubits to reduce the time complexity of the preparation of these states, and prove a time-space tradeoff TS=O(m), where m is the number of edges of the graph. We consider the case where unitary operators are used and also the case where only measurements are available. Finally, we prove upper and lower bounds on the size of the measurements needed when no ancillary qubits are available.