In the range of applications opened by quantum technology, often a highly entangled source state is needed as an input for a protocol (target state). The easiest example of such an application is QKD, other examples are quantum secret sharing and measurement based quantum computing. Generating a non-local entangled state is however not trivial. Let us assume that there is an entangled state (source state) present in the network before the start of the protocol. One can ask than whether this source state can be transformed to the target state with only local operations. Local operations usually have a lower error rate compared to non-local operations. As the set of all quantum states increases exponentially, we will restrict ourselves to graph states (quantum states described by a simple graph). This allows one to study the graphs and local operations in a graph theory perspective, instead of in a quantum information perspective. In this thesis we investigate the complexity of deciding equivalence of two graph states under local multi-qubit operations (T-LMQC-equivalent), where T refers to the partition denoting which qubits are on the same device which allows multi-qubit operations.

When T consist only of single qubit nodes, this problem reduces to the single qubit Clifford equivalence problem (SQC-EQUIV). It is known that SQC-EQUIV can be solved in O(N^4). On the other side, if all qubits are in the same node, the problem can be solved in O(1) as every source state can be transformed to any graph state on the same vertex set. We will present three algorithms to solve T-LMQC equivalence. The first algorithm solves the problem in general but the running time scales exponentially in the number of multi-qubit nodes and the size of the graph. The other two scale polynomially in the size of the graph, but do not allow for nodes with more than 2 qubits. The remaining question is indeed whether deciding T-LMQC equivalence is an easy (in P) problem or a hard problem (NP-complete).