Measurement-based Quantum Computation

Hello! I am back. It has been a while since I wrote a blog. As the title suggests, this is a blog about my understanding of the ‘Measurement-based Quantum Computation’, so far. I had actually come across this type of Quantum Computation late last year, but at that point of time, I could not follow it much. When 2022 started, I decided that I should finally focus on this topic and then, I realized I can also write a blog on this. While trying to study this topic, I stumbled upon this nice course on Coursera which is related to the topic. I audited the course and a lot of my understanding can be attributed to this course. Now lets get started. To follow this blog, I assume we know a little about the Gate-based Quantum Computation and Linear Algebra. If you don’t know about these yet, I highly recommend you go through the Qiskit textbook (getting an idea of the first two chapters should be sufficient to follow this blog). It is an excellent resource to just get started with Quantum Computing. I can’t thank IBM and the amazing Qiskit contributors enough for all that they are doing to help many of us get excited about this mind boggling emerging field. I sincerely hope that one day I also become one among these contributors. With that, let’s really get started.

Measurements in any arbitrary basis

We should first of all, focus a little on ‘measurements’. We know that a measurement basically means observing a quantum system which leads to a collapse of the wavefunction associated with the quantum system or simply speaking, collapse of the quantum state. What we usually study is that the measurement of a qubit would either give us a 0 or a 1. However, unlike classical bits, the states of qubits actually form a ‘Hilbert space’ and there comes the use and beauty of Linear Algebra. Consider the below figure:

The X axis and Y axis above form the XY plane or the R² Hilbert space. The X-axis is formed by scaling the vector (1,0) over the field of Real numbers (R) and similarly, the Y-axis is formed by scaling the vector (0,1) over R. The XY plane, as a result is formed by all linear combinations of (1,0) and (0,1) (over R). The vectors (1,0) and (0,1) form what is known as an ‘orthonormal’ basis (they are orthogonal with lengths 1 unit each). We also drew X’ and Y’ above in such a way that they are orthogonal (perpendicular) to each other. When we want to find the coordinates of the point A (as shown in the figure) with respect to the XY plane, we project the point onto X axis to get the x-coordinate and project it onto Y axis to get the y-coordinate. It is clear that all we needed to define the location of the point were the X and Y axes, but are they the only axes possible to define the point? It is like asking is there a unique way to define the location of a place on a map. Clearly, there can be several reference points. The above figure should also give us a hint. The answer is clearly a no. If you think about it, all we need is a pair of orthogonal vectors or lines, and there are uncountably infinite number of such pairs. That’s exactly what we are trying to say from the figure above. We can also define the location of the point A with respect to X’ and Y’ by projecting the point onto them. Suppose, you want your computer to do this for you, but your computer is designed in such a way that it can only give you coordinates with respect to X and Y axes. Clearly, the coordinates when seen with respect to X’Y’ plane is not the same as when seen from XY plane. What will we do now? Intuitively, we would like to rotate X’Y’ in such a way that after rotation X’ and Y’ would coincide with X and Y respectively. The point A would also rotate by the same angle and in the same direction. The new point A’ can now be projected on X and Y axes to get the coordinates with respect to X’Y’ plane.

All that we saw so far is intuition behind ‘measurement in a different basis’ in Quantum Computing. Few obvious differences are that in Quantum Computing, we deal with Hilbert spaces over the field of Complex numbers ( C ) and the magnitude of every quantum state has to be 1 implying that we would be dealing with orthonormal basis instead of just orthogonal basis. This is a very simple concept, but it is extremely important in a lot of Quantum applications. How does all this relate to measurements of Quantum systems? When we calculate the probability of getting a 0 or a 1 after measuring a qubit state, we are essentially projecting the state onto |0> and |1> (we apply Born’s rule to get these probabilities mainly because we are dealing with amplitudes that are complex numbers). If the projection on |0> is higher than the projection on |1>, it means that the superposition state of the qubit is actually closer to |0> than it is to |1>. This means that if we measure the same state several times (referred as number of shots in the Qiskit’s qasm simulator), we would be getting |0> more often than |1>. How much more depends on how much higher the projection on |0> is than projection on |1> or how much closer the state is to |0> than it is to |1>. As discussed above, we can do the measurement with respect to X’ and Y’ axes as well. In Quantum Computing, we can perform measurements with respect to eigen states of any operator. The most common operators are of course, the X, Y and Z Pauli operators. So when we get |0> or |1> after measuring a qubit, we are basically measuring the qubit in the Z-basis. If we were to measure the qubit in X-basis, theoretically, we should be expecting the eigen state |+> or the eigen state|-> (eigenvectors of X Pauli matrix) and if we were to measure in Y-basis, we would be expecting |+i> or |-i>(eigen states of Y Pauli matrix), but because our quantum computers are designed to measure only in the Z basis, we would have to follow the same steps we discussed when we had to measure the point A in X’Y’ plane but our computer could only do it in XY plane, just that the steps now need to be followed on a Bloch sphere.

We just discussed that to measure point A in X’Y’ plane when our computer can only measure in XY plane, we had to perform some rotation and then measure in XY plane. In Quantum Computing, this means that any measurement basis can be implemented by a suitable unitary operator and Pauli Z measurements. Let’s look at things more mathematically now. Let’s say our qubit is in a superposition state |x>. Since it is a superposition, it can be written as a|0>+b|1> where a, b are some elements in the set of complex numbers that ensure|a|² + |b|² =1. By Born’s rule, probability of getting a |0> given this state, after measurement is |<x|0>|² where <x|0> denotes the inner product between |x> and |0>. Hence, |<x|0>|² = |a|². We can also say that |<x|0>|² is same as measuring the outcome +1 (eigenvalue of state |0> with respect to Pauli Z. The +1 actually corresponds to <0|Z|0> ( for a state |y> and a Hamiltonian H, the expectation is calculated as <y|H|y> and you might have seen this if you have had a chance to read about or work with VQE and similar variational algorithms. This clearly equals the eigenvalue of |y> when |y> is a eigenstate of H and as we discussed, measurements give out the eigenstate on which the projection of the given state is maximum. So in variational algorithms, our idea is to get the best circuit with respect to a Hamiltonian that would increase the projection of the quantum state to the desired eigenstate which is usually the one with the least eigenvalue). Similarly, probability of getting |1> would be|<x|1>|²=|b|². Now, we can write |0> = 1/sqrt(2)(|+>+|->) and |1> = 1/sqrt(2)(|+>-|->). With this, we can write:

|x> = a|0>+b|1> = (a+b)/sqrt(2) |0> + (a-b)/sqrt(2) |1>. This would result in the probability of getting |+> or eigenvalue +1 after X basis measurement as |a+b|²/2. Similarly, probability of measuring |-> or eigenvalue -1 would be |a-b|²/2. But we can only measure in Z basis and so as discussed, we need to perform some operation and then, perform Z measurements. We know that the Hadamard operation (H) converts |0> and |1> to |+> and |-> respectively. This would give:

(I know the symbols here are different from the symbols I have been using, but one can just consider the state psi to be state x, alpha to be a and beta to be b). Seeing above and by applying Born’s rule, it should be clear that the probability of measuring |0> with this transformed state is |a+b|²/2 and that of getting |1> is |a-b|²/2. This is exactly what we were getting for |+> and |-> when we were discussing about measuring directly with the X basis. How did this work? The diagram with X, Y, X’ and Y’ axes along with point A and its transformed version A’ should explain this. Mathematically, it is happening because of the following and one can see the same for |-> state and -1 eigenvalue:

Bell Measurement

Now, let’s look at a common application using this trick: the Bell Measurement which is commonly used in Quantum Communication. Let’s consider the Bell basis. We want to measure any state which is in a superposition of |00>, |01>, |10> and |11> in the Bell basis:

With the trick we have been discussing so far, we want a 2 qubit unitary U to satisfy the following:

There is a well know unitary that does this for us, it is basically a CNOT followed by a H on the control qubit.

Measurement Operators

With this, let’s wrap up the concept of ‘Measuring in different basis’. There is another useful concept as far as Measurements are concerned, the ‘Measurement Operator’. When we say operators, we refer to matrices that act on vectors or quantum states. This means that a Measurement Operator is a matrix. What matrix is it? For the Z-basis, the measurement operator corresponding to the |0> outcome is simply |0><0| and the measurement operator corresponding to the |1> outcome is |1><1|. |0><0| means:

There are three popular rules when it comes to measurement operators:

Sandwich rule: Calculating the probability is same as calculating the expectation value of the measurement operator. We had noted something about expectation above (remember we described <y|H|y> for a state |y> and Hamiltonian H). If we denote the measurement operator corresponding to the |0> outcome as M0, the sandwich rule is just:

Identity rule: This just says that the sum of all measurement operators corresponding to a Hamiltonian is the Identity matrix. This is clear from the sum |0><0| + |1><1|. The Identity rule is a necessity so that the sum of probabilities of a state measuring in different basis states adds up to 1.

Normalization rule: Since we are discussing about measurement operators that act on quantum states, we have to ensure that the global phase of the outcome ends up having a amplitude s such that|s|² = 1. So while we apply the measurement operator, the overall calculation or operation would be such that it would ensure this.

We only discussed about measurement operators w.r.t the Z basis. It should be clear that the measurement operators w.r.t the X basis would be |+><+| and |-><-| and w.r.t the Y basis would be |+i><+i| and |-i><-i|.

Cluster States

Understanding cluster state is important for understanding measurement-based Quantum Computing. This type of computation is performed on a cluster state. Cluster states are analogous to an undirected mathematical graph. An undirected graph is pair G = (V,E) where V = {1,2,3,…n} is a finite set of vertices and E is a subset of the cartesian product of V with V i.e. E is a subset of V cross V. If you have ever studied Graph Theory, you would know about Adjacency matrix. An adjacency matrix is a square matrix of dimension equal to the number of vertices. An (i,j)th entry in an adjacency matrix is 1 if the vertices i and j are connected, else it is 0.

Some examples of undirected graphs are as following:

In above, V = {1,2,3} and E={(1,2),(2,3)}

The adjacency matrix corresponding to above graph is:

To generate a cluster state that satisfies a particular graph G=(V,E), we perform the following steps:

1. To each node i in V, we associate a qubit in the superposition state |+>.
2. For all pairs (i,j) in E, there is a cPhase or CZ where either of i or j qubit could be the control qubit and the other could be the target qubit. Note that we are saying either qubit could be a control qubit, this is because we defined a cluster state to be of the type of an undirected graph, so it doesn’t matter which is control and which is target. In fact, in the implementation of different operators, we could consider CZ in either direction.

Recall that a Z gate adds a phase of -1 to |1> state and a phase of 1 to the |0> state. This is because |0> and |1> are eigenstates of the Pauli Z operator. So, CZ is just controlled Z which would act if the control qubit is in |1> state. With all that we discussed so far, a cluster state can be written as below:

So for a 2 node cluster state given as below, the final state would be 1/sqrt(2) (|0>|+> + |1>|->). Note the flip of phase that caused the 2nd qubit to change from |+> to |->.

Consider a 3 node cluster:

Note that in the above cluster state, 2 is connected to both 1 and 3 and the cluster state is undirected which means I can consider the edges to be CZ where control is 2 and target is 1, and CZ where the control is 2 and the target is 3. The final state can thus be obtained by just expanding |+> state in terms of |0> and |1> for the 2nd qubit and taking the 1st and the 3rd qubit as |+>. The final state is therefore:

1/sqrt(2)(|+>|0>|+> + |->|1>|->)

Measurement-based Quantum Computation

With all that we saw so far, we can now discuss about Measurement-based Quantum Computation. This type of Quantum Computation is also often called One-way Quantum Computation. Why one-way? We know that measurements collapse the wavefunction of a quantum system. Once collapsed, we don’t know about the original quantum state. Since it is irreversible, it is called a one-way quantum computation.

The above figure summarizes the difference between the gate-based quantum computation and the measurement-based quantum computation. We know that in the gate based quantum computation, we basically apply a set of unitary operations to evolve the quantum system as per our use-case. This evolution is deterministic which means that I exactly know the quantum state after application of any unitary. It is a different story that the current day quantum computers are subject to noise that might make results a bit uncertain, but given an ideal quantum computer, one would typically know the exact evolution process. Unitary operators are also reversible, so one can apply the inverse of a unitary to revert back to some quantum state in history. The measurement-based quantum computation, on the other hand, is probabilistic because for a given superposition state, the measurement outcomes would always be random. The extent of randomness would differ for different superposition states. For instance, for |+> or |-> states, the outcomes would be absolutely random, in the sense that typically one would get a |0>, 50% of the times and similarly for |1>. For something like 1/sqrt(3)|0>+sqrt(2/3)|1>, the chances of getting a |1> is higher. The collapse of the wavefunction after measurement also means that the measurement operator is irreversible and one cannot get back the original state. When we discussed measurement operators, it was obvious to see that the operators are non-invertible matrices.

Implementing different operations by using different types of measurements locally

This part is the key in understanding how measurement-based quantum computation works. Let’s consider below:

The |in> state could be anything, it can actually just be |+> and in fact, from what I understand it would be |+> in case of the cluster state on which measurement-based quantum computation is carried out. What does |out;X,+ or -1> mean? That’s just a notation to show that |out> is the state of the 2nd qubit when X measurement is performed on the 1st qubit and the X measurement can either yield a eigenvalue of +1 or -1. We have already seen that the state of the quantum system after the application of cPhase or CZ would be (here control is the upper qubit in the figure on which an X measurement is applied(denoted as 1) and the target is the bottom qubit (denoted as 2):

Now the outcome of the X basis measurement would either give a state |+> or the state |->. In order to check what |out> would be when the measurement on qubit 1 is |+> or |->, it would be good to just express |0> and |1> in terms of |+> and |->. |0> = 1/sqrt(2)(|+>+|->) and |1> = 1/sqrt(2)(|+> — |->). Once we do that and with some simple rearrangement of terms, we should get below:

What do you see in the above quantum state? It shows that when the first qubit turns out to be |+> post measurement, the 2nd qubit would be in the state a|+>+b|->, this state is nothing but a H (Hadamard operation) applied to the psi state or the |in> state. If the first qubit ends up being |->, the 2nd qubit would be in a|+>-b|-> state. This clearly is an application of Z operation followed by a Hadamard. So the overall quantum state as given above can be written as:

Now that’s interesting. It is like a quantum teleportation of the |in> state from qubit 1 to qubit 2, but it is teleported with some operations. We can therefore say that we have implemented that operation with a measurement-based quantum computation. This can be considered as an implementation of the Hadamard operation.

Now, what if the first qubit was measured in the Y-basis. Recall that the eigenstates of the Pauli Y operator are |+i> and |-i> where |+i> = 1/sqrt(2)(|0>+i|1>) and |-i> = 1/sqrt(2)(|0>-i|1>). We will follow the same steps we did for the X basis measurement with the only change being that we would now express |0> and |1> as the superpositions of |+i> and |-i>. |0> = 1/sqrt(2)(|+i>+|-i>) and |1> = 1/sqrt(2)(|+i>-|-i>). After rearrangement of terms, similar to what we did when the qubit 1 was measured in X basis, we would be getting the result: if the measurement outcome of the Y basis measurement is |+i>, the |in> state would get teleported to the 2nd qubit with an operation of H and a rotation by an angle of pi/2 about the Z axis. Similarly, when the measurement outcome is |-i>, the |in> state would get teleported to the 2nd qubit with an operation of H, a rotation by an angle of pi/2 about the Z axis and a Pauli Z operation. The states would look like below, with the first one being the outcome when measurement resulted in |+i> state:

This can be considered the implementation of a H and a pi/2 rotation about Z.

Now, what if we do below:

This would just simply give |+> on the 2nd qubit if the first qubit ends up being |0> and |-> if the first qubit ends up being |1>. This is clear from the initial state of the quantum system itself (shown below):

Therefore, Z basis measurement is really not doing anything, it is neither teleporting the |in> state nor is it performing any operation.

Because the X and Y basis measurements perform some operations, we consider only measurements that are some combinations of X and Y if our intention is to implement operations. What kind of combination though? We would choose something like:

Now one may wonder why only this kind. It is basically a choice because the eigenstates of this operator are similar to the eigenstates of X and Y operators with just a difference of phase on the |1> state. You can easily verify that the eigenstates of this operator are:

This just makes it simpler because we just have to follow similar steps as we followed for X and Y basis measurements on the first qubit. What we end up getting as the state of the 2nd qubit when the measurement outcome of the 1st qubit is |e1> is:

Similarly, we end up getting the below state when the measurement outcome of the 1st qubit is |e2>:

So now we are not only able to implement H, a rotation of angle pi/2 about Z axis, but also an arbitrary rotation about the Z axis.

We can just write the |out> state as:

All that we saw above can just be written in the form of a few steps that we need to follow to implement single qubit transformations:

1. cluster state preparation;
2. cPhase or CZ between qubits in input states to some nodes of a cluster state;
3. local measurements of some nodes of the resulting state.

We saw in the above cases that we implemented rotations of arbitrary angles about Z axis, but that’s not enough for performing any single qubit transformation.

Let’s talk a little about Universal single qubit transformations: Any Hermitian matrix can be decomposed using Pauli matrices. Also, for every Hermitian, there is a corresponding unitary matrix and vice versa.

Here U is the unitary operator corresponding to Hermitian operator H which is decomposed in terms of X,Y and Z operators, as seen above. This shows that the unitary operator is basically a composition of rotations about x, y and z axes on the Bloch sphere. In the case above, the unitary can be arrived at with rotation by an angle theta/2*ax (x is the subscript)about x axis, rotation by theta/2*ay about y axis and rotation by theta/2*az about z axis. Since ZX=iY and in fact, every Pauli can be seen as a multiplication of the other two Pauli matrices, one can just consider rotations about 2 axes to define any unitary operation. So if we want to implement any single qubit transformation through measurement-based quantum computation, we would like to get something like below:

With 2 node clusters when we performed X, Y, Z and A(theta) measurements, we could only get arbitrary rotations about z axis. If we want something beyond that, we would require more nodes and a bigger cluster. Consider below:

Once we have the results for the 2 node clusters where we performed measurements with different operators, it is simple to see what |out> will be for this case:

This again shows that we have been able to implement rotations about z axis, but if we want to see if this can also show some rotation about x axis, we would have to use some relationships:

The first relationship basically shows that a rotation about z axis and the Pauli Z matrix commute, this is very intuitive because Z itself is a rotation about z axis by angle pi. Talking more about commutativity, two operators A and B commute if AB=BA ([A,B]=0), they anti-commute if AB=-BA and they don’t commute if AB is not equal to BA. The 2nd relation above can be just verified. Using these relations, the |out> state could be rewritten as:

So we now are able to show that we can also perform a rotation about x axis, but you see, this still does not mean we have been able to implement any single qubit transformation because as we saw above, we want to get:

As you might have guessed, this would require even more number of nodes and more measurements. Consider a 4 node linear cluster:

On this cluster, let’s consider the following:

With all the results we have seen for 2 nodes and 3 nodes clusters with different types of measurements, we can see that this would give:

Does that help? Well, we need to use a trick. Let us just fix theta1=0

Ah! Now that seems like what we want and this shows that we can implement any single unitary transformation. We can do some change of variables and show:

To understand universality better, I highly recommend this chapter from the Qiskit textbook. It is one of my favorite chapters.

Now it only remains to show that we can also implement a CNOT operation. Consider below:

Actually, the fact that we create cluster states using CZ operations itself should make it seem that implementing CNOT is not a big deal in measurement-based quantum computation, especially because we already saw the implementation of H operation with 2 node clusters. Recall that HXH=Z and H(CNOT)H=CZ (here H is applied on the target qubit). So, if we look at the above figure, the X-basis measurement on 1st qubit would teleport the Hadamard transformed|in1> state from qubit 1 to qubit 2. Similarly, the X-basis measurement on qubit 4, would teleport Hadamard transformed|in2> from qubit 4 to qubit 3. Now the CZ between qubits 2 and 3 can be written as H(CNOT)H. Assuming we get a |+> state measurement outcome from both the measurements and since H.H=I, we get the following output state:

Considering all possibilities of |+> and |-> measurement outcomes, we would be getting:

We can also implement multiple CNOTs, for example, like below:

One more implementation would be:

A typical cluster state would look like:

So we have been able to implement universal single qubit operations and CNOT operation, which means we can do any transformation we like with the measurement-based quantum computation. You can see that there is a lot of flexibility in how one can implement any quantum operation, for instance, one can choose any nodes to measure and choose any node where one would like to see the |out> state. Pictorially, this can be explained as following:

Suppose, we want to implement below:

This can be implemented in either ways below (this is just a very general example). Note that the yellow nodes show the nodes that have been used for implementing U, the blue correspond to the nodes that have been used for implementing CNOT, the nodes we don’t see are measured with the Z-basis.

As a conclusion we can say that implementing any operation on a cluster state with the measurement-based quantum computation is basically just choosing the right type of measurements on the appropriate nodes or qubits. If we want to not perform anything on a bunch of qubits, we can simply measure them with the Z-basis since we saw that the Z basis doesn’t contribute to implementation of any operation.

A glimpse of Quantum Error Correcting codes

Before I end the blog, I want to talk about Quantum Error Correction Codes. The reason is that there is some similarity between error correction and measurement-based quantum computation, in the sense that both work on a lattice of qubits. Quantum Error Correction also involves local measurements that help in detecting the errors. I would not get into details of Quantum Error Correction. If you want to dive deeper into this topic, I highly recommend following Dr. James Wootton’s blogs. He is currently writing a series of blogs explaining Quantum error correction. In fact, I had stumbled upon his excellent series of blogs that he had written in 2016 on the same topic. A few additional concepts that will help us generalize Quantum Error correction are Stabilizers, stabilizers of cluster states, the fact that they form an abelian group by multiplication, understanding the weight of an error, identifying error matrices depending on the errors we want to identify and correct, finding a subgroup from the group of stabilizers that contain operators that commute with each other but anti-commute with the error matrices and why these are the errors we can correct.

I will finally conclude now. Before I end, I would like to say that there is much more to measurement-based quantum computation than what I have covered in this blog and what I currently know. For example, there is measurement-based quantum computation even for the continuous variable set up. In this blog, we only dealt with this type of quantum computation from a discrete variable perspective. Understanding the practical hardware implementation of measurement-based quantum computation is also a very interesting topic. We can further dive into these topics in future blogs. For now, I am ending it. I hope this blog helped all of us understand the concept behind measurement-based quantum computation. Feel free to provide your feedback on this blog. I really look forward to discussions and suggestions :)