Editing Glossary (section)

===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 <math>|+\rangle</math> entangled by <math>\mathrm{CZ}</math> indicated by the edges. It is known to be universal i.e. it can simulate any quatum gate.<br/>
<div id="5"> 
[[File:Cluster State.jpg|center|thumb|500px|Figure 5: Cluster State]]</div>
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 [[Supplementary Information#6|Figure 6]] to understand the conversion from circuit model to graph state model. As the computation relation follows <math>X=HZH</math>, thus, Figure [[Supplementary Information#6a|Figure 6a]] represents Circuit diagram for <math>\mathrm{CNOT}</math> gate in terms of <math>\mathrm{CZ}</math> gate and Single Qubit Gate <math>\mathrm{H}</math>.<br/>
<div id="6"><div id="6a"><div id="6b"><ul> 
<li style="display: inline-block;"> [[File:Circuit Diagram to implement C-NOT.jpg|frame|500px|(a)Circuit Diagram to implement C-NOT]] </li>
<li style="display: inline-block;"> [[File:Graph State Pattern for C-NOT.jpg|frame|500px|(b)Graph State Pattern for C-NOT]] </li>
<center><caption>Figure 6: Measurement Pattern from Circuit Model</caption></center>
</ul></div></div></div><br/>
[[Supplementary Information#6a|Figure 6b]] shows implementation of the first Hadamard gate on the second input state as measurement <math>\mathrm{M}_\mathrm{2}</math> on qubit <math>\mathrm{2}</math>. Then <math>\mathrm{CZ}</math> gate is implemented by the entangled qubits <math>\mathrm{3}</math> and <math>\mathrm{1}</math> in the graph state. Qubit <math>\mathrm{3}</math> is entangled to another qubit <math>\mathrm{4}</math> to record the output while measurement <math>\mathrm{M}_\mathrm{3}</math> on qubit <math>\mathrm{3}</math> implements the second Hadamard gate. Finally, the states to which qubits <math>\mathrm{(1)}</math> and <math>\mathrm{(4)}</math> are reduced to determine the output states of the two input qubits after <math>\mathrm{CNOT}</math> gate operation.</br>
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 <math>\{\mathrm{1,2}\}</math>. If qubit <math>\mathrm{1}</math> is to be eliminated, we operate <math>\mathrm{CZ}</math> with <math>\mathrm{2}</math> as target and <math>\mathrm{1}</math> as control.<br/></br>
<math>{\mathrm{CZ}}_{\mathrm{12}}{|+\rangle}_{1}|+\rangle_2=|0\rangle_1|+\rangle_2+|1\rangle_1|-\rangle_2</math></br></br>
Thus, if measurement on <math>\mathrm{1}</math> yields <math>\mathrm{m}</math>, qubit <math>\mathrm{2}</math> would be in the state <math>\mathrm{Z}^\mathrm{m}|+\rangle</math>. Hence, such Z-basis measurements invoke an extra <math>\mathrm{Z}^\mathrm{m}</math> 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.
 <div id="7"> 
 [[File:Brickwork State.jpg|center|thumb|500px|Figure 7: Brickwork State]]</div>
'''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):''
#	''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]).''
#	''For each row, apply the operator c-Z on qubits (i,j) and (i,j + 1) where 1 ≤ j ≤ m − 1.''
#	''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).''
#	''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).''

====Cylinder Brickwork States====

<div id="7"> 
 [[File:Brickwork state cylinder.png|center|thumb|500px|Figure 8: Cylinder Brickwork State]]</div>

The cylinder brickwork state <math>G^{C}_{n*m}</math> is a modification of the brickwork state of size <math>n*m</math>, for even n, where the first and the last rows are connected such that the regular brickwork structure is preserved while introducing rotational symmetry. A tape <math>T_i</math>, shown in Fig 8.3, present in a cylinder brickwork graph is the subgraph which includes all the states in the random rows <math>i</math> and <math>i + 1</math>.

If all the nodes in <math>T_i</math> of the graph <math>G^{C}_{n*m}</math> are prepared in the dummy qubit state, <math>|z\rangle</math> where <math>z \in {0,1}</math> and the rest of the nodes are prepared in the state <math>|+_{\theta_i}\rangle</math>, then after entangling according to the cylinder brickwork state, the nodes are completely disentangled from the rest of the graph. The final obtained graph would be <math>G^{C}_{(n-1)*m} \bigotimes^{m}_{i=1} |z\rangle</math>.

The steps to perform single trap verifiable universal blind quantum computing are:
* A random qubit is chosen to be the trap qubit (red node in Fig 8.1)
* All other vertices in the tape containing the trap qubit (solid black nodes in Fig 8.2), are set to be dummy qubits
* This results in an isolated trap qubit in the state <math>|+_{\theta_i}\rangle</math> together with many dummy qubits after entanglement operations (Fig 8.3)
* The net result, after discarding the dummy qubits, is a disentangled trap qubit in a product state with a brickwork state (Fig 8.4)

====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 <math>|\psi\rangle = a|0\rangle + b|1\rangle</math>, we consider the case of a two qubit graph state <math>\mathcal{C}_{2\text{x}1}</math>.<br/>
<div style='text-align: center;'><math>\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</math><br/></div>
If one measures qubit i in <math>\{|+\rangle,|-\rangle\}</math> basis and gets outcome s, qubit j reduces to,<br/>
<div style='text-align: center;'><math>=(a+b)|0\rangle+(a-b)|1\rangle, \text{if s=0}</math></br>
<math>=(a-b)|0\rangle+(a+b)|1\rangle, \text{if s=1}</math></div>
	
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 <math>H|\psi\rangle</math>.<br/>
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).<br/>
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.<br/>
*'''Preparation''' prepares all input qubits in the required state, generally represented as <math>|+_\theta=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta}|1\rangle)</math> where <math>\theta\epsilon[0,2\pi]</math>.  
*'''Entanglement''' entangles all the qubits according to the required graph state. This operation is denoted by <math>E_{ij}</math>, where C-Z is operated with i as control qubit and j as target qubit.<br/>
*'''Measurement''' assigns measurement angle in X-Y plane for each qubit. Measurement operator is notated as <math>M^\alpha_i</math>: the qubit ’i’ would be measured in <math>\{|+_\alpha\rangle,|-_\alpha\rangle\}</math> basis i.e. if the state is  <math>\frac{1}{\sqrt{2}}(|0\rangle+e^{i\alpha}|1\rangle)</math> one gets outcome 0 and if the state is <math>\frac{1}{\sqrt{2}}(|0\rangle-e^{i\alpha}|1\rangle)</math>, the outcome is 1.<br/>
*'''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.<br/>
The effect of X gate on a measurement angle (<math>\alpha</math>) in X-Y plane is to change its sign and Z gate is to add a phase <math>\pi</math>.<br/>
<div style='text-align: center;'><math> ^t[M^\alpha_i]^s=M_i^\alpha Z^t X^s=M_i^{(-1)^s\alpha+t\pi}</math></div>
We shall denote measurement in X-basis (<math>M_i^0</math>) as <math>M_i^x</math> and Y-basis (<math>M_i^\frac{\pi}{2}</math>) as <math>M_i^y</math><br/> 
Commutation relations:<br/><div style='text-align: center;'>
<math>E_{ij}X_i^s=X_i^sZ_i^sE_{ij}\quad\quad (EX)</math><br/>
<math>E_{ij}X_j^s=X_j^sZ_j^sE_{ij}\quad\quad(EX)</math><br/>
<math>E_{ij}Z_i^t=Z_i^tE_{ij}\quad\quad(EZ)</math><br/>
<math>E_{ij}Z_j^t=Z_j^tE_{ij}\quad\quad(EZ)</math><br/>
<math>^t[M^\alpha_i]^sX^r_i=^t[M^\alpha_i]^{s+r}\quad\quad(MX)</math><br/>
<math>M_i^xX_i^s=M_i^x\quad\quad(MX)</math><br/>
<math>^t[M^\alpha_i]^sZ^r_i=^{t+r}[M^\alpha_i]^s\quad\quad(MZ)</math></div>
The last second equation is implied from the fact that for <math>M_i^x</math>, <math>x=0=-0</math>. 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<br/>
Outcomes: <math>s_1, s_2, s_3, s_4</math><br/>
Circuit Operation: <math>X^{s_3}_4M_3^xE_{34}E_{13}X_3^{s_2}M_2^xE_{23}</math><br/>
<div style='text-align: center;'>
<math>X^{s_3}_4M_3^xE_{34}\mathbf{E_{13}X_3^{s_2}}M_2^xE_{23}\overset{\text{EX}}{\implies}</math><br/>
<math>X^{s_3}_4Z_1^{s_2}M_3^x\mathbf{E_{34}X_3^{s_2}}M_2^xE_{13}E_{23}\overset{\text{EX}}{\implies}</math><br/>
<math>X^{s_3}_4Z_4^{s_2}Z_1^{s_2}\mathbf{M_3^xX_3^{s_2}}M_2^xE_{13}E_{23}E_{34}\overset{\text{MX}}{\implies}</math><br/>
<math>X^{s_3}_4Z_4^{s_2}Z_1^{s_2}M_3^xM_2^xE_{13}E_{234}</math><br/></div>
Hence, we obtain a measurement pattern to implement C-NOT gate with a T-shaped graph state with three qubits entangled chain <math>\{2,3,4\}</math> and 1 entangled to 3. X dependency sets for qubit <math>1:\{s_3\}</math>, <math>2:\phi</math>, <math>3:\phi</math>, <math>4:\phi</math>. Z dependency sets for qubit <math>1:\{s_2\}</math>, <math>2:\phi</math>, <math>3:\phi</math>, <math>4:\{s_2\}</math>. 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 (<math>s^X_i=s_1\oplus s_2\oplus...</math>) and Z (<math>s^Z_i=s_1\oplus s_2\oplus...</math>), separately. Thus, <math>X^{s^X_i}Z^{s^Z_i}</math> is operated on qubit i. <br/>