Quantum Computation & Speed-Up

0:00 I'm taking a look at some quantum algorithms. The algorithms I want to look at are basically the shore algorithms, the jewel in the crown of quantum algorithms, and Simon's algorithms. related to the original version of the Deutsche Jösser algorithm, which is Deutsche's Ex-Aura algorithm. Usually, Deutsche's Ex-Aura algorithm is treated as just some kind of curiosity because it doesn't really achieve an exponential speedup. But I want to show you that actually all the secret of quantum computing is already involved in that shore output. So that's a very simple algorithm, and I'm going to begin with that. Before beginning with that, though, let me just take a quick look initially at the shore output and show you, well, how complicated it looks. Now, the Shor algorithm, as I said a few minutes ago, is sort of the jewel in the crown of quantum computation because it's the reason why people like the National Security Agency and so on are interested in what's going on in quantum cryptography in quantum computation because, well, as everybody knows, it's a factorization algorithm. factorization is at the heart of RSA, the RSA encryption protocol, which is the most commonly used form of encrypting information. So the RSA protocol goes something like this. If you want to communicate with your bank, say, by making a transaction, you take out money from a machine, well, the bank publishes a public key, which consists of two numbers, a large number, N, and another number, and you take these two numbers and, well, this happens automatically, of course, when you buy something on the internet or when you function your PIN number, you send your PIN number to the bank in an encrypted form by

2:30 performing a certain function on the PIN number depending on the public key, these two numbers. And the bank then has a private key, and with the private key can decrypt the number that Now, the private key can be found once you know the factors, the two prime factors of this large number. And of course, finding the prime factors of a very large number, like I had in 2060, is an odd problem. That is, the number of steps required in a confirmation grows exponentially the size of the number. So, Schor's algorithm is an algorithm for computing the prime factors of a large number in polynomial time, that is, using a polynomial number of steps in the algorithm. And it goes like this. You start off with two registers, one of which space of dimension Q, another one in the space of dimension N. Capital N is a number that you want to factorize, so initialize the state. I'm just going to run through this quickly just to show you what the steps are, and then afterwards go slowly through the number of algorithms that get back to the shore output. Initially, I just wanted to run through the Then you apply a number of Hadamard gates to the input register, and you create a superposition over all possible input states. And the third step involves computing a function, and the The function you compute to work out the period is this, my transparency is a little too large. You calculate a function, Zn is my annotation for the additive group of integers mod n. So, you're calculating a function from zq to zn, which is a to the power x mod n, n being the number you want to factorize. And it turns out, because of number theoretic arguments, which I simply don't want to go into here,

5:00 that if you take a number which is co-prime to n, this is the number a, that is, it has no common factors with n, and you compute this function a to the x mod n, once you find a period of that, the function is going to be periodic. And once you find a period of that function, then generally from that you can find the factors of n. I say generally because this algorithm could fail. So here's a calculation of the function, you apply some unitary transformation which is going to involve, and of course it has It has to be shown that there are a polynomial number of gates in this unity transformation. We'll talk about that a little bit afterwards. So you calculate the function, which that is to say you're correlating values of x from each value of x with the value of the function, which is x plus a to the power x mod n. and then you measure the register 2, and you're going to find a particular value, i, and so because of periodicity, you will, if you like, project the state or collapse the state onto to a state of this form. If the period r divides q, if it's a q-dimensional fielded space exactly, then this factor will be squared with q over r. If not, there's a slight adjustment that you have to make. This number here that you get is going to be some offset, as one says, which depends on the outcome i, and will be different for And these, here are all the values of, well, they are parametrized by j, all the values for which, well, the value of the function is just i, so that f x i plus j r is going to be i. Then what you do is you apply a discrete Fourier transform to the first register, and that transforms this offset, which you don't want to, because the period is right there.

7:30 But what you're going to get is a number, which is going to be some offset plus some model of the period. But the discrete Fourier transform, which is a map of the following sort, is, I mean, that's the output, here's the, sorry, here's the discrete Fourier transform. So it will take that state x to this linear superposition. What it will do to this state over here is produce this state where the offset is no longer in the state register, but it's a phase factor, and you're left with just some multiple Q overall. The phase now becomes, it gets kicked back down there. And then you just make the number of measurements on this register, sufficient number of measurements because what you're going to get is each time you're going to get kq over r for some value of k, and you repeat until you obtain a value of kq prime qr and then you cancel things out and you make the number of r. So all I've intended by this initial introduction is to show that there are a whole number of steps. The first step involving application of a Hadamard transformation to get all possible values of x. The second step, you have some unit transformation which computes the function. But now you've got an entangled state which relates every value of x to the corresponding value of the function. And then there's another, apparently, this discrete Fourier transform. So there are a number of elements, and it's rather complicated and interesting, but it's time to see how that, you know, what that is possible, during what, how it's working. And in fact, if you take a look at what people say, um, about where the speed up comes from, uh, here is a typical quote of, uh, Andrew Steen from from non-computing computing. Anderstein is actually one of my heroes in the field. But I don't find this very helpful. So here's a quote.

10:00 This is my only quote in the talk. So it's a long quote, but I only have one quote. It says, the period-founding algorithm appears to be such a conjuring trick. It's not quite clear how the quantum computer managed to produce the period like a rabbit out of a hat. the most important features are contained in the combination of the value of the function for each of the values of the input. They're not only the quantum parallelism already mentioned, which is essentially this, but also quantum entanglement and finally quantum interference. So, I mean, everything has a problem. And each value of fx retains a link with the value of x which produced it through entanglement of the x and y registers inside. I mean, that's the x register, that's the y register. The magic happens when a measurement of the y register produces the special state, which is the state of this form. I can't believe it's very well the state of that form in the x-ray it's a quantum entanglement that reproduces this the final Fourier transform can be regarded as an interference between the various superposed states in the x-ray just to compare with the action of the fractional wave what's that? So the quote is from this very nice article, I guess, called Quantum Computing, which is an article, I forget the actual reference, in a collection, it's also on the quantum physics archives, if you just look up, and it's seen quite a long paper on quantum computing, which I found very helpful. I mean, I find most of it seem very helpful, but this I don't find helpful. Because this just basically says, well, the speed-up's because of entanglement and interference and parallelism somehow reduces it. Other people say things like, well, it's all in the fast Fourier transform, and that really that's exactly, once you understand what's happening there, that explains how you get the speed-up on the capital. So, some people say quantum parallelism, some people say phosphory and transform, but what is really going on? Okay, now we'll leave that and get back to it in the end, and take this very simple algorithm, Deutsch's XOR algorithm,

12:30 and take a look at what's going on here, because I want to show you that actually the Shor algorithm involves the same idea. The XR algorithm is very simple. You've got a Boolean algebra, 0 and 1, or a candidate group of integers 1 and 2, and you consider all the functions from B to B. While there are only four possible functions, 0 goes to 0, you can get both 0 and 1 both go to 0, 0 and 1 both go to 1, in which case you say the function is constant, or one goes to one and the other goes to zero, in which case do we choose the term balanced for the function. Now, the constant function can be defined this way, this is addition to log two. So when the function is constant or balanced is a global property of the function. And the aim is to find out for a particular function, you've got a black box which computes the function, and this is the way it's used to be put, and can you find out whether the function is global, is it possible balance with just one application of the black box, or this can be associated with the interview transfer. Now, if you think about it, if you were doing this classically and you want to find out whether the function is constant or balanced, you're going to have to find out what happens to the value zero and what happens to the value one, and check to see whether they're the same or different, that involves several steps. So, this is what Deutsch suggests. We initialize a data register or a query register or a target register, perform a adamant transformation on the data register, which takes you from 0 to 0 plus 1. It's easy to see what's happening here. Then you put both registers into this energy transform, into this box which performs a energy transformation, and that produces that, 0 f0 plus 1 f1. Now, if the function is constant, you're going to get 0 going to 0 and 1 going to 0, or 0 going to 1 and 1 going to 1, and so those are going to be the two final entangled constant states, c1 and c2. In balance, 0 is going to go to 0 and 1 is going to go to 1, or the other way around, 0 is going to go to 1 and 1 is going to go to 0,

15:00 two balanced states. And it's fairly easy to see, I mean it's immediately obvious, that these two states are orthogonal. I mean this is 0, 0, plus 1, 0. This is 0, 1, plus 1, 1. These two states are orthogonal. These two states are orthogonal. So these two states span a plane, called Pc, in this four-dimensional field space, and the balanced states span a What's maybe not immediately obvious, although perhaps it is, is that these two planes are orthogonal, except for an overlap, except for an intersection. So the picture geometrically looks like this. you've got these two planes. When I say they're orthogonal except for an overlap, I mean that they're going to have, you can think of them like two planes which are at right angles and which have each other. I mean, you can check in the best case. And the overlap is then this line here. So here's a picture of what's happening. I mean, this is supposed to be a drawing of a, this is a four-dimensional open space, so 0, 0, 1, 0, 1, 1, and 0, 1 are four orthogonal lines, and I've got B1 and B2. B1 lies in the 0, 0, 1, 1 plane, and B2 lies in the 1, 0, 0, 1 plane, and C1 and C2 lie in this plane here, and they're intersected in a state which sort of comes out in a vital right back in that state. And it's important for the algorithm that the planes are orthogonal except for an overlap because that means that the projection operates a new and that means that you can make one measurement which will tell you which plane the state ends up in. So let me now write this just to make it even more obvious. Let me write the states in the constant state and the valid states in the prime basis, that is the basis 0'1' related to 0'1 in this way.

17:30 If I write it in the prime basis, then the C plane, which can be thought of as the plane spanned by constant C1 plus C2, C1 minus C2, or C1 plus C2 is the same as B1 plus C2. Anyway, in the prime basis, we see that the C plane, so the state ends up either in the the c-plane and the b-plane, is just the span of 0 prime 0 prime and 0 prime 1 prime. And the b-plane just turns out to be the span of 0 prime 0 prime and 1 prime 1 prime. The other vector of the orthogonal quadruple would be 1 prime 0 prime. So the way one normally puts the algorithm is you mention the second register. And if you find the value 0, you mentioned the state of the register in the prime indexes. If you find the value 0, well then you don't know if the function is cost of balance because that would mean that the state has collapsed onto this overlap. If you find the 1 here, then you just look at the value of this register and if it's 0, well you know it's in this plane. And if it's one, then you know it's in this plane. So the algorithm fails or succeeds with 50% probability all the time you fail, and it doesn't seem that interesting because it's not producing an exponential speed. But the points I want to emphasize here are that what you've done is the following. You have what the algorithm achieves, and this is the punchline of the whole talk, and maybe, I mean, having seen this, it seems to me that it may be so obvious that at this point people can just leave the room, but punchline into what you're doing in a common computation is, well, you're calculating a global property of the function. A global property of a function corresponds to a disjunctive property, this or this or this or this. And the disjunctionally corresponds mechanically to a plane or a hyperplane in subspace and hilted space. And the way the algorithm works is that you have a number of subspaces which are all going to commute. And so you can take a measurement which will tell you, except for the problem of the overlaps, which subspace you're in. compute the value of a disjunction without computing the values of the disjunction.

20:00 And this seems to me to be the trick, and the origin of the speed app. So, as I put it here with the right algorithm, just mentioned the observable, but I can state 00'01'10'11', and you'll distinguish between the two planes with probability 0.5. Now, what you could also do, if you don't like measuring in the prime basis, is you could just make a Hadamard transformation and rotate the state and then measure in the unprime basis. And that Hadamard transformation here then amounts to the, is the counterpart of the Fourier transformation. So it's really, from this point of view, and I hope I can show this precisely, I'll just jump in some references, which I would use, in the Simon algorithm, is really what the cross-grade transform is doing. It's really just taking you back to the computational basis. Let's look at the Simon algorithm, which is, because it's a period climbing algorithm, is closely related to the Schor algorithm. But what's not evident is that the Simon algorithm is really just, if you like, a generalization of the, of, of, uh, Dewey's XOR algorithm. I want to show it to you explicitly, just to run through the steps as they usually put. What you do is you compute the value of function which is taking you from a cross product of in Boolean Algebras, this product of N to the same thing, and you have a function which takes you, the value of the function is, for a value of x, it's x, so if this register So in y, you get y plus, and this is an addition modular to fx. And this function is promised to be a two-to-one function with a periodicity r. So r is going to be some value of b to the n.

22:30 And the output is going to be some number such that y dot r is equal to zero, So just to run through it quickly, before taking a common example, you initialize the state, you apply Atomard-Gates, you calculate the function, just as before, and in the end of the day, you measure register number 2. I should say that measuring register number 2 is completely unnecessary but it just makes it easier to understand what's going on because measuring register number 2 will tell you that state number 1 is a particular state but even if you know that state number 1 is a mixture of all these states and so you could just consider it from that point of view. but it's easier to think about it by saying measure register 2. Do measure register 2 and keep the corresponding state of register 1, which will be a state of this form. Remember, the function is promised to be a 2 to 1 function, so for each value of the function, there are going to be two input values, which are going to be separated by the period. That's then the offset. The offset will depend on the value of the function that you found. So again, the state has the desired information of R, but with this unwanted offset, and what people usually say is, look, if you measure the label, that is to say the label of this interstate, you're not going to get any information about R because you've got this offset involved in it. So you need to apply a discrete Fourier transform, which in this particular case, for this Boolean algebra to power in, is an Adamart transformation. And then if you take a look at what this is doing, again, this X value becomes a phase, and then you manage the register and you get the C1. So it's fairly similar in that sense. But let's take a look at it from this sort of chronological or geometric point of view. I'm going to run through it again, but this time slowly. The function is promised to be 2 to 1 in the period r. So that means that the function has the same value,

25:00 even only if y is equal to x plus r, and this is, you know, a bitwise addition. You've got some unity transformation which is going to transform states in that way. So what's going to happen? Well, let's say that you've got an input state. You leave these zeros, by the way. This is shorthand for a string of qubits. I'm just making it explicit over here. This actually is also a string of n qubits. If I finally have a transformation to this guy, position here. If I apply the function, I'm going to get nx values here, and now I measure radius to 2, the value of radius to 1, and so I get s-state this. And what does that look like? What does that look like if I take the value of a equals 2? Well, then the periods are, well, not 0,0 wouldn't be a periodic function, so the period is 0,1, or 1,0, or 1,1, and three periods, a few possible periods. If the period is 0,1, then the function is going to look like this. I'm going to have 0,0 plus 0,1 will be, will both be the value 0,0, because 0,0 plus 0,1 is 0,0. And 1,0 plus 1,1, the difference of 0,1 here, is going so that will take the function value will be f1 0 because f1 0 comes to f1 1 for this period the offset here is 1 0, the offset here is x 0. If I measure this register in this state then I'm either going to get that state or that state. And suddenly for the other possible periods I'll either get this state or this state or this state or this state Now if you take a look at it geometrically as the x-order problem. Look at these states. This state is 0, 0 plus 1, 0. This is 0, 1 plus 1, 1. Those were the constant states in the previous problem. These states are the balanced states. And the other two states are the two states now for this other possible orthogonal direction in the 4-dimensional helix space. So in the

27:30 prime debaseless, what it looks like is that C1 and C2 are 0, 0 prime plus 0 prime 1 prime, and this is 0 prime 0 prime minus 0 prime 1 prime, associated with this period, this period, this period. So we have exactly the same exactly the same problem for n equal to as in the previous case. So we could simply measure in a prime basis and find the period. Alternatively, we could apply a atom log transformation here. All that does is drop primes. I mean, you're computing 0 prime 0 prime to 0 prime 0 prime. And so, if you apply the handle mode afterwards, then you have the luxury of measuring in the computational basis instead of measuring in the prime basis. So measure if you, if you, this hadamod will do the, give you all possible input states, so to speak, within your superposition, apply the unit transformation, you get the entanglement, apply the final hadamod is in a sense unnecessary, but I think, but in a sense necessary, but in a sense unnecessary, in a sense that you could at this point just measure in the prime basis and you distinguish the three planes. How would you be associated with the three periods? It's just to make sure that this is not just a clue. Take a quick look at the case n equal 3. It gets a little more interesting. Well, if you take the case n equal 3, you're going to have seven periods. 001 and 010 and so on. You get 000 plus 001 and 00. The function will look like that if the period is 001. Offsets are going to be 00, 00, so you're going to have four offsets. That means if you measure the second register, you're either going to get this state, this state, this state, or this state, which will leave the first register in this state, this state, this state, this state. So you will end up with the first register in one of these four states, which again are orthogonal lines and span a four-dimensional subspace.

30:00 And you're going to get four different orthogonal lines for each of the periods here. So you're going to get a four-dimensional subspace for each of the periods. And in the prime basis, the subspace associated with this period is just different, or just span by different linear superpositions of 0, 0, 0, 0, 1, 0, 1, 0, and 1, 1, 0 in the prime. If you apply a Hadamon transformation, then you just drop the primes, and the subspace is spanned by these states. So now if you look at the other periods, it looks like this. For each possible period, you're going to get a four-dimensional subspace. and these they span by these states these states, these states this is after the Adamant transformation and they intersect in planes let's take a look at this one the period the first period and the second possible period they intersect in these two states and they also intersect in these two states so what you end up with are, I mean these planes are a problem except for an overlap they commute The overlaps, they're four-dimensional subspaces, the overlaps are planes, two-dimensional planes, and the, so what you have to do is make a measurement to distinguish which four-dimensional subspace the state ends up in, and once you find that, then you can count the period. So the period is one of seven possibilities. There are seven four-dimensional subspaces. You could measure in a computational basis. Of course, you might end up in the overlap. But a sufficient number of repetitions will determine which subspace you're in. And on the average, it's only going to be a polynomial number of dimensions. So again, finding the subspace is finding the value of its disjunction without finding the values of the disjunction. How much time do I have? Oh, two.

32:30 How quickly? Okay. So now let's take a look at the shore algorithm, which we had before, which we started out with. And let me now run through this dip slowly and show you what's happening here. Here's a black box, an article which computes a function from the q, z, n, where the additive group of integers mod n. The black box implements the transformation as a unit of transformation, so we get that. And this function is a to the x mod n for some number a co-prime to n. Remember that came from the classical number theory. and again you have a slight problem if this period R doesn't divide the number Q which is going to be the dimension of the input of the space exactly otherwise the function is going to be almost periodic so you have to say some things about that but I'm not going to bother with that because that doesn't change moral of the story let's factorize n equals 15. So suppose n is 15. And the number a that I'm choosing co-prime to n is 7. 7 and 15 have no common factors. And take q that I mentioned on the infra-kilbert space as having 8 qubits. So q would be 256. 2 to the 8. Now let's calculate the value of the function. Well, it's 7 to the 0, mod 15, you know, it's A to the X, mod 15, 7 to the 1, mod 15, 7 to the 2, mod 15, and so you get values 1, 7, 4, 13, and then they repeat. So the period is 4 in this particular case. Now, let's look at what's happening. The next step, I'm supposed to perform a discrete Fourier transform, this one, on the integers. And so let's just take a look at what's happened. The state, the entangled state, after the computation

35:00 of the value function by the unitary transformation will look like a sum like this. that is 0, again, it's associated with the value, the function value for 0 is 1, for 1 it's 7, that is 7 to the power 0 mod 15, and suddenly for 1, 2, 3, so you get the values 1, 7, 4, 13, 1, 7, 4, 13, and that's what the thing looks like. Now you measure register 2, which means you're going to get either 1 or 7 or 4 or 15, keep the state in register 1, you're going to get a state which looks like that. I mean, if you measure one, you're going to get this state. If you measure seven, you're going to get this state, four, three, and so on. And then you've got four or five more lines. People usually say the direct measurement of the label will give their information about R. The direct measurement of the label means that once you've measured register two and the state is stated this state, If you simply measure the state of register 1 in the computational basis, well, you're going to get a number like 8. But what are you going to do with 8? I mean, the period is, which you're supposed to be finding, is 4. So the claim is that doesn't help because there's an offset 0 or 1 or 2 or 3 here, and you don't know what that offset is. So apply to the discrete Fourier transform. But what is the discrete Fourier transform doing? for the period 4, the state is going to end up in this particular case in a four-dimensional subspace which is scanned by these four lines. Performing the discrete Fourier transform is just performing a unity transformation. In this particular case, it will take these four lines to these four lines. So you can see the subspace associated with period 4 is the subspace which is spanned by different linear combinations of 0, 64, 128, and 192. So the same is in this four-dimensional subspace of the period, which is 4.

37:30 Now, what you're supposed to do, surely, is consider all possible periods for which fx is equal to a to the x115, And actually, you don't have to consider all possible periods because only values of R which are even are going to enable you to find the factors of 15 because of this algorithm. And the value of R can't be more than 15 anyway. So you're going to actually need even numbers based. You know what 15 is? 15 is the number of finite macros. So it's a rather small number of R's that you have to consider. And so let's consider r equal 2. Well, r equal 2, you're going to get just two possible values for functions, and they're going to be associated with two orthogonal lines. If you like, apply the, just to see what's going on, apply the discrete Fourier transform, which is just a unity transformation, and you can see that the two lines here are 0 and 128. If you remember that before, the subspace associated with r equals 4 was a four-dimensional subspace spanned by 0, 64, 128, and 192. This is a plane spanned by 0 and 128, so this plane is inside the four-dimensional subspace. And it's pretty clear, and this is a general feature, that the different periods in this particular case are going to be associated with different subspaces which are nested, one inside the other. In the Simon algorithm, there were four-dimensional subspaces, which are essentially two-dimensional planes. Then you're going to get a two-dimensional plane inside a four-dimensional subspace, inside an eight-dimensional subspace, and so on. and the, uh, but they won't commute. And, um, the aim is to find which, where the subspace is. I mean, to find out, sorry, to find out which subspace the state ends up in.

40:00 And the usual recipe is this. Measure the first register in the computational basis to get a value of C, which is this number that's in here, which is k q over r where k is, and we chose an entry probably because all these coefficients are the same and you repeat until you find a value k co-prime to r Now let's just see what this means in this particular case If in fact r is 4 it's no use finding a value k which is say 2 it's not co-prime to r Our value k equals 2 will be associated with 128, and that means it could be in either a two-dimensional subspace or a four-dimensional subspace, which contains a two-dimensional subspace. If you find the value, say, 1 or 3, which is co-prime to 4, well, then you're either going to get 64 or 192, which will tell you that you're not in the plane, but you're in the four-dimensional subspace. What you don't know is that, well, maybe the period is 8, so maybe there's a bigger subspace. But what you do is that if the period is 8, well, and k was 2, 2 is not co-prime to 8, so actually you're supposed to continue until you find the number co-prime to 8, which means from a theoretical perspective that you just make some more measurements. and clearly the probability of let's suppose the period is in and your first measurements found a value inside the four dimensional subspace the probability of finding a value in the other four dimensions is half so if you just do one or two measurements and if it really spans that other eight dimensional subspace contains a four dimensional subspace, it was probably half, you're going to find a value outside Do it a few times until you're pretty sure which subspace you're in, and then you found a period. And once you found a period, you found the, by a simple formula, you can figure out the fact that you take a to the power r over 2 plus or minus 1, and you consider the common factor of those two numbers with n, and you'd be working on something. So, where does the

42:30 speed up come from? The situation looks like this, you've got a four-dimensional subset 0, 64, 128, 192, for r equals 4, for r equals 2, you're in this plane, 0, 128. It's not exactly obvious what one means by that question, because you're really comparing apples and r equals. In the classical case, what you mean by a computation is rather different than the quantum mechanical case. So, you have an initial preparation, an initial state, initialization. Then you perform an atom-art transformation, which takes you to this linear superposition of all possible eight-groups. So, that's just a unit transformation. Then you perform a unit transformation, which computes the value of the function. That's just another unit transformation. Then, in order to make the measurement in the computational basis, you could form another unity transformation an atomized transformation or more generally a discrete Fourier transform and then you make a measurement but clearly the measurement you make in the end is just three unity transformations which is just a big unity transformation and then a measurement so you could equally well have made a measurement in a basis which was the inverse of this unity transformation So you don't have to make any transformations to compute the value of the function. You just take an initial state and make a measurement. One measurement, and you're done. So if you think about it that way, which is silly, of course, because you have to know what basis to make the measurement in. And in order to know what basis to make the measurement in, of course, you have to perform the computation with a pencil and paper or something. So it doesn't help to say that, well, actually, you need to make one measure, that's all. But then you have to think, well, exactly what do I mean by saying that this algorithm is a polynomial time algorithm as opposed to exponential?

45:00 So people make various rules. And the rules are, any old measurement is not counted as just one stick. What counts as a one-step measurement is a measurement of the elements in a computational basis. And if you have N elements in a computational basis, that's going to be N steps. So you've got unit-taskimations and measurements. So one decides that the way we're going to count how costly the algorithm is, is to count measurements as measurements in a computational basis instead of measurements in a computational basis. And as far as unity transformations are, for instance, not any old unity transformation counts as one step, but what counts as one step is a unity transformation in a small chosen set of unity transformations, which are either going to be one qubit or two qubits of transformations, and each of those will count as one step. And that seems to be a sensible procedure to count how many steps the computation is actually costing. And then you can show, let's say, the Schor algorithm that each of these stages of the algorithm, the original Idenauer transformation across the discrete Fourier transform, the same thing in this case, the unit transformation that provides the values to the function, and the final Fourier transform, which is allowing you to make the measurements in computational phases, each of these steps only involves a number of gates which increases polynomially with the size of the input. And so on, it says that the algorithm is in polynomial time. But from the point of view of this sort of intuitive question Well, what is it about quantum computation? I mean, how is quantum mechanics achieving the speed? I mean, the answer I've seen here is all sort of entangling interference and all the sort of quantum mechanical features. But really, it seems to me that the essential feature is that you're using the features of quantum mechanics, entanglement basically, that in order to compute a disjunction, disjunctive property of a function, without computing the values of the disjunction.

47:30 You want to know what the period of a function is, and so you want to consider all possible periods, a range of possible periods. each period is going to correspond to a global property of the function. Say the function has period four, which is a different global property, and I'm saying it has a period two. And each of those properties are around the same, the disjunction. And what you do is you found the value of the disjunction without finding the value of the disjunction. So, not only do you not have to find the value of the discharge, which you would have to classically, but you end up not knowing the value of the discharge and knowing the value of the whole distraction. And I would say that that's sort of the essential feature of what makes a quantum computation speedier than a classical computation. The Fourier transform, which is involved essentially in two steps. It's really Fourier transform, unity transformation, computing value of function, Fourier transform. What this is doing in the first step is just giving you linear two positionable possible values. What it's doing in the last step is just taking you back to the computational basis. And in the case, say, of Simon's algorithm, it's just taking you from the x-basis to the z-basis. So you could be equally well measured in the x-basis. But the reason one regards it as essential to get back to the computational basis is that you can't just allow unrestricted measurements as measurements in the annual basis to count once there. And so there's a, let's say, a convention about how you count steps. But other than that, it seems that the function before that step, before the final Atomar transformation, the function is actually, the entire state that results from this accommodation, is actually in one or the other of a meshing, and all you have to do is make a measure which tells you which it's in, and then you've got the value of the contribution.

50:00 Okay, let's start there. Thank you. I have a question to comment about the punchline. Okay, you say the core idea is that we can find the truth value of a disjunction without finding the truth values of the disjunction, but when we ascertain the state of a classical system progressively, that also can happen. we can restrict to a subset of phase space that is a union of two components we find which component that is a union of two components we don't know which you see, so this is a classical logic thing not an intuitionistic logic but very classically we can know a disjunction through and not know which disjunction so it seemed to me I didn't follow the detail but in the easy case the two planes each intersecting in the ray in h2 times c2 times c2 what surely what matters is that you you ascertain that it's the good old projection postulate but not necessarily a physical process it's determining from the state that it's projection into a plane which is left as containing still the two possibilities it's one of all the quantum superposition principle probably that's clever rather than the principle that a disjunct can be known without its disjuncts being known well in the very simple XOR algorithm what you end up with you see very quickly Okay, you take an initial state and you perform a energy transformation.

52:30 There were no measurements here, nothing. Then the result of that is that you've got two resistance, and they become entangled as a result of this transformation. And the state, oh, actually, in this particular state, in this particular case, it, OK, that's this. So you end up, sorry, you end up without any measurements, either in this particular plane here, which I call or this plane over here. If you're in a four-dimensional Hilbert space, you know that you're not in this plane out here. So you're either after the unity transformation in one of two planes, and they do have this intersection here, then you make a measurement. And the measurement is simply, could simply be immediately observable with possible eigenstates, this, this, this, and this, which are four orthogonal states, and because the state is either in this plane or in this plane, if you measure that observable, you're either going to get a collapse onto this line with probability of, or you're going to get a collapse onto this line if it's in here, or you're going to get a collapse onto this line. It's in here. But before you make any measurements, the state is in this plane or it's in this plane. And the computation has, in fact, given you a state which is in one or two above the plane. And this plane is the plane which represents the value of function being a constant. I mean, this plane corresponds quantologically, if you like, to the proposition the value of f is constant, which is to say the value of f is a disjunction in the common sense. It says 0 goes to 0 and 1 goes to 0, or 0 goes to 1 and 1 goes to 1. And those are, let's say, quantum mechanical disjunctions. So the quantum mechanical disjunction is true of the state before you look at it. that you ended up with a state for which a certain proposition is true.

55:00 And if you think of state-based, the classical analogy that we're talking about, and the system will end up in a certain state. The state is a point in a phase-based. That means that the disjuncts are true or false. I mean, the state either lies in a set or it finds out a set. All these possible problems. I mean, there's two-value monomorphism on the Boolean algebra of subsets of the place. But here, what you have is a state which just lies on its plane. So you could say the plane is true in the sense that the state is contained in the subspace, but these lines aren't true or false. That's what I wanted to say. Surely the distinctive thing is that we can have the true value, the disjunction true, and the disjunction not true. Yes, yes. Right. I thought you said the punchline was you can know that a disjunction is true without knowing that the disjunction is a boring old pattern. So as usual, you have corrected my sloppiness. Thank you. No, I should have put it exactly the way you put it. The state ends up as a state in which a certain proposition is true. I mean, you know, then there's a way you should find out which, you know, what they're playing on. But the punchline is, I mean, the main point is that as you could have lived, it's hard to think, it's hard to think, it's hard to think. I have a slightly different objection. The NSF surely funds for the computing because it can be done efficiently. Yes. Now, I think that your considerations would also play it just the same way if you had a quantum computer that wasn't built of cubits, where it was entangling with the expansion growth of the cyberspace with a number of components. But they just made up of a system that has a very large number of levels. So I think the Hillbosystem analysis would just be the same thing.

57:30 Only I wouldn't have students. And to actually implement all these operations would be very inefficient. So is it true that your analysis does not distinguish between this inefficient, not past and not interesting from the that doesn't make the distinction between these two and if it does isn't then the fact that it's made of qubits and the exponential world of states isn't that a very material I think it is, yeah, because that's sort of related to the comment that I made that you could just make one mission and the mission would be a big issue instead of speaking on something widely tangled and so on. So in order to have an efficient process, you need to consider, well, what would be an efficient process? And so on, consider it as humans, and so on. But the specific answer to your question is, yes, I mean, you could do all of this analysis in a general field of space, everything that I say would be correct. And then you would say, yes, but in what sense can I relate this to efficiency? And then you would say, no, but look, yes, I can. The general discussion of this is generally any of the space. But as a matter of fact, you can implement this on a two-bit space of qubits. and then we can quantify in a sensible way the number of steps that are involved as operations of humans. But I think the point is, if you, I mean, I guess maybe, I was thinking, I was trying to understand the Shor algorithm and reading all this about phosphory transforms and so And it's clear that the class Fourier transform was simply enabling you to make the measurement in a computational basis. And then even before you made the class Fourier transform, in the basis obtained, by simply making a transformation of the state, just making an inverse Fourier transform on your basis, on your coordinate system, so to speak.

1:00:00 Everything that you could say after the final Fourier transform, you could equally as well say before making a final Fourier transform, because it's just a unique, you're just sort of retaining things in a general sense. So the computation is, in a sense, done before that. And so what exactly does the computation consist of? I think people suddenly say, well, it's a massive amount of parallelism. But looking at the very simple XOR, it was clear there that, well, the state ends up after the energy transformation, which is supposed to function in some, in one of the number of subspaces which are all and if you look at, I mean it must be the case, we go for any computation of the function, any function at all, you must think about the two pieces, one of the number of subspaces. And then it was clear that the period finding algorithms have the same feature And so the conclusion is that, well, what we try to do is to find that big subspace, the state, the entire state, and so on. And then there are all these other things in there. Last, very quick question. This is a very great question. And to your Japanese comments and your remarks, when you say that PR comes from a disjunction project, if I'm correct, you are saying that disjunction has to be understood as a quantum ball, quantum logical. I mean, that's the point. So it's a disjunction that has to be formulated as an all, which is just the closure of the union of two subspaces. That's it. So you have two closed subspaces, x and y, and x or y is just the closure of the union of the two subspaces. In the sense that a state may belong to the all, to the junction, but it does not necessarily belong to x or y. So, the chronological feature, the speed-up, the root of the speed-up, your thesis, the root of the speed-up of quantum computation is large in a chronological disjunction.

1:02:30 Yes, that's correct. Yes, that's correct. And, I mean, what's the connection between that and speedup? Well, I mean, I haven't... The connection between that and speedup is sort of the intuitive connection that you can have a very long distraction, so there are many possibilities, but you... So, classically, you have to get true or false for all of these, and quantum mechanically, you find out the true failure of the whole thing Thank you. Thank you.