Graphical description of the action of Clifford operators on stabilizer states

We introduce a graphical representation of stabilizer states and translate the action of Clifford operators on stabilizer states into graph operations on the corresponding stabilizer-state graphs. Our stabilizer graphs are constructed of solid and hollow nodes, with (undirected) edges between nodes and with loops and signs attached to individual nodes. We find that local Clifford transformations are completely described in terms of local complementation on nodes and along edges, loop complementation, and change of node type or sign. Additionally, we show that a small set of equivalence rules generates all graphs corresponding to a given stabilizer state; we do this by constructing an efficient procedure for testing the equality of any two stabilizer graphs.

Figure 1

(a) A generator matrix for a stabilizer state. (b) A canonical-form generator matrix obtained from (a) by row and qubit swapping. (c) The adjacency matrix indicated by (b). (d) The adjacency matrix of (c) with the qubit swaps undone. (e) The reduced stabilizer graph associated with (a). In parts (a)–(d) the columns have been labeled by the corresponding qubit. In part (e) the nodes are labeled sequentially, beginning with the top node and moving clockwise. It is clear that the qubit swaps are not actually necessary, since we reverse them in the end. The generator matrix in (a) can be converted to graph form directly by exchanging columns 2 and 3 on the left with the matching columns on the right, an operation that corresponds to applying a Hadamard to qubits 2 and 3. In graph form, the adjacency matrix is just the right half of the generator matrix. Loops arise from 1s on the diagonal of the adjacency matrix, and hollow nodes are used to indicate which columns were exchanged between the right and left halves of the generator matrix to get the adjacency matrix. Notice that there are no edges between hollow nodes, nor are there any loops on hollow nodes.

Figure 2

(a) A circuit in graph form. (b) A stabilizer graph corresponding to the circuit in (a). ${}^{C}Z$ gates between qubits are transformed into links between nodes, terminating $Z$ gates become negative signs, terminating $S$ gates result in loops, and terminating $H$ gates are denoted by hollow nodes. Nodes in (b) are labeled sequentially, beginning with the top node and moving clockwise.

Figure 3

Simple circuit identities, which we use to derive more complex identities. Identity (a) follows trivially from the steps shown. Identities (b) and (c) are easily verified in the standard basis.

Figure 4

Circuit identities relevant to transforming a stabilizer graph under local Clifford operations. Each identity is illustrated for the case of four neighbors connected to a qubit of interest; equivalent expressions hold for other numbers of neighbors. Identities (a) and (b) follow immediately from the identity in Fig. 3a. The proof of (c) relies on decomposing ${}^{C}Y$ using $Y=iXZ$, the equivalence of ${}^{C}i$ to $S$ on the control qubit, and the identity in Fig. 3c. The first step in identity (d) uses the fact that $I=e^{-i\pi /4}{\left(HS\right)}^3$, which gives $SHS=e^{i\pi /4}XHSH$; the second and third steps follow from identities (c) and (a). The identity in Fig. 3c generates the thicket of controlled-sign gates in the lower left of the final circuits in (c) and (d), thereby giving rise to local complementation in the corresponding stabilizer graphs. In (b) and (d), the phase shifts on the top qubits, $i$ and $e^{i\pi /4}$, are global phase shifts and thus can be omitted. To complete the transformation rules, it is necessary to know what happens in each of these circuit identities when there is a $Z$ gate on the top qubit immediately after the ${}^{C}Z$ gates. Ignoring overall phases, the effect on the third layer of the final circuit is, for (a) and (b), to include an additional $Z$ on the top qubit and, for (c) and (d), to include an additional $Z$ on all qubits.

Figure 5

(a) An illustration of a circuit identity used in the removal of pairs of Hadamards. The identity is shown for the case of four neighbors connected to a qubit of interest; equivalent expressions hold for other numbers of neighbors. The crucial trick here is the use of the decomposition of SWAP in terms of three ${}^{C}X$ gates. (b) A circuit identity demonstrating transformation rule E2. The selection of neighbors of the top two qubits, the decision qubits, is chosen to display the behavior of all kinds of edges in which both end nodes are connected to at least one of the decision qubits. The first equality in (b) employs the identity from part (a), while the subsequent ones follow from basic circuit identities. Concerning edges, the net effect of E2 on a stabilizer graph is to perform local complementation along the edge joining the decision nodes, i.e., to swap the connections of the decision nodes and to complement any edges whose end nodes connect to the decision nodes in different ways. The latter of these effects is contained in the controlled-sign gates in the lower left of the final circuit. Circuits illustrating E2 for other initial fill states can be obtained simply by applying additional terminal Hadamards to the circuits in (b). The sign rule for E2 expresses the effect of a $Z$ gate on a decision qubit before the Hadamard gate in the third layer of the initial circuit. Such a $Z$ gate can be pushed through the succeeding Hadamard, becoming an $X$ gate; in the final circuit, this $X$ gate, when processed using the identity in Fig. 3a, deposits an additional $Z$ gate on the qubits that were originally connected to the other decision qubit, excluding the decision qubit that originally possessed the $Z$.

Figure 6

An example sequence of graphs representing parts 1–3 of the equivalence-checking procedure in Sec. 5C. Nodes are labeled sequentially, beginning at the top node and moving clockwise. The graph on the left-hand side of (a) is equivalent to the reduced graph on the left-hand side of (b) by the application of E2 to the pair of nodes {1,5}. Likewise, an application of E1 to node 3 in the graph on the right-hand side of (a) yields the reduced graph on the right-hand side of (b). The graph of (c) results from the application of E(ii) to the pair of nodes {1,2} in the graph on the left of (b). An application of E(i) to the pair of nodes {3,4} in the graph on the right-hand side of (b) also yields the graph in (c), verifying, as per Sec. 5C3, that the graphs in (a) represent the same state.

Figure 7

An example of the process described in Sec. 5C3. A simplified reduced-graph equivalence test is shown in (a). The test is simplified because a node that is hollow in only one graph is never connected to a node that is hollow only in the other. The test is also false, since such an equivalence is satisfied if and only if the two graphs are identical. By switching to circuit notation, it is possible to see why these graphs correspond to different states. Translating the graph equality in (a) into circuit notation yields the circuit equality in (b), where the nodes of (a) are taken to be numbered sequentially, beginning at the top node and moving clockwise. The fact that the graphs are reduced implies that qubits with terminal $H$ gates, such as qubit 3 in the left-hand circuit, are not connected to other qubits with terminal $H$ gates. This allows us to pull out the ${}^{C}Z$ gates acting on qubit 3 on the left side and transfer the resulting ${}^{C}X$ gates to the other side of the equation, yielding the equality in (c). That the graph equality was simplified guarantees that $H$ gates do not prevent us from then pushing the ${}^{C}X$ gates to the beginning of the right-hand circuit in (c), as shown in (d). Qubit 3 winds up separable on both sides of the equation (though this is not generally the case), allowing us to verify the inequivalence of the prepared states since $|0⟩\ne \left(|0⟩-i|1⟩\right)/\sqrt{2}$.

Figure 8

Circuit identities for transforming a reduced stabilizer graph under ${}^{C}Z$ gates. In (a)–(c) the identity is illustrated for the case of four neighbors connected to a qubit of interest; equivalent expressions hold for other numbers of neighbors. Identities (a) and (b) give the rule T(ix) for transforming a reduced graph when a ${}^{C}Z$ gate is applied to a hollow node and a solid node. The effect of a $Z$ gate on the hollow qubit in the third layer of (a) or (b) is to deposit an additional $Z$ gate on both the hollow and solid qubits in the third layer of the final circuit. The identity in (c) relies on (b); this identity is extended in (d) to a demonstration of the rule T(x) for transforming a reduced graph when a ${}^{C}Z$ gate is applied to two hollow nodes. If there is a $Z$ gate on the lower hollow qubit in the third layer of (c), the result in the third layer of the final circuit is to put a $Z$ gate on that qubit and on the neighbors of the other hollow qubit. Translated to (d), this means that a $Z$ gate in the third layer on either hollow qubit leads in the third layer of the final circuit to additional $Z$ gates on that qubit and on the neighbors of the other hollow qubit.