Glossary

Quantum computation is marked by a set of unitary matrices (quantum gates) acting on qubit states followed by measurement. The most used representation is the circuit model of computation, comprising straight lines and boxes. The horizontal lines represent qubits and boxes represent single qubit unitary gates. A two qubit unitary gate links one qubit from another via vertical lines. Some useful notations are given below.

Quantum States

• $|+\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle ),\quad |-\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle -|1\rangle )$
  
• X basis/Diagonal basis/x basis: $\{|+\rangle ,|-\rangle \}$
• Z basis/Rectilinear basis/+ basis: $\{|0\rangle ,|1\rangle \}$

Unitary Operations

• ${\text{X (NOT gate)}}$: $X|0\rangle \,\to \,\ |1\rangle ,\quad X|1\rangle \,\to \,\ |0\rangle ,\quad X|+\rangle \,\to \,\ |+\rangle ,\quad *X|-\rangle \,\to \,\ -|-\rangle$
• ${\text{Z (Phase gate)}}$: $Z|+\rangle \,\to \,\ |-\rangle ,\quad Z|-\rangle \,\to \,\ |+\rangle ,\quad Z|0\rangle \,\to \,\ |0\rangle ,\quad Z|1\rangle \,\to \,\ -|1\rangle$
  

Thus, $|0\rangle$, $|1\rangle$ are eigenstates of Z gate and $|+\rangle$, $|-\rangle$ are eigenstates of X gate.

• Failed to parse (syntax error): {\displaystyle \text{H (Hadamard gate)|} : $H|0\rangle \,\to \,\ |+\rangle$ or $H|1\rangle \,\to \,\ |-\rangle$

$X=\left[{\begin{array}{cc}0&1\\1&0\\\end{array}}\right],\quad Z=\left[{\begin{array}{cc}1&0\\0&-1\\\end{array}}\right],\quad H={\frac {1}{\sqrt {2}}}\left[{\begin{array}{cc}1&1\\1&-1\\\end{array}}\right]\quad$

• ${\text{Controlled-U(CU)}}$: uses two inputs, control qubit and target qubit. It operates U on the second(target) qubit only when the first (source) qubit is 1. C-U gates are used to produce entangled states, when the target qubit is $|+\rangle$ and control qubit is not an eigenstate of U. In the given equation 'i' denotes the source qubit and 'j', the target qubit. Following are two important C-U gates.

${\text{Controlled-NOT(CX or CNOT): }}CX_{ij}|+\rangle _{i}|0\rangle _{j}\,\to \,\ {\frac {1}{\sqrt {2}}}(|0_{i}0_{j}\rangle +|1_{i}1_{j}\rangle )$
${\text{Controlled-Phase(CZ): }}CZ_{ij}|+\rangle _{i}|+\rangle _{j}\,\to \,\ {\frac {1}{\sqrt {2}}}(|0_{i}+_{j}\rangle +|1_{i}-_{j}\rangle )$

The commutation relations for the above gates are as follows:
$XH=HZ,\quad XZ=-ZX$
$(X\otimes I)CZ=CZ(X\otimes Z),\quad (Z\otimes I)CZ=CZ(Z\otimes I)$

Hierarchy of Quantum Gates

There are different class of quantum gates as follows,

• Pauli Gates(U): Single Qubit Gates I (Identity), X, Y, Z. All the gates in this set follow $U^{2}=I$
• Clifford Gates(C): Pauli Gates, Phase Gate, C-NOT. This set of gates can be simulated on classical computer. All the gates in this set follow CU=U'C, where U and U' are two different Pauli gates depending on C
• Universal Set of gates: This set consists of all Clifford gates and one Non-Clifford gate (T gate). If a model can realise Universal Set of gates, it can imlement any quantum computation efficiently. T gates follow $UT=P^{a}U'T$, where P is the phase gate and U, U' are any two Pauli gates depending on C. Parameter $a\epsilon {0,1}$ is obtained from U, such that $P^{0}=I$, $P^{1}=P$.
  

To summarize, if $C^{1}=$P, $C^{2}=$C, $C^{3}=$T, then $C^{k}=\{U:UQU=C^{k-1}|Q\epsilon C^{1}\}$

Magic States

It is any state that, if you have an unlimited supply of them, can be used to give you universal quantum computation when used in conjunction with perfect Clifford operations. The standard example is that if you can produce the state $(|0\rangle +e^{i\pi /4}|1\rangle )/{\sqrt {2}}$, then you can combine this with Clifford operations in order to apply a T gate, and we know that T+Clifford is universal.

Universal Resource

A set of $|+_{\theta }\rangle$states on which applying Clifford operations is enough for universal quantum computation.

Superposition

Superposition is a fundamental concept in quantum mechanics which states if two states $|\psi \rangle$ and $|\phi \rangle$ are representing two valid state in a Hilbert space, their linear combination exist in the same Hilbert space as well and refer to another valid states. We call state $\alpha |\psi \rangle +\beta |\phi \rangle$ a superposition of the two states. This property leads to most of the non-classical properties of quantum mechanics such as entanglement.

Entangled States

An entangled state is the quantum state of a group of particled (or a two party or multiparty system) that cannot be described as the independent states of these particles (or subsystems). The subsystems of such a quantum state, have quantum correlation even over a long distance. Mathematically, a multiparty entangled state cannot be written in following way:
$|\psi _{1-N}\rangle =|\psi _{1}\rangle \otimes ...\otimes |\psi _{N}\rangle$
The states that can be written in the above from, are called separable states.

EPR Pairs

EPR pairs refer to the pairs of particles with a conjugate physical property such as angular momentum. This concept has been introduced for the first time by the EPR (Einstein–Podolsky–Rosen) paradox which is a thought experiment challenging the explanation of physical reality provided by Quantum Mechanics. The particles that have been used in the EPR paradox had perfect correlation in such a way that measuring a quantity of a particle A will cause the conjugated quantity of particle B to become undetermined, even if there was no contact, no classical disturbance. A two party quantum state with above property can be described with the following state:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\Phi^+\rangle = \frac{1}{sqrt{2}} (|00\rangle + |11\rangle)}
This is one of the Bell states.

Bell States

Bell states are maximally-entangled two-qubit states. These are the states that violate the Bell's inequality with maximal value of $2{\sqrt {2}}$. These states make a compelete basis for the two-qubit (4 dimensional) Hilbert space:

$|\Phi ^{+}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle _{A}\otimes |0\rangle _{B}+|1\rangle _{A}\otimes |1\rangle _{B})$
$|\Phi ^{-}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle _{A}\otimes |0\rangle _{B}-|1\rangle _{A}\otimes |1\rangle _{B})$
$|\Psi ^{+}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle _{A}\otimes |1\rangle _{B}+|1\rangle _{A}\otimes |0\rangle _{B})$

$|\Psi ^{-}\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle _{A}\otimes |1\rangle _{B}-|1\rangle _{A}\otimes |0\rangle _{B})$

Bell State Measurement

Bell state measurement is termed as the projection of two qubits into one of the four Bell States as described above. It is done operating a Hadamard gate on one qubit and then, operating a C-NOT gate with this qubit as control and the other qubit as target. More on BSM can be found in [1]

Fidelity

The Fidelity is a quantum distance measure between two quantum states. For two general state $\rho$ and $\sigma$ it is defined as followes:

$F(\rho ,\sigma )=[Tr({\sqrt {{\sqrt {\rho }}\sigma {\sqrt {\rho }}}})]^{2}$
The definition reduces to the squared overlap between the pure states $|\psi _{\rho }\rangle \$and\$|\psi _{\sigma }\rangle$:
$F(|\psi _{\rho }\rangle ,|\psi _{\sigma }\rangle )=|\langle \psi _{\rho }|\psi _{\sigma }\rangle |^{2}$

Density Matrix, Pure and Mixed states

A density matrix is the matrix representation of a statistical state in quantum mechanics. This is a useful representation for mixed states. The mixed states are the states which cannot be described with a single vector $|\psi\rangle$ in Hilbert space. Instead, they are statistical mixture of several pure states. These states are also useful for describing the quantum state of a subsystem of a multi-party or larger quantum sysytem where the overall state can be shown as pure states. a density matrix in general can be shown as:

$\rho =\sum _{i}p_{i}|\psi _{i}\rangle \langle \psi _{i}|$
where $|\psi _{i}\rangle$ are pure states and $p_{i}$ are the relative probabilities. For a pure quantum state $|\psi \rangle$ the density matrix representation will be:
$\rho =|\psi \rangle \langle \psi |$

Unitary transformation

A unitary transformation is an isomorphism between two Hilbert spaces, These transformation preserve the inner products of the vector states and can be shown as matrices where $UU^{\dagger }=U^{\dagger }U=I$.

Monogomy of entanglement

Monogamy is one of the most fundamental properties of entanglement and can, in its extremal form, be expressed as follows: If two qubits A and B are maximally quantumly correlated they cannot be correlated at all with a third qubit C. In general, there is a trade-off between the amount of entanglement between qubits A and B and the same qubit A and qubit C. This is mathematically expressed as:
$E(A|B1)+E(A|B2)\leq E(A|B1B2)$
where $E()$ is a measure for entanglement.

Ancilla or Ancillary states

Ancillary states are extra states used in some quantum algorithms and are usually measured or discarded at the end of the procedure or they represent the state of an extra quantum system that is used for computation or etc.

Bloch Sphere

In quantum mechanics, the Bloch sphere is a geometrical representation of the pure state space of a two-level quantum mechanical system (qubit). The Bloch sphere is a unit 2-sphere, with antipodal points corresponding to a pair of mutually orthogonal state vectors. The north and south poles of the Bloch sphere are typically chosen to correspond to the standard basis vectors $|0\rangle$, $|1\rangle$ respectively, which in turn might correspond e.g. to the spin-up and spin-down states of an electron. This choice is arbitrary, however. The points on the surface of the sphere correspond to the pure states of the system, whereas the interior points correspond to the mixed states.

Quantum One Way Function

Based on the fundamental principles of quantum mechanics, QOWF was proposed by Gottesman and Chuang [2] and its definition is presented as follows.
Definition 1 Let k, $|f_{k}\rangle$ be classical bits string of length $L_{1}$, quantum state of $L_{2}$ qubits, respectively. A function $f:k\rightarrow |f_{k}\rangle$, where $|f_{k}\rangle$ satisfies $\langle f_{k}|f_{k'}\rangle \leq \delta <1$ for $k\neq k'$, is called a QOWF under physical mechanics if

1. Easy to compute: The mapping $f:k\rightarrow |f_{k}\rangle$ is easy to compute by a quantum polynomial-time algorithm.
2. Hard to invert: Given $|f_{k}\rangle$, it is impossible to invert k by virtue of fundamental quantum information theory.

Gate Teleportation

The idea comes from one-qubit teleporation. This means that one can transfer an unknown qubit |ψi without actually sending it via a quantum channel. The underlying equations explain the notion. See Figure 1 for circuit.

Figure 1: One Bit Teleportation

$(H\otimes I)(CZ_{12})|\psi \rangle _{1}|+\rangle _{2}$

$(H\otimes I)(CZ_{12})(a|0\rangle _{1}+b|1\rangle _{1})|+\rangle _{2}$ $(H\otimes I)(a|0\rangle _{1}|+\rangle _{2}+b|1\rangle _{1}|-\rangle _{2})$ $a|+\rangle _{1}|+\rangle _{2}+b|-\rangle _{1}|-\rangle _{2}$ $|0\rangle _{1}\otimes (a|+\rangle _{2}+b|-\rangle _{2})+|1\rangle _{1}\otimes (a|+\rangle _{2}-b|-\rangle _{2})$ $|0\rangle _{1}\otimes (a|+\rangle _{2}+b|-\rangle _{2})+|1\rangle _{1}\otimes X(a|+\rangle _{2}+b|-\rangle _{2})$ $|0\rangle _{1}\otimes H(a\rangle 0\rangle _{2}+b\rangle 1\rangle _{2})+|1\rangle _{1}\otimes XH(a|0\rangle _{2}+b|1\rangle _{2})$ $|0\rangle _{1}\otimes H|\psi \rangle _{2}+|1\rangle _{1}\otimes X|\psi \rangle _{2}$ $|m\rangle \otimes X^{m}H|\psi \rangle$

Similarly if we have the input state rotated by a $\mathrm {Z} (\theta )$ gate the circuit would look like Figure 2a. As the rotation gate $\mathrm {Z} (\theta )$ commutes with Controlled-Phase gate. Hence, Figure 2b is justified.

• 

  2(a)Modified Input
• 

  2(b)Gate Teleportation

This shows that for a pair of $\mathrm {CZ}$ entangled qubits, if the second qubit is in $|+\rangle$ state (not an eigen value of $\mathrm {Z}$) then one can teleport (transfer) the first qubit state operated by any unitary gate $\mathrm {U}$ to the second qubit by performing operations only on the first qubit and measuring it. Next, we would need to make certain Pauli corrections (in this case ${\mathrm {X} }^{\mathrm {m} }$) to obtain $\mathrm {U} |\psi \rangle$. In other words, we can say the operated state is teleported to the second qubit by a rotated basis measurement of the first qubit with additional Pauli corrections.

Graph states

The above operation can also be viewed as a graph state with two nodes and one edge. The qubit 1 is measured in a rotated basis $\mathrm {HZ} (\theta )$, thus leaving qubit 2 in desired state and Pauli Correction $\mathrm {X} ^{|}\mathrm {s1} \rangle \mathrm {HZ} (\theta _{1})|\psi \rangle$, where $\mathrm {s1}$ is the measurement outcome of qubit 1. See Figure 3

Figure 3: Graph State for Single Qubit Gates

Now, suppose we need to operate the state with two unitary gates $\mathrm {Z} (\theta _{1})$ and $\mathrm {Z} (\theta _{2})$. This can be done by taking the output state of $\mathrm {Z} (\theta _{1})$ gate as the input state of $\mathrm {Z} (\theta _{2})$ gate and then repeating gate teleportation for this setup, as described above. Thus, following the same pattern for graph states we have now three nodes (two measurement qubits for two operators and one output qubit) with two edges, entangled as one dimensional chain (See Figure 4).

Figure 4: Gate Teleporation for Multiple Single Qubit Gates

The measurement on qubit $\mathrm {1}$ will operate $\mathrm {X} ^{\mathrm {s1} }\mathrm {HZ} (\theta _{1})|\psi \rangle \otimes I$ on qubits $\mathrm {2}$ and $\mathrm {3}$. If qubit $\mathrm {2}$ when measured in the given basis yields outcome $\mathrm {s2}$, qubit $\mathrm {3}$ results in the following state ${\mathrm {X} }^{\mathrm {s2} }\mathrm {HZ} (\theta _{2}){\mathrm {X} }^{\mathrm {s1} }\mathrm {HZ} (\theta _{1})|\psi \rangle$. Using the relation we shift all the Pauli corrections to one end i.e. qubit $\mathrm {3}$ becomes ${\mathrm {X} }^{\mathrm {s2} }\mathrm {HZ} (\theta _{2})\mathrm {HZ} (\theta _{1})|\psi \rangle$ (${\mathrm {Z} }^{\mathrm {s1} }\mathrm {H} ={\mathrm {HX} }^{\mathrm {s1} }$). This method of computation requires sequential measurement of states i.e. all the states should not be measured simultaneously. As outcome of qubit $\mathrm {1}$ can be used to choose sign of $\pm \theta _{2}$. This technique is also known as adaptive measurement. With each measurement, the qubits before the one measured at present have been destroyed by measurement. It is a feed-forward mechanism, hence known as one way quantum computation.

Measurement Based Quantum Computation (MBQC)

MBQC is a formalism used for quantum computation by operating only single qubit measurements on a fixed set of entangled states, also known as graph states. Graph states denote any graph where each node represents a quantum state, and the edges denote entanglement between any two vertices. The measurement on successive layers of qubits is decided by previous measurement outcomes. Outcomes of last qubit layer gives the result of concerned computation. Following, we illustrate certain primitives necessary to understand the working of MBQC.

Cluster States

In case of multi-qubit quatum circuits, one needs a 2-dimensional graph state. Cluster State is a square lattice used as substrate for such computation. All the nodes are in $|+\rangle$ entangled by $\mathrm {CZ}$ indicated by the edges. It is known to be universal i.e. it can simulate any quatum gate.

Figure 5: Cluster State

Each row would thus represent the teleporation of starting qubit in that row horizontally. On the other hand, vertical edges indicate different input qubits linked with multi-qubit gates (same as circuit model). For example, see Figure Figure 6 to understand the conversion from circuit model to graph state model. As the computation relation follows $X=HZH$, thus, Figure Figure 6a represents Circuit diagram for $\mathrm {CNOT}$ gate in terms of $\mathrm {CZ}$ gate and Single Qubit Gate $\mathrm {H}$.

• 

  (a)Circuit Diagram to implement C-NOT
• 

  (b)Graph State Pattern for C-NOT
Figure 6: Measurement Pattern from Circuit Model

Figure 6b shows implementation of the first Hadamard gate on the second input state as measurement $\mathrm {M} _{\mathrm {2} }$ on qubit $\mathrm {2}$. Then $\mathrm {CZ}$ gate is implemented by the entangled qubits $\mathrm {3}$ and $\mathrm {1}$ in the graph state. Qubit $\mathrm {3}$ is entangled to another qubit $\mathrm {4}$ to record the output while measurement $\mathrm {M} _{\mathrm {3} }$ on qubit $\mathrm {3}$ implements the second Hadamard gate. Finally, the states to which qubits $\mathrm {(1)}$ and $\mathrm {(4)}$ are reduced to determine the output states of the two input qubits after $\mathrm {CNOT}$ gate operation.
It is evident that one needs to remove certain nodes from the cluster state in order to implement the above shown graph state. This can be done by Z-basis measurements. Such measurements would leave the remaining qubits in the cluster state with extra Pauli corrections. This can be explained as follows. Consider a two-dimesional graph state $\{\mathrm {1,2} \}$. If qubit $\mathrm {1}$ is to be eliminated, we operate $\mathrm {CZ}$ with $\mathrm {2}$ as target and $\mathrm {1}$ as control.

${\mathrm {CZ} }_{\mathrm {12} }{|+\rangle }_{1}|+\rangle _{2}=|0\rangle _{1}|+\rangle _{2}+|1\rangle _{1}|-\rangle _{2}$

Thus, if measurement on $\mathrm {1}$ yields $\mathrm {m}$, qubit $\mathrm {2}$ would be in the state $\mathrm {Z} ^{\mathrm {m} }|+\rangle$. Hence, such Z-basis measurements invoke an extra $\mathrm {Z} ^{\mathrm {m} }$ Pauli correction on all the neighbouring sites of 1 with 1 eliminated, in the resulting graph state. Thus, to summarise, we design a measurement pattern from gate teleportation circuit of the desired computation as shown above. The cluster state is converted into the required graph state by Z-basis measurement on extraneous sites. Measuring all the qubits in the required basis and we get the required computation in the form of classical outcome register from measurement of the last layer of qubits. If it is a quantum function, the last layer of qubits is the output quantum register.

Brickwork States

Although cluster states are universal for MBQC, yet we need to tailor these to the specific computation by performing some computational (Z) basis measurements. If we were to use this principle for blind quantum computing, Client would have to reveal information about the structure of the underlying graph state. Thus, for the UBQC protocol, we introduce a new family of states called the Brickwork states which are universal for X − Y plane measurements and thus do not require the initial computational basis measurements. It was later shown that the Z-basis measurements can be dropped for cluster states and hence cluster states are also universal in X-Y measurements.

Figure 7: Brickwork State

Definition 1 A brickwork state Gn×m, where m ≡ 5 (mod 8), is an entangled state of n × m qubits constructed as follows (see also Figure 7):

1. Prepare all qubits in state |+i and assign to each qubit an index (i,j), i being a column (i ∈ [n]) and j being a row (j ∈ [m]).
2. For each row, apply the operator c-Z on qubits (i,j) and (i,j + 1) where 1 ≤ j ≤ m − 1.
3. For each column j ≡ 3 (mod 8) and each odd row i, apply the operator c-Z on qubits (i,j) and (i + 1,j) and also on qubits (i,j + 2) and (i + 1,j + 2).
4. For each column j ≡ 7 (mod 8) and each even row i, apply the operator c-Z on qubits (i,j) and (i + 1,j) and also on qubits (i,j + 2) and (i + 1,j + 2).

Flow Construction-Determinism

Measurement outcomes of qubits is not certain, hence it renders MBQC a non-deterministic model. This can still be rectified by invoking Pauli corrections based on the previous outcomes, as evident from above. For example, to implement Hadamard gate on input state $|\psi \rangle =a|0\rangle +b|1\rangle$, we consider the case of a two qubit graph state ${\mathcal {C}}_{2{\text{x}}1}$.

${\mathcal {C}}_{2{\text{x}}1}=CZ_{ij}|\psi _{i}\rangle |+_{i}\rangle =a|00\rangle +a|01\rangle +b|10\rangle -b|11\rangle$

If one measures qubit i in $\{|+\rangle ,|-\rangle \}$ basis and gets outcome s, qubit j reduces to,

$=(a+b)|0\rangle +(a-b)|1\rangle ,{\text{if s=0}}$
$=(a-b)|0\rangle +(a+b)|1\rangle ,{\text{if s=1}}$

As, the two possible output states are different, it shows this method is non-deterministic. One could end up with any of the two states and there is no certainty. Nevertheless, we observe that if X gate is operated on the second qubit after measurement if outcome is 1, both the equations would be same and hence, obtained state is $H|\psi \rangle$.
Flow construction is the semanticism to construct the measurement pattern for a given graph state. It gives the Pauli corrections for a particular qubit in the graph state, called X and Z dependencies. In simpler words, it records the effect of shifting all Pauli X and Z corrections to the left of (after performing) Entanglement and Entanglement operations, respectively, for each qubit. The result is recorded as sets of X, Z corrections required for each site. These sets depend on the graph state and not the computation or measurement results. Hence, it can be computed while choosing the graph state for a required computation. Following we illustrate how to construct such models with ease using Measurement Calculus to invoke determinism in One-Way Quantum Computation(MBQC).
Choose a unitary gate for the circuit and hence, its measurement pattern. In order to implement this pattern on a graph state, there are four basic steps: Preparation, Entanglement, Measurement, Corrections.

• Preparation prepares all input qubits in the required state, generally represented as $|+_{\theta }={\frac {1}{\sqrt {2}}}(|0\rangle +e^{i\theta }|1\rangle )$ where $\theta \epsilon [0,2\pi ]$.
• Entanglement entangles all the qubits according to the required graph state. This operation is denoted by $E_{ij}$, where C-Z is operated with i as control qubit and j as target qubit.
  
• Measurement assigns measurement angle in X-Y plane for each qubit. Measurement operator is notated as $M_{i}^{\alpha }$: the qubit ’i’ would be measured in $\{|+_{\alpha }\rangle ,|-_{\alpha }\rangle \}$ basis i.e. if the state is ${\frac {1}{\sqrt {2}}}(|0\rangle +e^{i\alpha }|1\rangle )$ one gets outcome 0 and if the state is ${\frac {1}{\sqrt {2}}}(|0\rangle -e^{i\alpha }|1\rangle )$, the outcome is 1.
  
• Correction calculates all Pauli corrections to be applied on a given qubit in the pattern. The set of such parameters are called Dependencies for X and Z operators individually. To calculate all the Pauli Corrections on a given qubit, one needs to take into account the measurement outcomes of previous qubits as well as commutation relations. Both affect the Pauli corrections for a given qubit. Below is a formalism to explain the process with an example.
  

The effect of X gate on a measurement angle ($\alpha$) in X-Y plane is to change its sign and Z gate is to add a phase $\pi$.

$^{t}[M_{i}^{\alpha }]^{s}=M_{i}^{\alpha }Z^{t}X^{s}=M_{i}^{(-1)^{s}\alpha +t\pi }$

We shall denote measurement in X-basis ($M_{i}^{0}$) as $M_{i}^{x}$ and Y-basis ($M_{i}^{\frac {\pi }{2}}$) as $M_{i}^{y}$

Commutation relations:

$E_{ij}X_{i}^{s}=X_{i}^{s}Z_{i}^{s}E_{ij}\quad \quad (EX)$
$E_{ij}X_{j}^{s}=X_{j}^{s}Z_{j}^{s}E_{ij}\quad \quad (EX)$
$E_{ij}Z_{i}^{t}=Z_{i}^{t}E_{ij}\quad \quad (EZ)$
$E_{ij}Z_{j}^{t}=Z_{j}^{t}E_{ij}\quad \quad (EZ)$
$^{t}[M_{i}^{\alpha }]^{s}X_{i}^{r}=^{t}[M_{i}^{\alpha }]^{s+r}\quad \quad (MX)$
$M_{i}^{x}X_{i}^{s}=M_{i}^{x}\quad \quad (MX)$

$^{t}[M_{i}^{\alpha }]^{s}Z_{i}^{r}=^{t+r}[M_{i}^{\alpha }]^{s}\quad \quad (MZ)$

The last second equation is implied from the fact that for $M_{i}^{x}$, $x=0=-0$. Thus, X gate has no effect on measurement in X-basis for the given states. Using above notations we express the equation for circuit model of C-NOT from Figure 6 with two inputs and two outputs: Qubits: 1,2,3,4
Outcomes: $s_{1},s_{2},s_{3},s_{4}$
Circuit Operation: $X_{4}^{s_{3}}M_{3}^{x}E_{34}E_{13}X_{3}^{s_{2}}M_{2}^{x}E_{23}$

$X_{4}^{s_{3}}M_{3}^{x}E_{34}\mathbf {E_{13}X_{3}^{s_{2}}} M_{2}^{x}E_{23}{\overset {\text{EX}}{\implies }}$
$X_{4}^{s_{3}}Z_{1}^{s_{2}}M_{3}^{x}\mathbf {E_{34}X_{3}^{s_{2}}} M_{2}^{x}E_{13}E_{23}{\overset {\text{EX}}{\implies }}$
$X_{4}^{s_{3}}Z_{4}^{s_{2}}Z_{1}^{s_{2}}\mathbf {M_{3}^{x}X_{3}^{s_{2}}} M_{2}^{x}E_{13}E_{23}E_{34}{\overset {\text{MX}}{\implies }}$

$X_{4}^{s_{3}}Z_{4}^{s_{2}}Z_{1}^{s_{2}}M_{3}^{x}M_{2}^{x}E_{13}E_{234}$

Hence, we obtain a measurement pattern to implement C-NOT gate with a T-shaped graph state with three qubits entangled chain $\{2,3,4\}$ and 1 entangled to 3. X dependency sets for qubit $1:\{s_{3}\}$, $2:\phi$, $3:\phi$, $4:\phi$. Z dependency sets for qubit $1:\{s_{2}\}$, $2:\phi$, $3:\phi$, $4:\{s_{2}\}$. The measurements are independent of any outcome so they can all be performed in parallel. In the end, Pauli corrections are performed as such. Parity (modulo 2 sum) of all the previous outcomes in the dependency set is calculated for each qubit (i), for X ($s_{i}^{X}=s_{1}\oplus s_{2}\oplus ...$) and Z ($s_{i}^{Z}=s_{1}\oplus s_{2}\oplus ...$), separately. Thus, $X^{s_{i}^{X}}Z^{s_{i}^{Z}}$ is operated on qubit i.

References

*contributed by Shraddha Singh