In this course we will extend the qubit concept and start doing some algebra. We will learn how to manipulate qubits, how quantum logical gates works, and try defining the Y, Z and phase gates, giving us the full range of single qubit gates used in this mod: X, Y, Z, Hadamard, S and T. (S and T are both phase gates).
Course Block A.
You also need to know linear algebra and the basics of complex numbers. There are links to resources nearby.
This course is divided up into lectures. For the quantum computing theory, we're gonna use parts of the video series Quantum Computation for the determined. It's a series of short video lectures given out by a well known phycisist and author named Michael Nielsen. It aims to teach non quantum physicists quantum computing. Each lecture will require you to watch a few of those videos.
It is of course recommended to watch them all, but the most relevant videos are listed in each section. When you are done with this course, it may be a good idea to watch them all in order again.
Note on math
In the first video he mentions a webpage where they teach linear algebra. This link takes you to that site: Khan Academy Linear Algebra. That site seems to require some sort of registration, however, and that may not be such a hassle if you like it, but otherwise there are other alternatives. A quick google search shows that MIT has an online linear algebra course, complete with study material and video lectures. MIT Linear Algebra.
A primer on complex numbers can be found here: http://www.clarku.edu/~djoyce/complex/
Lecture 1 - qubits, vectors and basesEdit
Watchlist: Videos 1 and 2.
By watching Nielsen we have improved the concept of a qubit that we developed in the last course. A qubit is the unit of quantum information, and also - it represents the simplest possible quantum system!
A general qubit can be written as such:
In the last course we referred to the numbers α and β loosely as probabilities tied to the bit values |0> and |1>. When we measure a qubit we get either |0> or |1>, and the numbers determines the probabilities for each. Nielsens videos has now given us more information about α and β. They are numbers, and the square of the absolute values of these numbers are the actual probabilities. They are complex numbers, which is why we must use the absolute value.
Nielsen also shows us what |0> and |1> are, in a more mathematical sense. They are two vectors, and these vectors form an orthonormal basis for all possible qubit states. The "normal" part of orthonormal means the basis vectors have norm = 1, and ortho means the two vectors are orthogonal (perpendicular).
An analogy could be made with the real plane (a.k.a. the 2D plane). We can use the unit vector of x (1,0) and y (0,1) to express any point in the plane (a,b). All points are linear combination of those vectors:
(a,b) = a(1,0) + b(0,1)
This is an orthonormal basis, because the norm of both (1,0) and (0,1) is 1, and they are perpendicular. Orthogonality is usually tested by seeing if the dot product of the vectors are 0, because this works for N-dimensional vectors as well. We can test this:
|0> and |1> are in fact (1,0) and (0,1), but not in the real plane. The numbers α and β are complex, so we have a different type of space, but it behaves a lot like the real plane. We will use that fact to explain a lot of the basics. There are some caveats though.
The normalization constraint
There are some rules that separates qubit states from general pairs of complex numbers. The most important rule is the normalization constraint. The sum of the probabilities must be 1, so we get:
If we consider only real alpha and beta, this would put all pairs of real numbers that represents a qubit on the unit circle in the plane. It's a bit different in the general case, but there is a geometric figure that works for complex alpha and beta as well, called the Bloch sphere. More on that later.
When working with qubit states, we often use the vector rules to express and manipulate them. A common state is for example the "fifty fifty state", which means the probabilities for both |0> and |1> is 50% (or 0.5).
Thus, the state can be written:
Normally we break the constant out:
Besides the normalization constraint, there is another important rule about qubit states. It is regarding scalar multiples of qubit states. If we have two qubit states that only differ by a (complex) constant, they are considered equal:
The reason is because it's impossible to separate two such states when measuring. This means the number gamma can essentially be tossed away. Consider this example:
Now take this state:
We could re-write the second state like this:
The constant rule means these two states are for all intents and purposes the same. The number gamma would of course be -1 in this case.
The constant multiple is normally referred to as a "global phase". Given that we have:
For a constant multiple, we get this:
This puts gamma on the unit circle in the complex plane, which means that the only thing about gamma that affects the state is its argument, or "angle", so it will only "rotate" the qubit state. In the example above we used -1 as the constant, but |-1| is 1, so it's legal, and the argument for -1 (seen as a complex number) is 180 degrees.
Change of basis
We get back to the fifty fifty state here. Lets say you have these two states:
Notice they are not constant multiples of each other - there is only one minus sign in the second state, not two.
These two states happens to form a basis in the qubit space, just as |0> and |1>. It happens to also be an orthonormal basis. In fact, those states are so important they have their own symbols:
Geometrically, if we allow only real coefficients, |+> would be the blue vector in the diagram, and |-> the purple one. They sort of represent a 45 degree clockwise rotation of the |0> and |1> basis (the "computational basis"), then a flip around the x-axis. The flip is because |-> is derived from |1>, and |+> from |0>.
Btw, if we allow complex coefficients this analogy still holds, in a way, but we will discuss that in the final lecture.
Now, lets say I have a qubit state that I express in this basis rather then the computational basis.
What if I want to express this in the computational basis instead? I could do that, using the normal vector rules.
If we re-organize the terms, we get this expression on the normal computational basis form:
As long as these two terms satisfy the normalization constraint, we have a legal qubit state. An example would be if we have this:
This pair would give the constant 1 at |0>, and 0 at |1>, so the entire state would simply be |0>. This makes sense geometrically, since it would represent the vector that lies "half way between |+> and |->, which would be |0> according to the figure.
The reason we did this is first of all to show that normal vector algebra generally works, but also to show the square root factor. It happens to be the most commonly occurring superposition, and you will see it all the time.
If all of this seems weird, here are some good news: When working with qubits, the only states you see on a regular basis is |0> and |1>, sometimes positive sometimes negative, and the |+> and |-> states. Being able to convert between the two, combine them into multi-qubit states, and knowing what happens when they are run through the most common gates is actually enough to become "proficient" in quantum computing.
Lecture 2 - Single qubit quantum gatesEdit
Watchlist: Videos 3, 4 and 5.
Quantum logical gates
Quantum logical gates "acts" on qubit states. The quantum NOT gate acts on the basis states in the following way:
The Hadamard is slightly more complex. It acts on the basis states in the following way:
These are the |+> and |-> states from the previous lecture.
Measuring and reversibility - unitary matrices
When measuring a qubit, the state will collapse into either |0> or |1>. The chance for each outcome is determined by the two numbers 'a' and 'b'. We will not get into more details yet, but after a qubit has been measured it no longer contains any (hidden) information about 'a' and 'b', which means that measurement is an irreversible process. There is no way to undo the measurement to get 'a' and 'b' back. The gates X, Y, Z and H are all reversible gates, which means that the process of applying the gate to a state does not destroy the old state. All quantum gates must be reversible, because of how quantum systems evolve.
Mathematically we can reformulate the last statement by saying that all matrices that represent quantum gates must be invertible. if you have a state |v> and apply an invertible matrix M, you get M|v> = |u>. If you apply M-1 to |u>, you get |v> back: M-1|u> = |v>
We also have another requirement, and that has to do with the normalization constraint. If you have a valid qubit state - applying a quantum gate to it must yield a new valid qubit state. For example, if you have a valid state |v>, and a gate with matrix M, then |u> = M|v> must also be a valid state.
There are other properties required for a matrix to be able to work as a quantum gate, and it is all neatly summed up in the concept of unitary matrices. A unitary matrix has the following properties:
1) It is a square matrix.
2) Its inverse is the conjugate transpose:
The conjugate transpose is the complex analogy of the real transpose. For real matrices, we would require:
The difference between the conjugate transpose and the regular transpose is that we don't have the element-by-element relation , but instead , where * means the complex conjugate. As you can see - if all elements in a matrix is real (as with X, Z and H), they are in fact the same.
We will get into this more in later courses, but it's good to know about it from the start.
Qubits and gates can be expressed using vectors and matrices. The vectors |0> and |1> has the following representations:
An arbitrary qubit state can be written as a linear combination of |0> and |1>:
This is just a different way of doing things.
When applying a gate to a qubit state, we do matrix-vector multiplication. Take the NOT, or X gate for example. It has the following matrix representation:
Applying this to |0> would be multiplying X with |0>:
Single qubit gates and ket algebra
These are the matrix representations for X, Y, Z and the Hadamard
If we want to calculate the effect on a certain gate on the basis states, we could do that using matrices and vectors. For example, let's calculate Z|0> and Z|1>.
Now we can figure out the effect of the Z gate on a general qubit state. Remember, gates act linearly, so we get:
Lets do the same for H|0> and H|1>, to derive the expressions we saw earlier in this section.
It's important not to pay too much attention to what these various states are useful for. We only need to know how to work with them at this point.
Finally, the X gate is the quantum NOT gate, as we've already seen. It also represents a rotation around an axis, but we need more theory to understand how and why (Bloch sphere related stuff). The Y and Z gates acts on a qubit in the exact same manner, however, but their axes of rotation are different. We will get more into this later.
Gates and bases
So X is the NOT gate, that much is clear, but at this point you may ask yourself what the Y and Z gates are used for. We will encounter the Z gate several times in the superdense coding and quantum teleportation protocols. It is actually a sort of NOT gate as well.
Let us work in another basis for a while, namely the +/- basis. We can transform a qubit into and out of this basis by using the Hadamard gate. The Hadamard is its own inverse, meaning HH = I. The operation is therefore similar to a 180 degree rotation in the plane, for example, or a reflection. If you do these operations twice you get back to the point where you started.
We've seen how |0> and |1> is transformed into |+> and |-> by applying the Hadamard operator. Now we will show that |+> and |-> is transformed back into |0> and |1> by applying the Hadamard gate again.
If we start with |0> we can change that into |+> by applying the Hadamard operator. Let us apply the X gate to the new state and see what happens. We use only kets this time.
Notice in the two equations right before the last |+> we just change the order of the terms.
We can also show that X|-> = -|->:
The last state can be rewritten:
Apparently, when working in the +/- basis the X gate is no longer the NOT gate. In fact, it acts very much like the Z gate.
What about the Z gate then? We apply it to |+> and |->
When we are in the +/- basis, the Z gate acts as a NOT gate.
There is an important principle here. Superpositions allow us to put qubits in states that changes the way gates work. We can't do that in classical computing.
What about Y? Well, we could do stuff with it, but the Y gate is not often used (at least not in simpler algorithms and protocols), and make things harder. We will get to that later.
Before finishing this lecture, we will express the last stuff we did in form of gate substitution. We saw that X became Z, and Z became X when we did a basis change using the Hadamard. Lets say we had a circuit for that.
That circuit would then be equivalent to the circuit:
We can actually express this in a more compact form. For the Matrices H, Z and X, we have the following relations:
HZH = X
HXH = Z
The operation here is regular matrix multiplication.
There are other relations that can be found when combining gates, but this is one way. It is useful to play around and look for various connections (or at least try and verify these two).
Lecture 3 - Multigates and qubit compositionEdit
Watch list: Video 9
The controlled-NOT gate (or cNOT) acts on the combined state of two qubits. The possible basis states for two qubits are not |0> and |1>, but |00>, |01>, |10> and |11>. The state |00>, for example, would be "two qubits, each in the state 0". This is also written sometimes as |0>|0>.
Think of this as you think of regular bits. A two-bit string is 01 or 00 for example. The same principle applies here. These particular four states can be used as the four basis states for a two-qubit state, just as |0> and |1> are basis states for a single qubit.
There are several ways one could think about these combined states. We remind ourselves that a general single-qubit state can be written as a linear combination of the two basis states:
Given that we know what the basis vectors are, we can also express this simply as:
A general two-qubit state can be expressed as the linear combination of the four basis states |00>, |01>, |10>, |11>:
We can also write this simply as:
The column matrix forms of each of the two-qubit basis states would be:
Combining qubit states
At this point one might ask - what is the relation of |0> and |1> to the two-qubit basis vectors? Apparently they can be combined, but how is |0> and |0> combined to form |00>, and of course - how is (1,0) and (1,0) combined to form (1,0,0,0)?
It is done using something called the tensor product, or Kronecker matrix product. We will study the tensor product in course C, but up to then we will stick to the conventient "braket" notation. Combining kets is fairly straight-forward.
We know how to combine the basis states, but what about superpositions? Well, we go back to the regular bit-strings. If you have two bits - bit one, which is 0, and bit two, which is 1, the combination becomes 01. Now think of the bit values 0 and 1 as something different then numbers - like for example true (T) and false (F). What if bit one is in the state F with a certain chance, and the state T with another chance? We could express that as the state of the bit being (aF + bT), where a and b are probability amplitudes. The combined state of bit one and two would be (aF + bT)T instead of FT (01). If bit one is measured to be F, we get FT (01). If we measure it as T, we get TT (11).
If qubit two is in a superposition as well (cF + dT), we get the combined state (aF + bT)(cF + dT). We have no superpositions in classical computing, however, so the only possibilities for qubit one are (a = 1,b = 0) and (a = 0,b = 1). We have the same situation for qubit two, so the only possible states are FF, FT, TF, TT.
Let us now do some algebra. We know how to combine bits. It turns out we can use the associative law, and the regular distributive law over addition, and some other rules. Let's expand:
(aF + bT)(cF + dT) = (ac)FF + (ad)FT + (bc)TF + (bd)TT
If we plug in a = 0 in the left hand side, we get:
(0F + 1T)(cF + dT) = T(cF + dT)
This is as expected. What if we do it on the right hand side?
0cFF + 0dFT + 1cTF + 1dTT = cTF + dTT = T(cF + dT)
This is just an analogy, but it works for qubits. We just replaced |0> with F, and |1> with T here, and applied the same math.
When it comes to qubits and probabilities, these results makes a lot of sense. If there is a 50% chance that qubit one is in the |0> state, and a 50% chance that qubit two is in the |0> state, we would expect a 25% chance to find both the qubits in the |0> state - provided that the probabilities are independent (which they are in this case). If we look at the algebra above, we would get "ac" as the probability amplitude for FF (00), which implies that the probability amplitudes should be multiplied. If this was the case, we would also have a 50% chance for |1> in both qubits, and so forth, so each combination |00>,|01>,|10>,|11> would have a 25% chance, adding up to a total of 100% chance to find the qubit in either of these states (there is no "fifth alternative"....).
Is this always the case? Will the probabilities in a combined state always sum to 1? The answer is yes. Both of the individual qubits are in a legal state. If we call them (a,b) and (c,d) we get:
For the 2-qubit state to be normal, we would require:
We can re-write the left side:
Using the fact that qubits A and B are normal, we get this:
Lets look at the rules for combining kets a bit closer. We know that kets can be combined, but what are the general rules?
First of all, we have to keep the order. If we combine |0> and |1>, that implicitly means |0> comes first, so we get |01>. If we combine |1> and |0>, we get |10>. These are different states! In other words - combining states is a non-commutative operation.
Combining works linearly. Technically we would say the tensor product is distributive over addition, and we touched on this earlier. It means we can combine kets as such: |0>(|0> + |1>) = |00> + |01>.
Lets look at an example. We want to combine |0> with the state |+>:
We could also end up having to combine |+> with |0> (note the difference), giving us:
So what does these states mean? The first one is a state where we might end up with the first qubit being |0> 100% of the time, and the other qubit being either |0> or |1> - each with a 50% chance. Notice that there is no |10> or |11> term, or actually they are there, but the coefficients for those are 0.
In the second state, we end up with the first qubit being |0> or |1>, each with a 50% chance, and the second qubit is always |0>. There is no |01> or |11> term.
That's all we need to know about combining qubits for now.
Applying gates to combined states
If we apply a NOT gate to the state |00>, what happens? It will only act on the first qubit, so we would only be concerned with the first part of the state. If we write the state |00> = |0>|0>, for clarity, applying the NOT gate to the first bit would give us the state (X|0>)|0> = |1>|0> = |10>.
This makes sense. What if we apply the NOT gate to the second qubit? We get the state |0>(X|0>) = |0>|1> = |01>.
We remind ourselves that the gates, or operators, all act linearly. This means we can do this to a combined state as well. Lets look at a series of examples.
NOTE: We're gonna omit the normalization constants here to make things more clear.
We have the following state:
That is a 1-qubit state. In fact it's the state you after applying the Hadamard gate to |0>, but without the normalization factor. What happens if we apply a not gate to this state? The usual:
If we look at it we notice it actually does not change, but that's not important.
What if we apply the NOT gate to this combined state?
We could first re-write it to make things more clear.
We must now ask ourselves - on which of the qubits do we apply the NOT? This is a combined state, and the left qubit in each basis state is the first one, while the right one is the second one. Lets say we apply the NOT to the first qubit. We would get:
now we use the fact that we apply this to the first qubit...
If we applied the NOT to the second qubit, the last part would change to this:
We can also illustrate this in another way. Lets take two qubits in the |0> + |1> state, and combine them. We would get this:
Applying a not gate on the first qubit would be the same as doing this:
If we expand this, we see that only the first qubit has been affected:
The controlled NOT
The controlled NOT-acts in the following way on the basis states:
A general two qubit state could be expressed as such:
Since gates acts linearly on qubit states, we can calculate the result of applying the cNOT to an arbitrary 2-qubit quantum state:
The cNOT has a matrix representation as well:
Applying the cNOT to a 2-qubit state is the same as multiplying the cNOT matrix with the state. This carries over larger composite systems as well. In general, a vector representing an N-qubit state requires 2N elements, and the matrix M for a gate operating on N qubits is of dimensions (2N,2N).
Lecture 4 - EntanglementEdit
Watch list: Videos 11 and 13 (12, 14 and 15 harder and optional)
The theory is covered in the videos.
Combined states and entanglement
If we look at the notes in lecture 3, we combine two qubit states into one, for example like this |0>|1> = |01>. Since the two qubit states are merged into one state, does that mean they are entangled? The answer is no.
An entangled state is a certain type of combined state. Mathematically we have this rule:
If a combined state can be written as a product of individual qubit states, the state is called a product state. An entangled state is not a product state. In fact, it's defined as the opposite of a product state.
Good examples of product states are four states |00>, |01>, |10> and |11>. Each can be written as a combination of two one-qubit states, for example: |01> = |0>|1>. If we measure the particle corresponding to the |0> state, we get |0>, and if we measure the particle corresponding to the |1> state, we get |1>. The measurement result for the first qubit does not depend on the result for the second qubit, and vice versa.
Distinguishing a product state from an entangled state can be hard some times. Luckily, we can also find out if a state is entangled by inspection, that is - without having to try and factor it into a product of single qubit states. We will look at an example of that in the next section.
The Bell states
The bell state is the two-qubit state:
The column vector form would be:
This is a good time to remind ourselves what this really represents - a two qubit state with 50% chance of being |00> and a 50% chance of being |11> when measuring. We can't get the states |01> or |10>.
if we measure qubit 1 or 2, we will end up with either |0> or |1>. If lets say qubit 1 is measured and gives |0>, that means we must have had the combined state |00>, which effectively puts qubit 2 in the |0> state. This happens as a consequence of measuring qubit 1. Same thing if qubit 1 measures |0>. We also have the same situion if either of the qubits are |1>.
This is another definition of an entangled state. If the measurement outcome of qubit 1 depends on the measurement outcome of qubit 2, or vice versa, they are entangled. It coincides with the product state definition in a not so obvious way, and we don't have to know exactly why. It suffices to be aware of both of them at this point.
An entangled two-qubit state |w> can not be expressed |w> = |u>|v> for any one-qubit states |u> and |v>.
That is the mathematical definition of entanglement, and it can be extended to entangled N-qubit states.
There are more Bell states then the "Bell state". In fact, there are four of them:
We are going to show how these are generated in the next section.
This video shows an implementation of the superdense coding protocol.
This video may seem a bit weird, but what it does is poking fun at the fact that you are actually generating and transmitting two qubits "behind the scenes" - not one, as implied. Much like you are actually creating and transmitting no less then three qubits in the quantum "teleportation" protocol, and there has to be a quantum channel between the sender and receiver. This bugged me a little when I got started.
Anyways, in this protocol we start out by generating the Bell state:
This is done in two steps. We start out with two qubits (1 and 2) both in the |0> state. We then apply a hadamard to qubit 1. This gives us the combined state:
We then apply a cNOT to that state. We only have to think about how the cNOT modifies basis states, since it acts linearly, and from lecture 3 we know that:
This means we get the Bell state from applying the cNOT.
Alice then manipulates the states, as shown in the video, and depending on the gate combination she chooses, the state is changed, and the measurement results at Bobs will be affected.
We could do the algebra for all four cases, but lets focus on the case where she uses only the Z gate.
Before alices interaction, we have the bell state:
Alice is in control of the first qubit, and applies a Z gate. The Z gate acts in the following way on the basis states:
Applying the Z-gate locally to the first qubit will change the combined state into this:
When bob gets it, he applies a cNOT:
Now, in order to finish this calculation we have to factor the two individual qubit states out. We can do it like this:
As we see here, the second qubit is |0>. The first qubit is the state |->, which you get from applying a Hadamard gate to a qubit in the state |1>. This is important, because the last thing bob does is to apply a Hadamard locally to the first qubit. The Hadamard is self-inverse, meaning HH = I. Which means we will end up with this state:
Lecture 5 - Measurement and quantum teleportationEdit
Watch list: 16,18,19 (17 optional)
As mentioned before, measurement (in the computational basis) will collapse a qubit state into either |0> or |1>, depending on the probability-amplitudes for each. What about when we have a combined state?
We have already touched on this in the superdense coding protocol. In that case, though, we always got a basis state in the end - meaning the two qubit final state was either |00>,|01>,|10>, or |11>. When measuring these states, nothing really happens. Measuring does not change the state.
This has been the case in most examples, actually. We have been able to tell the final state of a circuit simply by inspection. Like a circuit with a single X gate where the initial state is |0>. We can tell the final result by the equation: X|0> = |1>. It does not require an actual measurement to take place. This is of course not always the case.
When measuring a state like |+>, for example, we will take the state from |+> to either |0> or |1> with a 50% chance for each. This means we will have a pre-measurement state |+>, and a post measurement state that is |0> or |1>. Something has happened to the state, and we can not get back the old state. For example, if we have |0>, that could have been the measurement result of any qubit with a probability for |0> larger then 0.
We will learn the "real math" behind measuring in course C, because it requires some more math, but we can still work with it on a "conceptual level".
Partial measurement, product states
Partial measurement is when you measure a qubit that is part of a combined state. Lets say you have the Bell state. It is made out of two qubits. If you want to measure qubit 1 or 2, but not the other, you need to do a partial measurement.
This is often not hard, though. Lets say we have a two qubit product state:
The state ket-psi is the product of the two one-qubit states ket-psi-zero and ket-psi-one. The two qubit basis states are on this form, of course, but there are others as well. Lets look at this state:
We've encountered this state before, in the lecture about combining states. When we measure this state, |+> will be either |0> or |1>, so the post state can become either |0>0> or |1>0>, or in other words |00> and |10>.
If we have the state |+>|+>, or |++>, we could do the same thing. If we measure qubit 1, it will be either |0> or |1>, each with a 50% chance, so the post measurement state would be |0>|+> or |1>|+>. This is not a basis state, like the first one. We would have to measure qubit 2 as well. If we got |0>|+> from the first measurement, we would have |00> and |01> with a 50% chance for each, otherwise |10> and |11> with a 50% chance for each. The chance for getting |00> is therefore 0.5*0.5 = 0.25, so 25%.
Note that two events has to be independent for this to be true (for probabilities to be multiplied), but they are. Remember - this is the difference between entangled and product states. Also, it is easy to check that if we start by measuring qubit 2, then 1, we get the same outcomes with the same probabilities.
The independence criterion for non-entanglement is actually equivalent to the product state definition. We have dealt with this "intuitively", but will now make a more formal statement:
Theorem: If we have an N-qubit state, either both of these are true, or neither:
(2) The results from a partial measurement of any qubit in the state is independent of the result of a partial measurement of any other qubit in this state.
Partial measurement, entangled states
Sometimes we can't write a qubit state as a product, so we have to look at the entire state as "one big thing". But first, if we look again at the state |+>|0>, and write |+> in the computational basis:
We obviously still have a 50% chance of getting |00> and a 50% chance of getting |10>, so the same thing. If we have the Bell state, for example, we can use the same reasoning there. It is not a product state, but we can express it (like all states) in ket form.
In this case, if we measure qubit 1, there's a 50% chance we get |0> and a 50% chance we get |1>. Why? Because the only basis state with a |0> in the first term is |00>, and the probability for that is 50%. Same thing for |1>, and also - the same thing holds for measuring qubit 2.
We can generally write a qubit in the ket form, entangled or not, and determine the probabilities, and what the post partial-measurement state will be.
Partial measurement - a simple recipe
Enough discussion. How do we perform a partial measurement on an arbitrary state? This is a simple routine:
(1) Define the size of the state. What is the number of qubits in it? Call that number 'N'.
(1) Ask the question - what qubit am I measuring. It will be between 1 and N (inclusive). Call it 'k'.
(2) Ask the question - what state am I looking for? |0> or |1>.
(3) Lets say it's |0>, because the same thing goes for both: Find all terms with a 0 in the k'th place, and add the sum of squared amplitudes. That is the chance to measure |0> in the k'th qubit.
(4) Write out the post measurement state by taking the old state, removing all the terms that didn't have 0 in their k'th place, and re-normalize. You re-normalize by dividing all the remaining terms with their norm.
(5) If the probability for |0> is 0, i.e. there are no terms, the probability for |1> is 100%, so the post state is the pre-state, and the result we always get when measuring this qubit is |1>.
OK lets get to work. This is shown best by an example.
We have this three-qubit state:
Lets start by separating all basis states to make it easier to see what's going on:
Is this even a legal state? Lets take the sum of the squares to find out. It should be 1.
We will do both |0> and |1> for all three qubits, but you will see the second is fast because we can cheat, and the third is even faster.
First we take qubit 1.
(1) The size of the state is 3 qubits. N = 3.
(2) We choose qubit 1 first, so k = 1.
(3) We start with |0>. There is only one state with |0> in the first place, and that state is |011>. The probability for that is 0.25 (amplitude squared).
(4) The post measurement state is |011> with 100% chance, because to give one single term the norm 1 requires the coefficient to be 1. Technically we would get:
Now we take (3) with |1> instead.
The terms with |1> in 1'st place is |101> and |111>. The probability for this is the sum of the squares of their amplitudes, meaning:
The post state would be these two terms normalized, which would be:
Now we take qubit 2.
(1) N = 3, still.
(2) k = 2.
(3) The states with |0> in the second place is only 101. There is a 50% chance for that.
(4) The post measurement state would be |101>, and because it is only one term, the amplitude must be 1.
Now we do (3) for the state |1>. We will take a shortcut now. Since we know that |0> has a 50% chance, and the probailities sum to 1, we must have 50% chance for |1> as well.
For (4), we can cheat a little as well. Notice the amplitudes for |011> and |111> are both 0.5. This means in the post state, they will also be the same, since we only divide them with a constant. The only possible way for two amplitudes to be the same, given the normalization constraint, is of course this:
Now we take qubit 3.
N is still 3, for (1).
We take k = 3 for step (2)
For step (3), the terms with |0> in their third position is none! In other words, there is no chance we will measure the state |0> for the third qubit. Thus it can't happen, so the post measurement state does not exist, which means we don't have to try and find it by using the formula and normalization stuff.
It's equally easy for I1>. The chance for |0> is 0, meaning the chance for |1> is 1, and thus the post measurement state must be the same as the pre measurement state (since it does not change).
We will get more into measurement and the algebra of the amplitudes in multi qubit states in course C, but this is enough to understand how to do measurements using pen and paper, based on a given circuit and starting state.
The quantum teleportation protocol is similar to the superdense coding protocol in that it involves the Bell state, and an X and Z gate to do stuff to this state. It is more advanced though, as it requires measurements done within the circuit. In other words - Measuring is part of the mechanics of the circuit, and must be there in order for it to work. It's not like in the other cases where we measure only at the end to find out what the values are.
We will also encounter our first three-qubit circuit here. There will be many operations on it as well, so it's important to pay attention to the terms and their order, and be careful not to make mistakes. Also, we need to pay attention to what's going on to learn what is actually going on.
The circuit has three qubits in it - Q1 Q2 and Q3. We focus on the upper diagram (a).
We will designate the arbitrary state of Q1:
We want this to be equal to the final state. That is the point of the protocol.
Qubits Q2 and Q3 starts out in a combined state - the bell state:
Next we want to combine the states of Q1 and Q2, but since Q2 is in an entangled state with Q3, we will combine Q1 with both of those into a three-qubit state:
This expression can be simplified a bit, and should be. It's important to see that no matter what - we are dealing with two "groups" of kets, separated by the alpha and beta constants. Lets write it in this form instead:
Now we are going to apply a cNOT to the first two qubits. There are three qubits in each basis state now, but the cNOT only affects the first and second one, and will do nothing to the third one, so cNOT|100> = |110> and so forth. Same rules as always:
You may notice it only affected the kets in the beta part.
Now we need to apply a hadamard to Q1 - giving us no less then 8 kets to keep track of. We would replace all the first |0>'s and |1>'s with |+> and |-> respectively:
After a bit of algebra we get a fairly clean expression. The square root of two normalization term from the Hadamarded terms can be factored out and multiplied with the already existed one, so we end up with this:
Now, doing this for all four states would require a whole lot of work, so we are only going to do it for when both Q1 and Q2 is measured to be in the |0> states - thus triggering none of the X or Z gates. The principle is easy to apply for all four possible cases though. Lets start with qubit 1. We use the partial measurement recipe:
(1) State has 3 qubits, N = 3. (2) We are studying qubit 1, so k = 1. (3) We don't care about this. The algorithm only cares about if the measurement is |0> or |1> - not the chances for each. It would also be impossible to compute without knowing the values of alpha and beta. (4) We group all terms with |0> first and then normalize.
The number denoted N here is the normalization factor, and we have to pay special attention to it. By inspection, we see that it becomes (term by term):
It is assumed that the initial state of Q1 is a valid qubit state, so the sum of squares of alpha and beta is 1, thus:
We get this:
OK, now it's time to measure Q2:
(1) N still 3. (2) k = 2 (3) Going for |0>. Same thing as last time - the probability does not matter. (4) We organize all terms with |0> in the second state together, and remove the others, then renormalize. Note that we already measured once, so we need to use the post state from last time, not the state with 8 kets in it.
Normalization factor this time:
If we had tested for |1> in either the first or second measure, or both, we would have applied the X and/or Z gate to Q3, but we didn't do that, so we now have the final state. Behold:
Q3 is the qubit we want to get the prepared state of Q1, and as you can see - it has got that very same state.
The "key thing" to take away from the weird pre-measurement three-qubit state is that it is divided up into two groups of kets - one multiplied by alpha and one by beta. Each of these four qubit groups are in turn divided up into two groups. We essentially have a state like this:
Each letter is the sum of two kets. A is the two kets with |0> first, and B the ones with |1> first. Same for C and D, respectively. If the first measurement (of qubit 1) is |0>, it'll go with:
If it is |1>, we get:
It is then two possibilities for each of those, choosing one ket from A and one from C in the first place, or one from B and one from D in the second, to get the final state. This gets us four possible combinations in total. Each combination corresponds to a combination of applying the X and Z gates (both, only X, only Z, or neither).
Lecture 6 - Qubits and phases, complex amplitudes, the bloch sphereEdit
Amplitude and phase
We have mentioned that when measuring a qubit (in the standard computational basis), it will collapse into either |0> and |1>, depending on the probabilities for each. The qubit state |0> will collapse into |0> with 100% chance. The state H|0> will be 50/50. What about the state Z|1> = - |1> ?
The coefficient in question here is -1, and if we take the square of the absolute value of -1 we get 1, so it will be |1> with 100% chance.
What if we somehow ended up with the state Y|1> = i|1>. What would the measurement result be? Well, we would take the square of the absolute value of 'i' we get 1, so we get |1>.
Since we can't seem to distinguish these types of states from one another when measuring, what's the point of using them?
We have already answered that question in the superdense coding protocol, for example, where the use of these type of states can produce different measurement outcomes in the end. Now is a good time to start distinguishing between two properties of these coefficients - their amplitudes and their phase.
Amplitudes are the things that we see when measuring. Phase is things like sign changes. They can't be seen when measured, but can be used in algorithms to affect the measurements at the end. Also, saying that they can't be seen when measured is not completely right - it only applies when using certain bases (like the computational basis). If we measure in other bases we can detect phase.
Real coefficients and the unit circle
Before continuing on about phases and amplitudes we're gonna look at geometric shapes that can be used to visualize qubits.
We may think that this shape would require four real dimensions generally, since a qubit is a pair of complex numbers, and complex numbers are two dimensional. This is "sort of right", but if we are dealing only with qubits that has got real coefficients 'a' and 'b', we don't have to use two complex planes to represent the state, but the regular two dimensional real plane will do (a.k.a. just "the plane"), so lets start there.
We have a qubit state:
Even if 'a' and 'b' are only real values, we still have the normalization constraint:
This means all these qubit states can be found on the unit circle in the real plane. This in turn means we can express them only in terms of an angle:
Due to the trigonometric identity:
This means we have a good, compact way of representing these types of qubits - simply as an angle! If qubits only had real coefficients, they would essentially be one dimensional.
What about when 'a' and 'b' are complex. Can we still simplify them into one single value (an angle)? If not, can we extend the angle representation somehow to the general case? The answers are no, and yes. It turns out we can do it using two angles, but it takes a little bit of work.
Let us assume the numbers are complex, and let's call them 'z' and 'w'. We have the general state:
The normalization constraint means we have:
First thing to keep in mind here is that a complex number z with the modulus |z| = 1 can be expressed as a simple complex exponential corresponding to some angle (the argument of z):
The problem here is that 'z' and 'w' doesn't have to have modulus 1 - the only constraint is that the sum of the squares of their moduli must be 1.
If two complex numbers satisfy the normalization constraint, we can however re-write them as such:
'v' and 'u' are the complex numbers with the same arguments as z and w, respectively, but with |v| = |u| = 1.
NOTE: Keep in mind, the normalization constraint does not impose any restrictions on the arguments of the two complex numbers, only their moduli are affected. For example, if 'w' is 0, that means the square of the modulus of 'z' must be 1. This puts 'z' on the unit circle, but any number on the unit circle will do, i.e. 'z' can have any argument.
Clearly we have:
v and u has modulus 1, so they are complex exponentials:
Given this relationship, we can now express the qubit in the following way:
This involves three angles, but we will actually only need two. If the only thing separating two qubits is a global phase, they are for all intents and purposes the same. We talked about that in lecture 1. The reason is that during measurement, there is no way of distinguishing between the two. We can use this to cheat and divide by the second exponential term (actually multiply with the inverse in this case...):
Since this can be done for all qubits, the only thing separating one from another is the angle between the first and the second coefficient. We will call the difference of the angles ϕ (the relative phase), and use the relative phase to re-write the expression. We're also gonna use θ/2 for reasons that will be made clear in course C:
Now we want to express this as a geometric object. One way of doing it could be to expand the complex exponential into the trigonometric terms, and multiply everything out. The only thing that would give us though is a weird mixture of trigonometric terms, kets, and 'i'. It wouldn't be of much use.
A much better way is to use the Bloch sphere. The axes in the bloch sphere are not the real and imaginary axes, for example; it has its own set of axes. These axes are actually eigenvectors of the X, Y and Z matrices, and we will get more into that later. What the Bloch sphere does is to map all possible qubit states onto its surface. If you have a valid qubit state, it can be found as a point on the surface of the Bloch sphere. The sphere is of radius 1, and points on the sphere can be expressed in terms of the theta and phi angles. Finally, this only applies to something called "pure states". There is something called mixed states as well, which you get when grouping a bunch of states together with certain probabilities. We don't deal with those, but they are important, and it could be interesting to know that mixed states can be expressed as points inside this sphere. The "Bloch vector" of these qubit does not have length 1.Back to phases and amplitudes
We can tie amplitudes and phases to this expression. Amplitudes are the absolute values of the coefficients. The absolute value of the phase factor is always 1, so the amplitudes are completely determined by the cos and sin factors. Those are real, and can therefore not affect the phase., which means the phase is fully determined by the exponential term. Keep in mind - we only care about relative phase, because states that only differ by a global phase are equivalent.
As an example of amplitudes and phase, the state H|0>, or |+>, would correspond to the two angles:
Notice we get the correct amplitudes, and the phase factor becomes 1. You also need to keep in mind that we use theta/2 in the equation.
The phase term is what creates all the sign changes etc. Lets take the -|1> state. We have this equation:
This means that the state -|1> corresponds to the two angles:
There are 28,5 points in total. 15 is needed to pass. Good luck.
In course A we talked about qubits as being pairs of probabilities (p0,p1), where p0 is the probability that the qubit collapses into the |0> state, and p1 the probability it collapses into |1>.
a) When expressing a qubit on the form |v> = a|0> + b|0>, if we have the probabilities (20,80), give two possible values for 'a' and 'b'. (1p)
b) Are there more then one combination of 'a' and 'b' that would give the (20,80) probabilities? (1p)
c) How does the normalization constraint tie in with these probabilities? What does it ensure? (1p)
a) Express the |+> and |-> vectors in terms of the computational basis. (2p)
Express the following vectors in the computational basis:
a) The vector form for |0> is (1,0), and |1> is (0,1). Put those in column matrix form and calculate the following vectors:
Y|0>, Y|1>, Y(a|0> + b|1>)
The result should be in the form of column matrices.
b) Express the three vectors calculated in (a) in ket form. (1,5p)
c) Calculate |v> = X|0>, then |u> = X|v>. What is |u>? The answer should be in ket form? (1p)
The chain of equations in (2c) would be the result of having two X (NOT) gates in a row, then passing a qubit in the |0> state through them:
|0> -----X-----X-----> |u>
Algebraically, we could instead calculate the new state |u> like this:
|u> = X|v> = X(X|0>) = (XX)|0>
XX is the product of the matrix X with itself. This means that instead of applying the first gate to |0>, update the state, then apply the second gate on the updated state, we can just multiply the gate matrices together, then apply their product to the original state |0> directly.
For the new equations to work, what would XX has to be? What is XX? (1p)
Compute the following vectors and answer in ket form, and in the computational basis (|0> and |1>):
a) X|+> (1p)
b) Z|-> (1p)
c) H|-> (1p)
d*) The hadamard matrix can be expressed in the following way:
We know that ZZ = I and XX = I. We also claimed that HH = I. If you write HH = I using the sum expression for H, you will find that a certain relation between X and Z must be true. Which relation is that? Verify that it is in fact so.
e**) What is the relation between X and Z in (d) called in mathematical language? Does it hold for matrices in general?
Express the following states using the two-qubit bases: |00>,|01>,|10>,|11>
a) |1>|+> (1p)
b) |->|0> (1p)
c) |+>|+> (1p)
Express the following states using the eight three-qubit bases: |000>, |001>, |010>, |011>, |100>, |101>, |110>, |111>
a) |0>|+>|1> (1p)
b) |10>|-> (1p)
c) |->|->|-> (1p)
Calculate the following states:
a) (X|1>)|0> (1p)
b) |1>(X|0>) (1p)
c) (X|1>)(X|0>) (1p)
d) cNOT|01> (1p)
e) cNOT((X|1>)|1>) (1p)
f) cNOT (-|11>) (1p)
g) cNOT (cNOT |10>) (1p)
Lectures 5 and 6 are tough, so the test is light. You really only need to get a feel for entanglement and partial measurement to be able to move on.
There is 18 points in total, and you need 9 to pass.
Is the state entangled or not? (HINT: Try writing it as a product.)
a) Show how to generate the Bell state from |00> by using the Hadamard and cNOT gates. Use kets. (1p)
b) Start with a bell state, then show the superdense coding math for when Alice uses only the X gate. (2p)
You will be doing partial measurements on this state:
a) What is the chance of measuring qubit 1 in the |0> state? What would the post state be? (1p)
b) Same thing for qubit 1 and |1>? (1p)
c) What is the chance of measuring qubit 2 in the |1> state? What would the post state be? (1p)
d) Same thing for qubit 2 and |0>? (1p)
e) Is this an entangled state? (0,5p)
You will be doing partial measurements on this state:
a) What is the chance of measuring qubit 1 in the |0> state? What would the post state be? (1p)
b) Same thing for qubit 1 and |1>? (1p)
c) What is the chance of measuring qubit 2 in the |1> state? What would the post state be? (1p)
d) Same thing for qubit 2 and |0>? (1p)
e) Is this an entangled state? (0,5p)