Quantum Computing Course – Math and Theory for Beginners

Key Takeaways

Quantum Computing leverages the principles of quantum mechanics to process information at incredible speeds this 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 the first section covers all the essential mathematics and the second section is a deeper exploration into the mechanics of quantum computers you'll learn why quantum computers are so powerful and how they're poised to transform technology Michael from Quantum sore created this course if you were to search up 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 when I first started learning about quantum computers these analogies and explanations never made sense this course was created in order to provide a solid foundation on Quantum computation without using analogies but teaching how quantum computers actually work let's quickly look at the structure of this course the 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 cupid is and how we can represent them mathematically we also explore some single qbit operations and discuss some of their properties the third section introduces how we can represent multiple cuq bits mathematically and explor some operations we can perform on multiple cuq bits this section ends on exploring the strange Quantum phenomena of quantum entanglement and phase Kickback in the final section of this course we use everything we have studied up until this point to analyze Quantum algorithms this section showcases why quantum computers as such revolutionary technology let's start with understanding imaginary and complex numbers but before that we need to consider the square roots of numbers let's say we have the equation x^2 is equal to 4 which means X is equal to Plus or - 2 easy but what if x^2 is equal to -4 since a number squared is always greater than zero how can X2 ever be a negative number this is where imaginary numbers come in if we let I be the < TK of1 we can then write the < TK of-4 as plus orus 2 I this is an imaginary number any number that contains a factor of theare < TK of1 or I now we move one level up to complex numbers all a complex number is is a number that contains a real number plus an imaginary number a standard complex number looks like this a plus I B 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 complex 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 we can add and subtract complex numbers pretty easily all we do is add or subtract the real parts and the imaginary Parts pause the video and try adding up these complex numbers multiplication is pretty simple as well but we must remember the before we get i s that becomes -1 since I is the square root of1 the complex conjugate of a complex number is when you take the complex number and flip the sign or negate the imaginary part this is denoted by an asteris here are some examples one cool property of complex numbers is if we multiply any complex number by its complex conjugate the result is always a real number try multiplying 2 + 3 I with 2 - 3 I and confirming this is the case we 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 for example the complex number -2 + 3 I would be a vector that would end at the point -2 3 when 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 this 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 plus I is equal to the square root of a^ 2 + b^ 2 pause the video and see if you can find the magnitude of 4 - 3 I this is not 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 xais using trigonometry we find that we can also represent complex numbers in the form r cos theta plus I sin Theta where I is the magnitude of the complex number and Theta is the angle it makes with the Positive X AIS we 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 this is called Polar form there is also one other form which is r e to the power of I Theta this form is exponential form pause the video now and try to convert the complex number 1 + I into Polar form then into exponential form in Quantum Computing we almost exclusively use complex numbers in exponential form this 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 you will see once we start studying Quantum Computing that this property is very useful in representing Quantum States a matrix is a 2d arrangement of numbers in the next lesson we will get to the applications of matrices and how they relate to Quantum Computing but in this this lesson we will quickly Define some properties and operations we can do on them we say we have an M byn Matrix if the number of rows is M and the number of columns is n so this Matrix here would be a 2x3 Matrix pause the video and see if you can find out the dimensions of these matrices if we want to add two matrices together all we need to do is add each element of the matrices this is the same for subtraction note 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 pause the video and see if you can add these matrices we can also multiply matrices by a scalar if we do each element in the Matrix gets multiplied by the scaler giving us another Matrix when 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 dotproduct of the first row of the left Matrix and the second column of the right Matrix we continue this process until we have all the elements in the new Matrix pause the video and try to complete this matrix multiplication it'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 for example we can't multiply these two mates here since the first one has two columns but the second one has three rows if we have a n by one Matrix we call it a column Vector we can graph these like any other Vector these are useful as one of the ways we can represent a state of a Quantum computation is through a column Vector it turns out that when we multiply a matrix with a column Vector we get another column vector intuitively what is happening is the column Vector is getting transformed by The Matrix so we can use matrices as Transformations on a vector here are some examples graphically as 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 we also have a special Matrix called an identity Matrix this Matrix is all zeros except for the main diagonal that has all ones if we multiply the identity matrix by any Matrix we get back the original Matrix verify this is true by multiplying the two-dimensional identity Matrix with this Matrix and check to make sure you get back the original Matrix matrices also have what's called an inverse that when multiplied with the original Matrix gives us the identity Matrix we denote this with a ne1 graphically this means that if we have a matrix a and we apply it to a column Vector 1 one if we then apply the inverse of a we lend back on the point 1 one therefore 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 with complex numbers we can also take the complex conjugate of a matrix this is denoted by the asteris on the top right of the Matrix just like with complex numbers when we apply this we flip the sign of all the imaginary components of all the elements in The Matrix pause the video and find the complex conjugate of this Matrix we can also do what we call the transpose of a matrix this is denoted by the T and involves exchanging its rows with its columns if 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 what was the point of all this in Quantum Computing we use two types of matrices to apply our operations one of them is unitary matrices these have the property that given a unitary Matrix u u * U dagger is equal to the identity Matrix so U dagger is its inverse geometrically when a unitary Matrix acts on a vector the length of the vector stays the same but it is rotated or flipped this property may not seem very useful but once we start talking about probabilities in quantum computers it will all start to make sense the other type of Matrix we use to apply operations in Quantum Computing is the Homan Matrix these matricies have the property that given a Homan Matrix H H is equal to H dagger as you go through the quantum Computing sections of this course you will start to understand why we use these types of matricies to perform operations on quantum computers sometimes 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 when this happens we call the vector an igen Vector of the transformation matrix that we applied and the Scala we factored out an igen value let's go through an example if we have the Matrix 20112 with the vector 03 applying the Matrix on the vector gives us the vector 06 with this we can Factor at a two leaving us with two times the vector 03 this gives us an igen value of two with the igen vector 03 for that Matrix classical computers use binary zeros and ones to store and process their data quantum computers on the other hand use Q bits or Quantum bits which can be zero and one at the same time we have all heard this explanation of quantum computers but what does that actually mean in order to understand what a quantum computer is actually doing we must look at how we represent them mathematically instead of using binary like classical computers quantum computers use cubits physically a cubit can be any Quantum particle that exists in two distinct states such as a photon of light being polarized either horizontally or vertically just like classical computers we still use zeros and ones but in Quantum computation we Define them instead as the column vectors 1 0 and 01 respectively the weird brackets around 0 and one is direct notation we will look more into it later you 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 so back to our Photon polarization example this means that the photon is both horizontally and vertically polarized at the same time in terms of quantum Computing we say a cuit is in superp position if it is both zero and one at the same time let's look at how we represent cubits mathematically mathematically we can represent a qit as a column Vector with two elements the top element indicates how much the qbit is in the zero State and the bottom element indicates how much the cuit is in the one state the convention for a Quantum state is to set it equal to the Greek letter s we'll talk more about this in the next video so if we have a cubit in the state 1 Z it now makes sense why this is zero since it is all in the zero State and none in the one we can say the same for Q bit in the state 01 being one if a qbit 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 one since it is both of the states at the same time so now we know how to represent a cubit mathematically but how do we measure the cubits for that we must look at another rule of quantum mechanics when we measure a Quantum system it changes the state of the system to the measurement what 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 and once it has been measured it collapses into the state we measured so if it was in a super position and we measure it to be horizontally polarized it would collapse and become horizontally polarized meaning it is not in a super position anymore the same thing happens when we measure Q bits we can only measure a zero or one we do not measure how much the QQ bit is in the zero state or how much the cuq bit is in the one state immediately after measuring a cuq bit its state changes to either zero or one depending on the measurement so what is the point in those numbers telling us how much the cuq bit is in the zero State or the one state what those numbers tell us is the probability of measuring a 0 or 1 the probability of measuring zero is the magnitude squar of the amplitude of the zero State and the probability of measuring one is the magnitude squ of the amplitude of the one state so for this example Cubit when we measure it we have a 75% chance of measuring a zero and a 25% chance of measuring a one if we now think about how we defined the Z and one state at the start of the lesson they should now start to make sense we stated that Zer was the column Vector 1 0 and now we can see why the probability of measuring Z is 1 so will always be measured as zero this 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 Cubit State since 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 qbit that is in superp position it collapses into the measured state so if we measure this state to be zero it collapses into the zero state so every measurement after will be zero this is because of the laws of quantum mechanics when we measure something it permanently changes the state of the system to that measurement normally when we are mathematically representing a Quantum state of a quantum computer instead of using matrices we use a specific notation called direct notation to see how this works let's convert an arbitrary Cubit State Alpha Beta into direct notation all we need to to do is turn the Matrix into the sum of two matrices and then factor out the Alpha and the beta now if you look at the column vectors they are the zero and one States as we saw in the previous lesson this gives us a linear combination of the zero and one States those brackets around the 01 and S are called KS all they tell us is that 0 1 and S are quantum States pause the video and convert this Cubit state from Matrix to direct notation this 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 we can represent a cuit graphically on what is called a block sphere on the top we have the zero State and on the bottom we have the one state on the horizontal we have the plus State minus State I State and negative I State we will discuss these in later lessons the closer up the cuit is to the zero State the higher probability of measuring a zero and the same goes for the one state that means that if we have the state 1 on < tk2 1 on < tk2 it will lie halfway between the North and South Poles since it has an even chance of being measured as Zer or one you may notice that since it is a sphere the cubic can spin around the sphere this is called phase we will talk about this in later lessons right now it is important to understand the basic idea that the higher up the qbit is the more likely we are to measure a zero and the lower the qbit the more likely we are to measure a one pause the video and think about where the state 1 on 2 < tk3 on2 will be on the Block sphere the cuit 1 on2 < tk3 on2 would be halfway between the Equator and the one state since it has a one on4 chance of being measured as a zero and a 3 on four chance of being measured as a one with classical computers we use logic gates to process data with 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 the most common single Cubit gates are the X Y and Zed Gates let's first look at the X gate if we have a Q bit in the zero State and apply the X gate to it it flips to the one state let's try a q bit that is halfway between 0 and one try and see if you can figure out what the xgate is doing let's try a q bit in this state as you can see the xgate flips the Cubit 180° or Pi radians around around the x-axis now let's have a look at the Y gate here are some examples of the Y gate transformation as you can see it does the same thing as the xgate but instead it rotates the Cubit State 180° or Pi radians around the Y AIS lastly we have the Z gate which rotates the cubeit 180° or Pi radians around the Z axis since these Gates rotate the cuit around the specified axis by pi radians if we apply the same gate twice one after the other then the Cubit returns to its original position this means that these three gates are their own inverses we can represent these Gates as matrices here are the matrices for these gates for the moment ignore the complex numbers in the Y gate mat mat we will explain this later in the next lesson when we talk about phase mathematically to apply a gate to a cubit we can multiply The Matrix that represents the gate with the column Vector of the Cubit pause the video and prove that applying the X gate to the zero State gives us the one state in direct notation if we 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 indicates the column Vector the zero state becomes after applying the gate and the second column indicates the column Vector the one state becomes then we can factor out both our zero and one States again to get back into direct notation also since Quantum gates are linear if we apply an arbitrary gate U that gate acts on each of the superposition States individually let's look at an example of applying a gate in direct notation if 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 state 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 with this pause the video and prove that applying a zed gate to a cuit in the state Alpha 0 plus beta 1 gives us the state Alpha 0 minus beta 1 looking at this you may be thinking what is the point of the Zed gate this Q bit still has an alpha squar chance of being zero and a beta Square chance of being one it didn't affect their probabilities in the next lesson we will finally bring complex numbers into Quantum Computing with an introduction to phase on the Block sphere we saw in the previous lessons that we could also rotate around the Zed AIS this is called phase it 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 we will get into the uses of phase in the next lesson in this lesson we will see how we can represent phase mathematically to represent phase we have to bring back our old friend complex numbers in Quantum Computing we mostly use complex numbers in exponential form you will now see why but first let's consider some states in the block sphere let's first consider the states 1 or < tk2 0 plus 1 or < tk2 1 if we apply a zgate we get it to the state 1 or < tk2 0 0 - 1 < tk2 1 as you can see the one state was multiplied by a factor of -1 and the Cubit rotated Pi radians around the Z AIS if we represent the -1 as a complex number in exponential form we get e to the I Pi notice how the angle of the complex number is pi radians let's try another example let's plot the state 1 on < tk2 0 + 1 < tk2 1 and 1 on < tk2 0 + I on < tk2 1 if we represent I as a complex number in exponential form we get e to the I Pi / 2 and if you look at the Block sphere to get that state we rotate Pi / 2 radians around the Z AIS we 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 Cubit with the complex number e to the I we rotate the Cubit around the Z AIS 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 Global phase is when the entire cuit is multiplied by a complex number and relative phase is when just the one state is multip IED by a complex number it 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 relative phase on the other hand is extremely important and matters in our calculations relative phase is when the amplitude of the one state has a factor of a complex number as we saw earlier having relative phase rotates the Cubit on the Block sphere around the Z AIS 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 qbit creating a global phase and relative phase then we can discard the global phase leaving us with a qbit with a relative phase we saw previously on the Block sphere that phase does not affect the probability of measuring a zero or a one as the cupit stays the same distance from the zero State and the one state no matter how far we rotate around the block sphere if we look at an arbitrary Cubit State Alpha 0 plus e to the I5 beta 1 the probability of measuring a one is the magnitude of e the5 beta squar we can split the absolute values up like this the magnitude of e to the II is 1 since the coefficient of the complex number in exponential form states its magnitude so the probability of measuring one is still the magnitude of beta squ in the next lesson we will see why relative phase matters before we discuss perhaps the most important gate in Quantum Computing we will quickly revisit the block sphere in earlier lessons we saw that on the equator we have four states the plus State minus State I State and negative I State now that we know about phase we can Define these states all they are a shorthand for commonly used States since they all lie on the equator of the block sphere they all have an even chance of being measured as zero or one but each one contains a different relative phase the plus state is the state 1 < tk2 0 + 1 < tk2 1 the next state is the minus State this is the same as the plus state but with a relative phase of -1 the I state has a relative phase of I and the negative I state has a relative phase of negative I now let's look at the hadam mod gate here is the Matrix for the gate if we look at how the gate acts on a qit on the Block sphere we see that the zero state gets trans transformed into the plus State and the one state gets transformed into the minus State applying a hadam mod to the plus State gives us the zero State and applying a hadam mod to the minus State gives us a one state this means that the hadam mod is its own inverse if we wanted to apply a hadam mod gate to an arbitrary Cubit state in direct notation we can replace the zero with the plus State and the one with the minor State and expand the hadamar gate shows that phase matters if we apply the gate to the plus State we get zero and to the minus State we get one these 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 zero and a 0.5 chance of being measured as one in the fourth section of this course we will start to look at some Quantum Computing algorithms and you will start to see why the hadide gate and phase is so powerful now that we understand relative phase let's introduce two new gates the s and t Gates the S gate adds a relative phase of Pi on 2 radians the T eate adds a relative phase of Pi on 4 radians if we take the conjugate transpose of the two matrices of the two gates we get their inverses for 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 this means that if we apply a 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 we also have the T dagger gate which is the same thing as the S dagger but adds a relative phase of piun on 4 radians instead meaning it is the inverse of the T gate if we have multiple cuq bits we represent them through the tensor product for example if we had two cuq bits in the zero state then we would represent the state like this this is usually shortened to this where we have the two zeros in the one get Vector if we wanted to represent two cubits in superp position we can expand it out like any other operation by multiplying the amplitudes of the states and using the tensor product on the zero and one States as you can see now we have four states the 0 0 01 1 0 and one one States this makes sense since those are the possible combinations of zeros and ones we can have with two cubits measurement works the exact same as before the probability of measuring 0 0 is the magnitude squared of the coefficient of the 0 State and so on here is an example of combining these two cubits if we want to add another q bit to the system all we need to do is tensor it onto the end of the state we also have some Shand notation you will sometimes see if we have n Zer we can write it like this which means 0 tensed with itself n times so this state would be shorthand for 5 ones this represents ation of cuits is great but what if we wanted to apply a gate to a certain cuit how would we indicate that we wanted to let's say apply an xgate to the second cubit in this state for this we use a diagram called the quantum circuit here is an example of one on the vertical we have the cubits each line representing a singular Cubit the states on the left are the initial states of the cuits the bo boxes are the quantum Gates and the letters on the boxes are the type of gate we are applying for example this is an X gate these boxes are measurements and represent us measuring the Cubit the horizontal is the order in which we apply the gates we start from the left and go to the right sometimes you will also see size States pointing to different points in the circuit these are used to represent the state of the system at different points during the algorithm let's go through this circuit at S Sub 0 we have the state 0 01 then at SI sub one we apply an X gate to the second Cubit at SI sub 2 we apply a hadam mod gate to the second Q bit giving us this state then at S Sub 3 we apply an xgate to both the first Cubit and the third Cubit giving us this state then at size sub 4 we measure the cubits so we will get one of these states with these probabilities now let's introduce some gates that act on multiple cuy bits the most common multibit gate is the c not or controlled X gate here is the gate on a Quantum circuit the gate acts on two Q bits one of the Q bits is called the control Q bit and the other is called the target QQ bit the C not gate applies an X gate to the Target QQ bit if the control QQ bit is a one and does nothing if the control is a zero let's look at the C not gate acting on some states if we apply a c not to this state with the first Q bit as the control and the second Q bit as the target then we apply that c not gate to each of the superposition States giving us this state here is another example we also have the tooli gate this gate is very similar to the C not but instead it has two control cubits here it is on a Quantum circuit if we apply a tooli gate to this Cubit state with the second and third cuq bits as control and the fourth Cubit as the target we get this state it 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 we represent these on a Quantum circuit like this with the regular gate box but with a line going out to the control CU bit for example here is the controlled es gate on a Quantum circuit where the second qbit is the control and the first is the target now 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 CU bit is one then summing up the probabilities of measuring those States Let's do an example if we wanted to find the probability of measuring a zero in the first CU bit then we sum the probabilities of measuring each of the states where the first Q bit is a zero but how do we know what the state collapses to once we measure a qbit remember once we measure a qbit it collapses its superp position and becomes the measurement let's look at an example say we have this state and we measured me the first cuit to be a one then the state collapses and since the first cuit becomes a one we get rid of all the superposition states where the first Cubit is not a one remember the probabilities must add up to one but we have just removed some states so the probabilities will be less than one we fix this by multiplying the state by what we call a normalization constant let's call it a now we can normalize the state by using the identity that the probabilities must add up to one this gives us values for a so if we measure the first CU bit to be one the state collapses to this state we can use these techniques with any number of cubits let's go through an example with three cubits let's say we have this state and we measure the middle Cubit to be zero the state collapses like this collapsing into this state let's consider this Quantum circuit at SI Sub 0 we have the state 0 0 then at S Sub 1 we have the state 1 on < TK to 0 plus 1 0 Let's distribute the zero State into the equation giving us the state 1 < tk2 0 0 + 1 0 now at size sub 2 we apply a cot with the first qbit being the control and the second being the target this 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 Q bit flips to a one this leaves us with the state 1 on < tk2 0 0 + 1 1 can you notice anything weird about this state if we were to measure one of the cubits 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 cubits by measuring one of them we immediately know the state of the other Cubit this is called entanglement there are many different entangled States we say a state is entangled if it cannot be factored into the tensor of single Cubit States for 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 Cubit States what this means is that when the cuits are entangled they depend on each other to determine their state there are two types of entangled States maximally entangled States and partially entangled States we say CU bits are maximally entangled if measuring one of the CU bits 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 here are the common maximally entangled States with two cubits we call these states the Bell States and we denote them with capital fi and S we say cubits are partially entangled if the measurement of a cubit affects the probabilities or phase of the other cubits for example with this state if we measure the first cuq bit as zero the state collapses to this but if we measure the first Q bit as a one then it collapses to this state as you can see the two states have different probabilities of measuring Zer or one so this state is partially entangled since measuring one cubit affects the probabilities of the other another quantum property we can use is something called phase Kickback to understand and how this works let's consider this circuit as you can see we have a Q bit in the plus State and another q bit in the state V we also have an arbitrary controlled U operation let'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 now at sub one we have the state plus V Let's expand the plus State and distribute the V State into the plus State at 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 we can now Factor back out the V state from the equation can you see what has happened V is unchanged even though it was the Target qit and a factor of e the I Theta has been applied as a relative phase to the control Cubit this occurs if V is an igen state of the gate you are applying we call this phenomenon phase Kickback and it is used in some Quantum algorithms let's have a look at superdense coding this Quantum protocol allows us to send two bits of classical information with only one cubit to do this we need entanglement we'll say that the person sending the Cubit is Alice and the person receiving this Cubit is Bob to start off with Alice and Bob maximally entangle two cubits so they are in this state Alice takes one and Bob takes the other we will say that Alice takes the left QQ bit and Bob takes the right cuq bit then Alice and Bob take those cubits with them now 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 Q bit if Alice wants to send the two classical bits 0 0 she does nothing and sends her Q bit to Bob if Alice wants to send 01 she an X gate to her qbit transforming the CU bits to this state then she sends her Cubit to Bob if Alice wants to send one Z she applies a zgate to her Q bit transforming the Q bits to this state then she sends it to Bob lastly if she wants to send one one she applies both an x and z gate to her cuit giving us this state she then sends her qbit to Bob now Bob has both the cubits in one of these four states he now applies a c not with the first Cubit as a control and the second as the target giving us these states then he applies a hadam mod gate to the left key bit this gives us this state that Alice wanted to send all 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 with quantum computers we can send two bits of classical information by sending one Q bit this works since there are two entangled Q bits in the entire system before 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 there are four main operations we can perform on classical bits the and or not and exclusive or operations let's go through each one of them quickly the simplest is the not gate which flips 0 to 1 and 1 to zero here is the truth table for the gate where X is the input and F ofx is the output as you can see this gate acts on one bit now let's look at the end gate here is the truth table for the gate the operation acts on two bits and returns one if the two bits are one and zero otherwise the orgate acts on two bits as well if either of the bits is a one or both or one then it returns one otherwise it returns zero lastly we have the exclusive or gate here is the truth table for the operation as you can see it returns one if either of the inputs is one and returns zero if both the bits are zero or one we use the exclusive or operation to reversible classical Gates we say a function f is reversible if given F ofx we can determine the value of x so if we are given the output we can determine the input so 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 it could have been any of these three inputs to make any classical gate reversible we must input another bit let's call it C and instead of only returning F ofx we return the input X as well as C exclusive or with F ofx this makes the operation reversible let's look at converting the orgate to a reversible operation here is a normal orgate and here is a reversible orgate as you can see we input another bit C and return it exclusive or with the output now 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 what is the point in all this well with quantum computers all operations besides measuring the qits must be reversible this is because every operation must be unitary if you remember from the first section of this course unitary matrices rotate and flip a vector so they must be reversible in 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 we discussed in the previous lesson how we can make classical Gates reversible now let's use this same technique to make Quantum functions since 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 to do this we use the same techniques for making classical Gates reversible a standard Quantum function looks like this where we input X and Y and get back X and Y exclusive or with f ofx now 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 ofx zero exclusive or with any bit gives us back that bit this means that zero exclusive or with f ofx is just F ofx this allows us to query the function and get its output on a quantum computer we can encode functions within a unitary Matrix and so it is a valid Quantum gate we usually denote a function f as U subf so overall if we apply a function f to the state x0 we get the state x f ofx then to get the function output we can measure the second register of cuits let's see what happens if we apply a function f to this state with the output register being the minor State first let's rewrite the minor State like this and distribute the X State into the superposition since the function is a unitary operation it gets distributed into the superposition like any other gate then it acts on each of the superposition States individually applying U subf we get this state the zero exclusive W with f ofx becomes F ofx and the One exclusive W with f ofx becomes not F ofx now let's consider two scenarios if f ofx is equal to 0 then the state becomes 1 < tk2 x0 - X1 which we can rewrite as x minus on the other hand if f ofx is equal to 1 then the state becomes 1 on < tk2 X1 - x0 we can factor out the -1 leaving us with the state-1 on2 x0 - X1 this can be further factored intox minus now looking at these two states we can see that the only difference is the phase at the front we can combine these two equations into -1 to^ FX xus so if we apply a function to the state xus we get back -1 to the^ of f ofx xus when we query a function in this way where the output bit is in the minor State we call it a phase Oracle in the next lesson we will finally see how quantum computers can outperform classical computers with Deutsch's algorithm which uses this technique of the phase Oracle one more thing we will discuss when it comes to quantum computers is a theorem called the no cloning theorem when 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 if we have a CU bit 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 if we were to measure s we would get Z or 1 but to copy the state we need to know the amplitudes so we would need to know Alpha and beta we could easily copy qbit states where we know the amplitudes by applying the needed Gates but if we do not know the state we cannot copy a cuit now let's finally look at a Quantum algorithm deutch's algorithm but first let's look at the problem it solves and how we would solve that problem with a classical computer say we have a function f that takes in a bit and returns a bit we don't know what the function does all we can do is send in a bit and read the output bit it is like a black box our t ask is to find out whether the function f is constant or balanced if a function is constant then it Returns the same bit no matter the input here are the two constant functions that can act on one bit constant one which always returns one and constant zero which always returns zero balanced functions on the other hand return zero for half the inputs and one for the other half of the inputs here are the 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 as you can see both these operations return zero for one input and one for the other input for 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 if 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 if f of0 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 so we need to query the function twice once with zero as the input and once with one as the input with 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 here is the circuit for the algorithm the U of represents the function f at S Sub 0 the Q bits are in the state 0 0 then at SI sub 1 the cubits are in the state 01 at SI sub 2 we apply a hadam mod to each of the cubits leaving us with the state plus minus let's expand the plus State and distribute the minus state into the equation now at SI sub 3 we apply the unitary Matrix UF acting as the function to the state since all Quantum operations are linear UF gets distributed into the state and acts on each of the superposition States individually if 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 of1 1 minus the minus qbit is not needed for the rest of the algorithm so we will emit it to clean up the equation now 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 therefore if F of 0 equal F of 1 the state becomes 1 / < tk2 0 + 1 or the plus State now let's look at if F of 0 does not equal F of 1 so if F0 = 0 and fub1 = 1 the state becomes 1 / < tk2 0 - 1 if F of 0 = 1 and F of 1 = 0 then the state becomes 1 / < tk2 - 0 + 1 with this we can factor out a global phase of -1 leaving us with the minus state so overall if F of 0 equals F of one the state becomes the plus State and if F of0 does not equal F of 1 the state becomes the minor State see if you can finish the rest of the algorithm off yourself now at SI sub 4 we apply a hadam mod to the Q bit in 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 one the state becomes one now 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 of0 equals F of 1 and if we measure one then the function is balanced since F of 0 does not equal F of one as 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 in the next lesson we will look at the DEA algorithm which considers itself with the same problem of deutch's algorithm of finding out if a function is constant or balanced but in instead of having a function that only inputs one bit the algorithm is a general case that accepts any number of bits as input the deuts josa algorithm considers itself with the same problem of deutsche'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 let's quickly revise constant and balanced functions constant functions always return the same value no matter the input here are the two constant functions constant Z and constant one balanced functions return zero for half the inputs and one for the other half of the inputs here is an example of a balanced function that takes in a bit string of length three as you can see the function returns zero for four of the inputs and one for the other four of the inputs for 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 this is because in the worst case we check half of the inputs and get the same output for all of them when this happens we need to check one more input to determine whether the function is constant or balanced the there are two to the N possible bit strings of length n so 2 the nus1 is half of the possible inputs therefore we need to check half + 1 so 2 n-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 deutch's algorithm to determine whether the function is constant or balanced here is a circuit for the algorithm this line here going through the circuit represents n qits and the hamod gates tensor n represent n hadam mod Gates each one being applied to one of the N cubits let's go through the algorithm at S Sub 0 we have n z minus then at S Sub one we apply a hadam mod gate to each of the N zeros giving us this state let's quickly derive anide identity that we frequently use when applying hatam mods to a register of zeros this gives us n plus States if we expand them out we get 1 / < tk2 0 + 1 tens with 1/ < tk2 0 + 1 and so on N times let's try different values of n to figure out how we can represent this mathematically if we have Nal 2 we have the plus state tensored with itself Distributing the states gives us a state one of a < tk2 2 0 0 + 0 1 + 1 0 + 1 1 we can represent the superposition States like this with a sum over all bit strings of length 2 x let's try n = 3 with this we have the plus state tensored with itself three times Distributing gives us this state we can once again represent the superposition States as a sum of all possible bit strings of length three and X resulting in this state we can generalize this and say that if we apply a hadam mod to each of the N zeros we get 1 / < tk2 to the^ of n time the sum of all bit strings of length n x this is a very important identity in Quantum algorithms and is used in many algorithms if you think about it this makes sense since each Cubit 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 going back to size sub 1 we can now change this to our identity now at size sub 2 we apply the Oracle function since the function acts on each of the superposition States we distribute it into the sum now if you look at each of the superposition states in the sum they are in the phase Oracle form applying the function