Optimal preparation of graph states

Optimal preparation of graph states Ad´an Cabello,1,* Lars Eirik Danielsen,2,† Antonio J. L´opez-Tarrida,1,‡ and Jos´e R. Portillo3,§ 1Departamento de F´ısica Aplicada II, Universidad de Sevilla, E-41012 Sevilla, Spain 2Department of Informatics, University of Bergen, P.O. Box 7803, Bergen N-5020, Norway 3Departamento de Matem´atica Aplicada I, Universidad de Sevilla, E-41012 Sevilla, Spain We show how to prepare any graph state of up to 12 qubits with (a) the minimum number of controlled-Z gates and (b) the minimum preparation depth. We assume only one-qubit and controlled-Z gates. The method exploits the fact that any graph state belongs to an equivalence class under local Clifford operations. We extend up to 12 qubits the classification of graph states according to their entanglement properties, and identify each class using only a reduced set of invariants. For any state, we provide a circuit with both properties (a) and (b), if it does exist, or, if it does not, one circuit with property (a) and one with property (b), including the explicit one-qubit gates needed. I. INTRODUCTION Building a quantum computer entails isolating atomic-scale systems, except when a controlled interaction (e.g., a logic gate) is applied. Isolation must be kept up until a subsequent controlled interaction is applied. Any undesirable coupling with the outside disrupts the quantum state of the systems and ruins the computation. Due to the enormous difficulties which keeping atomic-scale systems isolated and controlled entails, a main limiting factor preventing the development of quantum computing is the amount of time during which the systems must be kept isolated and controlled to achieve the computation. Therefore, the task of reducing this amount of time is an essential factor in the process of achieving the goal of building a quantum computer. Another limiting factor for quantum computation is the number of entangling gates needed. While one-qubit gates can be built with fidelities higher than 99%, two-qubit entangling gates hardly reach 93%, and this becomes worse for threequbit gates, etc. Therefore, since oneand two-qubit gates are enough for universal quantum computation, it is reasonable to focus on circuits with only oneand two-qubit gates, and having the least possible number of two-qubit gates. Here we address the problem of preparing an important class of quantum states with circuits requiring (a) the minimum number of two-qubit entangling gates and (b) the minimum preparation depth (i.e., requiring a minimum number of time steps). We assume that we can implement arbitrary one-qubit gates and one specific two-qubit entangling gate, the controlled-Zgate. The result can be easily extended to any other specific two-qubit gate. A. Graph states Graph states [1,2] are a type of n-qubit pure state with multiple applications in quantum-information processing. Two *[email protected] †[email protected].no ‡[email protected] §[email protected] important examples are in quantum error correction, the stabilizer codes which protect quantum systems from errors [3–5] and, in measurement-based (or one-way) quantum computation [6], the initial states consumed during the computation [7]. The definition of a graph state already provides a blueprint for its preparation: an n-qubit graph state |Gis a pure state associated with a graph G=(V,E) consisting of a set of nvertices V={0,...,n−1}and a set of edges E connecting pairs of vertices, E⊂V×V[1,2]. Each vertex represents a qubit. An edge (i,j)∈Erepresents an Ising-type interaction between qubits iand j. To prepare |G,first prepare each qubit in the state |+ = 1 √2(|0+|1), i.e., the initial state will be |ψ0=⊗ i∈V|+i. Then, for each edge (i,j)∈Econnecting two qubits iand j, apply a controlled-Z gate between these qubits, i.e., the unitary transformation CZ=|0000|+|0101|+|1010|−|1111|. B. Preparation using only controlled-Zgates Let us suppose that we have the state |ψ0=⊗ n−1 i=0|+i, and we want to prepare the eight-qubit graph state |Gwhose graph Gis in Fig. 1, using only controlled-Zgates. One possible way is to follow the preparation procedure suggested by G, taking into account the possible restrictions in performing two or more controlled-Zgates simultaneously, and optimally distributing the controlled-Zgates to minimize the number of steps. The preparation depth of |Gis the minimum number of time steps required to prepare |G[8]. The state |ψ0corresponds to a graph with nisolated vertices. The total number of edges in Ggives a trivial upper bound to the preparation depth of |G, since each controlled-Z can be applied in a time step. To find the minimum number of time steps, we have to explore the possibility of applying two or more controlled-Zgates in a single time step. Given a vertex iin G,theneighborhood of i,N(i), is the set of vertices connected to i. Now let us suppose that there is more than one element in N(i), i.e., |N(i)|>1, and let j,k ∈N(i) be two of the neighbors. Then, to prepare the corresponding graph state |Gwe must apply a controlled-Zgate to entangle qubits iand j, and another one to entangle qubits iand k. Applying a controlled-Zgate between qubits iand jin a 0 7 6 5 4 3 2 1 FIG. 1. (Color online) Graph corresponding to the eight-qubit graph state we want to prepare. Edges in the same color represent controlled-Zgates that can be performed in the same time step. certain time step implies that both qubits are busy during this entangling interaction. If we focus on qubit i,wehavetowait for a further time step to have qubit ifree before applying another controlled-Zgate to entangle iand k. Nevertheless, vertex kcould be connected to another vertex l={i,j}in G. If such is the case, we could in principle take advantage of the same time step we are using to entangle qubits iand jin order to do the same with qubits kand l, because both controlled-Z gates can be performed in parallel. Remarkably, the problem of determining the minimum number of time steps with the restrictions that we have mentioned is related to an old problem in graph theory: given an edge (i,j)inG, let us use a certain color to mark (i,j) and those other edges of Gcorresponding to controlled-Z gates that can be performed at the same time step than that of (i,j), and use different colors for those edges related to controlled-Zgates that do not fulfill this condition. Since two controlled-Zgates can be performed at the same time step if and only if the four qubits involved do not coincide, then every edge incident to the same vertex must have a different color. In graph theory this color configuration is called a proper edge coloring or, to put it more concisely, the graph is said to be edge-colored. Hence, the preparation depth problem is equivalent to determining the minimum number of colors required to get a proper edge coloring of G. This problem is known as the determination of the chromatic index or edge chromatic number χ(G). Let us denote by (G) the maximum degree of G(i.e., the maximum number of edges incident to the same vertex). Vizing’s theorem [9] states that Gcan be edge-colored in either (G)or(G)+1 colors, and not fewer than that. Therefore, χ(G)iseither(G)or(G)+1. A proof can be found in [10]. The important point is that χ(G) gives the preparation depth of |G[8,11]. Graphs requiring (G) colors are called class-1 graphs, and those requiring (G)+1 colors are called class-2 graphs. For instance, the four-qubit fully connected graph state is represented by a graph of four vertices, six edges, and maximum degree equal to 3: it is a class-1 graph, so that its preparation depth coincides with its maximum degree: 3. On the other hand, the three-qubit fully connected graph state is represented by a graph of three vertices with three edges and maximum degree equal to 2: it is the smallest class-2 graph and, as a consequence, its preparation depth is also 3. 12 34567 Qubit 1 Qubit 0 Qubit 2 Qubit 3 Qubit 4 Qubit 5 Qubit 6 Qubit 7 FIG. 2. (Color online) A circuit with minimum preparation depth for the graph state corresponding to Fig. 1, using only controlled-Z gates. In the circuit, a qubit (vertex of the graph) is represented by a horizontal wire, and a controlled-Zgate (edge in the graph) by a vertical segment with diamond-shaped ends connecting the qubits involved in the operation. Time steps are separated by vertical dashed lines. The graph in Fig. 1is a class-1 graph: it can be edge-colored with (G)=7 colors (this number corresponds to the degree of vertex 3). Hence, if we use only controlled-Zgates, the minimum preparation depth of the corresponding graph state is 7. For instance, one of the optimal distributions of the 13 controlled-Zgates is given in the circuit of Fig. 2, which has seven time steps. However, if we are allowed to use one-qubit gates, in most cases it is possible to get the desired graph state with a lower number of two-qubit gates and less preparation depth. For that purpose, one has to take into account the degree of entanglement of the state we want to prepare. C. Optimum preparation Two graph states have the same degree of entanglement if and only if they are equivalent under local unitary (LU) operations [12], so that they belong to the same LUequivalence class. Moreover, previous results suggest that for graph states of up to 26 qubits [13], the notions of LU equivalence and LC equivalence (equivalence under local Clifford operations) coincide, and, therefore, entanglement classes are in fact local Clifford equivalence classes (LC classes). This implies a remarkable simplification, since it is possible to carry out a graphical description of the action of local Clifford transformations on graph states [14]: the successive application of a simple graph transformation rule, the so-called local complementation, on a certain graph Gand on those that are obtained from G, allows us to generate the whole LC class of |G. The entire set of graphs connected to agivenGby a sequence of local complementations is usually referred to as the orbit of G(i.e., the LC class of |G). Any of the graph states belonging to a given LC class could be used as a representative for that orbit, but there is a practical advantage in taking one requiring (a) the minimum number of controlled-Zgates or (b) the minimum preparation depth of the class. If we can identify which LC class a given |Gbelongs to, then we can prepare |Gby preparing instead the LCequivalent state |Grequiring (a) and (b), and then transform |G into |G by means of single-qubit Clifford operations corresponding to a sequence of local complementations carried out on G. This last transformation from |G to |G requires only one additional time step, since the local complementation at vertex a is equivalent [1,2] to the unitary operation Uτ a(G)=exp −iπ 4σ(a) x b∈N(a) exp iπ 4σ(b) z,(1) where σ(a) xis the Pauli matrix σxacting on qubit a,σ(b) zis the Pauli matrix σzacting on qubit b, and N(a) is the neighborhood of a. Operations on different qubits commute, and therefore one can group together a sequence of local complementations Uτ a(G)intonone-qubit gates Ri(with i=0,...,n−1), which can be jointly performed in a single step. The preparation procedure of a graph state |Gthrough the optimum LC representative provides an advantage in time steps when compared to the standard graph-based controlled-Z procedure when χ(G)−χ(G)>1,(2) since the preparation depth for the standard procedure is χ(G), while the preparation depth through the optimum LC representative is χ(G)+1, that is, the sum of the preparation depth of the optimum LC representative plus a unit of time corresponding to the one-qubit gates. This means that the preparation depth through the optimum LC representative provides an advantage for most graph states. For instance, as we will see, for the graph state of Fig. 1, the optimum preparation circuit requires only seven controlled-Zgates and three time steps: saving six controlled-Zgates and requiring four time steps fewer than in the standard procedure. However, the preparation through the optimum LC representative requires us to identify which LC class |Gbelongs to. To be practical, this must require us to identify the simplest signature of the class. In Sec. II, we classify all LC classes for graph states up to n=12 qubits. This classification is based on a reduced set of invariants which allows us to identify which class a given state belongs to. In Sec. III, we provide a representative of the class with both properties (a) and (b), if it exists, or, if it does not, one with property (a) and one with property (b). All these results, which occupy several hundreds of megabytes, are organized in two tables, one for n<12 and one for n= 12, and presented as supplementary material [15]. Finally, in Sec. IV, we explain how to obtain the one-qubit gates needed and provide as supplementary material a computer program [16] to, given the graph Gcorresponding to the state we want to prepare, generate a sequence of local complementations which connect Gto the corresponding optimum graph(s). In Sec. V, the whole method is illustrated with an example. II. CLASSIFICATION OF GRAPH STATES IN TERMS OF ENTANGLEMENT The classification of the entanglement of graph states has been achieved up to n=7[1,2], and has recently been extended to n=8[17]. There are 45 LC classes for graph states up to seven qubits, and 101 LC classes for eight-qubit graph states, which are ordered according to certain criteria based on several entanglement measures, which are invariant under LC transformations. Here we extend the classification up to n=12. The number of orbits for n⩽8 qubits is 146. For n=9, there are 440 orbits; for n=10, there are 3132 orbits; for n=11, there are 40 457; and for n=12, there are 1 274 068. All the information about each LC class is presented as supplementary material [15]. For each LC class we give the number of nonisomorphic graphs in that class (size of the orbit), |LC|. Then, the orbits are classified according to the number of vertices (qubits), |V|; the minimum number of edges of a graph belonging to the class (controlled-Zgates needed for the preparation), |E|; the Schmidt measure, ES(upper and lower bounds are given where the exact value is unknown); and for n/2⩾i⩾2, the rank indexes RIifor bipartite splits with ivertices in the smallest partition. The classifying labels |V|,|E|,ES, and RIiare applied in this order. Additionally, we include the information regarding the existence (or not) of a two-colorable graph belonging to the class (a piece of data which is useful, in some cases, to calculate lower and upper bounds for the Schmidt measure). However, these numbers, which were (almost) enough to identify every class if n⩽8, are not enough to identify every class if n>8. In other words, the set of entanglement measures for n-qubit graph states used in [1,2,17] failed to distinguish between inequivalent classes under local Clifford operations if n>8: different LC classes had coincident values for those entanglement measures. In fact, the number of problematic LC classes increases with n. Therefore, using these invariants for deciding which entanglement class a given state belongs to is unreliable. A finite set of invariants that characterizes all classes has been proposed in [18]. However, already for n=7, this set has more than 2 ×1036 invariants which are not explicitly calculated anywhere, and hence this set is not useful for classifying a given graph state. Nevertheless, a compact set of invariants related to those proposed in [18] is enough to distinguish among all inequivalent LC classes with n⩽8 qubits: the four two-index invariants called cardinalities-multiplicities [19]. There is a straightforward procedure for calculating these four invariants using the information contained in the graphs. We have analyzed the utility and limitations of the cardinalities-multiplicities (C-M hereafter) as LC-class discriminants for graph states up to 12 qubits, a question that was left as an open problem in [19], where it was conjectured that four of these C-M invariants would be enough to label and discriminate all the LC classes. Our results show that for graph states of n⩾9 qubits, the C-M invariants fail to distinguish between inequivalent LC classes: the smallest counterexample of the conjecture corresponds to a pair of nine-qubit orbits that have exactly the same entire list of C-M invariants. These are the only problematic orbits for n=9 qubits. As an alternative for discriminating between them, we have calculated the whole list of Van den Nest-Dehaene-De Moor (VDD) invariants of type r=1[18] for these two orbits, and once again these invariants coincide. In order to determine the number of C-M and VDD “problematic” (undistinguishable) orbits, we have extended our calculations up to n=12 qubits. The ratio pf(n) of the number of graphs belonging to problematic TABLE I. Orbits for which C-M and VDD invariants are not good LC discriminants. nNo. of orbits No. of problematic orbits pf(n) ⩽8 146 0 0 9 440 2 0.001 221 8 10 3 132 8 0.000 699 6 11 40 457 78 0.001 192 9 12 1 274 068 472 0.000 094 9 orbits and the overall number of graphs for each n,givesthe probability that a randomly chosen graph state falls in one of the problematic orbits. The values of pf(n) are, fortunately, quite low (see Table I). Therefore, the first step of the procedure of preparation, i.e., the identification of the orbit, resorts to C-M invariants (and, sometimes, type r=1 VDD invariants), and works in most cases. For those rare states whose orbit identification through C-M or VDD (r=1) invariants is not univocal, one would resort to VDD invariants of higher order r[18]. However, the computational effort of this task makes this procedure less efficient than simply generating the whole LC orbit of the graph. In the supplementary material [15], those LC classes which have the same set of quantities {|V|,|E|,ES,RIi} are ordered according to the C-M invariants, going from the smallest cardinality (zero) to the biggest one, and increasing the value of the associated multiplicity of each cardinality. For those orbits with the same set of quantities {|V|,|E|,ES,RIi,C-M invariants}, orbits are ordered by the increasing size of the orbit, |LC|. We do not apply any subsequent classifying criteria, in case there were undistinguishable LC classes left. C-M invariants are given as an ordered list of multiplicities Mi,fori=0,...,x.ThevalueMiis the multiplicity of the cardinality i. We do not list all 2npossible multiplicities, but only the multiplicities of cardinalities 0,...,x, where xis the smallest number such that all “nonproblematic” orbits are distinguished. This may not be the smallest possible set of C-M invariants. For instance, only the cardinalities {0,1,3,4}are needed for n⩽8, but, for simplicity’s sake, we have included the continuous list {0,1,2,3,4}. III. OPTIMUM REPRESENTATIVE We have determined the optimum representatives for all the orbits up to 12 qubits, initially defined as one of those with the minimum number of edges in the orbit and, among them, one of those with the minimum chromatic index. In the supplementary material [15], we have included a column labeled min(|E|,χ,#) for each LC class, where |E|is the minimum number of edges in the class, χis the minimum chromatic index of the graphs with |E|edges, and # is the number of nonisomorphic graphs with |E|edges and chromatic index χ.Thevalueofχcoincides with the preparation depth of those representative states and indicates how much more efficient the preparation procedure we are proposing is than the standard one [it is χ(G)inEq.(2)]. While carrying out the LC classification, an interesting observation arose: the optimum representative of a certain orbit was determined by the application of two filters to the orbit in a certain order. First, we looked for the graph with the minimum number of edges (which implies a minimum number of two-qubit entangling operations), |E|, and second the minimum chromatic index χfixed that |E|(which means a minimum preparation depth given those graphs with |E| edges). However, if we commute the order of the filters, for n⩽7 qubits, the result of the permutation of the filters gives the same graph, but this is not the case for n>7. We get the simplest example of noncoincidence between the final optimum representatives for n=8, where there is only one orbit (LC class number 136) in which the permutation of the filters does not produce the same final graph. There are two graphs in this orbit with |E|=11 and χ=4, and one graph with χ=3 and |E|=12 (see Fig. 3). For each n⩽12, we calculated the number of orbits with different final representatives when we applied the filters in different order: the ratio of the number of “exceptional” orbits and the entire number of orbits increases with n,forn⩾9 (Table II). Moreover, we have included in our tables (see supplementary material [15]), beside the column labeled min(|E|,χ,#), another column labeled min(χ,|E|,#), with a 3-tuple of values (χ,|E|,#), where χis now the minimum chromatic index in the class, |E|is the minimum number of edges of the graphs with chromatic index χ, and # is the number of nonisomorphic graphs with chromatic index χand |E|edges. Checking the coincidence of χand |E|in both columns directly tells us if a certain orbit is exceptional or not. In case of coincidence, we have left the second column blank. From an experimental point of view, the appropriate order for the filters is something that the experimentalists should elucidate, since it is related to the physical substrate used to implement the qubits, and the resources at their disposal. If minimizing the number of two-qubit entangling operations is a critical factor, because the fidelity in performing such quantum gates is lower than desirable, then the appropriate order is (|E|,χ): once the number of gates is minimized, then it is the turn of reducing the preparation depth. To complete our results in [15] we provide, in the two final columns for each LC class, an optimum graph resulting from the filters applied in the order min(|E|,χ,#), and another one applying the filters as min(χ,|E|,#) (if it is not coincident with the former; in case of coincidence, the second final column is left blank). The edges of the graph are listed, with vertices indexed as 0,...,n−1. Moreover, edges are divided in classes (enclosed by parentheses) that define a proper edge-coloring (with χcolors). This information is equivalent to providing an optimum circuit [with a number of time steps equal to χ(G)] for preparing the optimum representative graph Gof the class. The graphs and circuits in Fig. 3have been designed according to the information in the supplementary material [15]forLC class number 136. IV. ONE-QUBIT GATES Assuming that an experimentalist has prepared the optimum representative graph state |Gcorresponding to the desired state |G, he or she needs to know at least one sequence of local complementations connecting |Gwith |G. The length of this LC sequence is not relevant, due to the possibility of 12 345 Qubit 1 Qubit 0 Qubit 2 Qubit 3 Qubit 4 Qubit 5 Qubit 6 Qubit 7 R0 R1 R2 R4 R5 R6 R3 R7 0 7 6 5 4 3 2 10 7 6 5 4 3 2 1 12 34 Qubit 1 Qubit 0 Qubit 2 Qubit 3 Qubit 4 Qubit 5 Qubit 6 Qubit 7 R’ 0 R’ 1 R’ 2 R’ 4 R’ 5 R’ 6 R’ 3 R’ 7 FIG. 3. (Color online) Two optimum representatives for LC class number 136 (up). The graph on the left is obtained by applying over the entire orbit the filter min(|E|,χ), i.e., first minimizing over |E|and then over χ, whereas the one on the right is obtained by applying the filter min(χ,|E|). Any graph state belonging to LC class number 136 could be prepared by means of the circuits depicted under those representatives. The circuit on the left prioritizes a lower number of entangling gates; the one on the right prioritizes a lower preparation depth. Riand R iare one-qubit gates. They are specific for the state of the class 136 we want to prepare. implementation of these local operations as one-qubit gates in only one time step, as was already discussed above. However, finding a way in the orbit from |Gto |Gis a hard task. To make the entire orbit-based preparation procedure practical, we have designed a computer program that accomplishes this task. Very briefly, it uses the information about the graph Grelated to the state |Gthat one wishes to obtain. The input is the information about the edges. The program finds the optimal graph(s) Gwith respect to both the number of edges and chromatic index (these two quantities are also part of the output), and provides a sequence of LC operations TABLE II. Orbits for which a different order of filters relating the minimum number of edges and minimum chromatic index produces a noncoincident representative graph. nNo. of orbits No. of exceptional orbits ⩽745 0 8 101 1 9 440 3 10 3 132 65 11 40 457 2 587 12 1 274 068 136 518 transforming |Ginto |G. This computer program is included as supplementary material [16]. V. EXAMPLE In order to clarify the whole process, we go back to the graph in Fig. 1. As we mentioned, Gis a class-1 graph. Therefore, the preparation depth of |Gusing only controlled-Zgates is 7. The orbit-based procedure allows us to reduce significatively the preparation depth and the number of controlled-Z gates. It consists of the following steps: 0 7 6 5 4 3 2 1 FIG. 4. (Color online) Graph state LC8, optimum representative of orbit 68. 12 3 Qubit 1 Qubit 0 Qubit 2 Qubit 3 Qubit 4 Qubit 5 Qubit 6 Qubit 7 R0 R1 R2 R4 R5 R6 R3 R7 FIG. 5. (Color online) Optimum circuit for preparing the graph state corresponding to Fig. 1. (I) To identify the orbit or LC equivalence class the graph state |Gbelongs to, we calculate the cardinality-multiplicity invariants [19]. The result is {0170,135,312,47}. Therefore, after consulting [15], we conclude that the graph state |Gbelongs to the LC class number 68. (II) Also in [15] we find the optimum representative graph G: it is the eight-vertex linear cluster LC8(see Fig. 4). Graph LC8is a class-1 graph, whose maximum degree is (G)=2. Hence its preparation depth is 2, which means a remarkable saving in the preparation depth compared to that of |G. (III) Therefore, it is worth preparing |Gby preparing |Gand then applying suitable one-qubit gates. The program in [16] outputs a sequence of local complementations which connects Gto G. For instance, the sequence of LC operations applied on vertices 6, 7, 4, 5, and 2 in graph Genables us to obtain G. Denoting the corresponding series of local Clifford operations by τ(G), we have |G=τ(G)|G. Applying Eq. (1) and rearranging terms so that τ(G)=i∈VRi, where Riis a specific gate on qubit i, we obtain that R0=exp iπ 2σ(0) z,(3a) R1=exp i3π 4σ(1) z,(3b) R2=exp −iπ 4σ(2) xexp iπ 4σ(2) z,(3c) R3=exp iπ 2σ(3) z,(3d) R4=exp iπ 4σ(4) zexp −iπ 4σ(4) xexp iπ 4σ(4) z,(3e) R5=exp −iπ 4σ(5) xexp iπ 4σ(5) z,(3f) R6=exp iπ 2σ(6) zexp −iπ 4σ(6) x,(3g) R7=exp iπ 4σ(7) zexp −iπ 4σ(7) x.(3h) In addition, the number of controlled-Zgates necessary to get |Gis remarkably reduced (six two-qubit gates fewer than in the standard preparation method). The optimum circuit for preparing |G, with a preparation depth equal to 3, is the one in Fig. 5. VI. CONCLUSIONS We have proposed a procedure for the optimal preparation of any of the more than 1.65 ×1011 graph states with up to 12 qubits, based on their entanglement properties. Optimal means with both (a) a minimum number of entangling gates and (b) a minimum number of time steps, when possible, or choosing between (a) or (b), in the other cases. The preference will depend on the particular physical system we are considering. The main goal has been to provide in a single package all the tools needed to rapidly identify the entanglement class the target state belongs to, and then easily find the corresponding optimal circuit(s) of entangling gates, and finally the explicit additional one-qubit gates needed to prepare the target, starting with a pure product state and assuming only arbitrary onequbit gates and controlled-Zgates, which constitutes the most common scenario for practical purposes. The results presented in this paper go beyond those in [1,2, 17,19] the classification of entanglement for a highly relevant family of qubit pure states (graph states and, by extension, stabilizer states) of 9, 10, 11, and 12 qubits. In total, almost 1.3×106entanglement classes are introduced. The results have experimental relevance. For example, imagine an experimentalist in the field of trapped ions who wants to prepare graph states. The experimentalist knows that he can keep, e.g., nine ions (qubits) isolated from external influences for a given period of time, and knows that during this time he can perform a maximum of mtwo-qubit entangling operations with an efficiency above a certain threshold. The experimentalist wants to know which classes of graph states (which classes of entanglement) are a reasonable target with these resources. The results in this paper allow him to answer this question: if m=8, he can prepare 47 different classes (classes 147–193 in [15]); if m=9, he can prepare 47 +95 =142 different classes (classes 147–288 in [15]), etc. Moreover, the paper tells the experimentalist which is the optimum sequence of lasers (gates) required for preparing any state of each class. More interestingly, consider that the experimentalist wants to prepare a specific nine-qubit graph state. The paper provides the simplest known protocol to identify which entanglement class the target state belongs to, and gives the simplest circuit to prepare it, where “simplest” means in most cases the one requiring the minimum number of entangling gates and computational steps, or, in those cases in which such a circuit does not exist, gives a circuit requiring the minimum number of entangling gates, and a circuit requiring minimum depth. ACKNOWLEDGMENTS The authors thank E. Kashefi and P. Moreno for useful conversations. A.C. and A.J.L.T. were supported by MICINN Project No. FIS2008-05596, A.C. was also supported by the Wenner-Gren Foundation, L.E.D. was supported by the Research Council of Norway, and J.R.P. was supported by MICINN Project No. MTM2008-05866. [1] M. Hein, J. Eisert, and H. J. Briegel, Phys. Rev. A 69, 062311 (2004). [2] M. Hein, W. D¨ ur, J. Eisert, R. Raussendorf, M. Van den Nest, and H. J. Briegel, in Quantum Computers, Algorithms and Chaos, edited by G. Casati, D. L. Shepelyansky, P. Zoller, and G. Benenti (IOS, Amsterdam, 2006). [3] D. Gottesman, Phys.Rev.A54, 1862 (1996). [4] D. Schlingemann and R. F. Werner, Phys. Rev. A 65, 012308 (2001). [5] D. Schlingemann, Quantum Inf. Comput. 2, 307 (2002). [6] R. Raussendorf and H. J. Briegel, Phys.Rev.Lett.86, 5188 (2001). [7] M. Van den Nest, A. Miyake, W. D¨ ur, and H. J. Briegel, Phys. Rev. Lett. 97, 150504 (2006). [8] M. Mhalla and S. Perdrix, in Proceedings of the 8th Workshop on Quantum Information Processing (QIP’05), Boston, January 2005 (unpublished), e-print arXiv:quant-ph/0412071. [9] V. G. Vizing, Diskret. Analiz. 3, 25 (1964). [10] J. Misra and D. Gries, Inform. Process. Lett. 41, 131 (1992). [11] A. Broadbent and E. Kashefi, Theor. Comput. Sci. 410, 2489 (2009). [12] M. Van den Nest, J. Dehaene, and B. De Moor, in Proceedings of the 16th International Symposium on Mathematical Theory of Networks and Systems, Katholieke Universiteit Leuven, Belgium, 2004 (unpublished). [13] Z. Ji, J. Chen, Z. Wei, and M. Ying, Quantum Inf. Comput. 10, 97 (2010). [14] M. Van den Nest, J. Dehaene, and B. De Moor, Phys. Rev. A 69, 022316 (2004). [15] Supplementary material (tables) at [http://www.ii.uib.no/∼ larsed/entanglement]. [16] Supplementary material (computer program) at [http://www. ii.uib.no/∼larsed/entanglement/findoptimal.c]. [17] A. Cabello, A. J. L´ opez-Tarrida, P. Moreno, and J. R. Portillo, Phys. Lett. A 373, 2219 (2009); 374, 3991 (2010). [18] M. Van den Nest, J. Dehaene, and B. De Moor, Phys. Rev. A 72, 014307 (2005). [19] A. Cabello, A. J. L´ opez-Tarrida, P. Moreno, and J. R. Portillo, Phys. Rev. A 80, 012102 (2009).