The graph state formalism is a useful abstraction of entanglement. It is used in some multipartite purification schemes and it adequately represents universal resources for measurement-only quantum computation. We focus in this paper on the complexity of graph state preparation. We consider the number of ancillary qubits, the size of the primitive operators, and the duration of preparation. For each lexicographic order over these parameters we give upper and lower bounds for the complexity of graph state preparation. The first part motivates our work and introduces basic notions and notations for the study of graph states. Then we study some graph properties of graph states, characterizing their minimal degree by local unitary transformations, we propose an algorithm to reduce the degree of a graph state, and show the relationship with Sutner sigma-game. These properties are used in the last part, where algorithms and lower bounds for each lexicographic order over the considered parameters are presented.
The graph state formalism is a useful abstraction of entanglement. It is used in some multipartite purification schemes and it adequately represents universal resources for measurement-only quantum computation. We focus in this paper on the complexity of graph state preparation. We consider the number of ancillary qubits, the size of the primitive operators, and the duration of preparation. For each lexicographic order over these parameters we give upper and lower bounds for the complexity of graph state preparation. The first part motivates our work and introduces basic notions and notations for the study of graph states. Then we study some graph properties of graph states, characterizing their minimal degree by local unitary transformations, we propose an algorithm to reduce the degree of a graph state, and show the relationship with Sutner sigma-game. These properties are used in the last part, where algorithms and lower bounds for each lexicographic order over the considered parameters are presented.
In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state | G ⟩ as the minimum number of two-qubit Clifford operations required to generate | G ⟩ from | 0 ⟩ ⊗ ( n + s ) for some s ≥ 0 . Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, | G ⟩ can be generated from another graph state | H ⟩ by an algorithm of CZ-complexity at most t if and only if G can be obtained from H by vertex deletions, local complementations and at most t elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph G with n vertices and rank-width r , the CZ-complexity is O ( r n ) , and if G is connected then it is at least n + r − 2 . We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity O ( n ) and O ( n log n ) , respectively.
Graph states are multiparticle entangled states that correspond to mathematical graphs, where the vertices of the graph take the role of quantum spin systems and edges represent Ising interactions. They are many-body spin states of distributed quantum systems that play a significant role in quantum error correction, multiparty quantum communication, and quantum computation within the framework of the one-way quantum computer. We characterize and quantify the genuine multiparticle entanglement of such graph states in terms of the Schmidt measure, to which we provide upper and lower bounds in graph theoretical terms. Several examples and classes of graphs will be discussed, where these bounds coincide. These examples include trees, cluster states of different dimensions, graphs that occur in quantum error correction, such as the concatenated [7,1,3]-CSS code, and a graph associated with the quantum Fourier transform in the one-way computer. We also present general transformation rules for graphs when local Pauli measurements are applied, and give criteria for the equivalence of two graphs up to local unitary transformations, employing the stabilizer formalism. For graphs of up to seven vertices we provide complete characterization modulo local unitary transformations and graph isomorphisms.
Graph states are special multipartite entangled states that have been proven useful in a variety of quantum information tasks. We address the issue of characterizing and quantifying the genuine multipartite entanglement of graph states up to eight qubits. The entanglement measures used are the geometric measure, the relative entropy of entanglement, and the logarithmic robustness, have been proved to be equal for the genuine entanglement of a graph state. We provide upper and lower bounds as well as an iterative algorithm to determine the genuine multipartite entanglement.
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.
Graph states are multipartite entangled states that correspond to mathematical graphs, where the vertices of the graph now play the role of quantum multilevel systems and edges represent interactions of the systems. Graph states are the basis of quantum error correction and one-way quantum computer. We systematically study the entanglement of non-binary graph states. Using iterative algorithm and entanglement bounds, we calculate the entanglement of all the ternary graph states up to nine vertices and parts of quaternary and quinary graph states modulo local unitary transformations and graph isomorphisms. The entanglement measure can be the geometric measure, the measure of relative entropy of entanglement or the measure of logarithmic robustness. We classify the graph states according to the entanglement values obtained. The closest product states obtained in the calculations are studied.
Graph states form a rich class of entangled states that exhibit important aspects of multi-partite entanglement. At the same time, they can be described by a number of parameters that grows only moderately with the system size. They have a variety of applications in quantum information theory, most prominently as algorithmic resources in the context of the one-way quantum computer, but also in other fields such as quantum error correction and multi-partite quantum communication, as well as in the study of foundational issues such as non-locality and decoherence. In this review, we give a tutorial introduction into the theory of graph states. We introduce various equivalent ways how to define graph states, and discuss the basic notions and properties of these states. The focus of this review is on their entanglement properties. These include aspects of non-locality, bi-partite and multi-partite entanglement and its classification in terms of the Schmidt measure, the distillability properties of mixed entangled states close to a pure graph state, as well as the robustness of their entanglement under decoherence. We review some of the known applications of graph states, as well as proposals for their experimental implementation.