This is the third course. The focus here will be computation. We will learn how to work with quantum gates and qubits in a more proper way then we have done thus far (throwing kets around).
This course lays the mathematical foundation for course D, in which we will finish Nielsen's video lectures and "wrap things up". Hopefully, at that point you will know enough quantum computing basics and math to be able to read and understand a real book on quantum computing (Nielsen's book, for example), should you want to take things further.
There is not much to say about this course. It's computation from start to finish.
Lecture 1 - The tensor productEdit
When we write things like this |0>|1>, or |01> (which is the same thing), we are combining two kets. What does this really mean? It means we take a certain type of product of the two. The product is called the tensor product. We will now learn how to do tensor multiplication formally, and look at some of its properties.
The tensor product can be applied to matrices and vectors alike. It can even be applied to scalars. The tensor product of two matrices A and B is written:
The ket notation |01> is just a simple way of expressing the tensor product of |0> and |1>.
Tensor product rules
The tensor product is associative, meaning we can do this:
The tensor product distributes over addition. So we can do this, for example:
Like the regular matrix product it is not commutative, however, so we generally have:
This is the reason why |01> and |10> are different vectors.
Tensor product computation
We will explain all tensor product rules by learning how to compute the tensor product of two matrices. These rules can be used for both matrices and vectors, and even scalars.
Take two matrices A and B.
1) The height of the tensor product will be the height of A multiplied with the height of B, and the width of the product will be the width of A multiplied with the width of B.
Lets say A is a 2x3 matrix, and B is a 5x1 matrix. The product would be a (2*5)x(3*1) = 10x3 matrix.
Lets say we have |0> and |1>. These are both 2 dimensional (column) vectors, so 2x1 matrices. The tensor product would be a (2*2)x(1*1) = 4x1 matrix, or in other words a 4 element vector.
2) The resulting matrix will be a series of copies of the right matrix (B), multiplied by the elements of A, in the following way - let:
When expanding B we get a 4x4 matrix:
This video shows examples on how to calculate tensor products.
Ket and gate combinations
We will now evaluate a simple quantum circuit in two different ways - first by running the qubits separately, then by combining their states and the gates. This illustrates how great braket notation really is.
The circuit we want to evaluate is this:
|1>---Z---> (qubit 2)
|0>---X---> (qubit 1)
We have qubit 1 in the |0> state, and qubit 2 in the |1> state, and we run them through an X and a Z gate respectively. What would the final states be?
The column vector forms would be:
We can also do this by combining the states.
We then form a two-qubit multigate by tensoring X and Z:
We then multiply the matrix with the state to get the final state:
Note that the final state can be written as the tensor product of the end results above:
This means we got the same result, but as a tensor product. You often end up with a composite state like this, which means you have to break out individual qubits before you can read their values. It is sometimes not possible to separate two qubit states, for example when the states are entangled, but you can always break a qubit state out if you measure it first.
Simplification using kets and product rules
We could have evaluated the circuit much easier by using kets. It would have required a product rule though. When combining matrix multiplication and tensor multiplication, the following rule holds:
Using this rule, we could have done this instead:
The last expression can be rewritten:
A scalar can be seen as a 1x1 matrix, so we can use tensor products on those as well. The number 4 would be a 1x1 matrix with the only element being 4.
Taking the tensor product of constant multiples of matrices or vectors follows the same rules:
The tensor product of a scalar and another scalar would be a 1x1 matrix with the only element being the product of the two scalars, so it turns out to be regular scalar multiplication.
Remember the probability rule? If we have a 50% chance of qubit A being |0> and a 50% chance of qubit B being |0>, the chance of both being |0> is 25%? We can derive that result using the tensor product rules.
Apply the distributive rule for addition:
Apply the tensor-matrix multiplication rule:
Apply the scalar multiplication rule:
Probabilities are multiplied.
Lecture 2 - Inner and outer productsEdit
The inner product and norms
In real linear algebra there is something called the "dot product". If we have two 2D vectors:
We calculate the dot product as such:
In the general case, if we have to N-dimensional vectors:
The dot product is:
We can use this product to define a norm:
That is the regular norm in euclidian N-dimensional space. If we take the vector (1,1), the length of that vector is . If we do the definition we get:
The absolute value of a real number can be written:
This means we can re-write the norm as such:
This emphasizes the fact that we're dealing with real distances. The norm is really just a generalization of the Pythagorean theorem to N-dimensional space.
What about in complex space? Lets say we have the same situation where the coefficients are complex, can we make a norm and a dot product as well? The answer is yes.
The dot product, or inner product of two vectors with complex entries are defined as such:
In this equation, * means the complex conjugate:
The norm is defined in the same way as in real space.
If we have a complex number, the absolute value (or modulus) of that number can be expressed:
For 1-dimensional vectors, the norm would be the absolute value of the coefficient. When there are more dimensions, we get the general expression:
It's a natural generalization of the norm of real vectors. Qubits (and their tensor products) live in N-dimensional complex space. Sometimes these (and similar) spaces are referred to as Hilbert spaces. What Hilbert space means in this context is basically this:
Hilbert space is a vector space of any dimension (including infinite) over the field of complex numbers, coupled with an inner product.
Finally, we can re-define the qubit normalization constraint using the norm:
The outer product
In the lecture 1 video on tensor products, we calculated the tensor product of the row and column vector representation of the same ket. For |0> it was done in the following manner:
This is a useful matrix. It happens to define a projection onto the basis state |0>. To give an example of this, consider an arbitrary qubit state:
Now multiply the ket-0 matrix with the vector.
What we got from multiplying the state with the |0> matrix was to give us only the |0> part of the vector.
For |1>, we have the following corresponding matrix:
If we do the same thing, we get:
Same thing there. We get the coefficient corresponding to |1> when using the |1> projection matrix.
This can be used for many things. For example, it's part of the mathematical model of measurement. Remember that alpha and beta are both probability amplitudes, so if we can separate them from a general state we can find out the probability of measuring a qubit in a certain state. More on this in the segment about measuring.
Bra and Ket
With each 'ket' comes something called a 'bra'. Take |0> as an example. The corresponding 'bra' would be written <0|. In order to explain what the bra is, we first need to solidify what a ket is:
A ket is always a column vector.
The term |0> always refer to the column vector form. it is never on the row vector format. Sometimes it's written (1,0) in running text, but it always refer to the column vector. Consider the expression X|0>. The X matrix multiplied with |0>. That would not be legal unless |0> represents a column matrix.
The bra is the row matrix form of the ket, but with each element being the complex conjugate of the corresponding element of the ket.
More formally, if we define a ket as such:
The corresponding bra would be:
Another way of defining it would be:
Because taking the complex conjugate twice is the same as doing nothing, we also get:
This turns out to be an extremely useful vector. Take the normal matrix product of the bra and ket, for example. It turns out to be the inner product:
We normally remove one of the bars as part of the notation:
This would also be equal to the inner product, so we use the same notation for the inner product:
The norm of a qubit state could now be expressed in this better looking form:
Since the square of 1 is 1, we can now update the normalization constraint to this:
It is also legal to take the inner product of two different vectors, provided they are of the same dimensions. The result could be different depending on which vector is in the ket form, and which vector is in the bra form. In other words:
Notice that since the 'bra' is a row vector, this would be a legal expression:
It would correspond to this:
Bra and Ket in outer product notation
One thing to keep in mind now is that despite adding the bra, we still consider the expression |0>|0> to be the tensor product of |0> with itself. Only in the case of bras do we mean matrix multiplication. <0|0> means matrix multiplication, |0>|0> means tensor product.
Now, if we consider the fact that the complex conjugate of a real number is the same:
we see that the tensor products of |0> and |1> in the outer product section could have been written like this instead:
The tensor product sign is often omitted in braket notation:
Unitary matrices and braketsEdit
In course B we talked loosly about unitary matrices. We're now going to formalize that a bit more.
Definition: A square matrix is called unitary if the following relation holds: , where * means the conjugate transpose.
We will first look at one of the most important properties of unitary matrices.
If a vector is acted upon by a linear operator O(|v>) = U|v>, where U is a unitary matrix, then we have:
We will prove this using kets. If we look at the definition of the conjugate transpose, we may notice that one way of defining a 'bra' is as the conjgate transpose of the corresponding 'ket' - and vice versa. The 'bra' will be a 1x2 matrix whos elements are the complex conjugates of the elements in a 2x1 matrix (the 'ket').
For the conjugate transpose, we have:
It works exactly like the transpose, in other words.
To get the norm of a ket, we have seen that we can take the matrix product of it and its 'bra' in the following way:
This can be used for matrix multiples of kets as well, using the standard matrix rules. If we have the vector , we can get the norm of that vector by matrix multiplying with its 'bra'. The 'bra' would be:
The norm becomes:
The thing to take away here is that by applying a quantum gate to a valid qubit state, we get a new valid qubit state, because all quantum gates are unitary matrices.
Unitary matrices and inverses
Unitary matrices has an inverse by definition. An inverse has the following properties: , and so has the conjugate transpose for a unitary matrix. We could put this in other terms:
If U is a unitary matrix, then we have:
This means that all unitary matrices represents reversible operations. All quantum gates can be reversed. To reverse it, just find the gate that corresponds to the conjugate transpose of the gate matrix and apply it. This can of course be tricky in practice, but in theory it is always possible.
Unitary matrices and orthogonal bases
If we look at the relation , we can find another important property of unitary matrices. Remember that * means conjugate transpose. If we only concern ourselves with N-dimensional Euclidian (real) space, with its standard norm and dot-product, * would mean transpose, so the equation becomes: . Now let us look at matrix multiplication. To get an element in the product C = AB, we calculate the dot product of row i of A, and column j of B. . If we have the relation that means the columns of B are the rows of A, so we get: .
Now, since the product is , we see that when . These are the entries on the main diagonal of C. In all other cases, . We can express this in one single equation using the Kronecker delta: .
What does this tell us? It tells us that the dot product of a row vector and itself is 1, and hence also the norm. . This means all row vectors are normal. It also means that the dot product of any row vector with another row vector is 0, which means they are orthogonal. Apparently, the following statement holds:
The row vectors of a unitary matrix forms an orthonormal basis of N-dimensional Euclidian space, where dim(U) = NxN.
Due to the nature of the transpose, it is easy to see that this holds for the column vectors as well. The set of column vectors of a unitary matrix forms an orthonormal basis of N-dimensional real space.
It is easy to check that this holds for complex vector spaces as well, using the regular inner product.
Unitary matrices and multi-gates
When we build circuits, we often have to combine gates by using matrix and tensor products. What are the rules concerning matrix- and tensor-products of unitary matrices?
Theorem: If U and V are two unitary matrices, then UV is unitary.
We prove this by showing that .
Theorem: The tensor product of two dimensional unitary matrices is an unitary matrix.
To prove this, we recall that unitary matrices are square matrices. If U has dimension NxN and V MxM. We need to show that , meaning their product is the identity matrix with the proper dimensions. First we need a small support statement, or "lemma":
Lemma: For any two matrices A and B, we have:
The lemma is trivial and does not need to be proved here. We will simply combine it with the tensor/matrix product rule to prove the theorem:
These results show that unitary matrices can be matrix multiplied and tensor multiplied without loosing the property of being unitary. This is not true for addition though. We can check that the sum of two unitaries, U + U = 2U, is not unitary - because it will scale the norm of any vector by a factor of 4:
In this section we will learn a simple procedure for measuring qubits using matrices and tensor products. This is how it's normally done, and how it's done in the mod code.
You may want to review lecture 5 of course B before reading this, or at least the part concerning partial measurements. That section contains a procedure for measuring qubits based on ket algebra. We will create a similar step-by-step procedure here.
Let us start with a single qubit state:
Now we evaluate this expression for j = 0 and 1:
Note that we have:
For 0, we get:
What we are left with is the probability amplitude for |0>. Now we do the same thing for |1>:
This gives the probability amplitude for |1>. Generally we have this:
Let be an orthonormal basis of 2-dimensional Hilbert space. The probability of getting when measuring a state is equal to:
Here, , j = 0 or 1.
The state after measuring is:
We have the state
We measure in the computational basis. What is the probability of measuring ?
We apply the formula:
If we have a multi-qubit state we can still apply the formula, but we have to "pad" the measurement operators with identity matrices.
Let's say we have an N qubit state . It will be made up of qubits 0, 1, 2, ... , N - 1. If we want to measure the probability of qubit k (0 <= k < N) having state , we will do this:
1) Create the measurement operator:
The M-operator should be in spot k, and the total number of terms should be N.
2) Apply the formula:
3) The post-measurement state will be:
We have the two-qubit state:
We want to calculate the chance that qubit 0 is measured in the 1 state.
We start by creating the measurement operator:
We do the p(j,k) calculation:
There is a 50% chance the first qubit is in the |0> state. If we measure it in this state, the post state will be:
The test-state is actually the matrix version of (H|0>)|0>, which explains why the first qubit is |0> with a 50% chance. If we measure the first qubit in the |0> state, the post measuring state will be |0>|0>.
The measurement operators has a few important properties. We've seen a few simple algebraic properties of |0><0| and |1><1| in the previous sections, but there are others. For example, they abide by the following rule:
We test this for the computational basis:
Let us also test this for the +/- basis:
At this point we can combine gates and qubits any way we like, and also measure them. This is essentially all we need to create a basic quantum computer simulator.
Course D deals with a few remaining subjects, such as the role of eigenvalues and eigenvectors, and a few important general laws of quantum computing theory and quantum mechanics that we have not yet touched upon.