text:
18 Pages

## Course InformationEdit

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).

## PrerequisitesEdit

Course Block A.

You also need to know linear algebra and the basics of complex numbers. There are links to resources nearby.

## IntroductionEdit

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.

Qubits extended

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:

$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$

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:

$(1,0) \cdot (0,1) = 1 \cdot 0 + 0 \cdot 1 = 0$

|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:

$|\alpha|^2 + |\beta|^2 = 1$

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.

Basic algebra

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).

$\alpha = \beta = \frac{1}{\sqrt 2}$

Thus, the state can be written:

$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle = \frac{1}{\sqrt 2}|0\rangle + \frac{1}{\sqrt 2}|1\rangle$

Normally we break the constant out:

$|\psi\rangle = \frac{1}{\sqrt 2}|0\rangle + \frac{1}{\sqrt 2}|1\rangle = \frac{1}{\sqrt 2}\left(|0\rangle + |1\rangle\right) = \frac{|0\rangle + |1\rangle}{\sqrt 2}$

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:

$|\psi_0\rangle = \gamma|\psi_0\rangle$

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:

$|\psi_0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt 2}$

Now take this state:

$|\psi_1\rangle = \frac{-|0\rangle - |1\rangle}{\sqrt 2}$

We could re-write the second state like this:

$|\psi_1> = (-1)\frac{(|0\rangle + |1\rangle)}{\sqrt 2} = (-1)|\psi_0\rangle$

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:

$|\alpha|^2 + |\beta|^2 = 1$

For a constant multiple, we get this:

$|\gamma\alpha|^2 + |\gamma\beta|^2 = 1$

$|\gamma|^2|\alpha|^2 + |\gamma|^2|\beta|^2 = 1$

$|\gamma|^2(|\alpha|^2 + |\beta|^2) = 1$

$|\gamma|^2 = 1$

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:

$|\psi_0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt 2}$

$|\psi_1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt 2}$

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:

$|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt 2}$

$|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt 2}$

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.

$|\psi\rangle = \alpha|+\rangle + \beta|-\rangle$

What if I want to express this in the computational basis instead? I could do that, using the normal vector rules.

$|\psi\rangle = \alpha|+\rangle + \beta|-\rangle = \alpha\left(\frac{|0\rangle + |1\rangle}{\sqrt 2}\right) + \beta\left(\frac{|0\rangle - |1\rangle}{\sqrt 2}\right) = \frac{1}{\sqrt 2}\left(\alpha|0\rangle + \alpha|1\rangle + \beta|0\rangle - \beta|1\rangle \right)$

If we re-organize the terms, we get this expression on the normal computational basis form:

$\frac{1}{\sqrt 2}\left(\alpha|0\rangle + \alpha|1\rangle + \beta|0\rangle - \beta|1\rangle \right) = \left(\frac{\alpha + \beta}{\sqrt 2}\right)|0\rangle + \left(\frac{\alpha - \beta}{\sqrt 2}\right)|1\rangle$

As long as these two terms satisfy the normalization constraint, we have a legal qubit state. An example would be if we have this:

$\alpha = \beta = \frac{1}{\sqrt 2}$

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.

Conclusion

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:

$X|0\rangle = |1\rangle$

$X|1\rangle = |0\rangle$

The Hadamard is slightly more complex. It acts on the basis states in the following way:

$H|0\rangle = \frac{(|0\rangle + |1\rangle)} {\sqrt 2}$

$H|1\rangle = \frac{(|0\rangle - |1\rangle)} {\sqrt 2}$

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:

$MM^* = I$

The conjugate transpose is the complex analogy of the real transpose. For real matrices, we would require:

$MM^T = I$

The difference between the conjugate transpose and the regular transpose is that we don't have the element-by-element relation $b_{ij} = a_{ji}$, but instead $b_{ij} = (a_{ji})^*$, 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.

Matrix notation

Qubits and gates can be expressed using vectors and matrices. The vectors |0> and |1> has the following representations:

$|0\rangle = (1,0) = \left[\begin{matrix} 1 \\ 0 \end{matrix}\right]$

$|1\rangle = (0,1) = \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]$

An arbitrary qubit state can be written as a linear combination of |0> and |1>:

$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle = (\alpha,\beta) = \left[\begin{matrix} \alpha \\ \beta \end{matrix}\right]$

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:

$X = \left[\begin{matrix} 0 & 1\\ 1 & 0 \end{matrix}\right]$

Applying this to |0> would be multiplying X with |0>:

$X|0\rangle = \left[\begin{matrix} 0 & 1\\ 1 & 0 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] = |1\rangle$

Single qubit gates and ket algebra

These are the matrix representations for X, Y, Z and the Hadamard

$X = \left[\begin{matrix} 0 & 1\\ 1 & 0 \end{matrix}\right], Y = \left[\begin{matrix} 0 & -i \\ i & 0 \end{matrix}\right], Z = \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right], H = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right]$

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>.

$Z|0\rangle = \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = |0\rangle$

$Z|1\rangle = \left[\begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix}\right] \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] = \left[\begin{matrix} 0 \\ -1 \end{matrix}\right] = -\left[\begin{matrix} 0 \\ 1 \end{matrix}\right] = -|1\rangle$

Now we can figure out the effect of the Z gate on a general qubit state. Remember, gates act linearly, so we get:

$Z|\psi\rangle = Z(\alpha|0\rangle + \beta|1\rangle) = \alpha(Z|0\rangle) + \beta(Z|1\rangle) = \alpha|0\rangle - \beta|1\rangle$

Lets do the same for H|0> and H|1>, to derive the expressions we saw earlier in this section.

$H|0\rangle = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 \\ 1 \end{matrix}\right] = \frac{1}{\sqrt 2} \left( \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] + \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\right) = \frac{|0\rangle + |1\rangle}{\sqrt 2}$

$H|1\rangle = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right] \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 \\ -1 \end{matrix}\right] = \frac{1}{\sqrt 2} \left( \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] - \left[\begin{matrix} 0 \\ 1 \end{matrix}\right]\right) = \frac{|0\rangle - |1\rangle}{\sqrt 2}$

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.

$H|+\rangle= \frac{1}{\sqrt 2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right] \frac{1}{\sqrt 2} \left[\begin{matrix} 1 \\ 1 \end{matrix}\right] = \frac{1}{2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right] \left[\begin{matrix} 1 \\ 1 \end{matrix}\right] = \frac{1}{2} \left[\begin{matrix} 2 \\ 0 \end{matrix}\right] = \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = |0\rangle$

$H|-\rangle = \frac{1}{\sqrt 2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right] \frac{1}{\sqrt 2} \left[\begin{matrix} 1 \\ -1 \end{matrix}\right] = \frac{1}{2} \left[\begin{matrix} 1 & 1\\ 1 & -1 \end{matrix}\right] \left[\begin{matrix} 1 \\ -1 \end{matrix}\right] = \frac{1}{2} \left[\begin{matrix} 0 \\ 2 \end{matrix}\right] = \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] = |1\rangle$

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.

$X|+\rangle = X\left(\frac{|0\rangle + |1\rangle} {\sqrt 2}\right) = \frac{X|0\rangle + X|1\rangle} {\sqrt 2} = \frac{|1\rangle + |0\rangle} {\sqrt 2} = \frac{|0\rangle + |1\rangle} {\sqrt 2} = |+\rangle$

Notice in the two equations right before the last |+> we just change the order of the terms.

We can also show that X|-> = -|->:

$X|-\rangle = X\left(\frac{|0\rangle - |1\rangle} {\sqrt 2}\right) = \frac{X|0\rangle - X|1\rangle} {\sqrt 2} = \frac{|1\rangle - |0\rangle} {\sqrt 2}$

The last state can be rewritten:

$\frac{|1\rangle - |0\rangle} {\sqrt 2} = -\left(\frac{-|1\rangle + |0\rangle} {\sqrt 2}\right) = -\left(\frac{|0\rangle - |1\rangle} {\sqrt 2}\right) = -|-\rangle$

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 |->

$Z|+\rangle = Z\left(\frac{|0\rangle + |1\rangle} {\sqrt 2}\right) = \frac{Z|0\rangle + Z|1\rangle} {\sqrt 2} = \frac{|0\rangle - |1\rangle} {\sqrt 2} = |-\rangle$

$Z|-\rangle = Z\left(\frac{|0\rangle - |1\rangle} {\sqrt 2}\right) = \frac{Z|0\rangle - Z|1\rangle} {\sqrt 2} = \frac{|0\rangle + |1\rangle} {\sqrt 2} = |+\rangle$

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.

Gate substitution

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.

|v> ---H---X---H--->

That circuit would then be equivalent to the circuit:

|v> ---Z---->

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

Combined states

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:

$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$

Given that we know what the basis vectors are, we can also express this simply as:

$|\psi\rangle = \left[\begin{matrix} \alpha \\ \beta \end{matrix}\right]$

A general two-qubit state can be expressed as the linear combination of the four basis states |00>, |01>, |10>, |11>:

$|\psi\rangle = \alpha |00\rangle + \beta |01\rangle + \gamma |10\rangle + \delta|11\rangle$

We can also write this simply as:

$|\psi\rangle = \left[\begin{matrix} \alpha \\ \beta \\ \gamma \\ \delta \end{matrix}\right]$

The column matrix forms of each of the two-qubit basis states would be:

$|00\rangle = \left[\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ \end{matrix}\right], |01\rangle = \left[\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \\ \end{matrix}\right], |10\rangle = \left[\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ \end{matrix}\right], |11\rangle = \left[\begin{matrix} 0 \\ 0 \\ 0 \\ 1 \\ \end{matrix}\right]$

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:

$|a|^2 + |b|^2 = 1$

$|c|^2 + |d|^2 = 1$

For the 2-qubit state to be normal, we would require:

$|ac|^2 + |ad|^2 + |bc|^2 + |bd|^2 = 1$

We can re-write the left side:

$|ac|^2 + |ad|^2 + |bc|^2 + |bd|^2 = |a|^2|c|^2 + |a|^2|d|^2 + |b|^2|c|^2 + |b|^2|d|^2 = (|a|^2 + |b|^2)(|c|^2 + |d|^2)$

Using the fact that qubits A and B are normal, we get this:

$(|a|^2 + |b|^2)(|c|^2 + |d|^2) = 1 \cdot 1 = 1$

Algebra

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 |+>:

$|0\rangle\left(\frac{|0\rangle + |1\rangle}{\sqrt 2}\right) = \frac{|0\rangle|0\rangle + |0\rangle|1\rangle}{\sqrt 2} = \frac{|00\rangle + |01\rangle}{\sqrt 2}$

We could also end up having to combine |+> with |0> (note the difference), giving us:

$\left(\frac{|0\rangle + |1\rangle}{\sqrt 2}\right)|0\rangle = \frac{|0\rangle|0\rangle + |1\rangle|0\rangle}{\sqrt 2} = \frac{|00\rangle + |10\rangle}{\sqrt 2}$

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:

$|0\rangle + |1\rangle$

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:

$X(|0\rangle + |1\rangle) = X|0\rangle + X|1\rangle = |1\rangle + |0\rangle$

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?

$|00\rangle + |11\rangle$

We could first re-write it to make things more clear.

$|00\rangle + |11\rangle = |0\rangle|0\rangle + |1\rangle|1\rangle$

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:

$X(|00\rangle + |11\rangle) = X(|0\rangle|0\rangle + |1\rangle|1\rangle) = X(|0\rangle|0\rangle) + X(|1\rangle|1\rangle)$

now we use the fact that we apply this to the first qubit...

$X(|0\rangle|0\rangle) + X(|1\rangle|1\rangle) = (X|0\rangle)|0\rangle + (X|1\rangle)|1\rangle = |1\rangle|0\rangle + |0\rangle|1\rangle = |10\rangle + |01\rangle($

If we applied the NOT to the second qubit, the last part would change to this:

$X(|0\rangle|0\rangle) + X(|1\rangle|1\rangle) = |0\rangle(X|0\rangle) + |1\rangle(X|1\rangle) = |0\rangle|1\rangle + |1\rangle|0\rangle = |01\rangle + |10\rangle($

We can also illustrate this in another way. Lets take two qubits in the |0> + |1> state, and combine them. We would get this:

$(|0\rangle + |1\rangle)(|0\rangle + |1\rangle) = |0\rangle|0\rangle + |0\rangle|1\rangle + |1\rangle|0\rangle + |1\rangle|1\rangle = |00\rangle + |01\rangle + |10\rangle + |11\rangle$

Applying a not gate on the first qubit would be the same as doing this:

$(X(|0\rangle + |1\rangle))(|0\rangle + |1\rangle) = (X|0\rangle + X|1\rangle)(|0\rangle + |1\rangle) = (|1\rangle + |0\rangle)(|0\rangle + |1\rangle)$

If we expand this, we see that only the first qubit has been affected:

$(|1\rangle + |0\rangle)(|0\rangle + |1\rangle) = |1\rangle|0\rangle + |1\rangle|1\rangle + |0\rangle|0\rangle + |0\rangle|1\rangle = |10\rangle + |11\rangle + |00\rangle + |01\rangle$

The controlled NOT

The controlled NOT-acts in the following way on the basis states:

$cNOT \cdot |00\rangle = |00\rangle$

$cNOT \cdot |01\rangle = |10\rangle$

$cNOT \cdot |10\rangle = |11\rangle$

$cNOT \cdot |11\rangle = |10\rangle$

A general two qubit state could be expressed as such:

$|\psi\rangle = \alpha |00\rangle + \beta |01\rangle + \gamma |10\rangle + \delta|11\rangle$

Since gates acts linearly on qubit states, we can calculate the result of applying the cNOT to an arbitrary 2-qubit quantum state:

$cNOT \cdot |\psi\rangle = \alpha |00\rangle + \beta |01\rangle + \delta |10\rangle + \gamma|11\rangle$

Matrix forms

The cNOT has a matrix representation as well:

$cNOT = \left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}\right]$

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:

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle} {\sqrt 2}$

The column vector form would be:

$|\Phi^+\rangle = \frac{1} {\sqrt 2} \left[\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}\right]$

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:

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle} {\sqrt 2} = \frac{1} {\sqrt 2} \left[\begin{matrix} 1 \\ 0 \\ 0 \\ 1 \end{matrix}\right]$

$|\Phi^-\rangle = \frac{|00\rangle - |11\rangle} {\sqrt 2} = \frac{1} {\sqrt 2} \left[\begin{matrix} 1 \\ 0 \\ 0 \\ -1 \end{matrix}\right]$

$|\Psi^+\rangle = \frac{|01\rangle + |10\rangle} {\sqrt 2} = \frac{1} {\sqrt 2} \left[\begin{matrix} 0 \\ 1 \\ 1 \\ 0 \end{matrix}\right]$

$|\Psi^-\rangle = \frac{|01\rangle - |10\rangle} {\sqrt 2} = \frac{1} {\sqrt 2} \left[\begin{matrix} 0 \\ 1 \\ -1 \\ 0 \end{matrix}\right]$

We are going to show how these are generated in the next section.

Superdense coding

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:

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle} {\sqrt 2}$

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:

$(H|0\rangle)|0\rangle = \left(\frac{|0\rangle + |1\rangle} {\sqrt 2}\right)|0\rangle = \frac{|00\rangle + |10\rangle} {\sqrt 2}$

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:

$cNOT |00\rangle = |00\rangle$

$cNOT |10\rangle = |11\rangle$

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:

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle} {\sqrt 2}$

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:

$Z|0\rangle = |0\rangle, Z|1\rangle = -|1\rangle$

Applying the Z-gate locally to the first qubit will change the combined state into this:

$\frac{(Z|0\rangle)|0\rangle + (Z|1\rangle)|1\rangle} {\sqrt 2} = \frac{|00\rangle - |11\rangle} {\sqrt 2}$

When bob gets it, he applies a cNOT:

$cNOT \frac{|00\rangle - |11\rangle} {\sqrt 2} = \frac{|00\rangle - |10\rangle} {\sqrt 2}$

Now, in order to finish this calculation we have to factor the two individual qubit states out. We can do it like this:

$\frac{|00\rangle - |10\rangle} {\sqrt 2} = \left(\frac{|0\rangle - |1\rangle} {\sqrt 2}\right)|0\rangle = (H|1\rangle)|0\rangle$

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:

$(HH|1\rangle)|0\rangle = |1\rangle|0\rangle$

## Lecture 5 - Measurement and quantum teleportationEdit

Watch list: 16,18,19 (17 optional)

Measurement

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:

$|\psi\rangle = |\psi_0\rangle|\psi_1\rangle$

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:

$|\psi\rangle = |+\rangle|0\rangle$

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:

(1) $|\psi\rangle = |\psi_0\rangle|\psi_1\rangle \ldots |\psi_N\rangle$

(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:

$|\psi\rangle = |+\rangle|0\rangle = \left(\frac{|0\rangle + |1\rangle}{\sqrt 2}\right)|0\rangle = \frac{|00\rangle + |10\rangle}{\sqrt 2}$

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.

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle} {\sqrt 2}$

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.

$|\psi_{post}\rangle = \frac{|\psi_{post}\rangle}{\||\psi_{post}\rangle\|}$

(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>.

Example

OK lets get to work. This is shown best by an example.

We have this three-qubit state:

$|\psi\rangle = \frac{|101\rangle}{\sqrt 2} + \frac{|011\rangle + 111\rangle}{2}$

Lets start by separating all basis states to make it easier to see what's going on:

$|\psi\rangle = \frac{|101\rangle}{\sqrt 2} + \frac{|011\rangle + 111\rangle}{2} = \frac{|101\rangle}{\sqrt 2} + \frac{|011\rangle}{2} + \frac{111\rangle}{2}$

Is this even a legal state? Lets take the sum of the squares to find out. It should be 1.

$\left(\frac{1}{\sqrt 2}\right)^2 + \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 = \frac{1}{2} + \frac{1}{4} + \frac{1}{4} = 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:

$|\psi_{post}\rangle = \frac{\frac{1}{2}|011\rangle}{\sqrt{\left(\frac{1}{2}\right)^2}} = \frac{\frac{1}{ 2}}{\frac{1}{2}}|011\rangle = |011\rangle$

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:

$\left(\frac{1}{\sqrt 2}\right)^2 + \left(\frac{1}{2}\right)^2 = \frac{1}{2} + \frac{1}{4} = 0.75$

The post state would be these two terms normalized, which would be:

$|\psi_{post}\rangle = \frac{\frac{1}{\sqrt 2}|101\rangle + \frac{1}{2}|111\rangle}{\sqrt{\left(\frac{1}{\sqrt 2}\right)^2 + \left(\frac{1}{2}\right)^2}} = \sqrt{\frac{2}{3}}|101\rangle + \sqrt{\frac{1}{3}}|111\rangle$

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:

$|\psi_{post}\rangle = \frac{1}{\sqrt 2}|011\rangle + \frac{1}{\sqrt 2}|111\rangle$

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.

Quantum teleporation

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:

$|\psi_{in}\rangle = \alpha|0\rangle + \beta|1\rangle$

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:

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle} {\sqrt 2}$

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:

$|\psi_{total}\rangle = (\alpha|0\rangle + \beta|1\rangle)\left(\frac{|00\rangle + |11\rangle} {\sqrt 2}\right) = \frac{1}{\sqrt 2}\left(\alpha|000\rangle + \alpha|011\rangle + \beta|100\rangle + \beta|111\rangle \right)$

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:

$\frac{1}{\sqrt 2}\left(\alpha(|000\rangle + |011\rangle) + \beta(|100\rangle + |111\rangle) \right)$

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:

$cNOT\left(\frac{1}{\sqrt 2}\left(\alpha(|000\rangle + |011\rangle) + \beta(|100\rangle + |111\rangle) \right)\right) =$

$\frac{1}{\sqrt 2}\left(\alpha(|000\rangle + |011\rangle) + \beta(|110\rangle + |101\rangle) \right)$

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:

$\frac{1}{\sqrt 2}\left(\alpha(|+\rangle|00\rangle + |+\rangle|11\rangle) + \beta(|-\rangle|10\rangle + |-\rangle|01\rangle\right)$

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:

$\frac{1}{2}(\alpha(|000\rangle + |011\rangle + |100\rangle + |111\rangle) + \beta(|010\rangle + |001\rangle - |110\rangle - |101\rangle))$

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.

$|\psi_{post}\rangle = \frac{\frac{1}{2}(\alpha(|000\rangle + |011\rangle) + \beta(|010\rangle + |001\rangle))}{N}$

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):

$N = \sqrt{\frac{1}{4}(\alpha^2 + \alpha^2 + \beta^2 + \beta^2)} = \sqrt{\frac{1}{4}(2\alpha^2 + 2\beta^2)} = \sqrt{\frac{1}{2}(\alpha^2 + \beta^2)}$

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:

$N = \sqrt{\frac{1}{2}}$

We get this:

$|\psi_{post}\rangle = \frac{\frac{1}{2}(\alpha(|000\rangle + |011\rangle) + \beta(|010\rangle + |001\rangle))}{\sqrt{\frac{1}{2}}} = \frac{1}{\sqrt 2}(\alpha(|000\rangle + |011\rangle) + \beta(|010\rangle + |001\rangle))$

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.

$|\psi_{post}\rangle = \frac{\frac{1}{\sqrt 2}(\alpha|000\rangle + \beta|001\rangle)}{N}$

Normalization factor this time:

$N = \sqrt{\frac{1}{2}(\alpha^2 + \beta^2)} = \frac{1}{\sqrt 2}$

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:

$|\psi_{post}\rangle = \frac{\frac{1}{\sqrt 2}(\alpha|000\rangle + \beta|001\rangle)}{\frac{1}{\sqrt 2}} = \alpha|000\rangle + \beta|001\rangle = |00\rangle(\alpha|0\rangle + \beta|1\rangle)$

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.

Finally

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:

$|\psi_{weird}\rangle = \frac{1}{\sqrt 2}(\alpha(A + B) + \beta(C - D))$

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:

$\frac{1}{\sqrt 2}(\alpha A + \beta C)$

If it is |1>, we get:

$\frac{1}{\sqrt 2}(\alpha B - \beta D)$

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:

$|\psi\rangle = a|0\rangle + b|1\rangle = a(1,0) + b(0,1)$

Even if 'a' and 'b' are only real values, we still have the normalization constraint:

$a^2 + b^2 = 1$

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:

$a = \cos (t)$

$b = \sin (t)$

Due to the trigonometric identity:

$a^2 + b^2 = \cos^2(t) + \sin^2(t) = 1$

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.

Complex coefficients

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:

$|\psi\rangle = z|0\rangle + w|1\rangle$

The normalization constraint means we have:

$|z|^2 + |w|^2 = 1$

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):

$z = |z|e^{i\phi} = e^{i\phi} = \cos (\phi) + i \cdot \sin (\phi)$

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:

$z = v \cdot \cos (\theta)$

$w = u \cdot \sin (\theta)$

'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:

$|z|^2 + |w|^2 = |v|^2 \cdot \cos^2(\theta) + |u|^2 \cdot \sin^2(\theta) = \cos^2(\theta) + \sin^2(\theta) = 1$

v and u has modulus 1, so they are complex exponentials:

$v = e^{i\phi_0}$

$u = e^{i\phi_1}$

Given this relationship, we can now express the qubit in the following way:

$|\psi\rangle = z|0\rangle + w|1\rangle = e^{i\phi_0} \cdot \cos(\theta)|0\rangle + e^{i\phi_1}\sin(\theta)|1\rangle$

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...):

$|\psi\rangle = e^{-i\phi_0}|\psi\rangle = \cos(\theta)|0\rangle + e^{i(\phi_1 - \phi_0)}\sin(\theta)|1\rangle$

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:

$|\psi\rangle = \cos \left(\frac{\theta}{2}\right)|0\rangle + e^{i\phi}\sin \left(\frac{\theta}{2} \right)|1\rangle$

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:

$\theta = \frac{\pi}{2}$

$\phi = 0$

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:

$e^{i\pi} = -1$

This means that the state -|1> corresponds to the two angles:

$\theta = \pi$

$\phi = \pi$

## Test 1Edit

There are 28,5 points in total. 15 is needed to pass. Good luck.

Lecture 1

1

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)

2

a) Express the |+> and |-> vectors in terms of the computational basis. (2p)

Express the following vectors in the computational basis:

b) $|\psi\rangle = \frac{|+\rangle + |-\rangle}{\sqrt 2}$ (1p)

c) $|\psi\rangle = \frac{|+\rangle - |-\rangle}{\sqrt 2}$ (1p)

Lecture 2

3

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.

(2p)

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)

4

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)

5

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:

$H = \frac{Z + X}{\sqrt 2}$

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?

Lecture 3

6

Express the following states using the two-qubit bases: |00>,|01>,|10>,|11>

a) |1>|+> (1p)

b) |->|0> (1p)

c) |+>|+> (1p)

7

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)

8

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)

END

## Test 2Edit

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.

Lecture 4

1

Is the state entangled or not? (HINT: Try writing it as a product.)

a) $\frac{|00\rangle + |11\rangle}{\sqrt 2}$ (1p)

b) $\frac{|10\rangle + |11\rangle}{\sqrt 2}$ (1p)

c) $\frac{|01\rangle + |10\rangle}{\sqrt 2}$ (1p)

d) $\frac{|00\rangle + |01\rangle}{\sqrt 2}$ (1p)

e) $\frac{|00\rangle + |01\rangle + |10\rangle + |11\rangle}{2}$ (1p)

f*) $\frac{|00\rangle + |01\rangle + |11\rangle}{\sqrt 3}$ (1p)

2

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)

Lecture 5

3

You will be doing partial measurements on this state:

$|\psi\rangle = \frac{|01> + |11>}{\sqrt 2}$

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)

4

You will be doing partial measurements on this state:

$|\psi\rangle = \frac{|00\rangle - |10\rangle + |11\rangle}{\sqrt 3}$

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)

END


text:
SSC (Marathi Semi-English) 10thMaharashtra State Board
Share

# Choose the Correct Option and Rewrite the Statement.Molecular Formula of the Chloride of an Element X is Xcl. this Compound is a Solid Having - SSC (Marathi Semi-English) 10th - Science and Technology - 1

#### Question

Choose the correct option and rewrite the statement.
Molecular formula of the chloride of an element X is XCl. This compound is a solid having high melting point. Which of the following elements be present in the same group as X.
(i) Na  (ii) Mg  (iii) Al  (iv) Si

#### Solution

Molecular formula of the chloride of an element X is XCl. This compound is a solid having high melting point. An element to be present in the same group as X is Na.

Is there an error in this question or solution?

#### APPEARS IN

Balbharati Solution for Balbharati Class 10 Science and Technology part 1 (2018 to Current)
Chapter 2: Periodic Classification of Element
Q: 2.3 | Page no. 28
Solution Choose the Correct Option and Rewrite the Statement.Molecular Formula of the Chloride of an Element X is Xcl. this Compound is a Solid Having Concept: Classification of Elements.
S

format: plain


text:
Emmanuel Rauzy

# Obstruction to a Higman embedding theorem for residually finite groups with solvable word problem

Open Access
De Gruyter | Published online: October 1, 2020

# Abstract

We prove that, for a finitely generated residually finite group, having solvable word problem is not a sufficient condition to be a subgroup of a finitely presented residually finite group. The obstruction is given by a residually finite group with solvable word problem for which there is no effective method that allows, given some non-identity element, to find a morphism onto a finite group in which this element has a non-trivial image. We also prove that the depth function of this group grows faster than any recursive function.

## Introduction

It is well known that there can be no Higman embedding theorem for recursively presented finitely generated residually finite groups, that is to say, not all finitely generated recursively presented residually finite groups embed into finitely presented residually finite groups. Indeed, a theorem of McKinsey [9, 11, 3] states that all finitely presented residually finite groups have solvable word problem, while on the other hand several recursively presented residually finite groups are known that fail to have solvable word problem: for instance, one example was constructed by Meskin in [10], and one by Dyson in [4].

It was unknown whether or not the condition of having solvable word problem is sufficient for such embeddings to exist. For instance, in the article [7], the authors ask whether “unsolvability of the word problem is the only obstacle” to embed recursively presented residually finite groups into finitely presented residually finite groups. We answer that question negatively.

Theorem 1

There exists a finitely generated residually finite group with solvable word problem, that does not embed in any finitely presented residually finite group.

Call a group 𝐺effectively residually finite if there is an algorithm that takes a word 𝑤 on the generators of 𝐺 as input and, if w e in 𝐺, produces a morphism 𝜑 from 𝐺 to a finite group 𝐹 that satisfies φ ( w ) e . What we actually prove here is the following theorem.

Theorem 2

There exists a finitely generated residually finite group with solvable word problem, that is not effectively residually finite.

Theorem 1 then follows from the following facts.

Fact 3

A finitely presented residually finite group is effectively residually finite.

Fact 4

A finitely generated subgroup of an effectively residually finite group is itself effectively residually finite.

Fact 3 follows from McKinsey’s algorithm. It comes from the fact that a finitely presented group has computable finite quotients; see [12]. Fact 4 is straightforward.

In the first section, Dyson’s groups are introduced, and they are used to reduce the proof of Theorem 2 to a problem about subsets of ℤ. In the second section, this problem is solved. In the last section, we show that the group constructed in order to prove Theorem 2 has a depth function that grows faster than any recursive function.

Following [4], throughout, recursively presented groups will be called re groups (for recursively enumerable), and groups in which there is an algorithm that recognizes non-trivial elements will be called co-re groups. A group has solvable word problem if and only if it is re and co-re.

## 1 Dyson’s groups

The author already used Dyson’s groups to investigate the property of having computable finite quotients [12]. What we construct here is a strengthening of the result obtained in that article; we will include here all definitions but omit the proofs that already appear there.

Dyson’s groups are amalgamated products of two lamplighter groups.

The lamplighter group 𝐿 is the wreath product of ℤ and Z / 2 Z , noted Z Z / 2 Z , which is by definition the semi-direct product Z Z Z / 2 Z , where ℤ acts on Z Z / 2 Z by permuting the indices. It admits the following presentation:

a , ε ε 2 , [ ε , a i ε a - i ] , i Z .
The element a i ε a - i of 𝐿 corresponds to the element of Z Z / 2 Z with only one non-zero coordinate in position i Z . We call it u i . Consider another copy L ^ of the lamplighter group; with an isomorphism, we write g g ^ . For each subset 𝒜 of ℤ, define L ( A ) to be the amalgamated product of 𝐿 and L ^ , with u i = a i ε a - i identified with u ^ i = a ^ i ε ^ a ^ - i for each 𝑖 in 𝒜. It has the following presentation:
a , a ^ , ε , ε ^ ε 2 , ε ^ 2 , [ ε , a i ε a - i ] , [ ε ^ , a ^ i ε ^ a ^ - i ] , i Z , a j ε a - j = a ^ j ε ^ a ^ - j , j A

Whether the group L ( A ) is residually finite depends on whether the set 𝒜 is closed in the profinite topology on ℤ. The profinite topology on a group 𝐺, which we denote by P T ( G ) , is the topology defined by taking cosets of finite index normal subgroups as a basis for the open sets. Thus a subset 𝒜 of ℤ is open in P T ( Z ) if and only if, for every 𝑛 in 𝒜, there exists an integer 𝑝 such that n + p Z A . The profinite topology on ℤ was rediscovered in 1955 by Furstenberg in [5] (the profinite topology on an arbitrary group was defined in 1950 in [6]), where it is used to give an elegant proof of the existence of infinitely many primes, and it was proven in [8] that this topology comes from a metric, which is given by the following formula:

x = 1 sup { n : 1 | x , 2 | x , 3 | x , , n | x } , d ( x , y ) = x - y .
The norm x is thus the reciprocal of the greatest integer 𝑛 with the property that 1 , 2 , , n all divide 𝑥. A sequence converges to 0 in that topology if and only if, for any integer 𝑘, there exists a point beyond which 𝑘 divides all terms of the sequence. For instance, n ! goes to 0 as 𝑛 goes to infinity. Define a function 𝜃 on the natural numbers by θ ( n ) = lcm { 1 , 2 , 3 , , n } . θ ( n ) is the smallest non-zero natural number such that θ ( n ) 1 n . The closed ball of radius 1 n and centered in 𝑥, which is the set { y Z , d ( x , y ) 1 n } , is simply the set x + θ ( n ) Z . It is in fact also open. Call B ¯ ( x , r ) the closed ball centered in 𝑥 and of radius 𝑟, and B ( x , r ) the corresponding open ball (but note that the latter is not the interior of the former). The distance 𝑑 is in fact ultrametric: for 𝑥, 𝑦 and 𝑧 integers, one has d ( x , z ) max ( d ( x , y ) , d ( y , z ) ) . This implies that each point of a ball can be taken as its center, and thus that if two balls intersect, one is contained in the other.

Of course, the distance 𝑑 is effective: 𝑑 is a recursive function. This implies that both the closed and open balls of P T ( Z ) are recursive sets.

Call an open set 𝑂effectively open (in P T ( Z ) ) if there is an effective procedure that, given any number 𝑛 in 𝑂, computes some integer 𝑝 such that n + p Z is contained in 𝑂. A set is effectively closed if its complement is effectively open.

We can now state the properties of the group L ( A ) that will allow us to prove Theorem 2.

Proposition 5

Let 𝒜 be a subset of ℤ.

1. L ( A ) is re, co-re or has solvable word problem if and only if 𝒜 is respectively re, co-re or recursive.

2. L ( A ) is residually finite if and only if 𝒜 is closed in P T ( Z ) .

3. L ( A ) is effectively residually finite if and only if 𝒜 is co-re and effectively closed in P T ( Z ) .

(1) and (2) were proved by Dyson in [4]. See also [12]. We prove here only the third point.

## Proof

Suppose first that L ( A ) is effectively residually finite. Then L ( A ) is co-re, and by (1), 𝒜 is co-re as well. Let 𝑥 be an integer in the complement of 𝒜 such that u x u ^ x - 1 1 in L ( A ) . By our hypothesis, we can effectively find a morphism 𝜑 from L ( A ) to a finite group 𝐹, with φ ( u x u ^ x - 1 ) 1 in 𝐹. Call 𝑁 the product of the orders of the images of 𝑎 and a ^ in 𝐹. We then claim that A ( x + N Z ) = . Indeed, if it were not the case, there would exist an integer 𝑘 such that x + k N A , that is to say, such that u x + k N = u ^ x + k N in L ( A ) . But then, this would imply

φ ( u x ) = φ ( a ) k N φ ( u x ) φ ( a ) - k N = φ ( a k N u x a - k N ) = φ ( u x + k N ) = φ ( u ^ x + k N ) .
Because it can similarly be proved that φ ( u ^ x ) = φ ( u ^ x + k N ) , this contradicts the assumption that φ ( u x u ^ x - 1 ) 1 . Thus 𝒜 does not meet x + N Z .

The proof of the converse follows closely the proof of (2) given in [12] (which differs from the original proof of Dyson), as one only needs to see that the hypothesis that 𝒜 is effectively closed in P T ( Z ) is enough to effectively carry out that proof. As we actually only use the first implication of (3) in the proof of Theorem 2, no further details are given here. ∎

From Proposition 5, to prove Theorem 2, it suffices to build 𝒜 with the following properties: 𝒜 is recursive, 𝒜 is closed, but not effectively so.

## 2 Construction in ℤ

Lemma 6

There exists a recursive subset 𝒜 of ℤ, closed in P T ( Z ) , but not effectively so.

## Proof

We construct a set ℬ, which will be the complement of the announced 𝒜. Thus it has to be recursive and open but not effectively open.

Call p n the 𝑛-th prime number. Define a sequence ( t n ) n 0 by t n = p 1 p n . This sequence is defined so that p k divides t n if and only if k n . Note also that t n divides t n + 1 .

Consider an effective enumeration of all Turing machines: M 1 is the first machine, M 2 is the second, …. We will build ℬ as a disjoint union of open sets X n , each X n being a neighborhood of t n defined thanks to a run of the 𝑛-th Turing machine M n . If this machine does not halt, X n is a closed ball centered at t n of radius 1 t n + 1 . If it halts, it is a finite union of balls, one of which is centered at t n , the radius of which depends of the number of steps needed for M n to halt. Thanks to this, information of the form “ X n contains a ball of radius 𝑟 centered in t n ” will translate into “if M n halts, it does so in less than 𝑁 steps”, where 𝑁 can be computed from 𝑟.

Initialize X n = { t n } . Call r n = 1 t n + 1 and m = θ ( t n + 1 ) so that the closed ball B ¯ ( t n , r n ) is the set t n + m Z . Start a run of the machine M n .

After each computation step of M n , note 𝑘 the number of steps already done in the computation and add, to X n , t n + k m , t n - k m , as well as open balls centered in those numbers that are contained in B ¯ ( t n , r n ) and do not contain t n . That is, we replace X n by

X n B ( t n + k m , 1 2 d ( t n , t n + k m ) ) B ( t n - k m , 1 2 d ( t n , t n - k m ) ) .
Because the distance 𝑑 is ultrametric, both balls B ( t n + k m , 1 2 d ( t n , t n + k m ) ) and B ( t n - k m , 1 2 d ( t n , t n - k m ) ) are contained in B ¯ ( t n , r n ) .

If, at some point, the machine M n halts, X n consists of t n and of finitely many open balls centered at points t n ± k m . By construction, a point from X n { t n } is at distance at least inf k { 1 2 d ( t n , t n ± k m ) } from t n . This infimum can be computed; call it 𝑟. Then compute the smallest natural number 𝑦 such that d ( t n , y ) < r , and call r the distance d ( t n , y ) . We then add to X n the ball B ( u n , r ) . This implies that X n cannot contain any ball of center t n and of radius strictly greater than r because it does not contain 𝑦. In particular, any ball centered in t n that contains one of the elements of the form t n ± k m that were added to X n is not contained in X n .

Of course, if the machine M n does not halt, X n will be the whole ball B ¯ ( t n , r n ) .

This ends the definition of X n , and ℬ is defined as the union X n . This union is disjoint because, by the choice of the radius r n , any element of X n is divisible by p n , but none is divisible by p n + 1 . We now prove that ℬ defined this way satisfies all three properties that appear in the statement of this lemma.

ℬ is clearly open, because each X n is open, whether or not the machine M n halts.

ℬ is a recursive set. It is obviously recursively enumerable because it was defined by an effective enumeration. To see that it is also co-re, let 𝑥 be an integer; we want to decide whether 𝑥 belongs to ℬ. By looking at the prime decomposition of 𝑥, one can find up to one 𝑛 such that 𝑥 might belong to X n . Because X n is always contained in B ¯ ( t n , r n ) , if d ( t n , x ) > r n , 𝑥 cannot be in X n . Otherwise, it belongs to B ¯ ( t n , r n ) = t n + m Z , and we can find 𝑘 such that x = t n + k m . Then, if a run of M n lasts more then 𝑘 steps, automatically, 𝑥 will belong to X n . On the other hand, if M n stops in less than 𝑘 steps, X n can be determined explicitly as a finite union of open balls, and thus the question of whether 𝑥 belongs to X n can be settled. Because the problem “does M n halt in more then 𝑘 steps” is a computable one, in either case, we will be able to determine whether or not 𝑥 belongs to ℬ.

Finally, ℬ is not effectively open. Suppose we have an algorithm that gives, for 𝑥 in ℬ, an integer 𝑘 such that x + k Z is contained in ℬ. Applying it to t n , we can find a radius 𝑟 such that B ( t n , r ) is contained in ℬ. We will show that this information implies a new information of the form: if the machine M n halts, then it halts in less than 𝑁 steps. This would of course allow one to solve the halting problem; thus such an algorithm does not exist.

Indeed, we have seen that if M n halts in 𝑁 steps, X n cannot contain any ball centered in t n that contains an element of the form t n ± k m , with k N . Turning this around, computing 𝑁 such that t n + m N belongs to B ( t n , r ) (for instance, N = θ ( 1 r + 1 ) ), the information “ B ( t n , r ) is contained in ℬ” implies that either M n does not halt, or it halts in less then 𝑁 steps.

This ends the proof of Lemma 6. ∎

What we do not know yet is whether the condition of being recursively presented and effectively residually finite, which is necessary to be a subgroup of a finitely presented residually finite group, is also sufficient. For instance, the strictly stronger condition of having computable finite quotients is not known to be unnecessary (see [12]).

## 3 Non-recursive depth function

In [1], Bou-Rabee introduced the residual finiteness growth function, or depth function, ρ G , of a residually finite group 𝐺. To a natural number 𝑛, ρ G associates the smallest number 𝑘 such that, for any non-trivial element of length at most 𝑛 in 𝐺, there exists a finite quotient of 𝐺 of order at most 𝑘 such that the image of this element in that quotient is non-trivial.

A finitely generated subgroup 𝐻 of a finitely generated residually finite group 𝐺 must have a depth function ρ H that grows more slowly than that of 𝐺 (see [1]). Because it is easy to see that a finitely presented residually finite group always has a recursive growth function, a subgroup of a finitely presented residually finite group must have its depth function bounded above by a recursive function. Note that, in [7], it was shown that finitely presented residually finite groups can have arbitrarily large recursive depth function. It was also known that the depth function of a residually finite group could grow arbitrarily fast (see [2]).

Note that an effectively residually finite group with solvable word problem always has its depth function bounded above by a recursive function.

Proposition 7

Let 𝒜 be the subset of ℤ given in Lemma 6. The depth function ρ L ( A ) of L ( A ) cannot be smaller than a recursive function.

## Proof

Suppose there exists a recursive function 𝑓 such that ρ L ( A ) f . Then, for each 𝑛 which is not in 𝒜, u n u ^ n - 1 is a non-identity element of L ( A ) , and thus it has a non-trivial image in a finite quotient 𝐹 of size at most f ( 4 n + 2 ) (because u n and u ^ n are of word length 2 n + 1 ). Now the orders of 𝑎 and a ^ in 𝐹 both divide f ( 4 n + 2 ) ! ; thus 𝐹 is a quotient of the quotient of L ( A ) given by adding to it the two relations

a f ( 4 n + 2 ) ! = e and a ^ f ( 4 n + 2 ) ! = e ( i.e. L ( A ) a f ( 4 n + 2 ) ! , a ^ f ( 4 n + 2 ) ! ) .
Thus, in this group as well, u n u ^ n - 1 is a non-identity element, and we know that this implies that n + f ( 4 n + 2 ) ! Z does not meet 𝒜 (see the proof of Proposition 5). This shows that 𝒜 is effectively closed, contradicting our hypothesis. ∎

Communicated by: Pavel A. Zalesskii

### References

[1] K. Bou-Rabee, Quantifying residual finiteness, J. Algebra 323 (2010), no. 3, 729–737. Search in Google Scholar

[2] K. Bou-Rabee and B. Seward, Arbitrarily large residual finiteness growth, J. Reine Angew. Math. 710 (2016), 199–204. Search in Google Scholar

[3] V. H. Dyson, The word problem and residually finite groups, Notices Amer. Math. Soc. 11 (1964), 616–617. Search in Google Scholar

[4] V. H. Dyson, A family of groups with nice word problems, J. Aust. Math. Soc. 17 (1974), 414–425. Search in Google Scholar

[5] H. Furstenberg, On the infinitude of primes, Amer. Math. Monthly 62 (1955), 353–353. Search in Google Scholar

[6] M. Hall, , A topology for free groups and related groups, Ann. of Math. (2) 52 (1950), 127–139. Search in Google Scholar

[7] O. Kharlampovich, A. Myasnikov and M. Sapir, Algorithmically complex residually finite groups, Bull. Math. Sci. 7 (2017), no. 2, 309–352. Search in Google Scholar

[8] R. L. Lovas and I. Mezo, On an exotic topology of the integers, preprint (2010), https://arxiv.org/abs/1008.0713. Search in Google Scholar

[9] J. C. C. McKinsey, The decision problem for some classes of sentences without quantifiers, J. Symbolic Logic 8 (1943), 61–76. Search in Google Scholar

[10] S. Meskin, A finitely generated residually finite group with an unsolvable word problem, Proc. Amer. Math. Soc. 43 (1974), 8–10. Search in Google Scholar

[11] A. W. O. Mostowski, On the decidability of some problems in special classes of groups, Fund. Math. 59 (1966), 123–135. Search in Google Scholar

[12] E. Rauzy, Computability of finite quotients of finitely generated groups, preprint (2020), https://arxiv.org/abs/2002.02541. Search in Google Scholar


text:
# What is the integral of 3x?

Dec 9, 2014

Power Rule for Antiderivatives

$\int {x}^{n} \mathrm{dx} = \frac{{x}^{n + 1}}{n + 1} + C$

$\int 3 x \mathrm{dx}$

by pulling $3$ out of the integral,

$= 3 \int x \mathrm{dx}$

by Power Rule,

$= 3 \cdot {x}^{2} / 2 + C = \frac{3}{2} {x}^{2} + C$

I hope that this was helpful.


text:
## Inflation on the Brane with Vanishing Gravity

##### Authors
Gallicchio, Jason
Mahbubani, Rakhi
##### Description
Many existing models of brane inflation suffer from a steep irreducible gravitational potential between the branes that causes inflation to end too early. Inspired by the fact that point masses in 2+1 D exert no gravitational force, we propose a novel unwarped and non-supersymmetric setup for inflation, consisting of 3-branes in two extra dimensions compactified on a sphere. The size of the sphere is stabilized by a combination of a bulk cosmological constant and a magnetic flux. Computing the 4D effective potential between probe branes in this background, we find a non-zero contribution only from exchange of level-1 KK modes of the graviton and radion. Identifying antipodal points on the 2-sphere projects out these modes, eliminating entirely the troublesome gravitational contribution to the inflationary potential.
Comment: 19 pages, 11 figures, JHEP format
##### Keywords
High Energy Physics - Theory


text:
# Chapter 1, Equations and Graphs - Section 1.5 - Complex Numbers - 1.5 Exercises - Page 130: 5

Yes.

#### Work Step by Step

Yes, every real number is also a complex number. If the real number is $x$, then the complex form is $x+0i$.

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.


text:
# Four-function and exponentiation console calculator

This code works as it is supposed to:

#include<iostream>
#include<cmath>
#include<cstdlib>

using namespace std;

int main()
{
char cAgain, type;
int x, y=0;
double addition(double num1, double num2), subtraction(double num1, double num2), division(double num1, double num2),
multiplication(double num1, double num2), exponential(double num1, double num2), num1, num2, total;
do
{
cout << "How many operations would you like to do?" << endl;
cin >> x;
if (x <= 0)
{
cout << "Error: You must have 1 or more operations." << endl;
}
else
{
while (x != 0, x--)
{
y++;
cout << "Enter in your "<<y<< " operation. (First Number (+,-,*,/,^) Second Number)" << endl;
cin >> num1 >> type >> num2;
switch (type)
{
case '+':
cout << num1 << " + " << num2 << "= " << total<< endl;
break;
case'-':
total = subtraction(num1, num2);
cout << num1 << " - " << num2 << "= " << total<< endl;
break;
case'/':
total = division(num1, num2);
cout << num1 << " / " << num2 << "= " << total<< endl;
break;
case'*':
total = multiplication(num1, num2);
cout << num1 << " * " << num2 << "= " << total << endl;
break;
case'^':
total = exponential(num1, num2);
cout << num1 << " ^ " << num2 << "= " << total << endl;
break;
}
}
}
cout << "Would you like to run the program again.(Y/N)" << endl;
cin >> cAgain;
} while (cAgain == 'Y' || cAgain == 'y');
return 0;
}

{
double total;
total = num1 + num2;
return (total);
}
double subtraction(double num1, double num2)
{
double total;
total = num1 - num2;
return (total);
}
double division(double num1, double num2)
{
double total;
total = num1 / num2;
return (total);
}
double multiplication(double num1, double num2)
{
double total;
total = num1 * num2;
return (total);
}
double exponential(double num1, double num2)
{
double total;
total = pow(num1,num2);
return (total);
}

It starts by asking for the number of operations to perform. You enter a number, such as 3. Then it asks you to enter in your operation, such as 5+5, which is 10. Then it asks for a second, such as 10^2, which is 100. Then it asks for a third, such as 100-10, which is 90. Then it asks if you'd like to start over.

• This is not the right place for such questions. Here, it is expected that you have working code but want to improve the quality of your code. – R Sahu Dec 24 '14 at 3:51
• This code does work, wrote it without errors, I'm trying to improve the quality of the code by making it more user friendly. As it works now it works like your old school basic calculator it is hitting the = sign after every operation. I'm looking for a way to make it more like a modern scientific calculator. – Styx Dec 24 '14 at 4:17
• Where's the modulo? :( – Yodism Dec 24 '14 at 4:49
• You should look up the Command Pattern. Then use a std::map<char, Command> – Martin York Dec 24 '14 at 4:57
• I have removed the off-topic part of the question. For inspiration, see questions tagged with math-expression-eval. – 200_success Dec 24 '14 at 5:09

There's a few issues here with c++ basics:

## using namespace std

using namespace std;

This is usually a code smell, generally speaking the only time you would really want to do this is when you are making some small throwaway program for testing a concept or making an example (or similar). In that case the reduction in typing time actually has a positive ROI. But you don't want to do it in any production code because this pollutes the global namespace which is something you should try to avoid, any benefit from time saved typing is immediately wiped out the first time your program breaks because a name conflict. See this StackOverflow question for more info on that.

If the main purpose for doing this is to cut down typing std:: then you can selectively bring in just the names you need by doing:

using std::cout;
using std::cin;

an so on. This cuts down on typing without the downside of polluting the global namespace.

## Function declarations

Currently you have this line:

double addition(double num1, double num2), subtraction(double num1, double num2), division(double num1, double num2),
multiplication(double num1, double num2), exponential(double num1, double num2), num1, num2, total;

First of all, this line is way too many characters wide to be readable. But more importantly you are declaring some functions and some variables on the same line. This is very bad for readability. Some people only have one declaration per line, but at the very least don't have more than one type of thing being declared on the same line.

The idiomatic c++ way to do function declarations is at the top of the file or in header files. Instead put the function declarations above main one per line:

double addition(double num1, double num2);
double subtraction(double num1, double num2);
double division(double num1, double num2);
double multiplication(double num1, double num2);
double exponential(double num1, double num2);

This way it's much clearer to the readers of your code which functions you are forward declaring.

## Unnecessary variables

In each of the functions that computes the value of an expression you have the same structure:

double addition(double num1, double num2)
{
double total;
total = num1 + num2;
return (total);
}

This can be simplified by just doing:

double addition(double num1, double num2)
{
return num1 + num2;
}

The reduction in the number of lines of code is a win for readability.

## Improving the features of the program

In order to compute the expressions such as 5+5^2-10 with correct operator precedence you will need to implement a parser. When I last did something like this I implemented a recursive descent parser. Be warned that this can be difficult to implement.

And looking into the Boost Spirit parser library.

• Thanks for the tips. I'm fairly new too coding and using namespace std; was just something my intro class added in as a starting standard code. – Styx Dec 24 '14 at 4:29
• @Styx, I see that a fair bit, it just happens to be something that can turn into a bad habit if you use it for any real projects. – shuttle87 Dec 24 '14 at 4:30

I'll mention some additional points that haven't been mentioned yet, but this does look like it can still be cleaned out quite a bit.

• You could define those functions above main() so that prototypes won't be needed. Otherwise, put them above main(), as already mentioned in another answer.

• These:

#include<iostream>
#include<cmath>
#include<cstdlib>

would look nicer with spaces:

#include <iostream>
#include <cmath>
#include <cstdlib>

Regarding spacing, you have some inconsistent spacing around the cases. Try not to neglect this as it could make your code more awkward to read for others.

• type, x, and y are all declared outside of the loop, but are only used inside of the loop. In order to help keep track of them, declare them right where they're first used. Doing this with every variable can help with maintaining cleaner code, especially with larger programs.

• This is not doing what you expect:

while (x != 0, x--)

The comma operator returns the result of the last expression, which is the x--. The other expressions are evaluated (from left to right) but the results of the expression are ignored. Thus, the result of x != 0 is evaluated with no side affects and the result dropped. This makes the expression equivalent to while (x--).

• You don't check for division by 0, so your program can break if this operation is done. You may throw an exception for that and handle it, so that you can get a different input. Just make sure this division doesn't happen.

• You don't need return 0 at the end of main(). The compiler will do this return for you after reaching this point.

• +1 Division by zero is a good point to mention, I totally missed that when I first glanced at the code. – shuttle87 Dec 24 '14 at 4:48

Just a minor thing:

    total = addition(num1, num2);
cout << num1 << " + " << num2 << "= " << total << endl;
break;

you can make it like this:

case '+':
cout << num1 << " + " << num2 << "= " << addition(num1, num2) << endl;
break;

• This may not work if the OP is trying to keep a running total. To be fair, it took me a while to find total hidden behind the lines of prototypes. – Jamal Dec 24 '14 at 5:12
• probably, depend on him if he considered what @shuttle87 recommend, for sure he needs to keep total variable – MORTAL Dec 24 '14 at 5:31
• @MORTAL as the program is currently programmed your improvements actually do simplify the code in a necessary way. Total will be needed after the code as implemented some of the improvements. – Styx Dec 24 '14 at 5:59


text:
MullOverThing

Useful tips for everyday

# What is VC dimension explain with one example?

## What is VC dimension explain with one example?

VC dimension of a finite projective plane Each line intersects every other line in exactly one point. Each point is contained in exactly n + 1 lines. Each point is in exactly one line in common with every other point. At least four points do not lie in a common line.

### How do you prove VC dimensions?

under the definition of the VC dimension, in order to prove that VC(H) is at least d, we need to show only that there’s at least one set of size d that H can shatter. shattered by oriented hyperplanes if and only if the position vectors of the remaining points are linearly independent. hyperplanes in Rn is n+1.

#### What is the VC dimension of line hypothesis?

The VC dimension of a set of hypotheses H is the size of the largest set C ⊆ X such that C is shattered by H. If H can shatter arbitrarily sized sets, its VC dimension is infinite. We now study the VC dimension of some finite classes, more in particular: classes of boolean functions.

What is VC dimension of instances points on a real line?

The VC dimension of a classifier is defined by Vapnik and Chervonenkis to be the cardinality (size) of the largest set of points that the classification algorithm can shatter [1].

Why is VC dimension important?

VC dimension is useful in formal analysis of learnability, however. This is because VC dimension provides an upper bound on generalization error. So if we have some notion of how many generalization errors are possible, VC dimension gives an indication of how many could be made in any given context.

## What is the VC dimension of H?

Definition 3 (VC Dimension). The VC-dimension of a hypothesis class H, denoted VCdim(H) is the size of the largest set C ⊂ X that can be shattered by H. If H can shatter sets of arbitrary size, then VCdim(H) = ∞.

### Is a higher VC dimension better?

The images shows that a higher VC dimension allows for a lower empirical risk (the error a model makes on the sample data), but also introduces a higher confidence interval. This interval can be seen as the confidence in the model’s ability to generalize.

#### What is a VC class?

If there is a largest, finite k such that C shatters at least one set of cardinality k, then C is called a Vapnik–Chervonenkis class, or VC class, of sets and S(C)=k its Vapnik–Chervonenkis index. …

Can VC dimension be infinite?

The VC dimension is infinite if for all m, there is a set of m examples shattered by H. Usually, one considers a set of points in “general position” and shows that they can be shattered. This avoids issues like collinear points for a linear classifier.

Why VC dimension is important?

## Is VC dimension useful?

### Why is VC dimension useful?

#### Which is an example of a large VC dimension?

VC dimension is the measure of how complex a classifier. Large VC dimension shows the classifier is more complex and vice versa. Consider a data with three instances (for example, Fig.1 (a) shown below with two empty circles labelled as +1 and one filled circle labelled as -1).

How to explain VC dimension and shattering in lucid way?

In Fig.3, Where the class of classifiers with width γ 2 which is greater than γ 1 could not seperate all the insances (see red arrowed points fig.3 (a) (d)). Suppose if we delete the red arrowed point from the dataset, then the classifier with width γ 2 can shatter the subset (two points) of data.

How is the VC dimension of a function shattered?

For each of these labellings, if you can draw a function from your function family that separates the labels, then the set of n points is said to have been shattered by your family of functions. The maximum n which you can shatter is the VC dimension, h, of your function family.

## What is the VC dimension of a hyperplane?

If your data has 2 dimensions and the function family we’re looking at is hyperplanes (which, in 2D, are lines), the VC dimension is 3. Since: We can find at least one set of 3 points in 2D all of whose 8 possible labellings can be separated by some hyperplane.


text:
# How do you write 7.2times10^5 in standard form?

Aug 3, 2016

720 000

#### Explanation:

$7.2 \times {10}^{5} \text{ is already expressed in "color(blue)"standard form}$

I believe you mean express as $\textcolor{b l u e}{\text{original number}}$

To do this consider ${10}^{5} \text{ or more generally} {10}^{n}$ where n is an integer.

• If n > 0 $\textcolor{red}{\text{move decimal point n places to the right}}$

• If n < 0 $\textcolor{b l u e}{\text{move decimal point n places to the left}}$

here n = 5 > 0, hence move decimal point 5 places to the right.

rArr7color(red)(•)2to720000color(red)(•)

$\Rightarrow 7.2 \times {10}^{5} = 720 000$