00:00Quantum Computing leverages the principles of quantum mechanics to process information at incredible speeds
00:08This course provides a solid foundation in Quantum Computing from the ground up, taking you from the basics to a thorough understanding of how popular Quantum algorithms work
00:15The first section covers all the essential mathematics, and the second section is a deeper exploration into the mechanics of quantum computers
00:22You'll learn why quantum computers are so powerful and how they're poised to transform technology
00:29Michael from Quantum Source created this course, if you were to search
00:37Up on Google, "M quantum computers," you would get answers in the form of analogies, like quantum computers use Q-bits that are both zero and one at the same time
00:44When I first started learning about quantum computers, these analogies and explanations never made sense
00:51This course was created in order to provide a solid foundation on quantum computation without using analogies, but teaching how quantum computers actually work
01:03Let's quickly look at the structure of this course
01:09The first section of this course goes through the basic mathematics needed to understand the rest of the course, including an Introduction to complex numbers and basic linear algebra, in the next section, we'll explore what a qubit is and how we can represent them mathematically
01:24We also explore some single qubit operations and discuss some of their properties
01:31The third section introduces how we can represent multiple qubits mathematically and explore some operations we can perform on multiple qubits
01:38This section ends on exploring the strange quantum phenomena of quantum entanglement and phase kickback
01:45In the final section of this course, we use everything we have studied up until this point to analyze quantum
01:50Algorithms, this section showcases why quantum computers are such revolutionary technology
02:03Let's start with understanding imaginary and complex numbers, but before that, we need to consider the square roots of numbers
02:09Let's say we have the equation x^2 is equal to 4, which means X is equal to plus or minus 2, easy
02:16But what if x^2 is equal to -4? Since a number squared is always greater than zero, how can X squared ever be a negative number? This is where imaginary numbers come in
02:22If we let I be the square root of -1, we can then write the square root of -4 as plus or minus 2I
02:41This is an imaginary number, any number that contains a factor of the square root of -1
02:46Or, now we move one level up to complex numbers
02:55All a complex number is, is a number that contains a real number plus an imaginary number
03:04A standard complex number looks like this: a + iB, where both A and B are real numbers, a being the real part of the number, and B being the imaginary part of the number
03:13Complex numbers may not seem very useful, but in the next lesson, we will see how we can represent complex numbers in another form, which is used to model Quantum Computing States
03:20We can add and subtract complex numbers pretty easily; all we do is add or subtract the real parts and the imaginary parts
03:33Pause the Video and try adding up these complex numbers
03:45Multiplication is pretty simple as well, but we must remember that before we get I squared, that becomes -1, since I is the square root of 1
04:09The complex conjugate of a complex number is when you take the complex number and flip the sign or negate the imaginary part
04:13This is denoted by an asterisk
04:18Here are some examples
04:22One cool property of complex numbers is if we multiply any complex number by its complex conjugate, the result is always a real number
04:29Try multiplying 2 + 3I with 2 - 3I and confirming this is the case
04:42We can think of a complex number as a vector where we have the Real axis on the horizontal and the imaginary axis on the vertical, this allows us to graph our complex numbers
04:49For example, the complex number -2 + 3i would be a vector that would end at the point -2, 3
05:01When we represent a complex number on the number plane like this, we also uncover another property, its magnitude, which is its distance from the origin
05:12This is denoted with vertical lines and is calculated by using Pythagoras's Theorem, so we get that the magnitude of some arbitrary complex number A + i is equal to the square root of a^2 + b^2
05:28Pause the video and see if you can find the magnitude of 4 - 3i
05:34This is
05:41Not the only way of representing complex numbers, instead of using real and imaginary parts as coordinates, we can represent them through their magnitude and the angle they make with the positive x-axis
05:47Using trigonometry, we find that we can also represent complex numbers in the form r cos theta plus i sin theta, where r is the magnitude of the complex number and theta is the angle it makes with the positive x-axis
06:05We can find theta by using the tan function, as tan of theta is equal to b/a, so theta is arctan of B of A
06:10This is called polar form
06:15There is also one other form, which is r e to the power of i theta
06:20This form is Exponential form, pause the video now and try to convert the complex number 1 + I into polar form, then into exponential form
06:34In quantum computing, we almost exclusively use complex numbers in exponential form
06:49This is because of the property that when we change theta, we rotate around a circle, so multiplying two complex numbers in exponential form whose magnitude is one, graphically, we are rotating around a unit circle as the angles of the two complex numbers add together
07:03You will see, once we start studying quantum computing, that this property is very useful in representing quantum states
07:12A matrix is A 2D arrangement of numbers
07:21In the next lesson, we will get to the applications of matrices and how they relate to quantum computing, but in this lesson, we will quickly define some properties and operations we can do on them
07:30We say we have an M by N matrix if the number of rows is M and the number of columns is N, so this matrix here would be a 2x3 matrix
07:44Pause the video and see if you can find out the dimensions of these matrices
07:52If we want to add two matrices together, all we need to do is add each element of the matrices
07:58This is the same for subtraction
08:04Note that we can only add and subtract matrices if the number Of rows and columns is the same for both, so we wouldn't be able to add these two matrices
08:10Pause the video and see if you can add these matrices
08:17We can also multiply matrices by a scalar
08:24If we do, each element in the matrix gets multiplied by the scaler, giving us another matrix
08:36When multiplying matrices, we have to do this weird operation where to get the element in the first column and first row, we take a sort of dot product with the first row of the left matrix and the first column of the right matrix, then to get the second column, first row, we take the dot product of the first row of the left matrix and the second
09:01column of the right matrix, we continue this process until we have all the elements in the new matrix
09:21Pause the video and try to complete this matrix multiplication
09:44It's important to note that we can only multiply two matrices together if the number of columns of the first matrix is the same as the number of rows in the second matrix
09:51For example, we can't multiply these two mates here, since the first one has two columns, but the second one has three rows
10:05If we have an n by one matrix, we call it a column vector
10:09We can graph these like any other vector
10:13These are useful as one of the ways we can represent a state of a Quantum computation is through a column vector
10:18It turns out that when we multiply a matrix with a column vector, we get another column vector
10:30Intuitively, what is happening is the column vector is getting transformed by the matrix, so we can use matrices as transformations on a vector
10:37Here are some examples graphically
10:50As you will see in the quantum computing sections, we do the same process of applying matrices to our quantum state to apply operations on qu computers
10:56We also have a special matrix called an identity matrix
11:03This matrix is all zeros except for the main diagonal that has all ones
11:08If we Multiply the identity matrix by any matrix, we get back the original matrix
11:14Verify this is true by multiplying the two-dimensional identity matrix with this matrix, and check to make sure you get back the original matrix
11:27Matrices also have what's called an inverse, that when multiplied with the original matrix, gives us the identity matrix
11:32We denote this with a -1
11:38Graphically, this means that if we have a matrix A, and we apply it to a column vector 1, 1, if we then apply the inverse of A, we land back on the point 1, 1
11:45Therefore, applying A than A inverse is the same as applying the identity matrix, which means The column vector stays in the same spot, as we saw previously
11:55With complex numbers, we can also take the complex conjugate of a matrix
12:06This is denoted by the asterisk on the top right of the matrix, just like with complex numbers
12:16When we apply this, we flip the sign of all the imaginary components of all the elements in the matrix
12:27Pause the video and find the complex conjugate of this matrix
12:35We can also do what we call the transpose of a matrix
12:44This is denoted by the T and involves exchanging its rows with its columns
12:53If we combine these two and find the complex conjugate and transpose of a matrix A, we get Something called a dagger, denoted by the dagger symbol
12:58What was the point of all this? In quantum computing, we use two types of matrices to apply our operations
13:03One of them is unitary matrices
13:10These have the property that given a unitary matrix U, U * U dagger is equal to the identity matrix, so U dagger is its inverse
13:22Geometrically, when a unitary matrix acts on a vector, the length of the vector stays the same, but it is rotated or flipped
13:27This property may not seem very useful, but once we start talking about probabilities in quantum computers, it will all start to make sense
13:34The other type of matrix we use to Apply operations in quantum computing is the Homan Matrix
13:42These matrices have the property that, given a Homan Matrix H, H is equal to H dagger
13:47As you go through the quantum computing sections of this course, you will start to understand why we use these types of matrices to perform operations on quantum computers
14:07Sometimes, when we apply a transformation to a vector, the vector stays in the same direction, but just gets stretched or compressed, meaning that we can factor out a scalar and get back that same vector
14:20When this happens, we call the vector an igen vector of the transformation matrix that we applied, and the scalar we factored out, an eigenvalue
14:30Let's go through an example
14:41If we have the matrix 2 0 1 2 with the vector 0 3, applying the matrix on the vector gives us the vector 0 6
14:47With this, we can factor out a two, leaving us with two times the vector 0 3
14:54This gives us an eigenvalue of two with the eigenvector 0 3 for that matrix
15:00Classical computers use binary zeros and ones to store and process their data
15:04Quantum computers, on the other hand, use Q bits, or quantum bits, which can be zero and one at the same time
15:08We have all heard this explanation of quantum computers, but what does that actually mean in order to
15:13To understand what a quantum computer is actually doing, we must look at how we represent them mathematically
15:19Instead of using binary like classical computers, quantum computers use qubits
15:26Physically, a qubit can be any quantum particle that exists in two distinct states, such as a photon of light being polarized either horizontally or vertically
15:38Just like classical computers, we still use zeros and ones, but in quantum computation, we define them instead as the column vectors 1 0 and 0 1 respectively
15:43The weird brackets around 0 and 1 is Dirac notation, we will look more into it later
15:57You may have heard Of the term superposition, what it means in quantum mechanics is that a quantum particle is in two states at the same time
16:02So back to our photon polarization example, this means that the photon is both horizontally and vertically polarized at the same time
16:15In terms of quantum computing, we say a qubit is in superposition if it is both zero and one at the same time
16:21Let's look at how we represent qubits mathematically
16:26Mathematically, we can represent a qubit as a column vector with two elements
16:32The top element indicates how much the qubit is in the zero state, and the bottom element indicates how much the qubit is
16:39In the one state, the convention for a quantum state is to set it equal to the Greek letter psi
16:45We'll talk more about this in the next video, so if we have a qubit in the state 1, it now makes sense why this is zero, since it is all in the zero state and none in the one
16:52We can say the same for Q bit in the state 01 being one
17:00If a qubit is in both the zero and one state, so it has nonzero numbers in the matrix, then we say it is in a superposition of 0 and 1, since it is both of the states at the same time
17:14So now we know how to represent a qubit mathematically, but how do we measure the qubits? For that, we must look at another rule of quantum
17:21Mechanics, when we measure a quantum system, it changes the state of the system to the measurement
17:28What does that mean? If we go back to our photon polarization example, if the photon is in a superposition of both horizontally and vertically polarized, then when we measure it, we will only measure it as one or the other, but not both
17:36And once it has been measured, it collapses into the state we measured
17:45So if it was in a superposition and we measure it to be horizontally polarized, it would collapse and become horizontally polarized, meaning it is not in a superposition anymore
17:54The same thing happens when we measure Q bits, we can only measure a zero or one
17:59We do not measure how much the Q bit is in the zero state, or how much the Q bit is in the one state
18:05Immediately after measuring a Q bit, its state changes to either zero or one, depending on the measurement
18:12So what is the point in those numbers telling us how much the Q bit is in the zero state or the one state? What those numbers tell us is the probability of measuring a 0 or 1
18:30The probability of measuring zero is the magnitude squared of the amplitude of the zero state, and the probability of measuring one is the magnitude squared of the amplitude of the one state
18:44So for This example, qubit, when we measure it, we have a 75% chance of measuring a zero and a 25% chance of measuring a one
18:50If we now think about how we defined the zero and one state at the start of the lesson, they should now start to make sense
18:58We stated that zero was the column vector 1 0, and now we can see why the probability of measuring zero is 1, so will always be measured as zero
19:12This is the same for the one state, since there are only two possible outcomes when measuring a Q bit, the probability of measuring a zero plus the probability of measuring a one must equal one, giving us this equation, so this would be a valid qubit state
19:31Since the probabilities add up to one, but this would not be, since the probabilities add up to more than one, when we do measure a qubit that is in superposition, it collapses into the measured state
19:39So if we measure this state to be zero, it collapses into the zero state, so every measurement after will be zero
19:51This is because of the laws of quantum mechanics, when we measure something, it permanently changes the state of the system to that measurement
20:09Normally, when we are mathematically representing a quantum state of a quantum computer, instead of using matrices, we use a specific notation called Dirac
20:16notation to see how this works, let's convert an arbitrary Qubit State Alpha Beta into Dirac notation
20:26All we need to do is turn the matrix into the sum of two matrices, and then factor out the Alpha and the Beta
20:34Now, if you look at the column vectors, they are the zero and one states, as we saw in the previous lesson
20:40This gives us a linear combination of the zero and one states
20:47Those brackets around the 0, 1, and S are called Kets
20:54All they tell us is that 0, 1, and S are quantum states
20:59Pause the video and convert this Qubit state from matrix to Dirac notation
21:09This notation might seem weird at first, but it is the Conventional way of writing a quantum computing state, since when we start adding more Q bits, using matrices to represent them becomes unmanageable, as we start to get very large matrices
21:18We can represent a qubit graphically on what is called a Bloch sphere
21:28On the top, we have the zero state, and on the bottom, we have the one state
21:37On the horizontal, we have the plus state, minus state, I state, and negative I state
21:43We will discuss these in later lessons
21:49The closer up the qubit is to the zero state, the higher probability of measuring a zero, and the same goes for the one state
21:57That means that if we have the state 1 on < tk2
22:061 on √2, it will lie halfway between the North and South Poles, since it has an even chance of being measured as zero or one
22:14You may notice that since it is a sphere, the qubit can spin around the sphere, this is called phase
22:21We will talk about this in later lessons
22:27Right now, it is important to understand the basic idea that the higher up the qubit is, the more likely we are to measure a zero, and the lower the qubit, the more likely we are to measure a one
22:34Pause the video and think about where the state 1 on 2, √3 on 2 will be on the Bloch sphere
22:48The qubit 1 on 2, √3 on 2 would be halfway between the Equator and the one state, since It has a one on four chance of being measured as a zero, and a three on four chance of being measured as a one
22:59With classical computers, we use logic gates to process data
23:10With quantum computers, we still use gates to change the states of our cubits, but they are a little bit different to your usual logic gates
23:21The most common single Cubit gates are the X, Y, and Zed Gates
23:26Let's first look at the X gate
23:30If we have a Q bit in the zero state and apply the X gate to it, it flips to the one state
23:34Let's try a Q bit that is halfway between zero and one, try and see if you can figure out what the X gate is doing
23:41Let's try a Q bit in this state, as you can see
23:48The X gate flips the qubit 180° or Pi radians around the X-axis
23:55Now, let's have a look at the Y gate
24:01Here are some examples of the Y gate transformation
24:08As you can see, it does the same thing as the X gate, but instead, it rotates the qubit state 180° or Pi radians around the Y axis
24:20Lastly, we have the Z gate, which rotates the qubit 180° or Pi radians around the Z axis
24:30Since these gates rotate the qubit around the specified axis by pi radians, if we apply the same gate twice, one after the other, then the qubit returns to its original position
24:37This means that these three gates are their own inverses
24:45We can represent These gates as matrices, here are the matrices for these gates
24:51For the moment, ignore the complex numbers in the Y gate
24:56We will explain this later in the next lesson when we talk about phase
25:01Mathematically, to apply a gate to a qubit, we can multiply the matrix that represents the gate with the column vector of the qubit
25:13Pause the video and prove that applying the X gate to the zero state gives us the one state in Dirac notation
25:25If we want to apply a quantum gate, we still use the matrices, but instead of using matrix multiplication, we look at the columns of the matrix, the first column of the matrix
25:36Indicates the column vector the zero state becomes after applying the gate, and the second column indicates the column vector the one state becomes
25:43Then we can factor out both our zero and one states again to get back into direct notation
25:56Also, since quantum gates are linear, if we apply an arbitrary gate U, that gate acts on each of the superposition states individually
26:03Let's look at an example of applying a gate in direct notation
26:11If we want to apply a Y gate to this state in direct notation, the Y gets distributed into the state, then the Y changes the zero state to the first column of the matrix and the one
26:24state to the second column of the Matrix, then we can factor out the I and the negative I, the column vectors once again become the zero and one States, leaving us with this state
26:42With this, pause the video and prove that applying a Zed gate to a qubit in the state Alpha 0 plus beta 1 gives us the state Alpha 0 minus beta 1
27:04Looking at this, you may be thinking what is the point of the Zed gate? This Q bit still has an alpha square chance of being zero and a beta Square chance of being one, it didn't affect their probabilities
27:13In the next lesson, we will finally bring complex numbers into Quantum Computing with an
27:23Introduction to phase on the Bloch sphere, we saw in the previous lessons that we could also rotate around the Zed AIS
27:32This is called phase
27:40It may not seem very useful, as the probability of measuring a zero or a one is still the same, no matter how much we rotate around, but phase is what makes quantum computers as powerful as they are
27:46We will get into the uses of phase in the next lesson
27:52In this lesson, we will see how we can represent phase mathematically
27:58To represent phase, we have to bring back our old friend, complex numbers
28:03In Quantum Computing, we mostly use complex numbers in exponential form
28:08You will now See why, but first, let's consider some states in the Bloch sphere
28:14Let's first consider the states 1 over √2 |0⟩ + 1 over √2 |1⟩
28:22If we apply a Z gate, we get it to the state 1 over √2 |0⟩ - 1 over √2 |1⟩
28:30As you can see, the one state was multiplied by a factor of -1, and the qubit rotated π radians around the Z axis
28:37If we represent the -1 as a complex number in exponential form, we get e to the iπ
28:43Notice how the angle of the complex number is pi radians
28:48Let's try another example
28:52Let's plot the state 1 over √2 |0⟩ + 1 over √2 |1⟩ and 1 over √2 |0⟩ + i over √2 |1⟩
28:57If we represent i as a complex number in exponential form, we get e to the iπ/2, and if you look at The Bloch sphere, to get that state, we rotate Pi/2 radians around the Z axis
29:17We use complex numbers in exponential form in quantum computing, since it gives us a nice mathematical way of rotating around a circle by changing the value of f, by multiplying the one state of the qubit with the complex number e to the I
29:31We rotate the qubit around the Z axis by five radians, but why is it the one state and not the zero state being multiplied by the complex number? There are two types of phase: global phase and relative phase
29:49Global phase is when the entire qubit is multiplied by a complex number, and relative phase is when Just the one state is multiplied by a complex number
29:54It turns out the global phase is physically irrelevant, so the state e to the I * 1 < tk20 + 1 < tk2 1 is logically equivalent to the state 1 < tk2 0 + 1 < tk2 1
30:03Relative phase, on the other hand, is extremely important and matters in our calculations
30:12Relative phase is when the amplitude of the one state has a factor of a complex number
30:21As we saw earlier, having relative phase rotates the Qubit on the Bloch sphere around the Z axis, but what if we have a complex number in both the amplitudes of the zero State and the one state? What we do is we factor out the complex number of The zero state from the entire qubit, creating a global phase and relative phase, then we can discard the global phase, leaving us with a qubit with a relative phase
30:45We saw previously on the Bloch sphere that phase does not affect the probability of measuring a zero or a one, as the qubit stays the same distance from the zero state and the one state, no matter how far we rotate around the Bloch sphere
31:01If we look at an arbitrary qubit state, alpha 0 plus e to the i5 beta 1, the probability of measuring a one is the magnitude of e to the i5 beta squared
31:12We can split the absolute values up like this, the magnitude of e to the II is 1
31:23Since the coefficient of the complex number in exponential form states its magnitude, so the probability of measuring one is still the magnitude of beta squared
31:34In the next lesson, we will see why relative phase matters
31:46Before we discuss perhaps the most important gate in quantum computing, we will quickly revisit the Bloch sphere
31:51In earlier lessons, we saw that on the equator, we have four states: the plus state, minus state, I state, and negative I state
31:58Now that we know about phase, we can define these states
32:04All they are is a shorthand for commonly used states, since they all lie on the equator of the Bloch sphere
32:10They all have an even chance of being measured as zero or one, but each one contains a different relative phase
32:17The plus state is the state 1/√2 0 + 1/√2 1
32:21The next state is the minus state
32:26This is the same as the plus state, but with a relative phase of -1
32:30The I state has a relative phase of I, and the negative I state has a relative phase of negative I
32:45Now let's look at the Hadamard gate
32:53Here is the matrix for the gate
33:02If we look at how the gate acts on a qubit on the Bloch sphere, we see that the zero state gets transformed into the plus state, and the one state gets transformed into the minus state, applying a Hadamard
33:07Applying a Hadamard to the plus state gives us the zero state, and applying a Hadamard to the minus state gives us a one state
33:12This means that the Hadamard is its own inverse
33:17If we wanted to apply a Hadamard gate to an arbitrary qubit state in Dirac notation, we can replace the zero with the plus state and the one with the minus state, and expand
33:24The Hadamard gate shows that phase matters
33:31If we apply the gate to the plus state, we get zero, and to the minus state, we get one
33:39These states only differ by a relative phase, but after applying the gate, they are different, even though initially they both had a 0.5 chance of being measured as
33:50Zero and a 0.5 chance of being measured as one
34:02In the fourth section of this course, we will start to look at some quantum computing algorithms, and you will start to see why the Hadamard gate and phase is so powerful
34:13Now that we understand relative phase, let's introduce two new gates, the S and T gates
34:20The S gate adds a relative phase of Pi on 2 radians
34:26The T gate adds a relative phase of Pi on 4 radians
34:31If we take the conjugate transpose of the two matrices of the two gates, we get their inverses
34:36For the S gate, we can see that applying S dagger adds a relative phase of negative pi on 2, which is the inverse of the S gate
34:49Means that if we apply an S gate, then an S dagger gate, we are back in the same spot, meaning the S dagger gate is the inverse of the S gate
34:54We also have the T dagger gate, which is the same thing as the S dagger, but adds a relative phase of pi over 4 radians instead, meaning it is the inverse of the T gate
35:17If we have multiple qubits, we represent them through the tensor product, for example, if we had two qubits in the zero state, then we would represent the state like this
35:28This is usually shortened to this, where we have the two zeros in the one ket vector
35:36If we wanted to represent two qubits in superposition, we can expand it
35:41Out like any other operation by multiplying the amplitudes of the states and using the tensor product on the zero and one states
35:46As you can see, now we have four states: the 0 0, 0 1, 1 0, and 1 1 states
35:59This makes sense since those are the possible combinations of zeros and ones we can have with two cubits
36:05Measurement works the exact same as before
36:12The probability of measuring 0 0 is the magnitude squared of the coefficient of the 0 state, and so on
36:18Here is an example of combining these two cubits
36:26If we want to add another q bit to the system, all we need to do is tensor it onto the end of the state
36:35We also have some
36:45Shorthand notation you will sometimes see, if we have n zeros, we can write it like this, which means 0 tensed with itself n times, so this state would be shorthand for five ones
36:55This represents an iteration of qubits is great, but what if we wanted to apply a gate to a certain qubit? How would we indicate that we wanted to, let's say, apply an X gate to the second qubit in this state? For this, we use a diagram called the quantum circuit
37:03Here is an example of one
37:11On the vertical, we have the qubits, each line representing a singular qubit
37:18The states on the left are the initial states of the qubits, the boxes are the quantum gates, and the letters
37:29On the boxes are the type of gate we are applying, for example, this is an X gate
37:34These boxes are measurements and represent us measuring the Cubit
37:38The horizontal is the order in which we apply the gates
37:43We start from the left and go to the right
37:48Sometimes you will also see size states pointing to different points in the circuit
37:53These are used to represent the state of the system at different points during the algorithm
37:57Let's go through this circuit
38:01At S Sub 0, we have the state 001
38:05Then at SI sub one, we apply an X gate to the second Cubit
38:09At SI sub 2, we apply a Hadamard gate to the second Q bit, giving us this state
38:23At S Sub 3, we apply an X gate to both the first Cubit and the third Cubit, giving us this state
38:29Then, at size sub 4, we measure the cubits, so we will get one of these states with these probabilities
38:36Now, let's introduce some gates that act on multiple Q bits
38:43The most common multi-bit gate is the C not, or controlled X gate
38:50Here is the gate on a Quantum circuit
38:55The gate acts on two Q bits
38:59One of the Q bits is called the control Q bit, and the other is called the target Q bit
39:03The C not gate applies an X gate to the Target Q bit if the control Q bit is a one, and does nothing if the control is a zero
39:15Let's look at the C not gate acting On some states, if we apply a CNOT to this state with the first Q bit as the control and the second Q bit as the target, then we apply that CNOT gate to each of the superposition states, giving us this state here
39:31Here is another example
39:37We also have the Toffoli gate
39:43This gate is very similar to the CNOT, but instead, it has two control qubits
39:49Here it is on a quantum circuit
39:58If we apply a Toffoli gate to this qubit state with the second and third cuq bits as control and the fourth qubit as the target, we get this state
40:10It turns out that we can use senal gates to create controlled versions of single qbit gates, so we also have Controlled Y, Z, S, T, and Hadamard Gates, they act the same as the C not flying the gate if the control is one, and does nothing if the control is zero
40:30We represent these on a Quantum circuit like this, with the regular gate box, but with a line going out to the control CU bit
40:38For example, here is the controlled ES gate on a Quantum circuit where the second qbit is the control, and the first is the target
40:57Now that we have multiple cuq bits, how do we measure a single cuq bit? Let's say we have two cuq bits in this state, and we wanted to find the probability of measuring the second Cubit as a one, we do this by looking at all the Superposition states where the second Q bit is one, then summing up the probabilities of measuring those states
41:11Let's do an example
41:25If we wanted to find the probability of measuring a zero in the first Q bit, then we sum the probabilities of measuring each of the states where the first Q bit is a zero
41:39But how do we know what the state collapses to once we measure a Q bit? Remember, once we measure a Q bit, it collapses its superposition and becomes the measurement
41:46Let's look at an example
41:54Say we have this state, and we measured the first Q bit to be a one, then the state collapses, and since the first Q bit becomes A one, we get rid of all the superposition states where the first Cubit is not a one
42:05Remember, the probabilities must add up to one, but we have just removed some states, so the probabilities will be less than one
42:20We fix this by multiplying the state by what we call a normalization constant, let's call it A
42:25Now, we can normalize the state by using the identity that the probabilities must add up to one
42:30This gives us values for A, so if we measure the first CU bit to be one, the state collapses to this state
42:37We can use these techniques with any number of cubits
42:43Let's go through an example with three cubits, let's say we have
42:49This state, and we measure the middle qubit to be zero, the state collapses like this, collapsing into this state
42:58Let's consider this quantum circuit
43:06At S sub 0, we have the state 0 0
43:15Then at S sub 1, we have the state 1 on √2, 0 plus 1 0
43:23Let's distribute the zero state into the equation, giving us the state 1/√2, 0 0 + 1 0
43:31Now, at size sub 2, we apply a CNOT with the first qubit being the control and the second being the target
43:38This means that the 0 0 state stays the same since the control is zero, but for the one zero state, the control is one, so the second qubit flips to a one
43:50This leaves us with the state 1/√2, 0 0 + 1 1
43:56Can you Notice anything weird about this state? If we were to measure one of the qubits as a zero, the other would collapse into a zero, and if we were to measure a one, the other would collapse to a one, so without even looking at both the qubits, by measuring one of them, we immediately know the state of the other qubit
44:07This is called entanglement
44:18There are many different entangled states
44:29We say a state is entangled if it cannot be factored into the tensor of single qubit states
44:35For example, this state is not entangled, since we can factor it like this, but this state is entangled, since we cannot factor it into singular
44:42Qubit States, what this means is that when the qubits are entangled, they depend on each other to determine their state
44:54There are two types of entangled States: maximally entangled States and partially entangled States
45:00We say qubits are maximally entangled if measuring one of the qubits tells us the state that the other Q bits are in, so the example entangled state from the beginning, 1 on < tk2 0 0 + 1 1 is maximally entangled
45:18Here are the common maximally entangled States with two qubits
45:25We call these states the Bell States, and we denote them with capital fi and S
45:36We say qubits are partially entangled if the Measurement of a qubit affects the probabilities or phase of the other qubits, for example, with this state, if we measure the first qubit as zero, the state collapses to this, but if we measure the first Q bit as a one, then it collapses to this state
45:55As you can see, the two states have different probabilities of measuring zero or one, so this state is partially entangled since measuring one qubit affects the probabilities of the other
46:20Another quantum property we can use is something called phase kickback
46:24To understand how this works, let's consider this circuit
46:28As you can see, we have a Q bit in the plus
46:31State and another q bit in the state V, we also have an arbitrary controlled U operation
46:36Let's say that V is an igen state of U, so if we apply the U gate to the state V, we get e to the I Theta V, since all I values of quantum computers can be represented as e to the I Theta
46:45Now, at sub one, we have the state plus V
46:53Let's expand the plus state and distribute the V state into the plus state
47:02At S Sub 2, we apply the controlled uate; nothing happens to the first superposition state, since the control is a zero, but the second superposition state has the gate applied to the V state, since the control is a one
47:13We can now factor back out the
47:24V state from the equation, can you see what has happened? V is unchanged, even though it was the target qubit, and a factor of e to the i-theta has been applied as a relative phase to the control cubit
47:36This occurs if V is an eigenstate of the gate you are applying
47:41We call this phenomenon phase kickback, and it is used in some quantum algorithms
47:48Let's have a look at superdense coding
47:56This quantum protocol allows us to send two bits of classical information with only one cubit
48:03To do this, we need entanglement
48:09We'll say that the person sending the cubit is Alice, and the person receiving this cubit is Bob, to start off with
48:16Alice and Bob maximally entangle two qubits, so they are in this state
48:19Alice takes one, and Bob takes the other
48:23We will say that Alice takes the left qubit, and Bob takes the right qubit
48:29Then Alice and Bob take those qubits with them
48:35Now, when Alice wants to send two bits of classical information to Bob, depending on which two bits of information Alice wants to send, she performs some operations on her qubit
48:41If Alice wants to send the two classical bits 0 0, she does nothing and sends her qubit to Bob
48:54If Alice wants to send 0 1, she applies an X gate to her qubit, transforming the qubits to this state, then she sends her qubit to Bob
49:00If Alice wants to send one, she applies a Z gate to her Q bit, transforming the Q bits to this state, then she sends it to Bob
49:07Lastly, if she wants to send one one, she applies both an X and Z gate to her cuit, giving us this state
49:13She then sends her Qbit to Bob
49:20Now Bob has both the cubits in one of these four states
49:27He now applies a C not with the first Cubit as a control and the second as the target, giving us these states
49:33Then he applies a Hadamard gate to the left key bit
49:37This gives us this state that Alice wanted to send
49:40All Bob now has to do is measure the Q bits, and he will get the two bits Alice intended to send, as you can see
49:44With quantum computers, we can send two bits of classical information by sending one Q bit
49:52This works since there are two entangled Q bits in the entire system
50:08Before we look at how we can apply functions on quantum computers, we will quickly look at how classical computers perform operations on bits, and how we make classical operations reversible
50:20There are four main operations we can perform on classical bits: the AND, OR, NOT, and exclusive OR operations
50:24Let's go through each one of them quickly
50:29The simplest is the NOT gate, which flips 0 to 1 and 1 to zero
50:33Here is the truth table for the gate where X is the Input and F of x is the output
50:39As you can see, this gate acts on one bit
50:44Now let's look at the AND gate
50:48Here is the truth table for the gate
50:53The operation acts on two bits and returns one if the two bits are one, and zero otherwise
50:57The OR gate acts on two bits as well
51:00If either of the bits is a one, or both are one, then it returns one, otherwise it returns zero
51:04Lastly, we have the exclusive OR gate
51:09Here is the truth table for the operation
51:13As you can see, it returns one if either of the inputs is one, and returns zero if both the bits are zero or one
51:18We use the exclusive OR operation to reversible classical gates
51:26We say a function f is Reversible, if given F of x, we can determine the value of x, so if we are given the output, we can determine the input
51:39So this function here, where we negate the second bit, is reversible, since each row of the truth table for this function is unique, so we can map each output to a unique input, but the OR operation, on the other hand, is not reversible, since if we get an output of one, we cannot say what the input was
51:59It could have been any of these three inputs
52:05To make any classical gate reversible, we must input another bit, let's call it C, and instead of only returning F of x, we return the input X, as well as C exclusive OR with F
52:12Of, this makes the operation reversible
52:19Let's look at converting the OR gate to a reversible operation
52:23Here is a normal OR gate, and here is a reversible OR gate
52:28As you can see, we input another bit C and return it exclusive OR with the output
52:32Now, looking at the truth table, each row of the outputs is unique, so the gate is reversible since we can determine the input from the output
52:48What is the point in all this? Well, with quantum computers, all operations besides measuring the qubits must be reversible
52:53This is because every operation must be unitary, if you remember from the first section of this course, unitary
52:58Matrices rotate and flip a vector, so they must be reversible
53:06In the next lesson, we will discuss how we can apply functions on quantum computers using the same techniques that we used to make reversible classical gates
53:22We discussed in the previous lesson how we can make classical gates reversible
53:27Now, let's use this same technique to make quantum functions
53:32Since the operations we perform on quantum computers must be reversible, if we wanted to apply a function on a quantum computer, the function must be reversible
53:39To do this, we use the same techniques for making classical gates reversible, a standard
53:45Quantum function looks like this, where we input X and Y and get back X and Y exclusive or with f of x
53:57Now, you might be thinking, how are we going to get the output if it is exclusive or with Y, but if we set Y to zero, then we get zero exclusive or with f of x
54:04Zero exclusive or with any bit gives us back that bit
54:11This means that zero exclusive or with f of x is just f of x
54:18This allows us to query the function and get its output on a quantum computer
54:24We can encode functions within a unitary matrix, and so it is a valid quantum gate
54:30We usually denote a function f as U sub f, so overall, if we apply a function f to the state x0, we get the State X, F of X, then to get the function output, we can measure the second register of qubits
54:43Let's see what happens if we apply a function F to this state with the output register being the minus state
54:55First, let's rewrite the minus state like this and distribute the X state into the superposition
55:01Since the function is a unitary operation, it gets distributed into the superposition like any other gate
55:08Then it acts on each of the superposition states individually, applying U sub F, we get this state
55:14The zero exclusive OR with F of X becomes F of X, and the one exclusive OR with F of X becomes not F of X
55:21Now let's consider
55:27Two scenarios: if f of x is equal to 0, then the state becomes 1 / √2 (x0 - x1), which we can rewrite as x minus
55:34On the other hand, if f of x is equal to 1, then the state becomes 1 / √2 (x1 - x0)
55:40We can factor out the -1, leaving us with the state -1 / √2 (x0 - x1)
55:46This can be further factored into x minus
55:53Now, looking at these two states, we can see that the only difference is the phase at the front
56:01We can combine these two equations into -1 to the power of f of x x minus
56:09So, if we apply a function to the state x minus, we get back -1 to the power of f of x x minus
56:17When we query a function in this way, where the output bit is in the minus state, we call it a phase Oracle in the next
56:24In this lesson, we will finally see how quantum computers can outperform classical computers with Deutsch's algorithm, which uses this technique of the phase Oracle
56:36One more thing we will discuss when it comes to quantum computers is a theorem called the no-cloning theorem
56:42When we want to copy bits on a classical computer, all we need to do is read the values of the bits and write the values to other bits, but with quantum computers, if we have a qubit in an unknown state, say we have S is equal to Alpha 0 + beta 1, we cannot copy this state if we don't know Alpha and beta
57:01If we were to measure S, we would get 0 or 1, but to copy The state, we need to know the amplitudes, so we would need to know alpha and beta
57:12We could easily copy qubit states where we know the amplitudes by applying the needed gates, but if we do not know the state, we cannot copy a qubit
57:31Now, let's finally look at a quantum algorithm, Deutsch's algorithm, but first, let's look at the problem it solves and how we would solve that problem with a classical computer
57:36Say we have a function f that takes in a bit and returns a bit
57:43We don't know what the function does
57:46All we can do is send in a bit and read the output bit
57:50It is like a black box
57:54Our task is to find out whether the function f is
57:57constant or balanced
58:03If a function is constant, then it returns the same bit, no matter the input
58:08Here are the two constant functions that can act on one bit: constant one, which always returns one, and constant zero, which always returns zero
58:14Balanced functions, on the other hand, return zero for half the inputs and one for the other half of the inputs
58:25Here are the two balanced functions that can act on one bit: identity, which returns the input, and the NOT gate, which we saw before, which flips the bit
58:32As you can see, both these operations return zero for one input and one for the other input
58:38For this problem, we Don't care if the function is a NOT gate or a constant zero, we only care if it is constant or balanced
58:51If we wanted to find out if F is constant or balanced on a classical computer, we would first need to input zero and then input one to see if we get the same or different values
59:02If F of 0 equals F of 1, then we know that the function is constant, and if F of 0 does not equal F of one, then the function is balanced
59:08So we need to query the function twice, once with zero as the input and once with one as the input
59:20With quantum computers and Deutsch's algorithm, however, we only need one query of the function to find out if the Function is constant or balanced
59:24Here is the circuit for the algorithm
59:29The U of represents the function f
59:33At S Sub 0, the Q bits are in the state 0 0
59:38Then at SI sub 1, the cubits are in the state 0 1
59:43At SI sub 2, we apply a Hadamard to each of the cubits, leaving us with the state plus minus
59:48Let's expand the plus state and distribute the minus state into the equation
59:54Now at SI sub 3, we apply the unitary Matrix UF, acting as the function to the state
01:00:00Since all quantum operations are linear, UF gets distributed into the state and acts on each of the superposition states individually
01:00:11If we look at each of the superposition, States, they are in the phase Oracle form, so applying U of f to the first state becomes -1 to the ^ of f of 0, 0 minus, and the second state becomes -1 to ^ f of 1, 1 minus
01:00:28The minus qbit is not needed for the rest of the algorithm, so we will emit it to clean up the equation
01:00:46Now let's consider two different scenarios: if F of 0 equals F of 1, then the state becomes 1 / < tk2, 0 + 1; if F of 0 and F of 1 equal 0, or 1 / < tk2, 0 - 1; if F of 0 and F of 1 = 1, with this we can factor out a global phase of -1, leaving us with 1 < tk2, 0 + 1
01:01:03Therefore, if F of 0 equal F of 1, the state becomes 1 / < tk2, 0 + 1, or the plus State
01:01:09Now let's look at if F of 0 does not equal F of 1, so if F0 = 0
01:01:26And f of 1 = 1, the state becomes 1 / √2 (0 + 1)
01:01:32If F of 0 = 1 and F of 1 = 0, then the state becomes 1 / √2 (- 0 + 1)
01:01:39With this, we can factor out a global phase of -1, leaving us with the minus state
01:01:46So overall, if F of 0 equals F of 1, the state becomes the plus state, and if F of 0 does not equal F of 1, the state becomes the minor state
01:01:52See if you can finish the rest of the algorithm off yourself
01:01:58Now, at SI sub 4, we apply a Hadamard to the Q bit
01:02:05In the case where F of 0 equals F of 1, this transforms the state into zero, and in the case where F of 0 does not equal F of 1, the state becomes one
01:02:17Now all that's left to do is measure the Cubit, looking at our Equations, if we measure a zero, then the function is constant, since F of 0 equals F of 1
01:02:28And if we measure one, then the function is balanced, since F of 0 does not equal F of 1
01:02:33As you can see, what took a classical computer two queries of the function was done with one query of the function on a quantum computer
01:02:39In the next lesson, we will look at the Deutsch-Jozsa algorithm, which considers itself with the same problem of Deutsch's algorithm of finding out if a function is constant or balanced, but instead of having a function that only inputs one bit, the algorithm is a general case that accepts any number of bits as input
01:03:08The Deutsch-Jozsa algorithm considers itself with the same problem of Deutsch's algorithm, of finding out if a function is constant or balanced, but instead, this algorithm is a general case that can accept any number of bits as input
01:03:15Let's quickly revise constant and balanced functions
01:03:22Constant functions always return the same value, no matter the input
01:03:30Here are the two constant functions: constant zero and constant one
01:03:38Balanced functions return zero for half the inputs and one for the other half of the inputs
01:03:43Here is an example of a balanced function that takes in a bit string of length three, as you can see
01:03:51The function returns zero for four of the inputs and one for the other four of the inputs
01:03:57For a classical computer to solve this problem, it would need to query the function in the worst case, 2 ^ n - 1 + 1, where n is the length of the bit string the function takes as input
01:04:06This is because, in the worst case, we check half of the inputs and get the same output for all of them
01:04:14When this happens, we need to check one more input to determine whether the function is constant or balanced
01:04:21There are two to the N possible bit strings of length n, so 2 to the n minus 1 is half of the possible inputs
01:04:28Therefore, we need to check half + 1, so 2
01:04:36N-1 + 1 inputs in the worst case to be certain the function is constant or balanced, with a quantum computer, we only need one query of the function, just like Deutsch's algorithm, to determine whether the function is constant or balanced
01:04:46Here is a circuit for the algorithm
01:04:57This line here, going through the circuit, represents N qits, and the Hamod gates tensor N represent N Hadamard gates, each one being applied to one of the N cubits
01:05:02Let's go through the algorithm
01:05:07At S Sub 0, we have N z minus
01:05:13Then at S Sub one, we apply a Hadamard gate to each of the N zeros, giving us this state
01:05:21Let's quickly derive an identity that We frequently use, when applying Hadamard gates to a register of zeros, this gives us n plus states
01:05:32If we expand them out, we get 1/√2 (0 + 1) tensored with 1/√2 (0 + 1), and so on, n times
01:05:40Let's try different values of n to figure out how we can represent this mathematically
01:05:45If we have n = 2, we have the plus state tensored with itself
01:05:51Distributing the states gives us a state 1/√2² (00 + 01 + 10 + 11)
01:05:58We can represent the superposition states like this, with a sum over all bit strings of length 2x
01:06:03Let's try n = 3
01:06:09With this, we have the plus state tensored with itself three times
01:06:13Distributing gives us this state, we can once again
01:06:17Represent the superposition states as a sum of all possible bit strings of length three, and X resulting in this state
01:06:20We can generalize this and say that if we apply a Hadamard to each of the N zeros, we get 1 / √2 to the power of n times the sum of all bit strings of length n x
01:06:34This is a very important identity in quantum algorithms and is used in many algorithms
01:06:41If you think about it, this makes sense, since each qubit is in the plus state, it has an even chance of being zero and one, so every possible combination of zeros and ones will occur in the state and with equal probabilities
01:06:58Going back to size sub 1, we can now change
01:07:02This to our identity
01:07:06Now, at size sub 2, we apply the Oracle function
01:07:10Since the function acts on each of the superposition states, we distribute it into the sum
01:07:16Now, if you look at each of the superposition states in the sum, they are in the phase Oracle form
01:07:21Applying the function gives us the equation 1 / √2 to the power of n times the sum of all bit strings of length n - 1 to the power of f(x) x
01:07:36Let's omit the minus Q bit from the equation, as it is not needed in the algorithm anymore
01:07:41At size sub 3, we once again apply a Hadamard to each of the CU bits
01:07:47What this means is that for every bit in the bit string X, we apply a Hadamard gate
01:07:53You may be looking at this and thinking that we can use the formula we used before, but that one can only be used when the state is all zeros
01:08:00The X State can be any combinations of zeros and ones
01:08:06Let's quickly figure out how we can represent this mathematically
01:08:12For this, we can rewrite the Hadamard transform on an arbitrary bit XI as 1 / √2 (0 + -1 to the power of x i 1), since if XI is 0, it becomes the plus State, and if x i is one, it becomes the minus State
01:08:18Let's try X being a bit string of length three
01:08:24This gives us this state
01:08:30If we tend to the states together, we get this state
01:08:36Let's quickly add the exponents of the negative 1s as You can see whenever there is a one in the superposition state, that state is being multiplied by a negative one to the power of x sub i, where x sub i is the position of the one
01:08:52We can rewrite this as the dot product of X with the superposition state
01:08:57Now, we can combine this state as the sum of all Zs that are bit strings of length three, -1 to the power of X dot z z
01:09:12Generalizing, we get this identity where applying a Hadamard to an arbitrary bit string of length n, x, gives us 1 / square root of 2 to the power of n, times the sum of all bit strings of length n, -1 to the power of X dot z z
01:09:28This is also a very important identity that is used in many quantum algorithms with this
01:09:34The qubits are now in this state
01:09:43Let's now consider the amplitude of the all-zero state
01:09:52We find that it is 1/2^n times the sum of all bit strings of length n - 1 to the power of f(x) + x dotted with all zeros
01:10:02The x dotted with the all zeros becomes zero, so the state becomes this state
01:10:07Now, if the function f is constant, then the value of f(x) will be the same, no matter the input
01:10:14This means that if f(x) is equal to Z, the amplitude of the state becomes 1/2^n times a sum over all X's, 1
01:10:25Evaluating the sum, there are two to the end possible combinations of zeros and ones of length n, so the sum is 1 + 1 + 1 and so on, 2 to the power of n * this gives us 1/
01:10:392 to the power of n times 2 to the power of n, which equals 1
01:10:45On the other hand, if f of x is equal to 1, we do the same thing, giving us negative -1
01:10:50So if the function is constant, the amplitude of the all-zero state is plus or minus 1
01:10:55If the function is balanced, then half the inputs will result in zero, and the other half will result in one
01:11:00If we look at the sum, this means that there will be the same number of ones being added to the same number of negative ones
01:11:07This means the sum will be evaluated to zero
01:11:14So if the function is balanced, then the amplitude of the all-zero state is zero
01:11:18Now we measure the cubits
01:11:23Before, we saw that if the function is constant, then the Amplitude of the all zero state is plus or minus one
01:11:27That means the probability of measuring the all zero state is one
01:11:34If the function is balanced, on the other hand, then the probability of measuring all zeros is zero
01:11:39What this means is that if we measure all zeros, the function is constant, but if we measure anything else, the function is balanced, and we're done
01:11:46We have determined if the function X f is constant or balanced in a single query of the function
01:11:54The key takeaway from this algorithm are these two identities
01:12:01They will keep popping up again and again
01:12:08Let's now look at the Bernstein-Vazirani algorithm
01:12:15Here is The problem it solves, imagine we have a function f that takes in a bit string of length n and returns a single bit, which is a DOT product of the input with some secret string S modulo 2
01:12:22Our task is to find out what the secret string s is
01:12:31On a classical computer, the approach is to input a bit string of all zeros except for one in one position
01:12:37This allows us to get the value of one position of the bit string S, as all the zeros in the input will cancel out in the dot product
01:12:51This means that we must query the function n * when n is the length of s, since each query we get one value of s with quantum computers, on the other hand, we
01:12:57Only need to query the function once to find out what S is
01:13:03If we look at the circuit, it may look familiar
01:13:09It's the same circuit as a DOA algorithm, just with a different function being applied to the cubits
01:13:17Initially, the cubits are in the state n z minus
01:13:24Then at S Sub 1, the state is 1 / < tk2 the^ n * the sum over all X, where X is a bit string of length n x minus
01:13:32At S Sub 2, we apply the Oracle
01:13:37Since the target Q bit is in the minus State, we use the phase Oracle property, so the state becomes 1 / < tk2 to^ n * the sum over all x -1 to the^ of f of x xus
01:13:52Let's rewrite f of x as a dot product of X and S, since that is the definition of our function
01:14:00Let's also emit the minus qbit, since it is not needed anymore
01:14:07Now, we apply a Hadamard to each of our Q bits
01:14:12Let's distribute the -1 to the power of X do s into the sum
01:14:17We can now add the exponents, giving us the dot product of s s and X plus the dot product of x and z
01:14:22We can factor out the X, giving us s + z dotted with x
01:14:30The plus indicates bit wise exclusive or, so for each bit in s, we exclusive or it with the bit in Zed that is in the same position
01:14:42So the I position of S Plus Z is S Sub I exclusive or with Z sub I
01:14:46This gives us another bit string of length n
01:14:50Now, we measure the Q bits
01:14:53Let's look at the probability of measuring s expanding
01:14:57Out, we find the amplitude of the S state is 1/2 to the power of n times the sum over all X's, where X is a bit string of length n
01:15:09-1 to the power of s + S dotted with X, since plus indicates bitwise exclusive, or S + S equals all zeros
01:15:22Now, in the X exponent, we have all zeros dotted with X, this will equal zero, since all the zeros will cancel out all the X's at each position
01:15:29Applying the power means the state becomes 1 on 2 to the power of n times the sum over all X's 1, since there are two to the power of n bit strings of length n, there are two to the N possible values of X, so evaluating the sum, we get 2 to the power of n
01:15:40This leaves the amplitude of the S state as one
01:15:52This means That the probability of measuring S after applying the algorithm is one, and that is it
01:16:03After one query of the function, we can find S by measuring the qubits
01:16:11You may start to see the similarities between this algorithm and the others
01:16:20Applying a Hadamard to each of the qubits so that the state is in a uniform superposition, then applying the function, and once again applying Hadamards, is used in many algorithms
01:16:25In the next two lessons, we will look at the quantum Fourier transform, as well as quantum phase estimation
01:16:31These are both used within many quantum algorithms, including Shor's algorithm
01:16:36Let's Let's start with the quantum Fourier transform, or QFT
01:16:44Before we look at the maths and circuit behind it, let's look at how it transforms states on the Bloch sphere, so we can gain some intuition
01:16:50On the top, we have how we would normally represent a number in binary
01:16:57As you can see, each of the Q bits is either zero or one, and if we take those bits, we get the number
01:17:04Then underneath, we have the same cubits after the quantum 4A transform has been applied
01:17:09As you can see, instead of encoding the numbers like we normally do in a classical computer with zeros and ones, the numbers are now encoded by the phase of the Q bits that are in a
01:17:16Uniform superposition, as you can see, the left Q bit has two possible phase options, either zero or -1 relative phase, then the next Qbit has four possible phase options, and so on, up until the last Qbit, which has two to the N possible phase positions, where N is the number of Qbits
01:17:38In this case, the right CU bit has 2 to the 3, or eight possible phase options
01:17:44Depending on the number, the phase of the CU bits is different
01:17:51Let's see how the number five is encoded
01:17:57Once the quantum 4A transform has been applied, as you can see, the right Q bit has been rotated around the Z AIS 5/8 * 2 pi radians, which is 5 pi/4 radians to get
01:18:04The amount rotated around the Z axis of the next qubit, we multiply the previous one by two, so the next qubit has been rotated 2 * 58 * 2 piun radians, so rotating the cub > / 2 radians around the Z axis, the last one is 2 * that, which is 2 * > / 2 radians
01:18:31This means that if we have this state, which is five in binary, and we apply the quantum Fourier transform, we get this state
01:18:43In the next lesson, we will see a use of the quantum Fourier transform, but for now, let's look at the circuit
01:18:50Here is the Quantum Fourier transform circuit for any number of bits
01:18:53As you can see, there are two gates that we have not seen before
01:18:57This gate here is a
01:19:00Controlled R gate, we will define this gate with this matrix
01:19:03As you can see, this gate has a variable K, which we can set and affects the phase applied
01:19:09This gate transformed the bas of State 0 into 0 and 1 into e 2 Pi / 2 to the K 1, giving us a relative phase
01:19:21If applied to a q bit in super position, the controlled version, like we have in this circuit, is the same as all the other controlled versions of other gates, only applying the gate if the control is a one
01:19:35This other weird looking gate is called a swap gate, and it swaps the states of the two Q bits
01:19:40For this lesson, we will go through an example with three bits for this
01:19:44For example, we'll use the state J as an input to the algorithm
01:19:48We will label each one of J's bits like this, where each ji is either Z or 1
01:19:52To keep our equations tidy, we will look at each one of the cubits individually, then combine them at the end of the algorithm
01:20:04Let's start with finding out what j0 becomes after the Hadamard gate
01:20:10The state becomes 1 / √2 (0 + -1 to the power of J 01)
01:20:18We can represent this like this
01:20:25You will see why we keep the j0 / √2 and don't simplify the fraction at the end
01:20:31Then we apply the controlled R2 gate with J1 as the control
01:20:46We apply the R3 gate in the same way
01:20:55Now let's find out what J1 becomes after the Hadamard gate, the state becomes this state
01:21:00Then, after the controlled R2 gate, and simplifying like we did previously, we get this state
01:21:08Lastly, we apply a Hadamard gate to the J2 Cubit, leaving it in this state
01:21:15So, after this part of the algorithm, our state J is in this state
01:21:21Now, once we swap the qubits, the state changes to this, and we're done with the algorithm
01:21:27It may not seem like we did much, but we have in fact encoded the value of J into the phase of the qubits, just like we saw with the animation previously
01:21:38Let's quickly check this by making J the value of five, so 101 in binary
01:21:45If we now input the values into the Equations for the state, then we can see that the phases do match up to what we had previously discovered at the beginning of the lesson
01:21:50If we were to apply the quantum Fourier transform to an arbitrary basis state J, we get 1 / √2 to the power of n, times the sum from K = 0 to 2n-1, E to the power of 2π i j k / 2 to the n k, where n is the number of bits in J
01:22:16We also have the inverse quantum Fourier transform, and that undoes the quantum Fourier transform
01:22:22So if we add this state, which is the state where we encoded five using the quantum Fourier transform, if we now apply the inverse quantum Fourier transform, we get back to our state 101, the quantum phase
01:22:34The estimation algorithm allows us to find the eigenvalue of an eigenvector given the matrix, so if we have a matrix U and apply it to its vector V, since V is an eigenvector, we get e to the I Theta V, where e to the I Theta is the eigenvalue
01:22:46We can represent all eigenvalues in quantum computing in this form
01:22:59The QPE, or quantum phase estimation algorithm, finds e to the I Theta to a certain accuracy
01:23:11This algorithm is a key part in many quantum algorithms, including Shor's algorithm, which we will discuss in the next lesson, which allows us to find prime factors of large numbers
01:23:23Here is the quantum phase estimation circuit, as you can See, we have two registers
01:23:31The first one contains M zeros and is used to store the estimated phase, and the second one, V, is n cubits and is the IG Vector of the gate we're trying to measure the IG value of
01:23:45Looking at the circuit, you can see that the gate U, which we're trying to find the I value of, is to the power of some numbers
01:23:51U to the power of n is the same as applying U to a qit n
01:23:57Also, you can see we have the inverse Quantum fora transform at the end of the algorithm
01:24:04Let's start going through the circuit
01:24:11At S Sub 0, we have the state M Z's V, then at SI sub 1, we apply the Hadamard mod gates to all the Q bits in the first register at SI
01:24:18Sub 2, we apply the U gate to the Eigen vector V, with the rightmost qubit in the first register as a control
01:24:31Since V is the Eigen vector of U, phase kickback occurs, which adds a relative phase of E to the I theta to the qubit
01:24:39Then, at step 3, we apply two U gates, or the U squared gate, with the qubit in the first register as a control and V as the target
01:24:45Once again, phase kickback occurs, applying a phase of E to the I theta * a to the I theta, or E 2I theta
01:24:51We continue this process for each of the qubits in the first register, which leaves us with this state
01:25:04Now, we let theta equal 2 pi J, where J is a number between 0 and 1, since theta is an angle
01:25:12Between 0 and 2 pi, with this, if we find J, we can find Theta
01:25:19Substituting this in, we get this equation
01:25:26Now, since J is a bit string less than one, we can represent it like this, which converts it from a decimal in binary to a decimal in base 10
01:25:30If we now sub that into our equation, it becomes this
01:25:34Now, if we look at the first Cubit, we have a factor of 2 to the ^ of n minus 1
01:25:38If we distribute that into J, we get this
01:25:44Since all these terms are integers, when we expand them out, they will be a factor of 2 Pi, so they are not needed since they are redundant
01:25:51This leaves us with J m-1 / 2
01:25:59If we do the same process to the rest of the cubits, we are Left with this state, can you notice anything about this state? This is the same state as if we were to apply the quantum Fourier transform to the state J
01:26:11So when we apply the inverse Quantum Fourier transform, we end up with the state J
01:26:17All we need to do is measure the state, and we've approximated J to M bits
01:26:23Now with J, we can multiply it by 2 pi to get Theta, and then we can find the I value as e to the I Theta
01:26:34Now we will tackle probably the most important and popular Quantum algorithm, Shor's algorithm
01:26:46This algorithm allows us to find the prime factors of a large number, so if we have a number n equal to PQ where PQ are both Prime
01:26:57Shaw's algorithm allows us to find P and Q
01:27:05This may not seem very useful, but this is the backbone of RSA, which is a widely used type of encryption, so using Shaw's algorithm will allow us to crack RSA encryption, but that won't happen for a while
01:27:16To run Shaw's algorithm, we will need a fault-tolerant quantum computer with millions of logical Q bits, which won't happen for some time
01:27:21This algorithm uses both classical and quantum computers for different steps
01:27:29First, we choose an A that is between 1 and N, and the GCD of A and N is one, so A and N share no common factors
01:27:39Next, we do the quantum step, but before that, we will look
01:27:48At some number theory in modular arithmetic, we say that A is congruent to B mod N if the remainder of A / N is B
01:27:58For example, 3 is congruent to 1 mod 2, since dividing 3 with 2 gives a remainder of 1
01:28:09We can reduce the factoring problem down into the problem of finding the period of modular exponentiation
01:28:15Modular exponentiation is when you take the powers of a number modulo a number
01:28:19Here is an example
01:28:23As you can see, if we have a number, in this case 2, and put it to increasing powers, we get a repeating pattern when we take the modulo
01:28:27The period of this pattern is the length of the sequence, and that is what We are looking for, in this case, the period R is equal to 6
01:28:43All of the sequences start with a ^ of 0 is congruent to one mod n, so we need to keep increasing the power until we get back to one
01:28:50If we are able to find the period, we can use some number theory to find the prime factors
01:28:57If we have a number n, which is equal to the product of two prime numbers p and Q, if we pick a number a where the gcd of A and N is equal to 1, so they share no common factors, and we find the period of a to the X Mod n, then if we get a good approximation for R, the gcd of a to the ^ of r / 2 - 1 and n, and the gcd of a ^ n / 2 + 1 and N has a good chance of containing the factors of
01:29:32And let's go through the steps in finding the period of modular exponentiation
01:29:38For this, we need to use this gate, let's call it U, which transforms the state x to the state x a mod n
01:29:43If we apply this gate to the one state multiple times, we can get powers of a in mod n
01:29:51How we construct this gate is outside the scope of this course, see the problem set for resources on how we can construct this gate
01:29:58Let's consider this state
01:30:06If we apply a U gate to the state, it gives us this state
01:30:19Looking at the a to the r mod n, we can change the to a to 0 mod n, since they are both 1
01:30:26If we multiply the right hand side by 1 or e to the 2i i s / R * e - 2i i s / R, we To get this state, we can change the E to -2 Pi i S over R to e to -2 Pi i 0 over r, since they are both equal to one
01:30:46Now, as you can see, this whole state becomes the US state
01:30:53This means that the US state is an igen vector of the uate with an igen value of e to the power of 2 pi i s over R
01:31:06This means that if we can construct the US state, we can use the quantum phase estimation algorithm to get the value of s over R
01:31:11It turns out that it is far easier to construct the equal superposition of all of the US states
01:31:17What this becomes is 1 mod n
01:31:23In the problem set for this lesson, we will prove this result
01:31:29We can construct the one mod n by applying a KN to the rightmost Q
01:31:35bit in a register of all zeros, which gives us the value one, which is equal to one in mod n
01:31:40So by creating the state 1 mod n, we are actually creating the state 1 / √R * the sum from s = 0 to R -1 of us
01:31:47Here is the circuit for the algorithm
01:31:54Looking at it, this is just the quantum phase estimation circuit
01:32:01As you can see, we now know that one is an eigenvector of the U gate, so we are using this to estimate the eigenvalue e to ^ 2 pi i s / R, where s is an integer from 0 to R -1
01:32:08This is because our eigenvector 1 mod n is equal to 1 / √R * the sum from S = 0 to R -1 of U, so we will get the I value e to ^ of 2 pi i s / R for one value of s, so when we measure the qits, we Will get the eigenvalue of one of the U's, which means that we will get S/R for 1 s from 0 to R
01:32:43Thus, one if we happen to get zero as our eigenvalue, so s = 0, then we repeat the circuit, so we can get an eigenvalue that is non-zero
01:32:57Now we have a decimal number J, which is equal to S/r, that is the quantum part of the algorithm done
01:33:04Now we estimate the values of S and R by using a technique called continued fractions
01:33:10Here is an example with the decimal 0.312, we start by writing it as a fraction, then we flip the fraction, we continue this process until we have the number one in the numerator by representing a decimal in this way, we can
01:33:20Approximate its value with a fraction by rounding off the continued fraction
01:33:30Here are the first three approximations for the decimal 0.312
01:33:40To approximate S / R, we find an approximation where the denominator is less than N, since the period R must be less than N
01:33:52If R is odd, then we repeat the algorithm and get a new value of R
01:33:59Now that we have a value for R, we can use this to find the factors of N
01:34:05We know that A to the R is congruent to 1 mod N, so A to the R - 1 is congruent to Z mod N
01:34:12This means that A ^ of R - 1 has a factor of N, since when we divide it by N, we get zero remainder if we factor A^ R - 1 with the difference of two squares
01:34:23Then we get this
01:34:34From this, we can see that if we calculate the GCD of a^R/2 - 1, n, and the GCD of a^R/2 + 1 and N with our approximation of R, we have a good chance of them being one of the factors
01:34:45This allows us to find p and Q
01:34:50Let's go through a quick example with n = to 15, so p is 3 and Q is 5
01:34:55In step one, we choose an a which is relatively prime to 15
01:35:00Let's choose AAL 7
01:35:06Now, in step two, we use the quantum part of Shaw's algorithm to find the period or R, so we need to find R such that 7 to the power of R is congruent to 1 mod 15
01:35:18By using the algorithm, we find that R is equal to 4
01:35:24Now we calculate the GCD of 7^4/2 - 1 and 15, and the GCD of 7^4/2 + 1
01:35:30And 15, the first one becomes the GCD of 48 and 15, and the second becomes the GCD of 50 and 15
01:35:44The GCD of 48 and 15 is three, and the GCD of 50 and 15 is five
01:35:49As you can see, we have found the factors of 15, 3 and 5, using Shor's algorithm.
