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).
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).
Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G) can be transformed into another graph state |G) using LC + LPM + CC is NP-complete, which was previously not known. We also show that the problem remains NP-complete even if |G) is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G) can be transformed to another graph state |G) is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G' is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is NP-complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on n labelled vertices in O(n6.38) bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost O(n5) bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.
Abstract Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G⟩ can be transformed into another graph state |G′⟩ using LC + LPM + CC is N P -complete, which was previously not known. We also show that the problem remains NP-complete even if |G′⟩ is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G⟩ can be transformed to another graph state |G′⟩ is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G′ is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is N P -complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.
In quantum computing and quantum information processing, graph states are a specific type of quantum states which are commonly used in quantum networking and quantum error correction. A recurring problem is finding a transformation from a given source graph state to a desired target graph state using only local operations. Recently it has been shown that deciding transformability is already NP-hard. In this paper, we present a CNF encoding for both local and non-local graph state operations, corresponding to one- and two-qubit Clifford gates and single-qubit Pauli measurements. We use this encoding in a bounded-model-checking set-up to synthesize the desired transformation. Additionally, for a completeness threshold on local transformations, we provide an upper bound on the length of the transformation if it exists. We evaluate the approach in two settings: the first is the synthesis of the ubiquitous GHZ state from a random graph state where we can vary the number of qubits, while the second is based on a proposed 14 node quantum network. We find that the approach is able to synthesize transformations for graphs up to 17 qubits in under 30 minutes.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this manuscript a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.