Quantum Computing Course – Math and Theory for Beginners

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 function gives us the equation 1 / < tk2 the^ of n * the sum of all bit strings of length n -1 to the^ of f ofx xus let's emit the minus Q bit from the equation as it is not needed in the algorithm anymore at

size sub 3 we once again apply a hatam mod to each of the CU bits what this means is that for every bit in the bit string X we apply a hadam mod gate you 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 the X State can be any combinations of zeros and ones let's quickly figure out how we can represent this mathematically for this we can rewrite the hadam mod transform on an arbitrary bit XI

as 1 / < tk2 0 + -1 to the^ of x i 1 since if XI is0 it becomes the plus State and if x i is one it becomes the minus State let's try X being a bit string of length three this gives us this state if we tend to the states together we get this state let's quickly add the exponents of the negative 1es 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 i where x i

is the position of the one we can reite write this as the dotproduct of X with the superposition State now we can combine this state as the sum of all Zs that are bit strings of length three -1 to the^ of X do z z generalizing we get this identity where applying a hatam mod to an arbitrary bit string of length n x gives us 1 / < tk2 to the^ of n * the sum of all bits Str of length n -1 to the^ of X do z z this is also a very important

identity that is used in many Quantum algorithms with this the qits are now in this state let's now consider the amplitude of the all zero State we find that it is 1/ 2 ^ n time the sum of all bit strings of length n -1 to the^ of f ofx + x dotted with all zeros the X doted with the all zeros become zero so the state becomes this state now if the function f is constant then the value of f ofx will be the same no matter the input this means that if f ofx

is equal to Z the amplitude of the state becomes 1/ 2 to the^ of n time a sum over all X's 1 evaluating the sum there are two to the end possible combinations of Zer and ones of length n so the sum is 1 + 1 + 1 and so on 2 the^ of n * this gives us 1 / 2^ n * 2^ of n which equals 1 on the other hand if F ofx isal to one we do the same thing giving us netive - 1 so if the function is constant the amplitude

of the all zero state is plus or minus 1 if the function is balanced then half the inputs will result in zero and the other half will result in one if 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 this means the sum will be evaluated to zero so if the function is balanced then the amplitude of the all zero state is zero now we measure the cubits before we saw that if the function is constant then the amplitude of

the all zero state is plus or minus 1 that means the probability of measuring the all zero state is one if the function is balanced on the other hand then the probability of measuring all zeros is zero what 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 done we have determined if the function X f is constant or balanced in a single query of the function the key takeaway from this algorithm are these two identities they will keep popping up

again and again let's now look at the Bernstein vasani algorithm here 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 our task is to find out what the secret string s is on a classical computer the approach is to input a bit string of all zeros except for one in one position this 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 this 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 only need to query the function once to find out what s is if we look at the circuit it may look familiar it's the same circuit as a DOA algorithm just with a different function being applied to the cubits initially the cubits are in the state n z minus then

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 at S Sub 2 we apply the Oracle since 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 ofx xus let's rewrite f ofx as a dotproduct of X and S since that is the definition of our function let's also emit the minus

qbit since it is not needed anymore now we apply a hadam mod to each of our Q bits let's distribute the -1 to the power of X do s into the sum we can now add the exponents giving us the dot product of s s and X plus the dot product of x and z we can factor out the X giving us s + z dotted with x the 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 so

the I position of S Plus Z is S Sub I exclusive or with Z sub I this gives us another bit string of length n now we measure the Q bits let's look at the probability of measuring s expanding out we find the amplitude of the S state is 1 / 2 to^ n * the sum over all X's where X is a bit string of length n -1 to the power of s + S dotted with X since plus indicates bit yse exclusive or S + S equals to all zeros now in the X

exponent we have all zeros dotted with X this will equal Z since all the zeros will cancel out all the X's at each position applying the power means the state becomes 1 on 2 the^ n * 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 the^ of n this leaves the amplitude of the s State as one this means that the probability of measuring s after applying the algorithm

is one and that is it after one query of the function we can find S by measuring the cubits you may start to see the similarities between this algorithm and the others applying a hadam mod to each of the cubits so that the state is in a uniform superp position then applying the function and once again applying hadam mods is used in many algorithms in the next two lessons we will look at the quantum forier transform as well as Quantum phase estimation these are both used within many Quantum algorithms including Shaw's algorithm let's start with

the quantum fora transform or qft before we look at the maths and circuit behind it let's look at how it transforms states on the Block sphere so we can gain some intuition on the top we have how we would normally represent a number in binary as you can see each of the Q bits is either zero or one and if we take those bits we get the number then underneath we have the same cubits after the quantum 4A transform has been applied as 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 uniform superp position as you can see the left Q bit has two possible phase options either Zer or -1 relative phase then the next qbit has four possible phase options and so on up until the last CIT which has two to the N possible phase positions where n is the number of qits in this case the right CU bit has 2 to the 3 or eight possible phase options depending on the number the

phase of the CU bits is different let's see how the number five is encoded Ed once 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 piun radians which is 5 piun on 4 radians to get the amount rotated around the Z AIS of the next q bit we multiply the previous one by two so the next q bit has been rotated 2 * 58 * 2 piun radians so rotating the cub > / 2 radians around the Z AIS

the last one is 2 * that which is 2 * > / 2 radians this means that if we have this state which is five in binary and we apply the quantum forier transform we get this state in the next lesson we will see a use of the quantum forier transform but for now let's look at the circuit here is the Quantum forier transform circuit for any number of bits as you can see there are two gates that we have not seen before this gate here is a controlled R gate we will Define this gate

with this Matrix as you can see this gate has a variable K which we can set and affects the phase applied this 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 if applied to a q bit in in superp 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 this other weird looking gate is called a swap gate

and it swaps the states of the two Q bits for this lesson we will go through an example with three bits for this example we'll use the state J as an input to the algorithm we will label each one of J's bits like this where each ji is either Z or 1 to keep our equations tidy we will look at each one of the cubits individually then combine them at the end of the algorithm let's start with finding out what j0 becomes after the hadm mod gate the state becomes 1 < tk2 0 + -1

to the^ of J 01 we can represent this like this you will see why we keep the j0 ided 2 and don't simplify the fraction at the end then we apply the controlled R2 gate with J1 as the control we apply the R3 gate in the same way now let's find out what J1 becomes after the hadam mod gate the state becomes this state then after the controlled R2 gate and simplifying like we did previously we get this state lastly we apply a hatod gate to the J2 Cubit leaving it in this state so after

this part of the algorithm our state J is in this state now once we swap the cuits the state changes to this and we're done with the algorithm it may not seem like we did much but we have in fact encoded the value of J into the phase of the cubits just like we saw with the animation previously let's quickly check this by making J the value of five so 101 in binary if 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 if we were to apply the quantum fora transform to an arbitrary basis State J we get 1 / < tk2 to^ of n * the sum from K = 0 to 2 n- 1 E to the^ 2 pi i j k/ 2 the n k where n is the number of bits in J we also have the inverse Quantum fora transform and that undoes the quantum forier transform so if we add this state which is the state where we encoded five using the quantum forier transform

if we now apply the inverse Quantum forer transform we get back to our state 101 the quantum phase estimation algorithm allows us to find the igen value of an igen Vector given the Matrix so if we have a matrix U and apply to its vector v since V is an Vector we get e to the I Theta V where e to the I Theta is the igen value we can represent all igen values in Quantum Computing in this form the qpe or Quantum phase estimation algorithm finds e to the I Theta to a certain accuracy

this algorithm is a key part in many Quantum algorithms including shaes algorithm which we will discuss in the next lesson which allows us to find prime factors of large numbers here is the Quantum phase estimation circuit as you can see we have two registers the 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 looking 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 U to the power of n is the same as applying U to a qit n * also you can see we have the inverse Quantum fora transform at the end of the algorithm let's start going through the circuit at S Sub 0 we have the state M Z's V then at SI sub 1 we apply the hadam mod gates to all the Q bits in the first register at SI sub 2 we apply the uate to the igen vector v with the rightmost qbit in

the first register as a control since V is the IG Vector of you phase Kickback occurs which adds a relative phase of e to the a Theta to the Cubit then at SI sub 3 we apply two U Gates or the U squared gate with the qbit in the first register as a control and v as the target once again phase Kickback occurs applying a phase of e to the I Theta * a to the I Theta or e 2 I Theta we continue this process for each of the cuits in the first register which

leaves us with this state now we let Theta equal 2 pi J where J is a number between 0 and 1 since Theta is an angle between 0 and 2 pi with this if we find J we can find Theta substituting this in we get this equation now since 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 if we now sub that into our equation it becomes this now if we look at the first Cubit we

have a factor of 2 to the^ of nus1 if we distribute that into J we get this since 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 this leaves us with J m-1 / 2 if 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 for8 transform to the state J so when

we apply the inverse Quantum forier transform we end up with the state J all we need to do is measure the state and we've approximated J to M bits now 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 now we will tackle probably the most important and popular Quantum algorithm shaes algorithm this algorithm allows us to find the prime factors of a large number so if we have a number n equal PQ where PQ are both Prime Shaw's algorithm

allows us to find p and Q this may not seem very useful but this is the backbone of RSA which is a widely used type of encryption so using shaes algorithm will allow us to crack RSA encryption but that won't happen for a while to run sh's algorithm we will need a fault tolerant quantum computer with Mill ions of logical Q bits which won't happen for some time this algorithm uses both classical and quantum computers for different steps first 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 next we do the quantum step but before that we will look at some number theory in modular arithmetic we say say that a is congruent to B mod n if the remainder of a / n is B for example 3 is congruent to 1 mod 2 since dividing 3 with two gives a remainder of one we can reduce the factoring problem down into the problem of finding the period of modular exponentiation modular exponentiation is when you take the powers of a number modul a number here

is an example example as you can see if we have a number in this case two and put it to increasing Powers we get a repeating pattern when we take the modulo the 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 all 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 if we are able to find the period

we can use some number Theory to find the prime factors if 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 n let's go through the steps in finding the period of modular exponentiation for this we need to use this gate let's call it U which transforms the state x to the state x a mod n if we apply this gate to the one state multiple times we can get powers of a in mod n how we construct this gate is outside the scope of this course see the problem set for resources on how we can construct this gate let's consider this state us if we apply

a uate to the state it gives us this state looking at the a to the r mod n we can change the to a to 0 mod n since they are both 1 if we multiply the right hand side by 1 or e to the 2i i s / R * e - 2i i s / R we get this state we can change the E to -2 Pi I Sr / R to e to -2 Pi i 0/ r since they are both equal to one now as you can see this whole state becomes

the US state this means that the US state is an igen Vector of the uate with an igen value of e to ^ 2 pi i s / R this means that if we can construct the US state we can use the quantum phase estimation algorithm to get the value of s/ R it turns out that it is far easier to construct the equal superposition of all of the US states what what this becomes is 1 mod n in the problem set for this lesson we will prove this result we can construct the one mod

n by applying a KN to the rightmost Q bit in a register of all zeros which gives us the value one which is equal to one in mod n so by creating the state 1 mod n we are actually creating the state 1 /un R * the sum from s = 0 to R -1 of us here is the circuit for the algorithm looking at it this is just the quantum phase estimation circuit as you can see we now know that one is an igen Vector of the uate so we are using this to estimate

the igen value e to^ 2 pi i s / R where s is an integer from 0 to R -1 this is because our igen Vector 1 mod n is equal to 1 /un 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 I value of one of the US's which means that we will get S / R for 1 s from

0 to Rus one if we happen to get zero as our igen value so s = 0 then then we repeat the circuit so we can get an igen value that is non zero now we have a decimal number J which is equal to S / r that is the Quantum part of the algorithm done now we estimate the values of S and R by using a technique called continued fractions here 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 approximate its value with a fraction by rounding off the continued fraction here are the first three approximations for the decimal 0.312 to approximate s / R we find an approximation where the denominator is less than n since the period R must be less than n if R is odd then we repeat the algorithm and get a new value of R now that we have a value for R we can use this to find the factors of n we know

that a to the r is congruent to 1 mod n so a to the r -1 is congruent to Z mod n this 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 2 squares then we get this from 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 this allows us to find p and Q let's go through a quick example with n = to 15 so p is 3 and Q is 5 in step one we choose an a which is relatively prime to 15 let's choose AAL 7 now 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 by using the algorithm we find that R

is equal to 4 now we calculate the gcd of 7^ 4 /2 - 1 and 15 and the gcd of 7^ 4/ 2 + 1 and 15 the first one becomes the gcd of 48 and 15 and the second becomes the gcd of 50 and 15 the gcd of 48 and 15 is three and the gcd of 50 and 15 is five as you can see we have found the factors of 15 3 and 5 using shaes algorithm