Ученые создали квантовый сервер на основе оптических элементов для распределения запутанных состояний

Abstract One of the key aims of quantum networks is the efficient distribution of multipartite entangled states among end users. While various architectures have been proposed, each comes with distinct advantages and limitations. Many designs depend on long-lived quantum memories and deterministic gates, which, while powerful, introduce considerable cost and technical challenges. Experimentally cheaper alternatives that circumvent these constraints are often limited to specific types of entanglement and a specific number of users. Here, we present an experiment-friendly quantum server that relies only on linear optical elements, offering a flexible approach to multipartite entanglement distribution. Our so-called photon-weaving quantum server can generate and distribute one of several locally nonequivalent graph states, including Greenberger–Horne–Zeilinger (GHZ) states, as well as path, cycle, and caterpillar graph states. This is achieved through two distinct fusion protocols, i.e. multiphoton graph-state fusion (graph-state weaving) and multiphoton GHZ-state fusion (GHZ-state weaving), and can readily be implemented. Original content from this work may be used under the terms of the Creative Commons Attribution 4.0 license. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. 1. Introduction Quantum applications often require the generation and distribution of multipartite entangled quantum states in a quantum network [1]. While one is typically limited to a fixed network topology, many applications benefit from—or even require—different types of entanglement. For example, Greenberger–Horne–Zeilinger (GHZ) states are ideal for quantum communication [2], and cluster states are ideal for measurement-based quantum computing [3]. Interestingly, both GHZ states (up to single-qubit rotations) and cluster states belong to one of the most essential types of entangled states, namely graph states. Graph states are quantum states that can be described by a mathematical graph [4], and have a wide range of quantum applications in quantum networks. Characterized by the shape of their graph, e.g. star-shaped (GHZ) or grid-shaped (cluster), different protocols can be performed for different types of graph states. For example, path-graph states have been shown useful in anonymous quantum conference key agreement [5] or long-range quantum teleportation [6], cycle graph states in quantum secret sharing [7] or fusion-based quantum computing [8]. In general, having access to different graph-state building blocks allows for extended fusion and repeater protocols [9, 10], and extracting higher-entangled states from noisy states [11, 12]. On a more theoretical level, the above states also display strongly different entanglement structures. For example, in all of the above classes of graph states, the only state (with more than three qubits) that is absolutely maximally entangled is the cycle graph state on five qubits [13]. Such states have attracted a lot of attention over the years [14], motivating also their experimental creation. It is, therefore, important to design flexible quantum networks that are experimentally feasible but can still distribute various entangled states [15–17]. In general, there are different approaches to constructing quantum networks capable of distributing (multipartite) entanglement [18]. While each approach has its own drawbacks and benefits, one promising building block for more complex network topologies is a star-shaped network with a central node, i.e. a quantum server that shares an entangled Bell pair with each of the user nodes [1]. Now, one could assume long-lived memories, which are essential for storing, manipulating, and entangling qubits, and therewith the capability to perform deterministic single- and two-qubit operations. This would allow for designing powerful quantum servers, i.e. quantum servers that can distribute various types of entangled states [1, 19, 20]. However, such devices might not always be practical since they require sophisticated experimental setups. Several proposals have investigated ways around the above-mentioned need for quantum memories. Following the star-shaped network topology, one simple alternative is a quantum server directly distributing multiphoton entangled states to the distinct users. Possible distribution schemes could utilize postselection [21–23], heralding [24–26], or deterministic photon emitters [27, 28]. However, distribution schemes require a heralding mechanism at the network users to verify the successful entanglement distribution, directly measuring the incoming photons or using light–matter interaction to store the entanglement. A second alternative not requiring heralding at the users is a quantum server based on linear optical elements and performing multiphoton entanglement swapping. So far, such schemes have been discussed for the generation of W states [29, 30], Dicke states [31], and GHZ states [32–34]. However, a flexible and experiment-friendly quantum server that can flexibly decide to distribute one out of several graph states based on linear optics is still missing. Here, we propose such a quantum server based on linear optical elements only, which generates different locally nonequivalent graph states by (i) choosing one out of two photonic fusion protocols, i.e. multiphoton graph-state fusion called graph-state weaving [35], and multiphoton GHZ-state fusion [36], which we call GHZ-state weaving; (ii) performing different single qubit measurements in different bases to manipulate the distributed graph states further. This so-called photon-weaving quantum server (PWQS) is capable of distributing GHZ states, as well as path, cycle, and caterpillar graph states. Notably, these distinct classes of states can be produced using the same experimental setup, requiring only modifications to single-photon operations. Consequently, our PWQS offers an experimentally efficient platform for the distribution of multiple key classes of entangled states. The paper is structured as follows. First, we describe the theoretical background on graph states and photon-weaving in section 2. In section 3.1, we discuss our PWQS without the possibility of storing photons, i.e. all photons have to be fused and measured simultaneously, and perform a basic loss analysis in section 3.2. Afterward, in section 3.3, we discuss an adjusted version of our PWQS with the possibility of storing photons, which generates small building blocks connecting one or two users first. The building blocks are then fused in a second step. We classify the resultant graph states that a PWQS can generate in appendix 2. Background In this section, we review the basic concepts and tools we make use of throughout this work. 2.1. Graph states A graph state is a quantum state that is represented by a graph , given by a set of vertices and a set of edges [4]. In linear optical implementations, the vertices correspond to the photons and the edges indicate the entangling operations performed between the qubits to generate the graph state. That is, to generate an -photon graph state, one applies the controlled Pauli (CZ) gates according to the edges in to photons, each prepared in the state . Graph states can, therefore, be written in the form Graph states are a subset of stabilizer states. In fact, every stabilizer state is equivalent to a graph state, up to single-qubit Cliffords [37]. Our focus on graph states—as opposed to stabilizer states—is thus one out of convenience. As an example, the well-known -qubit GHZ state is single-qubit Clifford equivalent to both a star- and a complete graph state [4]. One powerful fact is that two graph states are single-qubit Clifford equivalent if and only if the two underlying graphs are related by a sequence of local complementations [37]. A local complementation on a vertex changes the presence/absence of an edge between each possible pair of neighbors of . That is, if there is an edge between neighbors of , remove the edge; if there is no edge between neighbors of , add the edge. We say that two graphs (and their associated graph states) are locally equivalent if they are related by a sequence of local complementations. 2.2. Postselection Here, we introduce the different linear optical postselection methods used in this work (further details can be found, e.g. in [35, 36, 38]). 2.2.1. Postselecting GHZ states Let us fix polarization degrees of freedom, i.e. horizontal () and vertical () polarization states. One of the standard methods for postselecting a GHZ state utilizes independent photons, each prepared in the state , and polarizing beam splitters (PBSs), which transmit and reflect (see figure 1) [36]. Postselecting for -photon coincidences, i.e. exactly one photon per output mode, can only be successful if all photons have the same polarization, either or . This happens with a probability of . Thus, for , one postselects the two-photon GHZ state, i.e. the Bell state see figure 1(a). For , one postselects the polarization version of the -photon GHZ state given in (2) see figure 1(b). 2.2.2. Postselecting path graph states To postselect path graph states, one simply has to add half-wave plates (HWPs) (see figure 2) to the GHZ state scheme (see figure 1) [38, 39]. The reason for this is that HWPs at an angle of rotate the polarization states to . Note that HWPs at an angle of perform Pauli gates, which, up to a phase, allows for postselecting GHZ states as described above. Hence, one can easily switch between the two schemes by rotating the HWPs. Throughout this paper, whenever mentioning HWPs we will assume an angle of . Download figure: Standard image High-resolution imageIn the case of three photons (see figure 2(a)), this scheme describes a photonic CZ gate [39], where the initial state is given by Successful action of the first PBS and the HWP changes this state to Again, we are postselecting for -photon coincidences and have left out the terms not fulfilling the postselection criterion. Due to this, the state is now normalized by the success probability, which is . The state after the second set of PBS and HWP takes the postselected form From this, one can see that the phase change only occurs if photons 1 and 2 are both in the state . Following the second HWP, the state given in lines 3 and 4 of (5) is identical to a three-qubit path graph state. This means that measuring out the auxiliary qubit in the basis projects the other two qubits into the two-qubit path graph state and completes the CZ operation. The success probability is . Note that the scheme can also be interpreted as two sequential type-I fusion gates [40]. The photon detected in the standard type-I fusion is recycled and used again for the second type-I fusion gate. Independently of the chosen interpretation, one can see that the performed operation can be continued, i.e. the auxiliary photon can interfere with more photons and thereby implement more CZ/type-I fusion gates (see figure 2(b)). Since each pair of subsequent photons in the identical state leads to a sign change, in total, this procedure postselects an -qubit path graph state ( when including the auxiliary photon) with a probability of [22, 38]. 2.2.3. Postselected photon weaving The scheme for postselecting path graph states has also been introduced in a more general form as photon weaving [35]. As can be seen in figure 3, the auxiliary photon weaves together the photons on its way, i.e. it entangles them through CZ operations. Note that in this work, besides the term (graph-state) weaving, we will also use the term GHZ-state weaving depending on the weaving mechanism used. This means that using only PBSs as described first corresponds to GHZ-state weaving while using PBSs and HWPs as described second corresponds to graph-state weaving or simply weaving. Download figure: Standard image High-resolution imageIn general, graph-state weaving allows two or more graph states to be weaved together [35], i.e. in effect, applying CZ gates between them. To understand this, we start by looking at two arbitrary graph states and . W.l.o.g., we assume that we want to weave and together using their qubits and , respectively. We know that we can rewrite the two states as with The complete state, including the weaving photon before entering the photonic CZ gate, takes the form Comparing (8) to (3)–(5), we can directly see the action of the CZ gate, which leads to where the qubits and of and , respectively, are now connected (see figure 4). Additionally, the auxiliary qubit is solely connected to qubit . It can either be removed by performing a measurement, i.e. a measurement in the basis, or used to connect the next graph state. The postselected gate connecting two graph states succeeds with probability . In total, weaving together graph states with the help of a weaving photon succeeds with probability . Again, this can be interpreted as subsequent type-I fusion operations, where one of the photons is being reused for the next fusion operation. Download figure: Standard image High-resolution imageDue to the postselection, the weaving photon cannot interact with the same photon twice. Hence, to weave a cycle graph state postselectively, the weaving photon must be part of an initial two-photon graph state of the form , which is equivalent to a single-photon rotated Bell state. Weaving then gives a path graph state that can be closed by weaving, i.e. fusing the first and the last photon. The postselected result is a cycle graph state with an additional photon connected to the circle (see figure 5; see appendix Download figure: Standard image High-resolution imageFinally, combining GHZ weaving and path graph or cycle graph weaving generates caterpillar graphs [41–43]. Here, caterpillar graphs are path graph states with additional leaves, which can be thought of as a connected chain of GHZ states. Similarly, this has been discussed for deterministic single photon emitters, combining the emission of photonic GHZ and photonic path graph states [27]. 3. Photon-Weaving Quantum Server In this section, we introduce our PWQS that acts as a central node and, simultaneously, as a possible user of a quantum network. It can distribute different types of entangled states to users by photon weaving, namely GHZ states, path graph states, cycle graph states, and caterpillar graph states (see appendix First, we describe a PWQS using linear optics only, where all photons must be simultaneously weaved. Second, we describe an adjusted PWQS, including the possibility of storing photons. It weaves smaller entangled states first, which are then fused together. Note that neither of the two versions takes into account the experimental implementation of the qubits belonging to the users. Depending on the chosen design, these could be photons or long-lived memories. We simply assume that the users can store their qubits and perform any required single-qubit operations. 3.1. Without storing photons GHZ state protocol. The first protocol the PWQS can perform is the standard scheme to generate -user GHZ states from polarization-encoded two-photon graph states (see figure 6) [44]. Each of the shared two-photon graph states is thereby prepared in the state . Identically to the GHZ-state weaving discussed in section 2 (see figure 1), the photons reaching the PWQS are sent into PBSs. Coincident detection of photons then verifies that all photons have had the same polarization. Detecting in the -basis further guarantees that the specific polarization remains unknown and the photons shared with the users are projected into a GHZ state of the form [44] where denotes the number of photons measured in the state . Hereby, the PWQS can freely decide if it wants to participate in the communication or not. To participate, it will employ one of the coincidentally detected photons to become part of the shared GHZ state. Assuming no loss, the success probability is given by . Download figure: Standard image High-resolution imagePath graph state protocol. The second possible protocol is based on photon weaving and a sequence of measurements [15], i.e. measurements in the basis, to generate an -photon path graph state connecting the users (see figure 7). Again, the PWQS can decide if it wants to participate in the generated graph state or not. Download figure: Standard image High-resolution imageUsing one of the shared photons as a weaving photon generates the comb-like graph state as shown in figure 8. Subsequently, performing measurements transforms this state into a path graph state in which the PWQS possesses one of the outer qubits. Under the assumption that all photons have arrived simultaneously, the success probability equals . Download figure: Standard image High-resolution imageAs discussed in [27], we can interpret the leaf qubits/users in the comb-like graph as redundantly encoded qubits. User and PWQS qubits can change roles through Hadamard rotations, i.e. basis changes. This means that measuring the PWQS qubits in the -basis projects the users into a path graph state, where all users except the first one would need to perform Hadamard rotations. Additionally, each PWQS qubit measured in the state requires a operation of its connected user. Therefore, local unitary corrections are only required from the users and can all be moved to the post-processing. Hence, the PWQS photons can be measured simultaneously without any additional corrections needed. Cycle graph state protocol. The third protocol is similar to generating a path graph state, except that the weaving photon is now part of a Bell pair that belongs to the PWQS completely (see figures 9 and 10). Performing measurements transforms this state into a path graph state where the PWQS possesses both the first and the last qubit. Finally, fusing the two outer qubits, both at the PWQS, generates a cycle graph state that includes the PWQS. As before, assuming no losses, the success probability is given by . Download figure: Standard image High-resolution imageDownload figure: Standard image High-resolution imageCaterpillar graph state protocol. By combining the different methods, one can distribute caterpillar graph states to the users. The success probability of generating a caterpillar graph is . Weaving with an additional Bell pair to close the caterpillar graph and generate a ‘cycle caterpillar graph’ has a success probability of . 3.2. Loss analysis and comparison To give an idea of how the described PWQS would perform in a realistic quantum network, we analyze the derived success probabilities under basic loss assumptions. To this end, we combine channel losses, source efficiencies, and detector efficiencies into a single parameter, , that describes the probability of a photon being emitted and detected. In the ideal case , in the case of loss . Independent of the state to be distributed, a factor of is added to the derived success probability per transmitted photon, i.e. user, leading to a total factor of . We plot the success probabilities with and without loss in figure 11. In the case of loss, we assume a maximum tolerable loss of per photon [45] to determine the maximum number of users for which the PWQS without photon storage can still be useful. For our analysis, we assume the use of up-to-date superconducting nanowire single-photon detectors with a dark-count probability per time window below . We find that without loss, noncycle, i.e. GHZ, path, caterpillar, graph states can be distributed to up to 30 users, whereas cycle and cycle caterpillar graph states can be distributed to up to 28 users. For maximum loss, the number of maximum users decreases by half to 15 (noncycle) and 14 (cycle). Download figure: Standard image High-resolution imageDue to postselection in the PWQS, i.e. detecting exactly incoming photons (plus two local photons for distributing circle graph states), any photon loss would immediately be detected. The state distribution can be retried until successful, and photon loss does not lead to a decrease in state fidelity of the distributed states. Note that we do not take into account noise arising from imperfect operations. Including noise would be expected to lead to an (approximately) exponential decrease in fidelity, since the number of noisy operations is linear in the number of end users. For protocols that close a graph state, the additional local resources and fusion operations at the PWQS would contribute further noise. We now compare this version of the PWQS to other central quantum servers capable of flexibly distributing graph states in a network. For this, two different designs exist. The first one would be reversing the PWQS, interfering single photons locally, and postselecting the successful state generation at the users [22]. Although the interference part shows the same success probabilities as our PWQS, it requires heralding of the incoming photons at the users. One option would be to directly detect the photons, reducing the usefulness of the distributed entanglement and preventing the users from performing entanglement distillation protocols. Another option would be to load the photonic entanglement to solid state qubits, further decreasing the overall success rates. The second design would utilize deterministic photon emitters, capable of emitting GHZ, path, and caterpillar graph states [27, 28]. In addition to heralding the incoming photons at the users, this scheme requires an experimentally sophisticated central quantum server and is currently limited to generating 14-photon states [28]. 3.3. With storing photons Due to the exponential decrease of the success probabilities and high photon losses, schemes completely based on postselective photon weaving, as described above, become impractical when increasing the number of users. In this section, we show that our PWQS can be adjusted to become practical in this regime, by assuming the ability to store and route photons. For storing photons, different techniques are available. The main techniques include quantum memories [46] and optical delay lines [47], both of which are experimentally challenging, require additional overhead such as active optical switching, and introduce additional noise, such as photon loss, and reduced coherence times. Nevertheless, current quantum memories have reached around % efficiencies with storage times above ms [46], and photon delay lines have losses of less than dB m yielding around % success probability to store a single photon for ns [47]. Since, in the following discussion, we want to give an idea of the usefulness of our PWQS in future quantum networks, we assume perfect photon storage. To this end, we present a PWQS that first weaves four-photon building blocks and then fuses them into larger graph states step by step. At the same time, unsuccessful fusion operations do not cause the complete weaving process to fail, but can instead be patched [48]. To generate a path-shaped four-photon building block, the PWQS weaves two photons belonging to Bell pairs shared with two users. As shown in figure 12, the weaving photon belongs to a deterministic Bell pair solely owned by the PWQS. In addition to the two shared Bell pairs, a second Bell pair owned by the PWQS is connected by weaving. Similar to the discussion above, this generates a comb-like graph state. Finally, the PWQS measures all photons involved in the weaving process to ensure that the shared photons have arrived and the weaving was successful. This generates the path-shaped four-photon building block in which the PWQS owns and stores the two outer photons (see figure 12). Download figure: Standard image High-resolution imageInstead of graph-state weaving, the PWQS could also perform GHZ weaving. Measuring all photons involved in the weaving process generates a star-shaped four-photon building block. Assuming no photon loss, the success probability for generating a four-photon building block, either path or star-shaped, is upper bounded by . Now, to generate an -user graph state, the PWQS fuses multiple building blocks (see figure 13). Hereby, each fusion measures one photon [40], and the second is stored at least until the next fusion is performed. In general, any fusion operation might fail with a probability of . However, a failed fusion does not mean all steps must be repeated. In particular, only the last two users must be removed from the graph by measurements and entangled with the PWQS anew. This means that only the last building block must be repeated. Download figure: Standard image High-resolution imageInstead of working with four-photon building blocks connecting two users, the PWQS could also generate three-photon building blocks connecting only one user. Although the success probability per building block is increased to , it also requires twice as many Bell pairs generated in the PWQS. Fusing such three-photon building blocks will generate a path graph state in a zigzag arrangement between users and the PWQS (similar as discussed in [19]). Finally, depending on the used building blocks and their resulting graph states (see figure 13), the PWQS can now distribute different states to the users by choosing different measurements. For example, path-shaped four-photon building blocks and measurements distribute a path graph state, while star-shaped four-photon building blocks and measurements distribute a GHZ state. Similarly, three-photon building blocks and either or measurements distribute a path graph state or a GHZ state, respectively. Note that combining different types of building blocks allows for the distribution of additional graph states. For example, combining path and star-shaped building blocks distributes caterpillar graph states. Note further that fusing the two outer photons in the PWQS creates cycle graph states. We provide a full characterization of all states that can be distributed to the users in this fashion in appendix 4. Conclusion In this paper, we introduced a flexible so-called PWQS based on linear optical elements only that can distribute different locally nonequivalent graph states. Our PWQS is based on two different photonic fusion protocols, i.e. GHZ-state weaving and graph-state weaving. We showed that depending on the chosen protocol, our PWQS can distribute GHZ states, as well as path, and caterpillar graph states. Furthermore, we showed that adding an ancilla Bell pair locally at the PWQS allows the generation of cycle and cycle caterpillar graph states. This additional cost can be justified, as cycle-shaped graph states are required by protocols such as quantum secret sharing [7] and fusion-based quantum computing [8], or as building blocks in larger graph-state schemes [10, 12]. We discussed two different possibilities for implementing our PWQS: (i) Without the possibility of storing photons, i.e. all photons have to be fused and measured simultaneously. This version of the PWQS allows for a simple and experimentally cheap distribution of different graph states to a network, but with an exponentially decreasing success probability. Performing a basic loss analysis, we have shown that the PWQS without storing photons can be useful in a range of 30 to 14 users for no loss and maximum loss of per photon, respectively. (ii) With the possibility of storing photons, which weaves small building blocks connecting one or two users first. The building blocks are only fused in a second step and can be prepared in parallel. Further, the failure of a single fusion of two building blocks does not make the complete fusion process fail. For the sake of simplicity, we focused on linearly weaving graph states and fusing building blocks. The only exception discussed is cycle graph states. However, it will be interesting to investigate schemes that weave graph states and fuse building blocks in a two-dimensional manner, e.g. see [19] for a discussion of two-dimensionally fusing zigzag graph states. Another helpful extension of our scheme would be allowing the PWQS to decide which users participate and in which order to weave them. This could be done by utilizing programmable photonic circuits [49]. In combination with considering a network of multiple PWQSs, this would allow for distributing larger and more diverse graph states. Other future directions might be to adjust the photon-weaving scheme to a heralding scheme without a central quantum server, as it has been discussed in [34] for GHZ states, or extend photon weaving to higher dimensions [50]. In addition to a more detailed discussion of losses, it will be important to discuss different types of errors, e.g. stemming from imperfections in the used devices. Including realistic noise would be expected to lead to an approximately exponential decrease in the fidelity, since the number of imperfect operations scales linearly with the number of end users. This will help to compare the PWQS to other schemes under realistic conditions [1, 51], and give an understanding of when additional entanglement distillation is needed [52]. Acknowledgment D B was supported by the JST Moonshot R&D program under Grant JPMJMS226C. The authors thank Maria Flors Mor-Ruiz and Jorge Miguel-Ramiro for their helpful comments on the manuscript. Data availability statement No new data were created or analysed in this study. Appendix A: Weaving cycle graph states: mathematical proof An arbitrary graph state , for example, a path graph state, is given. We briefly discuss fusing two specific qubits and of the graph, letting the two photons interfere at a PBS and postselecting for coincidences. The graph state can be rewritten in the following form: with Detecting coincidences after the PBS now postselects the two terms of (A1) in which qubit and qubit are in the same state, i.e. where we additionally have rotated the state of qubit by use of a HWP to complete the graph-state fusion. From (A3) we can see that all qubits previously connected to either qubit or qubit are now solely connected to qubit . Further, qubit is only connected to qubit . This proves the graph state’s form after fusing two of its own qubits. In particular, it proves that a path graph state is fused into a cycle graph state with an additional qubit attached when weaving its first and last qubit (see figure 5). Appendix B: The class of extractable states Our goal is to characterize the possible resulting states obtained by starting with a zigzag state and selectively measuring certain qubits (see figure 13(c)). First, we note that the analysis of the zigzag state also extends to the partial honeycomb (see figure 13(b)); this is because we only measure the qubits that are not connected to a leaf qubit. As such, performing these measurements and applying the CZ gate according to these edges commute. This means we can study the states that we end up when measuring select qubits from a cycle graph, perform the CZ gate afterward (and then potentially do local complementations/single-qubit rotations afterward). Note that at the end of this section, we briefly discuss the path graph shown in figure 13(a). One way to compute the resultant graph state after measurements is by using the relations found in [4]. Namely, measuring a vertex in corresponds to deleting the vertex from the graph. Measuring in corresponds to first performing a local complementation and then a measurement. Finally, measuring in corresponds to performing a local complementation on , then a local complementation on an arbitrary connected vertex , then a local complementation on again, and finally, deleting . If a graph can be reached from by performing the above three operations (plus local complementations), we say that is a vertex-minor of . While the above relations allow us to, in principle, find (representatives of) vertex-minors of the cycle graph, it suffers from two complications. First, the fact that the choice of vertex is arbitrary when measuring in complicates manners. Second, the state that one ends up after a measurement is only equivalent to the above-specified graph state up to local rotations. In particular, after only performing an measurement, the resultant state is not yet a graph state. We first have to perform single-qubit Clifford rotations to end up with the desired graph state. Instead, we will exploit the fact that cycle graphs are circle graphs. To define circle graphs, we need the notion of Eulerian tours on graphs. An Eulerian tour on a finite graph is a sequence of vertices such that are adjacent, and each edge in the graph is of the form (see figure 14). A famous result by Euler states that any connected graph whose vertices all have even degree is Eulerian, i.e. there exists an Eulerian tour on that graph. In particular, any connected -regular multigraph has an Eulerian tour . For given vertices and an Eulerian tour , we say that and interlace if they appear alternating as one follows . Given an Eulerian tour on a -regular multigraph , the interlacement graph of is defined as the graph with the same vertex set as , and where are connected if and only if and are interlaced with respect to . Not all graphs arise as interlacement graphs from Eulerian tours on -regular multigraphs; the ones that do are called circle graphs3. Download figure: Standard image High-resolution imageThe key point is that the interlacement graphs arising from the different Eulerian tours of form a single equivalence class under local equivalence; here two graphs are locally equivalent if they are related by a sequence of local complementations. In other words, a -regular multigraph (along with its set of Eulerian tours) describes an equivalence class of a circle graph. Furthermore, Pauli measurements (elements of an equivalence class) on circle graphs have a simple interpretation in terms of -regular multigraphs. The three Pauli measurements on a vertex of a -regular graph yield three possible transition-minors. These are the resultant -regular multigraphs corresponding to the three different ways to ‘disconnect’ the four edges incident on , see figure 15. Transition-minors will be useful to us since the Eulerian tours on the three transition-minors on give exactly the possible vertex-minors when measuring out . For more information on transition-minors and vertex-minors of circle graphs, see section F of [54], or definition C.1.3 from [55]. Download figure: Standard image High-resolution imageThe -regular multigraph associated with a cycle graph is particularly simple—it is given by the circulant graph , i.e. it is the multigraph with vertices to , where are connected iff . To see this, we depict the edges of the associated Eulerian tour associated with a -cycle in figure 14, indicated by following the edges in the ordering of red, green, blue and black. The general case follows straightforwardly. In the top of figure 15, we consider a small fragment of . Note that this fragment repeats. The bottom of figure 15 shows the three possible transition minors of that fragment. We label these as the -, -, and -fragments, since they correspond to -, -, and -measurements with respect to the Eulerian tour from figure 14. From the above, we find that the possible transition-minors are all possible sequences of length of -, - and -fragments (starting from a fixed vertex), see figure 16. We will write such a sequence as a word of length from the alphabet . Download figure: Standard image High-resolution imageLet us briefly recapitulate. We moved to the -regular multigraph picture since understanding all possible post-measurement states (up to single-qubit Clifford rotations) corresponds to understanding all possible Eulerian tours on certain transition minors of . We have shown that the transition minors can be described by a (cyclic) word . Since we do not care about the post-measurement state up to local single-qubit Cliffords, we will find instead only one Eulerian tour for each word . First, we can restrict ourselves to subwords that do not contain . This follows from the fact that a -regular multigraph of two disjoint circle graphs corresponds to a connected sum of the -regular multigraphs of the individual circle graphs, see section 1 of [56]. Intuitively, this follows from the fact that a measurement corresponds to vertex deletion on the cycle graph. For the second part, we introduce leaf expansions. To define a leaf expansion on , we will need an Eulerian tour on and a vertex . The leaf expansion of with respect to and is a -regular multigraph with vertex set , where is the symmetric set difference operation. That is, we can think of ‘splitting’ the vertex into two vertices . Furthermore, the edge set of is the same as (respecting the relabelling of to , ), and with two additional multi-edges between and . We show a leaf expansion in figure 17; note that inherits an Eulerian tour from , as indicated. Note that technically speaking a leaf expansion is not well-defined; there is an arbitrary choice of which vertex will be and which one . However, both resultant graphs are isomorphic. Download figure: Standard image High-resolution imageThe terminology of a leaf expansion comes from the following fact: if is the graph associated with the Eulerian tour, then the corresponding leaf expansion has an Eulerian tour (see figure 17) on it such that the associated graph is isomorphic to , but with a leaf attached to the vertex corresponding to . The proof of this fact follows from directly writing out the sequence of vertices visited from . From figure 18, it is clear that any segment consisting of - and -fragments corresponds to a sequence of leaf expansions on a path graph. In other words, the possible states are (locally equivalent to) disjoint copies of caterpillar graph states, where the vertices that are part of the subgraphs corresponding to star graphs need to be contingent. Furthermore, there is one final possibility where no -measurement is performed. In that case, one ends up with a cycle graph with attached leaves (with the same restriction on contingency). Download figure: Standard image High-resolution imageFinally, let us say something about the path graph shown in figure 13(a), where the server owns every third qubit, i.e. every third qubit will be measured. Since this graph is a combination of zigzag elements, each of the measured qubits has an identical neighborhood to the zigzag graph. Allowing the same measurements as before, starting from figure 13(a), we can only distribute disjoint copies of caterpillar graph states where each vertex of the path graph can have one leaf maximum. Footnotes - 3From this definition it is not clear why these graphs are called circle graphs; see for example [53] for more background.